Skip to content
AxonOps Documentation

AxonOps — AI-Native Control Plane for Open Source Data Platforms

SAI Query Execution

Storage Attached Index (SAI), introduced in Cassandra 5.0 (CEP-7, CASSANDRA-16052), introduces a fundamentally different distributed query architecture compared to legacy 2i and SASI. Rather than broadcasting to all nodes simultaneously, SAI implements adaptive coordinator-based range reading with dynamic concurrency adjustment, bounded memory consumption, and gossip-based index status propagation.

Coordinator-Level Query Planning

Section titled “Coordinator-Level Query Planning”

The SAI coordinator performs query analysis before dispatching requests:

  1. Index selectivity analysis: Identifies the most selective index among available SAI indexes to narrow the filtering space.
  2. Read command construction: Embeds selected index metadata into the distributed range read command.
  3. Concurrency factor estimation: Calculates an initial parallel replica query count using local data statistics and the query LIMIT parameter.
SAI Coordinator: Adaptive Range ReadingSAI Coordinator: Adaptive Range ReadingCoordinator ProcessingRound 1: Initial token rangesRound N: Subsequent ranges (if needed)1. Analyze queryIdentify most selective index2. Estimate concurrency factorBased on local data + LIMIT3. Dispatch to token ranges(parallel, bounded)Range ARange BRange CRange DRange EClient4. Collect resultsRecompute concurrency factor5. Return whenLIMIT satisfiedif moreresults neededLIMITsatisfied

Multi-Round Execution

Section titled “Multi-Round Execution”

SAI executes queries iteratively rather than broadcasting to all nodes at once:

  1. Round initialization: The coordinator dispatches requests to a subset of token ranges based on the computed concurrency factor.
  2. Response collection: Awaits responses from the requested replicas.
  3. Concurrency adjustment: Recomputes the concurrency factor based on the returned row count relative to the query limit.
  4. Iteration: Repeats until the query limit is satisfied or all ranges are exhausted.

Queries satisfied early — where the first round of ranges returns enough results — contact only a fraction of the cluster. This reduces network overhead, coordinator memory pressure, and tail latency compared to scatter-gather.

Index Status Propagation

Section titled “Index Status Propagation”

SAI nodes propagate local index status to peers via the gossip protocol. This enables the coordinator to:

  • Filter replicas with non-queryable indexes from request routing.
  • Detect index build completion status before routing queries.
  • Identify failed index states that require rebuild.

Queries are not silently degraded by failed index state — the coordinator routes around replicas whose index is not queryable.

Replica-Level Query Processing

Section titled “Replica-Level Query Processing”

Upon receiving a token range request, replicas execute local index queries through the Query Plan interface:

SAI Replica: Query Plan ExecutionSAI Replica: Query Plan ExecutionQuery Plan InterfaceToken Flow FrameworkPost-Filtering1. Expression analysisMap predicates to indexes2. Query ControllerAcquire SSTable referencesPrevents compactionuntil query completesMemtable indexiterationSSTable indexiterationAsync mergevia Token FlowPartition granularityfilteringTombstoneeliminationNon-indexedpredicate evaluationToken range requestfrom coordinatorFiltered resultsto coordinator

Query Plan Components

Section titled “Query Plan Components”
  1. Expression analysis: Determines which available SAI column indexes satisfy the query predicates.
  2. Query Controller acquisition: Obtains references to active SSTable index segments intersecting the requested token range.
  3. Reference retention: Holds SSTable references until query completion, preventing compaction from removing the underlying data mid-query.

Token Flow Framework

Section titled “Token Flow Framework”

SAI uses the Token Flow framework for asynchronous iteration over partition matches across Memtable and SSTable indexes:

OperationDescription
IterationSequential disk access via chunk cache to row IDs for partition key lookups
Token skippingAdvances past unmatched tokens at paging boundaries or during token intersection
Stream mergingCombines results from multiple indexes using Boolean logic for multi-predicate queries

The Token Flow framework enables multi-predicate queries to be satisfied by intersecting index streams rather than performing separate lookups and joining at a higher level.

Post-Filtering Pipeline

Section titled “Post-Filtering Pipeline”

Following index-based partition key retrieval, SAI applies a filter tree for secondary filtering:

Filter StagePurpose
Partition granularityWide partitions require row-level filtering beyond partition key matches
Tombstone eliminationRemoves rows deleted after indexing but before compaction
Non-indexed predicatesEvaluates query conditions that have no index support

Implementation Characteristics

Section titled “Implementation Characteristics”
CharacteristicImplementation
Storage structurePer-SSTable index with segment architecture
Memtable indexingEnables read-your-writes semantics on recently written data
Query coordinationAdaptive range reading with dynamic concurrency factor
Multi-predicateToken Flow framework with Boolean stream merging
Memory modelBounded via segment flushing and concurrency factor
Cluster awarenessIndex status propagation via gossip
Zero-copy streamingFully compatible

Latency Model

Section titled “Latency Model”
T_total = Σ(T_round_j)  where rounds ≤ ceil(LIMIT / concurrency_factor)

SAI’s multi-round execution terminates as soon as the query limit is satisfied. For bounded queries with a LIMIT clause, this can result in significantly fewer nodes contacted compared to scatter-gather, and latency is bounded by the concurrency factor rather than by the slowest node in the cluster.

Section titled “Related Documentation”