Read Path: Lookups and Indexes

A negative Bloom result terminates the search for that SSTable with no disk IO at all. A positive result advances to the two-level index: a binary search over the in-memory summary narrows to a range in Index.db, then a binary search within that region finds the exact Data.db position.

BTI replaces binary search over a sampled summary with a trie walk whose cost is proportional to key length rather than index size. There is no equivalent of Summary.db in BTI — the trie itself provides navigation.

Where s = summary entry count, n = partition count in the SSTable, \|key\| = key byte length, r = row index entry count.

Cassandra uses a 128-bit Murmur3 hash of the partition key, split into two 64-bit halves h1 and h2. The k individual bit positions are computed via double hashing:

This avoids computing k independent hashes while producing outputs with negligible correlation. Each h(i) addresses a single bit in the filter’s m-bit array; all k bits must be set for a positive result.

The false positive rate (FPR) for a Bloom filter with k hash functions, m bits, and n stored partitions is:

Cassandra derives k and m from the target FPR configured in the table definition. The per-table setting is bloom_filter_fp_chance, defaulting to 0.01 (1% false positive rate). Lower FPR = more memory for the filter; higher FPR = more wasted IO from false positives triggering index lookups.

Optimal k for a given p:

Increasing bloom_filter_fp_chance (toward 1.0) reduces filter memory but raises the rate of wasted index lookups. Decreasing it (toward 0.0) increases filter memory but reduces false positives. For write-heavy tables where reads are rare, a high FPR is acceptable. For read-heavy tables with large SSTable counts, a low FPR (0.001 or lower) may be worth the memory cost.

Each entry in Index.db encodes:

BIG format supports two entry variants:

VInt encoding allows small offsets (early in the file) to consume fewer bytes, producing a more compact index for dense keyspaces.

Summary.db holds a sampled subset of Index.db entries, selected at a configurable interval (index_interval in cassandra.yaml, default 128 entries per sample). The summary is sorted by token, loaded entirely into memory, and used as the entry point for partition lookups.

Binary search flow:

With concrete numbers, the decision looks like:

The summary reduces worst-case Index.db IO from a full file scan to a bounded region scan proportional to the sample interval.

For range scans (e.g., SELECT …​ WHERE token(pk) > X AND token(pk) < Y), the read path:

This means range scans over many partitions are sequential IO within the bounded Index.db region, which is cache-friendly.

The promoted index maps clustering key ranges to Data.db offsets within the partition:

The promoted index is written only when a partition exceeds the column_index_size threshold (default 16 KiB in cassandra.yaml). Narrow partitions — those under the threshold — have no promoted index in their Index.db entry. The read path checks whether a promoted index is present before deciding whether to scan or seek within the partition.

When a query requests a clustering key range (a slice), the read path:

This is critical for time-series workloads, where a single partition may contain millions of rows but a query targets only a narrow time window.

Partition keys are encoded as byte-comparable sequences before trie insertion. Byte-comparable encoding preserves the token ordering of the original keys, which means trie traversal naturally visits partitions in the same order as a token-sorted binary search would.

A partition lookup walks the trie one byte at a time, matching each key byte to a trie branch:

BTI trie shape, simplified:

The sign of the position value is the BTI format’s index disambiguation trick (see also Write Path). Contributors must preserve this convention when modifying trie writer or reader code.

For wide partitions (those above the column_index_size threshold), the row-level index is stored in Rows.db as a separate trie indexed by clustering key bytes. A leaf node in Rows.db encodes a Data.db offset for the row block at that clustering key position.

For narrow partitions, Rows.db is bypassed entirely — the negative position value in Partitions.db provides the Data.db offset directly.

The partition trie is built in a single pass during flush via IncrementalTrieWriter. Only the active path from the root to the current key is kept in memory at any time; trie nodes are finalized and written to Partitions.db as soon as their subtrees are complete. This bounds memory use during flush regardless of partition count.

PartitionIndexBuilder uses a one-key lookahead to write only the shortest prefix of each key that distinguishes it from the next key. This reduces the trie’s stored key bytes for high-cardinality keyspaces with shared prefixes, shrinking Partitions.db without affecting lookup correctness.

For uniform key distributions, BTI and BIG offer comparable read latency. For workloads with high key cardinality and long shared prefixes (e.g., compound partition keys with repeated prefix components), BTI’s prefix sharing and O(|key|) trie walk provide a meaningful worst-case improvement.

A point read targets a single partition key.

For narrow partitions, a single disk seek into Data.db follows the index lookup. For wide partitions with no clustering constraint, the entire partition is read sequentially from the partition start offset.

A slice read targets a partition key plus a clustering key range.

Slice reads are the normal access pattern for time-series and collection-heavy schemas. Without the promoted index (BIG) or Rows.db (BTI), a slice read would require scanning the entire partition from the start.

A range scan targets a token range, returning partitions across multiple partition keys.

Range scans are inherently multi-SSTable: all SSTables whose token ranges overlap the scan range are candidates. The read path merges results across SSTables using a priority queue sorted by token, resolving conflicting versions via timestamp.

The scatter-gather step (3c) is a local operation: the index and base table rows are on the same node. However, each node independently performs the lookup, so the full result set is assembled from all participating replicas.

Index and base table updates are not atomic. A write to the base table updates the index in the same local write path, but if the write fails partway through (e.g., before the index SSTable is flushed), a brief window exists where the index and base table are inconsistent. Cassandra uses a read-before-write to clean up stale index entries on read, but stale entries may persist until compaction or explicit cleanup.

Index SSTables use the same SSTable format (BIG or BTI) as the base table. The indexed value becomes the partition key of the index SSTable, and the base table’s partition key becomes a clustering column within each index partition. This means low-cardinality columns (few distinct index values) produce wide index partitions; high-cardinality columns produce narrow ones.

2i is best suited to:

Approximate lookup complexity: O(log S + K) for equality lookups, where S = index SSTable count and K = matching keys per SSTable.

Each SAI index column produces one segment file per SSTable. The segment file contains the column-level index for all rows in that SSTable. When SSTables are compacted, their corresponding SAI segments are merged into a new unified segment alongside the compacted SSTable. This keeps the index in sync with the data without requiring cross-SSTable index state.

The row ID step is important: SAI returns internal row identifiers from the segment scan, then fetches the actual row data from Data.db using those IDs. This is a two-phase lookup per SSTable — segment scan, then data fetch — but avoids the scatter-gather across nodes that characterizes 2i.

SAI vector indexes (available in Cassandra 5.0+) use per-segment approximate nearest neighbor structures. Each SSTable’s SAI segment contains an ANN graph for the indexed vector column. At query time, each segment is searched independently for the k nearest neighbors, the per-segment results are merged and re-ranked by actual distance, and the global top-k is returned. This design trades recall accuracy (approximation) for bounded search time even over large SSTable counts.

For wide partitions with a clustering predicate, insert between steps 4 and 5: