Manifest and snapshot trees

How do manifest trees make metadata scale like data, and what does that cost?

The metastore has two failures: it does not scale with object count, and it is not transactional with the data it describes. Both are fixed by one move: put the metadata in the same object store as the data, as immutable files arranged as a tree.

metadata file (root)          <- the single pointer says which one is current
   └── manifest list          <- "snapshot": which manifests make up this version
          ├── manifest A      <- lists data files + per-file statistics
          │      ├── data-001.parquet  (min/max per column, row count)
          │      └── data-002.parquet
          └── manifest B
                 └── data-003.parquet

A snapshot is one complete version of the table: a root file that points to a manifest list. A manifest is a file that lists data files together with statistics for each file.

Four consequences follow mechanically:

1. Metadata now scales like data, because it is data on the same storage.
2. Metadata is immutable, so a snapshot is a pointer and costs nothing to keep. And a general pattern arrives on schedule: immutable storage always grows an indirection layer (a lookup between the name and the location) plus a collector (a process that frees what nothing points to). Here the collector is snapshot expiry and orphan cleanup.
3. Reading metadata is a bounded fan-out of GETs, not a scan of a relational table.
4. Pruning becomes hierarchical: skip a whole manifest first, then skip files inside the others. Structurally this is a zone map over a zone map (metadata is data) (a zone map is a small summary, such as min and max, for a block of data that lets you skip the block). The index structures of databases recur one level up, with files playing the role of rows and manifests playing the role of pages.

The deeper consequence: per-file min/max statistics written at commit time replace the folder-name claim. Pruning stops depending on where you put the file and starts depending on what is in it. That is why partitioning becomes an optimization rather than a correctness-bearing declaration, and why hidden or derived partitioning (the engine computes the partition from a column, e.g. day(timestamp), and the user does not name folders) becomes possible.

The cost is exact recursion. Every commit writes new manifest files. Frequent small commits make many small manifests, which slows planning, which requires metadata compaction (merging small manifests). The small-file problem reproduces itself one level up and needs its own compactor. This is the cleanest example of a mechanism regenerating at the next level of abstraction. It will happen again above this level, because the cause is present at every level: a fixed cost per object and a near-zero marginal cost.

Metadata trees make metadata scale like data by making it data, including inheriting data's small-object pathology.