That’s a good question.
Restating your question so that we are on the same page: Partition Index tells us the offset (or the position) of the partition key in the SStable’s data file, but how does Cassandra filters out rows based on clustering columns? Does Cassandra start reading sequentially from the offset until it finds out the exact row?
To extend this question, if we are querying a set of columns, how does Cassandra finds out the exact position of a column for a given row? Is it a sequential search?
Answer: In the older Cassandra versions, it was sequential. Meaning, Cassandra goes to the offset given by the partition index and then starts reading sequentially until it finds the correct column or row.
In the latest releases of Cassandra, they have introduced the concept of “Promoted index” which is used for large partitions with many rows. “Promoted index” is also stored in the index file. To find a specific row in a partition with many rows the promoted index is used to find the data file portion that holds the information related to the range of rows this row belongs to.
In short, “Promoted index” divides the set of rows at 64KB blocks (by default); where each blockis summarized by index_info
structure containing: start_name
and end_name
are the names of the first and last columns in that block. To find a row, Cassandra does a binary search on these blocks and then scans the partition of the appropriate range.
For more details see the following links:
https://issues.apache.org/jira/browse/CASSANDRA-11206