Opaque values, documents and where order comes from

What do key-value and document layouts give up, and where does physical position come from?

Key-value layout

Key-value and document layouts are not peers of row, column and PAX. They are interface models, and each is realized by one of those three physical layouts underneath. What they change is what the store is allowed to see.

The key-value layout declares the value opaque. Everything else follows from that one decision.

If the store cannot inspect the value, then it cannot decide adjacency inside it, cannot encode it by type, cannot compute statistics over it and cannot skip on a predicate against it. All layout freedom collapses onto the key. So every real physical lever of a key-value (KV) store is key-shaped: hash versus range partitioning, sort order, composite key construction. This is why KV users spend their design effort on key schemas. That work did not disappear. It moved from the engine to the application. That is the conserved-cost rule in a very pure form: the cost moved to a different party.

Ask two standing questions. What does it assume it cannot verify? That values are unstructured and unrelated to each other. That is almost never true, because values are usually serialized records of one shape. Who pays when the assumption fails? The application, through denormalization (copying data into several places), manual secondary indexes, and reading and rewriting a whole value to change one field.

This generalizes into a principle:

It has the same shape as a file system that cannot compress what the application has already encrypted, or a network that cannot prioritize traffic it cannot parse.

Summary. Opacity is a bet that the key is enough. When it is not, layout design migrates into application code.

Document layout

Documents are self-describing: each record carries its own field names and types. The immediate cost is per-record metadata. A JSON document with 20 short fields is commonly half keys by volume. Binary encodings shrink the constant but not the overall pattern.

The structural cost is larger. If the schema lives in each record, then the dataset has no schema. A reader cannot know the layout without reading, which rules out structural skipping and rules out columnar encoding entirely. You cannot dictionary-encode a column that is not guaranteed to exist.

Shredding

The way out that everyone converged on is shredding: infer a schema, project the documents into columns, and store them columnar. Snowflake's VARIANT type, ClickHouse's JSON columns and Parquet's nested types are the same move.

The non-obvious part is what shredding must preserve. If you flatten a tree into arrays, you destroy the path information, and to rebuild the documents you must store it back. In Dremel (the Google system whose design Parquet follows), this is done with repetition levels and definition levels. For each value they record, in a few bits, where in the tree the value sat (which list element repeated) and how deep the nesting went before a missing value (null). Each costs roughly log₂(depth) bits. The general statement is worth keeping:

The real cost of shredding is not space but validity. It works only while the inferred schema holds. Rare or varied fields explode into sparse columns (mostly empty). And a schema drift event turns a fast table into a slow one, silently, with no error message.

Summary. Self-description moves the schema from the dataset to the record. That forbids skipping and encoding until you shred it back, and shredding is valid only as long as the inferred schema is.

Where does physical position come from? Two more items

The next two items are not really adjacency decisions. NSM, DSM and PAX answer "what is beside what". The next two answer "where does a physical position come from?" They combine with the three layouts above and do not compete with them. It helps to view them as a small group of their own, order origin, between layout and clustering.

Log-structured (append-only) layout

Here, physical position comes from arrival time. The reasoning is short. If the medium's write cost is lowest for sequential writes (disk seek amortization, flash erase-block size, object-store immutability), then the only write that costs nothing extra is the one that appends. Every other physical order must be constructed, and constructing it means rewriting.

The consequences chain together immediately:

Physical order carries no key information, so reads must merge across units.
Merge cost grows with the number of units.
The number of units grows without limit.
So there must be compaction (merging units to reduce their number).
So there must be a collector and an indirection layer to find the current version.

That is the immutable-substrate rule once more. The SSD's translation layer, the LSM tree, the Iceberg manifest and the Delta log are one design. Object storage grows it even though it is immutable only by interface, not by physics. This strongly suggests the rule is about the constraint, not the medium.

Summary. Append-only makes writes free by making order meaningless, and every cost you avoided reappears in the merge.

Heap versus clustered (index-organized) layout

This is also an order-origin item, and the most consequential one in the group.

A heap puts rows wherever there is free space. A row's identity is a physical address (page number, slot number), and that address is stable. Secondary indexes can store this address and reach a row in one hop.

A clustered (also called index-organized) table makes the physical order equal to the primary-key order. Range scans on the primary key become sequential. But when a page fills up and splits, rows move, so the physical address is not stable. A secondary index must then store the primary key instead, and every secondary lookup needs a second traversal. That is the whole difference between InnoDB (MySQL's storage engine, which is clustered) and the PostgreSQL heap. It can be derived, not memorized.

Generalize it, because it is load-bearing for the rest of this mechanism:

The same constraint returns in Mutation strategies as positional versus equality deletes (a positional delete is a claim about physical position and is valid only while nothing reclusters). It returns again in Physical clustering as the reason reclustering costs far more than the bytes it moves: you are not only moving data, you are invalidating every structure that referred to its position.

Summary. You may address by position or order by key, not both. The second one costs an indirection.

Details that complete the picture

These topics sit under or beside the layouts above. They are easy to miss and they explain many choices in real file formats.

Fixed width, variable width and the slotted page

Fixed-width values (integers, floats) can be found by arithmetic: value number 7 starts at byte 7 × 8. Variable-width values (strings, JSON) cannot. The standard mechanism is the slotted page. A page keeps a small slot directory: an array where entry i stores the offset and length of record i inside the page. Record data fills the page from the other end. A record is then addressed by (page number, slot number). If a record grows, shrinks or is moved inside the page, only its slot entry changes, and the record's address stays valid. If a record no longer fits, the system leaves a forwarding pointer in the old slot. The slotted page is the base for positional addressing, so it must exist before positional deletes (Mutation strategies) make sense.

Column chunk internals

Inside a Parquet file, a column chunk is divided into pages, each with an encoding. The boundaries between pages are the places where a reader can start decoding and where it can skip. They are also the places where late materialization becomes possible: first evaluate the filter on the filter column alone, then decode and fetch the other columns only for the rows that passed.

Schema evolution

Whether a file refers to its columns by name or by a stable ID decides whether a rename breaks old files. That is a physical consequence of a schema-evolution choice, and it explains why modern table formats address columns by ID.

Multidimensional and tiled layouts

There is a third meaning of "together": neither an entity nor an attribute, but a neighbourhood in a coordinate space. Chunked arrays, CSR (compressed sparse row, a compact way to store graphs), TileDB and Zarr tile d dimensions so that closeness in space becomes closeness in storage. This is a genuine peer of NSM, DSM and PAX. It also leads to Z-ordering in Physical clustering: Z-order is the same idea applied to placement rather than adjacency.