A type with 25 million records is stored as 250 segments of 100,000 records each. A query that searched every segment's index for every lookup would spend nearly all of its time confirming that a value is not there.
InventDB's read path is built to avoid that work. Before it descends any index in a segment, it checks whether the segment could hold the key it wants or a value in the range it wants. When a query asks for only the first N rows in some order, the engine reads its indexes in that order and stops at N. This article covers each mechanism, the numbers behind it and the cases where it does not help. The segments themselves are described in How a single instance holds 250 million records.
A Bloom filter for every segment's ids
Every segment keeps a Bloom filter of the record ids it holds. A Bloom filter is a bit array probed by k hash functions: inserting an id sets k bits, and a lookup that finds any of those bits clear knows that the id was never inserted. It can wrongly answer maybe, but it never wrongly answers no. A false maybe costs one wasted index descent, and a no lets the engine skip the segment with certainty.
Each filter is sized for 100,000 ids at a false-positive rate of 0.01% with the standard formulas, m = -n ln(p) / (ln 2)² bits and k = (m / n) ln 2 hash functions. That comes to 1,917,012 bits, about 234 KiB, and 13 hash functions. The 13 bit positions come from double hashing, bit i = (h1 + i × h2) mod m, with two independently seeded 64-bit hashes, so a lookup computes two hashes rather than 13. Bits are set with atomic operations, so concurrent writers can add ids to the same filter at once.
A lookup by id checks the active segment's filter first, then the sealed segments' filters from newest to oldest, and descends an id index only where a filter answers maybe. With 250 segments the expected number of wasted descents is 250 × 0.0001, or 0.025 per lookup, so a point read costs about one real descent however many segments the type has. Ids enter the active segment's filter on the write path, before the record reaches the id index, so a fresh record is never skipped. A segment whose filter file is missing is treated as answering maybe, which is slower and always correct.
Bloom filters cannot remove entries, so deleted ids stay in a segment's filter and raise its false-positive rate slightly. That costs an occasional extra descent and never a wrong answer.
Bloom filters for field values
Ids are not the only keys looked up one at a time. A join on a foreign key asks, for each parent row, which child rows hold that parent's id, and the child type's field index is spread across every segment. Minimum and maximum values cannot help here: parent ids are effectively random, so every segment's range spans nearly the whole key space.
For equality lookups, each sealed segment therefore also has a Bloom filter per field over the field's distinct values, at a false-positive rate of 0.1%. It is built the first time an equality lookup reaches that segment, from the field's counts tree, which holds exactly one entry per distinct value, so building it costs one pass over the distinct values rather than over the rows. Once built, it is saved next to the index and reused after a restart. Before descending a segment's value tree for customer_id = 'C-4410', the engine checks the segment's minimum and maximum and then this filter, and moves on if either rules the value out.
The active segment has no value filter. It changes on every write, so a filter sized when it was built would soon be too small, and keeping it current would add cost to every insert. With one active segment against hundreds of sealed ones, a filter there would save one descent at most.
Zone maps: a minimum and a maximum per segment
A zone map is the smallest and largest value a field holds in one segment. The engine updates it as values are indexed and stores it in the field's counts tree under a reserved key, so it loads with the index. Before a range scan descends a segment's value tree, the engine compares the query's range with the segment's minimum and maximum, which takes two byte comparisons, and skips the segment if they cannot overlap.
Zone maps work when a field's values follow insert order. Segments fill in insert order, so for a creation date each segment covers a narrow and mostly separate window of time:
A field whose values are spread evenly across all records, such as an age or a random code, gives every segment nearly the same minimum and maximum, and zone maps prune nothing for it. The same check also serves range aggregates, described in Columnar aggregates inside a JSON document database, and the equality lookups above.
Two rules keep pruning safe. Stored bounds are capped at 256 bytes: a long minimum is cut to a prefix, which is still a lower bound, and a long maximum is cut and followed by a 0xFF byte, which keeps it an upper bound. A segment with no zone map is treated as overlapping every range, so a missing map costs speed and never rows.
The ORDER BY LIMIT walk
Pagination and leaderboards ask for the first N rows in some order. The general plan filters every candidate, fetches it, sorts the whole set and keeps N, so its work grows with the number of matches. InventDB instead uses the fact that each segment's value tree already holds the field in sorted order.
For ORDER BY amount DESC LIMIT 5, the engine opens one cursor per segment on the amount value tree, each reading downward from the top, and puts each cursor's current entry into a heap. It pops the largest entry, emits it and advances only the cursor it came from. That is a k-way merge, and it stops after five entries. Cursors refill in chunks of 64 to 512 entries and resume from the exact position of their last entry. Each entry carries its sort bytes and its record id, so ties are broken by id and the order is the same on every run. Only the five winning records are read from the record files.
The walk serves these query shapes:
- No WHERE clause, ordering by a number, a date or a string, with or without OFFSET.
- A range on the ORDER BY field, such as
WHERE created_at >= '2026-09-01' ORDER BY created_at DESC LIMIT 20. The range becomes the cursors' bounds. - A range on the ORDER BY field combined with
INor=on another numeric or date field. The engine builds each segment's set of matching ids once, then skips entries outside it during the walk. - A range on a different numeric field. The walk tests each candidate's value as it goes, from the sealed segment's column, where the id hashes are sorted and searchable, or from the active segment's index.
ORDER BY _idwith no WHERE clause, which is answered from the id index because that index is already sorted by id.
The three shapes with a range need the ORDER BY field to hold numbers or dates.
OFFSET is handled by ranking OFFSET plus LIMIT entries and dropping the first OFFSET before any record is read, for windows of up to 100,000 rows; deeper pages take the general plan. If a condition matches so few rows that one segment's cursor would pull more than 2,000 times the limit or 50,000 entries, whichever is larger, the walk gives up and the general plan answers. Every shape can fall back to the general plan, so the fast path is never the only route to a correct answer.
An ORDER BY on two or more columns with no WHERE clause uses the first column's index to find its boundary group, which is the set of rows whose first-column value could still reach the top N. Only that group is fetched and sorted by every order column. If the group would exceed 2 million rows, a ranker that scans the id-to-value trees of up to four order columns takes over.
When it does not apply
- Values unrelated to insert order. Zone maps prune nothing for a field whose values are spread evenly across segments.
- Value filters serve only equality, and only sealed segments. A range on a field is pruned by zone maps alone.
- Filters take space. An id filter is about 234 KiB per segment, so 250 segments carry about 57 MiB of them. A value filter takes about 1.8 bytes per distinct value.
- Long values have no sorted position. Values over 1,024 bytes are indexed by hash, so the walk declines for a field that holds any of them.
- NULLs can send a query to the general plan. NULLs have no place in the value order, so when the ORDER BY field is missing or NULL in some rows, the general plan sorts the query and places them correctly.
How we test it
Pruning is only worth having if it never drops a row, so the tests compare answers as well as timings. A pagination check runs six query shapes at five LIMIT and OFFSET windows and checks each page against ground truth: the page must be sorted, and its first row must have exactly OFFSET rows ordered before it, counted by a separate COUNT(*) query. Each run of our 3,511-query SQL battery compares the rows every query returns, so a segment skipped in error shows up as a mismatch rather than as a fast answer. The engine also counts how many segments its zone maps checked and skipped, which lets us read the skip ratio of any query while profiling it.
Writing queries that read less
All of this is on for every type in InventDB Serverless and InventDB SOAR, with nothing to configure. A few habits let more of your queries use it:
- Filter and sort on fields that rise with insert order, such as creation dates and sequence numbers, so zone maps can skip segments.
- Put the range on the field you order by. Then the walk reads one field's index and fetches only the rows it returns.
- Page with a range on the order field rather than a deep OFFSET. A query that continues from the last value the client saw stays on the walk however far it goes.
POST /sql
Authorization: Bearer <token>
Content-Type: application/json
{
"sql": "SELECT order_id, total, created_at FROM shop.orders WHERE created_at < '2026-09-28T14:02:11Z' ORDER BY created_at DESC LIMIT 50"
}Each page sends the created_at of the last row it received. The engine starts a cursor on each segment's date index just below that point, so a segment whose dates all lie above it is exhausted at its first seek, and the walk reads 50 records whatever page the client is on.