...

• Native 2i
• Lucene
• Materialized views
• SASI

These solutions have the following drawbacks:

...

The SASI architecture was the best out of many that were evaluated, and was used as a starting point for SAI.

Challenges

Having outlined the potential benefits of SAI, there are two considerable architectural challenges it will face.

The first is that because SAI index components are SSTable-attached, its performance will be highly dependent on the compaction strategy in use. The more SSTables SAI must search, the slower local queries will be. This is similar to the general problem in C* around hitting too many SSTables for individual reads, but can be much worse for SAI, unless queries are restricted to partitions or small token ranges. A particularly painful case would be a query without token or partition restrictions on a table that uses LCS, which, by design, maintains hundreds or thousands of small SSTables.

Second, all C* secondary index implementations (and SAI would be no different) make distributed queries on top of the range read mechanism. This is problematic for two reasons. The first is that even at a read CL of ONE/LOCAL_ONE, N (# of nodes) / RF (replication factor) nodes/replicas must be contacted for any non partition/token restricted query. At higher CLs, we can effectively contact the entire cluster. Also, C* range queries are made in a single pass per replicas, with all replicas returning responses containing full rows over the wire rather than row identifiers and sorting information (as systems like SolrCloud/ES do, for instance). Historically, attempts have been made to mitigate this by only incrementally querying the token ring, but making multiple passes when the entire ring must be queried introduces considerable latency. The only way to avoid sending large amounts of data over the wire while simultaneously avoiding multiple query rounds is for query results to turn up a small number of results across the entire ring. This is explained in more detail in this blog post.

The only "easy" way around these two challenges is to focus our efforts on queries that are restricted to either partitions or small token ranges. These queries behave well locally even on LCS (given levels contain token-disjoint SSTables, and assuming a low number of unleveled SSTables), avoid fan-out and all of its secondary pitfalls, and allow us to make queries at varying CLs with reasonable performance. Attempting to fix the local problems around compaction strategy could mean either restricted strategy usage or partially abandoning SSTable-attachment. Attempting to fix distributed read path problems by pushing the design towards IR systems like ES could compromise our ability to use higher read CLs.