The Merge Iterator: Range Scans Across Sources

A range scan needs entries from every source — memtable, every L0 SSTable, every overlapping deeper SSTable — interleaved in sorted order. The construct that does this is a merge iterator.

It's k-way merge again, but in iterator form (lazy, pull-based) instead of compaction's batch form.

The API

The merge iterator pops the smallest key, then consumes all duplicate-key entries from other iterators so the next next() advances to a new key. This is how it skips obsolete versions in the middle of a range scan.

Snapshot Reads via Merge Iterator

If we want all visible-at-snapshot-S entries:

The merge iterator naturally surfaces the newest version of each key first; if it's > snapshot, walk to the next entry (still the same key, but older — pick the first one <= snap, or move on to the next key).

Tombstone Filtering

Tombstones (Ch 7) shadow older versions. When the merge iterator yields a key whose newest version is a tombstone:

• Skip the tombstone (don't yield it to the user).
• Skip every older version of the same key.
• Move to the next distinct key.

Performance

K-way merge over K iterators is O(N log K) for N total entries. For typical LSMs (K ≈ 10-20), the heap cost is dwarfed by the per-block decompression cost on each underlying iterator.

Where It Shows Up

• Range queries (SELECT * WHERE ...)
• Iteration over an entire keyspace (Cassandra KEYS, RocksDB Scan)
• Compaction (special case: writes to a new SSTable instead of streaming to user)
• Snapshot consistency (pin sequence number, merge iterator filters)

It is, in a sense, the central data structure of LSM reads. Every multi-source read uses it.