SASI 索引
SASIIndex，簡稱 SASI，是 Cassandra 的 Index 介面的實作，可用作現有實作的替代方案。SASI 的索引和查詢透過特別針對 Cassandra 的需求進行調整，進而改善現有實作。在以前需要進行篩選的查詢中，SASI 具有優異的效能。為了達成此效能，SASI 旨在比現有實作消耗更少的資源，包括記憶體、磁碟和 CPU 使用率。此外，SASI 支援字串的前置詞和包含查詢（類似於 SQL 的 LIKE = "foo*" 或 LIKE = "foo"'）。
以下內容將說明如何開始使用 SASI，示範如何使用範例，並提供一些實作的詳細資料。
使用 SASI
以下範例將逐步說明如何建立表格和其欄位的索引，以及如何對插入的資料執行查詢。
以下範例假設已建立 demo keyspace 並已使用中。
cqlsh> CREATE KEYSPACE demo WITH replication = {
... 'class': 'SimpleStrategy',
... 'replication_factor': '1'
... };
cqlsh> USE demo;
所有範例都針對 sasi 表格執行
cqlsh:demo> CREATE TABLE sasi (id uuid, first_name text, last_name text,
... age int, height int, created_at bigint, primary key (id));
建立索引
若要建立 SASI 索引，請使用 CQL CREATE CUSTOM INDEX 陳述式
cqlsh:demo> CREATE CUSTOM INDEX ON sasi (first_name) USING 'org.apache.cassandra.index.sasi.SASIIndex'
... WITH OPTIONS = {
... 'analyzer_class':
... 'org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer',
... 'case_sensitive': 'false'
... };
cqlsh:demo> CREATE CUSTOM INDEX ON sasi (last_name) USING 'org.apache.cassandra.index.sasi.SASIIndex'
... WITH OPTIONS = {'mode': 'CONTAINS'};
cqlsh:demo> CREATE CUSTOM INDEX ON sasi (age) USING 'org.apache.cassandra.index.sasi.SASIIndex';
cqlsh:demo> CREATE CUSTOM INDEX ON sasi (created_at) USING 'org.apache.cassandra.index.sasi.SASIIndex'
... WITH OPTIONS = {'mode': 'SPARSE'};
已建立的索引具有一些選項，可自訂其行為，並可能影響效能。first_name 上的索引不區分大小寫。分析器會在後續範例中進一步說明。NonTokenizingAnalyzer 對於文字不會執行任何分析。每個索引都有一個模式：PREFIX、CONTAINS 或 SPARSE，第一個為預設值。last_name 索引是使用 CONTAINS 模式建立的，它會比對字尾上的字詞，而不是只比對字首。以下提供此類範例，您可以在 OnDiskIndex 區段中找到更多詳細資料。created_at 欄位是使用 SPARSE 模式建立的，目的是改善查詢大型、密集數字範圍（例如每毫秒插入資料的時間戳記）的效能。您也可以在 OnDiskIndex 區段中找到 SPARSE 實作的詳細資料。age 索引是使用預設 PREFIX 模式建立的，而且由於欄位是數字，因此未指定大小寫敏感度或文字分析選項。
在插入下列資料並執行 nodetool flush 之後，可以在 Cassandra 的記錄中看到 SASI 執行索引快取至磁碟的動作，儘管不需要直接呼叫快取（請參閱 IndexMemtable 以取得更多詳細資料）。
cqlsh:demo> INSERT INTO sasi (id, first_name, last_name, age, height, created_at)
... VALUES (556ebd54-cbe5-4b75-9aae-bf2a31a24500, 'Pavel', 'Yaskevich', 27, 181, 1442959315018);
cqlsh:demo> INSERT INTO sasi (id, first_name, last_name, age, height, created_at)
... VALUES (5770382a-c56f-4f3f-b755-450e24d55217, 'Jordan', 'West', 26, 173, 1442959315019);
cqlsh:demo> INSERT INTO sasi (id, first_name, last_name, age, height, created_at)
... VALUES (96053844-45c3-4f15-b1b7-b02c441d3ee1, 'Mikhail', 'Stepura', 36, 173, 1442959315020);
cqlsh:demo> INSERT INTO sasi (id, first_name, last_name, age, height, created_at)
... VALUES (f5dfcabe-de96-4148-9b80-a1c41ed276b4, 'Michael', 'Kjellman', 26, 180, 1442959315021);
cqlsh:demo> INSERT INTO sasi (id, first_name, last_name, age, height, created_at)
... VALUES (2970da43-e070-41a8-8bcb-35df7a0e608a, 'Johnny', 'Zhang', 32, 175, 1442959315022);
cqlsh:demo> INSERT INTO sasi (id, first_name, last_name, age, height, created_at)
... VALUES (6b757016-631d-4fdb-ac62-40b127ccfbc7, 'Jason', 'Brown', 40, 182, 1442959315023);
cqlsh:demo> INSERT INTO sasi (id, first_name, last_name, age, height, created_at)
... VALUES (8f909e8a-008e-49dd-8d43-1b0df348ed44, 'Vijay', 'Parthasarathy', 34, 183, 1442959315024);
cqlsh:demo> SELECT first_name, last_name, age, height, created_at FROM sasi;
first_name | last_name | age | height | created_at
------------+---------------+-----+--------+---------------
Michael | Kjellman | 26 | 180 | 1442959315021
Mikhail | Stepura | 36 | 173 | 1442959315020
Jason | Brown | 40 | 182 | 1442959315023
Pavel | Yaskevich | 27 | 181 | 1442959315018
Vijay | Parthasarathy | 34 | 183 | 1442959315024
Jordan | West | 26 | 173 | 1442959315019
Johnny | Zhang | 32 | 175 | 1442959315022
(7 rows)
相等性與字首查詢
SASI 支援 CQL 已支援的所有查詢，包括用於 PREFIX、CONTAINS 和 SUFFIX 搜尋的 LIKE 陳述式。
cqlsh:demo> SELECT first_name, last_name, age, height, created_at FROM sasi
... WHERE first_name = 'Pavel';
first_name | last_name | age | height | created_at
-------------+-----------+-----+--------+---------------
Pavel | Yaskevich | 27 | 181 | 1442959315018
(1 rows)
cqlsh:demo> SELECT first_name, last_name, age, height, created_at FROM sasi
... WHERE first_name = 'pavel';
first_name | last_name | age | height | created_at
-------------+-----------+-----+--------+---------------
Pavel | Yaskevich | 27 | 181 | 1442959315018
(1 rows)
cqlsh:demo> SELECT first_name, last_name, age, height, created_at FROM sasi
... WHERE first_name LIKE 'M%';
first_name | last_name | age | height | created_at
------------+-----------+-----+--------+---------------
Michael | Kjellman | 26 | 180 | 1442959315021
Mikhail | Stepura | 36 | 173 | 1442959315020
(2 rows)
當然，由於在建立索引時提供的選項，first_name 欄位的查詢大小寫無關緊要。
cqlsh:demo> SELECT first_name, last_name, age, height, created_at FROM sasi
... WHERE first_name LIKE 'm%';
first_name | last_name | age | height | created_at
------------+-----------+-----+--------+---------------
Michael | Kjellman | 26 | 180 | 1442959315021
Mikhail | Stepura | 36 | 173 | 1442959315020
(2 rows)
複合查詢
SASI 支援具有多個謂詞的查詢，但由於預設索引實作的特性，CQL 要求使用者指定 ALLOW FILTERING，以選擇加入此類查詢的潛在效能陷阱。使用 SASI 時，儘管仍需要包含 ALLOW FILTERING，但由於過濾未執行，因此效能陷阱不存在，以減少對語法的修改。SASI 如何從多個謂詞加入資料的詳細資料，請參閱下方的 實作詳細資料 區段。
cqlsh:demo> SELECT first_name, last_name, age, height, created_at FROM sasi
... WHERE first_name LIKE 'M%' and age < 30 ALLOW FILTERING;
first_name | last_name | age | height | created_at
------------+-----------+-----+--------+---------------
Michael | Kjellman | 26 | 180 | 1442959315021
(1 rows)
字尾查詢
下一個範例示範 last_name 欄位上的 CONTAINS 模式。透過使用此模式，謂詞可以搜尋任何包含搜尋字串作為子字串的字串。在此情況下，字串包含 a'' 或 an''。
cqlsh:demo> SELECT * FROM sasi WHERE last_name LIKE '%a%'; id | age | created_at | first_name | height | last_name --------------------------------------+-----+---------------+------------+--------+--------------- f5dfcabe-de96-4148-9b80-a1c41ed276b4 | 26 | 1442959315021 | Michael | 180 | Kjellman 96053844-45c3-4f15-b1b7-b02c441d3ee1 | 36 | 1442959315020 | Mikhail | 173 | Stepura 556ebd54-cbe5-4b75-9aae-bf2a31a24500 | 27 | 1442959315018 | Pavel | 181 | Yaskevich 8f909e8a-008e-49dd-8d43-1b0df348ed44 | 34 | 1442959315024 | Vijay | 183 | Parthasarathy 2970da43-e070-41a8-8bcb-35df7a0e608a | 32 | 1442959315022 | Johnny | 175 | Zhang (5 rows) cqlsh:demo> SELECT * FROM sasi WHERE last_name LIKE '%an%'; id | age | created_at | first_name | height | last_name --------------------------------------+-----+---------------+------------+--------+----------- f5dfcabe-de96-4148-9b80-a1c41ed276b4 | 26 | 1442959315021 | Michael | 180 | Kjellman 2970da43-e070-41a8-8bcb-35df7a0e608a | 32 | 1442959315022 | Johnny | 175 | Zhang (2 rows)
非索引欄位上的表達式
SASI 也支援在非索引欄位上進行篩選，例如 height。表達式只能使用 AND 來縮小現有查詢的範圍。
cqlsh:demo> SELECT * FROM sasi WHERE last_name LIKE '%a%' AND height >= 175 ALLOW FILTERING; id | age | created_at | first_name | height | last_name --------------------------------------+-----+---------------+------------+--------+--------------- f5dfcabe-de96-4148-9b80-a1c41ed276b4 | 26 | 1442959315021 | Michael | 180 | Kjellman 556ebd54-cbe5-4b75-9aae-bf2a31a24500 | 27 | 1442959315018 | Pavel | 181 | Yaskevich 8f909e8a-008e-49dd-8d43-1b0df348ed44 | 34 | 1442959315024 | Vijay | 183 | Parthasarathy 2970da43-e070-41a8-8bcb-35df7a0e608a | 32 | 1442959315022 | Johnny | 175 | Zhang (4 rows)
基於分隔符號的標記化分析
提供的簡單文字分析是基於分隔符號的標記化。這提供了索引集合的替代方案，因為分隔符號分隔的文字可以在沒有 CONTAINS 模式的負擔下進行索引，也不需要使用 PREFIX 或 SUFFIX 查詢。
cqlsh:demo> ALTER TABLE sasi ADD aliases text;
cqlsh:demo> CREATE CUSTOM INDEX on sasi (aliases) USING 'org.apache.cassandra.index.sasi.SASIIndex'
... WITH OPTIONS = {
... 'analyzer_class': 'org.apache.cassandra.index.sasi.analyzer.DelimiterAnalyzer',
... 'delimiter': ',',
... 'mode': 'prefix',
... 'analyzed': 'true'};
cqlsh:demo> UPDATE sasi SET aliases = 'Mike,Mick,Mikey,Mickey' WHERE id = f5dfcabe-de96-4148-9b80-a1c41ed276b4;
cqlsh:demo> SELECT * FROM sasi WHERE aliases LIKE 'Mikey' ALLOW FILTERING;
id | age | aliases | created_at | first_name | height | last_name
--------------------------------------+-----+------------------------+---------------+------------+--------+-----------
f5dfcabe-de96-4148-9b80-a1c41ed276b4 | 26 | Mike,Mick,Mikey,Mickey | 1442959315021 | Michael | 180 | Kjellman
文字分析（標記化和詞幹提取）
最後，為了展示文字分析，需要在表格上新增一個欄位。其定義、索引和更新列的陳述式如下所示。
cqlsh:demo> ALTER TABLE sasi ADD bio text;
cqlsh:demo> CREATE CUSTOM INDEX ON sasi (bio) USING 'org.apache.cassandra.index.sasi.SASIIndex'
... WITH OPTIONS = {
... 'analyzer_class': 'org.apache.cassandra.index.sasi.analyzer.StandardAnalyzer',
... 'tokenization_enable_stemming': 'true',
... 'analyzed': 'true',
... 'tokenization_normalize_lowercase': 'true',
... 'tokenization_locale': 'en'
... };
cqlsh:demo> UPDATE sasi SET bio = 'Software Engineer, who likes distributed systems, doesnt like to argue.' WHERE id = 5770382a-c56f-4f3f-b755-450e24d55217;
cqlsh:demo> UPDATE sasi SET bio = 'Software Engineer, works on the freight distribution at nights and likes arguing' WHERE id = 556ebd54-cbe5-4b75-9aae-bf2a31a24500;
cqlsh:demo> SELECT * FROM sasi;
id | age | bio | created_at | first_name | height | last_name
--------------------------------------+-----+----------------------------------------------------------------------------------+---------------+------------+--------+---------------
f5dfcabe-de96-4148-9b80-a1c41ed276b4 | 26 | null | 1442959315021 | Michael | 180 | Kjellman
96053844-45c3-4f15-b1b7-b02c441d3ee1 | 36 | null | 1442959315020 | Mikhail | 173 | Stepura
6b757016-631d-4fdb-ac62-40b127ccfbc7 | 40 | null | 1442959315023 | Jason | 182 | Brown
556ebd54-cbe5-4b75-9aae-bf2a31a24500 | 27 | Software Engineer, works on the freight distribution at nights and likes arguing | 1442959315018 | Pavel | 181 | Yaskevich
8f909e8a-008e-49dd-8d43-1b0df348ed44 | 34 | null | 1442959315024 | Vijay | 183 | Parthasarathy
5770382a-c56f-4f3f-b755-450e24d55217 | 26 | Software Engineer, who likes distributed systems, doesnt like to argue. | 1442959315019 | Jordan | 173 | West
2970da43-e070-41a8-8bcb-35df7a0e608a | 32 | null | 1442959315022 | Johnny | 175 | Zhang
(7 rows)
索引詞和查詢搜尋字串會針對 bio 欄位進行詞幹提取，因為它已設定為使用 StandardAnalyzer，而 analyzed 已設定為 true。tokenization_normalize_lowercase 類似於 case_sensitive 屬性，但適用於 StandardAnalyzer。這些查詢展示了 StandardAnalyzer 套用的詞幹提取。
cqlsh:demo> SELECT * FROM sasi WHERE bio LIKE 'distributing'; id | age | bio | created_at | first_name | height | last_name --------------------------------------+-----+----------------------------------------------------------------------------------+---------------+------------+--------+----------- 556ebd54-cbe5-4b75-9aae-bf2a31a24500 | 27 | Software Engineer, works on the freight distribution at nights and likes arguing | 1442959315018 | Pavel | 181 | Yaskevich 5770382a-c56f-4f3f-b755-450e24d55217 | 26 | Software Engineer, who likes distributed systems, doesnt like to argue. | 1442959315019 | Jordan | 173 | West (2 rows) cqlsh:demo> SELECT * FROM sasi WHERE bio LIKE 'they argued'; id | age | bio | created_at | first_name | height | last_name --------------------------------------+-----+----------------------------------------------------------------------------------+---------------+------------+--------+----------- 556ebd54-cbe5-4b75-9aae-bf2a31a24500 | 27 | Software Engineer, works on the freight distribution at nights and likes arguing | 1442959315018 | Pavel | 181 | Yaskevich 5770382a-c56f-4f3f-b755-450e24d55217 | 26 | Software Engineer, who likes distributed systems, doesnt like to argue. | 1442959315019 | Jordan | 173 | West (2 rows) cqlsh:demo> SELECT * FROM sasi WHERE bio LIKE 'working at the company'; id | age | bio | created_at | first_name | height | last_name --------------------------------------+-----+----------------------------------------------------------------------------------+---------------+------------+--------+----------- 556ebd54-cbe5-4b75-9aae-bf2a31a24500 | 27 | Software Engineer, works on the freight distribution at nights and likes arguing | 1442959315018 | Pavel | 181 | Yaskevich (1 rows) cqlsh:demo> SELECT * FROM sasi WHERE bio LIKE 'soft eng'; id | age | bio | created_at | first_name | height | last_name --------------------------------------+-----+----------------------------------------------------------------------------------+---------------+------------+--------+----------- 556ebd54-cbe5-4b75-9aae-bf2a31a24500 | 27 | Software Engineer, works on the freight distribution at nights and likes arguing | 1442959315018 | Pavel | 181 | Yaskevich 5770382a-c56f-4f3f-b755-450e24d55217 | 26 | Software Engineer, who likes distributed systems, doesnt like to argue. | 1442959315019 | Jordan | 173 | West (2 rows)
實作細節
雖然 SASI 在表面上只是 Index 介面的實作，但其核心有幾個資料結構和演算法用於滿足它。這些在這裡說明。此外，說明了 Cassandra 內部支援 SASI 整合的變更。
Index 介面將實作者的責任分為兩部分：索引和查詢。此外，Cassandra 使得可以將這些責任分為記憶體和磁碟元件。SASI 利用 Cassandra 的一次寫入、不可變、已排序資料模型，在將記憶表沖洗到磁碟時建立索引，這就是「SSTable 附加次要索引」名稱的由來。
SASI 索引資料結構在撰寫 SSTable 時在記憶體中建立，並在 SSTable 撰寫完成前沖洗到磁碟。每個索引檔案的撰寫只需要對磁碟進行順序寫入。在某些情況下，會執行部分沖洗，然後再縫合在一起，以減少記憶體使用量。這些資料結構針對此使用案例進行最佳化。
在查詢時間利用 Cassandra 的已排序資料模型，縮小候選索引的搜尋範圍，將所做的工作量減到最低。然後使用一種有效率的方法進行搜尋，根據需要從磁碟串流資料。
索引
每個 SSTable，SASI 會為每個索引欄位寫入一個索引檔案。這些檔案的資料會使用 OnDiskIndexBuilder 在記憶體中建立。寫入磁碟後，資料會使用 OnDiskIndex 類別讀取。這些類別由表示索引詞彙的位元組組成，分別針對有效率的寫入或搜尋進行組織。它們所包含的鍵和值代表 SSTable 中的代碼和位置，而且會儲存在 TokenTreeBuilder（用於寫入）和 TokenTree（用於查詢）中，每個索引詞彙一個。這些索引檔案會在寫入磁碟後進行記憶體對應，以加快存取速度。SASI 會使用 IndexMemtable 類別索引記憶表中的資料。
OnDiskIndex(Builder)
每個 OnDiskIndex 都是修改過 後綴陣列資料結構的實例。 OnDiskIndex 由排序詞彙和指向詞彙相關資料的指標的頁面大小區塊組成，以及資料本身，也儲存在一個或多個頁面大小區塊中。 OnDiskIndex 的結構為陣列樹，其中每個層級描述下一個層級的詞彙，最後一個層級為詞彙本身。PointerLevel 和其 PointerBlock 包含詞彙和指向以這些詞彙結尾的其他區塊的指標。DataLevel（最後一個層級）及其 DataBlock 包含詞彙和指向資料本身的指標，資料本身包含在 TokenTree 中。
寫入 OnDiskIndex 的詞彙會根據其 模式而有所不同：PREFIX、CONTAINS 或 SPARSE。在 PREFIX 和 SPARSE 的情況下，詞彙的精確值會在每個 OnDiskIndex 中寫入一次。例如，當使用包含詞彙 Jason、Jordan、Pavel 的 PREFIX 索引時，這三個詞彙都會包含在索引中。CONTAINS 索引會為每個詞彙的每個後綴遞迴寫入其他詞彙。繼續使用前面的範例，儲存先前詞彙的 CONTAINS 索引也會儲存 ason、ordan、avel、son、rdan、vel 等。這允許針對字串的後綴進行查詢。SPARSE 模式與 PREFIX 的不同之處在於，對於每 64 個詞彙區塊，會建立一個 TokenTree，將每個詞彙的 TokenTree 合併成一個。這份資料拷貝用於有效率地反覆處理大範圍的資料，例如時間戳記。索引 模式 可在建立索引時針對每個欄位進行設定。
TokenTree(Builder)
TokenTree 是廣為人知的 B+-tree 實作，已針對其使用案例進行修改以進行最佳化。特別是，它已針對將令牌（長整數）與 SSTable 中的一組位置（也是長整數）關聯進行最佳化。允許一組長整數值能容納令牌中的雜湊衝突可能性，但資料結構已針對此類衝突不太可能發生的情況進行最佳化。
為了針對其一次寫入環境進行最佳化，TokenTreeBuilder 會在建置樹時完全載入其內部節點，並使用已針對大量載入資料結構進行最佳化的廣為人知的演算法。
TokenTree 提供方法來反覆運算與特定詞彙相符的令牌和檔案位置，並在反覆運算中向前跳過，這是查詢時間大量使用的操作。
IndexMemtable
IndexMemtable 處理索引化記憶體中儲存在記憶表中的資料。IndexMemtable 會依序管理每欄的 TrieMemIndex 或 SkipListMemIndex。所使用的索引類型選擇取決於資料。TrieMemIndex 用於文字類型。AsciiType 和 UTF8Type 預設為文字類型，但任何欄位都可以在建立索引時使用 is_literal 選項設定為文字類型。對於非文字類型，會使用 SkipListMemIndex。TrieMemIndex 是一種實作，可以有效支援針對類似字元的資料進行前置查詢。相反地，SkipListMemIndex 更適合其他 Cassandra 資料類型，例如數字。
TrieMemIndex 建置時會使用 com.goooglecode.concurrenttrees 套件中的 ConcurrentRadixTree 或 ConcurrentSuffixTree。這兩個選項的選擇是根據索引模式，分別是 PREFIX 或其他模式，以及 CONTAINS 模式。
SkipListMemIndex 建置在 java.util.concurrent.ConcurrentSkipListSet 之上。
查詢
負責將內部的 IndexExpression 表示轉換成 SASI 的 Operation 和 Expression 樹狀結構，最佳化樹狀結構以減少執行的工作量，並驅動查詢本身，QueryPlan 是 SASI 查詢實作的執行核心。為了有效執行聯集和交集運算，SASI 提供了幾個類似於 Cassandra 的 MergeIterator 的反覆運算器，但針對 SASI 的使用量身打造，同時包含更多功能。RangeUnionIterator，如同其名稱所示，會對符合查詢的代幣/金鑰集合執行集合聯集，僅從每個集合讀取滿足查詢所需資料。RangeIntersectionIterator 類似於其對應項目，會對其資料執行集合交集。
查詢計畫
每個搜尋查詢實例化的 QueryPlan 是 SASI 查詢實作的核心。其工作可分為兩個階段：分析和執行。
在分析階段，QueryPlan 會從 Cassandra 的 IndexExpression 內部表示轉換，該表示也已修改為支援編碼包含 OR 和使用括號對表示式進行分組的查詢（有關更多詳細資訊，請參閱下方的 Cassandra 內部變更 區段）。此程序會產生 Operation 樹狀結構，而 Operation 樹狀結構又可能包含 Expression，所有這些都提供查詢的替代、更有效率的表示。
執行期間，QueryPlan 使用從 Operation 樹狀結構建立的 DecoratedKey 產生反覆運算。這些金鑰會從磁碟讀取，並使用 Operation 樹狀結構再次進行最終檢查，以確保滿足查詢。在找到所需數量相符資料或沒有更多相符資料時，會透過現有的內部元件將結果組傳回給協調器。
每個表格/資料行家族會維護查詢數目（總計/失敗/逾時）及其延遲時間。
SASI 也支援在 SSTable 中同時反覆運算相同索引的詞彙。並行因素由 cassandra.search_concurrency_factor 系統屬性控制。預設為 1。
QueryController
每個 QueryPlan 都會參考一個 QueryController，用於整個執行階段。 QueryController 有兩個責任：管理並確保適當清除資源（索引），以及嚴格執行使用者透過範圍區段逾時設定的每個查詢時間限制。所有索引都是透過 QueryController 存取，以便稍後可以安全地釋放。 QueryController 的 checkpoint 函式會在執行路徑的特定位置呼叫，以確保執行時間限制。
QueryPlan 最佳化
在分析階段，QueryPlan 會對查詢執行多項潛在最佳化。這些最佳化的目標是減少執行階段執行的作業量。
執行的最簡單最佳化是將多個透過邏輯交集（AND）連接的表達式壓縮成單一 Operation，其中包含三個或更多 Expression。例如，查詢 WHERE age < 100 AND fname = 'p*' AND first_name != 'pa*' AND age > 21 在未修改的情況下，會有以下樹狀結構
┌───────┐
┌────────│ AND │──────┐
│ └───────┘ │
▼ ▼
┌───────┐ ┌──────────┐
┌─────│ AND │─────┐ │age < 100 │
│ └───────┘ │ └──────────┘
▼ ▼
┌──────────┐ ┌───────┐
│ fname=p* │ ┌─│ AND │───┐
└──────────┘ │ └───────┘ │
▼ ▼
┌──────────┐ ┌──────────┐
│fname!=pa*│ │ age > 21 │
└──────────┘ └──────────┘
QueryPlan 會移除多餘的右分支，其根節點為最後一個 AND，葉節點為 fname != pa* 和 age > 21。這些 Expression 會壓縮到父層 AND 中，由於 AND 具有結合性和交換性，因此這項操作是安全的。產生的樹狀結構如下所示
┌───────┐
┌────────│ AND │──────┐
│ └───────┘ │
▼ ▼
┌───────┐ ┌──────────┐
┌───────────│ AND │────────┐ │age < 100 │
│ └───────┘ │ └──────────┘
▼ │ ▼
┌──────────┐ │ ┌──────────┐
│ fname=p* │ ▼ │ age > 21 │
└──────────┘ ┌──────────┐ └──────────┘
│fname!=pa*│
└──────────┘
在使用 != 排除結果集中的結果時，QueryPlan 會決定最佳的處理方法。例如，對於範圍查詢，最佳化的方法可能是將範圍分成多個部分，並在排除部分留一個洞。然而，對於像這樣字串查詢，在掃描索引時，最佳化的方法是簡單地記錄要略過或排除的資料。在這個最佳化之後，樹狀結構如下
┌───────┐
┌────────│ AND │──────┐
│ └───────┘ │
▼ ▼
┌───────┐ ┌──────────┐
┌───────│ AND │────────┐ │age < 100 │
│ └───────┘ │ └──────────┘
▼ ▼
┌──────────────────┐ ┌──────────┐
│ fname=p* │ │ age > 21 │
│ exclusions=[pa*] │ └──────────┘
└──────────────────┘
針對此查詢套用的最後一種類型最佳化，當然是在不修改查詢意義的情況下，合併樹狀結構各個分支的範圍表達式。在這個案例中，由於查詢包含所有 AND，因此可以壓縮 age 表達式。隨著這個最佳化，也可以再次套用最初壓縮不必要的 AND，以產生這個最終樹狀結構，用來執行查詢
┌───────┐
┌──────│ AND │───────┐
│ └───────┘ │
▼ ▼
┌──────────────────┐ ┌────────────────┐
│ fname=p* │ │ 21 < age < 100 │
│ exclusions=[pa*] │ └────────────────┘
└──────────────────┘
運算式和表達式
正如討論的，QueryPlan 會最佳化一個樹狀結構，其內部節點由 Operation 表示，而葉節點由 Expression 表示。更具體地說，Operation 類別可以有 0 個、1 個或 2 個 Operation 作為子節點，以及無限個表達式。用來執行查詢的迭代器（在 `Range(Union|Intersection)Iterator'' 區段中討論）會實作必要的邏輯，以透明地合併結果，而不管 `Operation 的子節點為何。
Range(Union|Intersection)Iterator
抽象的 RangeIterator 類別在執行路徑中的各種層級中提供一個統一的介面，以執行 SASI 執行的兩個主要操作：集合交集和聯集。這些操作會以反覆運算或「串流」的方式執行，以避免不必要的元素讀取。在交集和聯集的情況中，演算法會利用預先使用相同排序順序（例如詞彙或標記順序）排序的資料。
RangeUnionIterator 執行 排序合併聯結 演算法的「合併聯結」部分，並具有外聯結或聯集的特性。它實作了多項最佳化，以提升其在大量反覆運算器（要聯集的集合）上的效能。特別是，反覆運算器會利用資料很可能具有許多重疊範圍的子群組，以及所有範圍不太可能彼此重疊的情況。如需更多詳細資訊，請參閱 javadoc。
RangeIntersectionIterator 本身不是 RangeIterator 的子類別。它是多個類別的容器，其中之一為 AbstractIntersectionIterator，是 RangeIterator 的子類別。SASI 支援兩種執行交集操作的方法，以及根據資料的某些屬性在兩者之間進行適應性選擇的能力。
BounceIntersectionIterator 和 BOUNCE 策略的運作方式類似於 RangeUnionIterator，因為它會執行「合併聯結」，但其性質類似於內聯結，其中相同的值會由資料特定的合併函數合併（例如，將兩個標記合併到清單中，以便稍後在 SSTable 中查詢）。如需更多關於其實作的詳細資訊，請參閱 javadoc。
LookupIntersectionIterator 和 LOOKUP 策略執行不同的操作，更類似於在關聯資料結構中查詢，或在資料庫術語中稱為「雜湊查詢」。同樣地，可以在 javadoc 中找到關於實作的詳細資訊。
在兩個反覆運算器之間的選擇，或 ADAPTIVE 策略，是基於最小範圍和最大範圍的交集資料集大小的比率。如果最小範圍中的元素數量除以元素數量是最大範圍小於或等於 0.01，則 ADAPTIVE 策略會選擇 LookupIntersectionIterator，否則會選擇 BounceIntersectionIterator。
SASIIndex 類別
上述元件是由 SASIIndex 類別黏合在一起，該類別實作 Index，並為包含 SASI 索引的每個表格實例化。它透過 sasi.conf.DataTracker 和 sasi.conf.view.View 元件管理表格的所有索引，透過其 PerSSTableIndexWriter 控制 SSTable 的所有索引寫入，並使用 Searcher 初始化搜尋。這些類別將先前提到的索引元件與 Cassandra 的 SSTable 生命週期黏合在一起，確保索引不僅在 Memtable 的快取時寫入，而且在 SSTable 壓縮時也會寫入。對於查詢，Searcher 幾乎沒有作用，但會轉交給 QueryPlan 並更新 SASI 顯示的例如延遲指標。
