SASI インデックス
SASIIndex（略してSASI）は、Cassandra のIndexインターフェースの実装であり、既存の実装の代替として使用できます。SASI のインデックス作成とクエリは、Cassandra のニーズに合わせて調整することで、既存の実装を改善します。SASI は、以前はフィルタリングが必要だったクエリの場合に優れたパフォーマンスを発揮します。このパフォーマンスを実現するために、SASI はメモリ、ディスク、CPU 使用量において、既存の実装よりもリソース消費量が大幅に少ないことを目指しています。さらに、SASI は文字列に対するプレフィックスと包含クエリをサポートしています（SQL のLIKE = "foo*"またはLIKE = "**foo**"'と同様）。
以下では、SASI の起動と実行方法、使用例、実装の詳細について説明します。
SASI の使用
以下の例では、テーブルとそのカラムにインデックスを作成し、挿入されたデータに対してクエリを実行する方法を説明します。
以下の例では、`demo`キースペースが作成済みで、使用中であると想定しています。
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`のモードがあり、デフォルトは`PREFIX`です。 `last_name`インデックスは、プレフィックスだけでなくサフィックスにも一致する`CONTAINS`モードで作成されます。この例は以下に示されており、詳細はOnDiskIndexのセクションにあります。`created_at`カラムは、ミリ秒ごとに挿入されるデータのタイムスタンプなど、大規模で密な数値範囲のクエリのパフォーマンスを向上させることを目的とした`SPARSE`モードに設定されて作成されます。 `SPARSE`実装の詳細は、OnDiskIndexのセクションにもあります。 `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 は、PREFIX、CONTAINS、SUFFIX 検索の LIKE ステートメントを含む、CQL ですでにサポートされているすべてのクエリをサポートしています。
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`カラムではクエリの case は問題になりません。
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)
`StandardAnalyzer`を使用するように設定され、`analyzed`が`true`に設定されているため、インデックスタ項とクエリ検索文字列は`bio`カラムに対してステミングされます。 `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`インターフェースの実装ですが、そのコアには、それを満たすために使用されるいくつかのデータ構造とアルゴリズムがあります。これらについてここで説明します。さらに、SASI の統合をサポートするための Cassandra 内部での変更点について説明します。
`Index`インターフェースは、実装者の責任をインデックス作成とクエリの 2 つの部分に分割します。さらに、Cassandra では、これらの責任をメモリとディスクのコンポーネントに分割することができます。SASI は、Cassandra の書き込み一回、不変、順序付けられたデータモデルを利用して、memtable のディスクへのフラッシュと共にインデックスを構築します。これが「SSTable Attached Secondary Index」という名前の由来です。
SASI インデックスデータ構造は、SSTable の書き込み中にメモリ内に構築され、SSTable の書き込みが完了する前にディスクにフラッシュされます。各インデックスファイルの書き込みには、ディスクへのシーケンシャル書き込みのみが必要です。場合によっては、メモリ使用量を削減するために、部分的なフラッシュが実行され、後でつなぎ合わされます。これらのデータ構造はこのユースケースに最適化されています。
Cassandra の順序付けられたデータモデルを利用することで、クエリ時に候補インデックスが検索対象として絞り込まれ、作業量が最小限に抑えられます。その後、必要に応じてディスクからデータをストリーミングする効率的な方法を使用して検索が実行されます。
インデックス作成
SSTable ごとに、SASI はインデックス付きの各カラムのインデックスファイルを書き込みます。これらのファイルのデータは、`OnDiskIndexBuilder`を使用してメモリ内に構築されます。ディスクにフラッシュされると、データは`OnDiskIndex`クラスを使用して読み取られます。これらは、インデックス付きの用語を表すバイトで構成され、それぞれ効率的な書き込みまたは検索のために編成されています。保持するキーと値は、SSTable 内のトークンと位置を表し、これらはインデックス付きの用語ごとに書き込み用の`TokenTreeBuilder`とクエリ用の`TokenTree`に格納されます。これらのインデックスファイルは、ディスクに書き込まれた後、より迅速にアクセスするためにメモリマップされます。memtable 内のデータをインデックス化するために、SASI は`IndexMemtable`クラスを使用します。
OnDiskIndex(Builder)
各`OnDiskIndex`は、変更された接尾辞配列データ構造のインスタンスです。 `OnDiskIndex`は、ソートされた用語のページサイズブロックと、用語に関連付けられたデータへのポインタ、およびデータ自体で構成され、1 つ以上のページサイズブロックにも格納されます。 `OnDiskIndex`は配列のツリーとして構成され、各レベルは下のレベルの用語を記述し、最終レベルは用語自体です。 `PointerLevel`とその`PointerBlock`には、用語と、それらの用語で*終わる*他のブロックへのポインタが含まれています。最終レベルである`DataLevel`とその`DataBlock`には、用語が含まれており、`TokenTree`に含まれるデータ自体を指しています。
OnDiskIndexに書き込まれるタームは、その`mode`によって異なります。`mode`は`PREFIX`、`CONTAINS`、または`SPARSE`のいずれかです。`PREFIX`と`SPARSE`の場合、タームの正確な値は`OnDiskIndex`ごとに1回だけ書き込まれます。たとえば、`PREFIX`インデックスで`Jason`、`Jordan`、`Pavel`というタームを使用する場合、これら3つすべてがインデックスに含まれます。`CONTAINS`インデックスは、各タームの各接尾辞に対して、再帰的に追加のタームを書き込みます。この例を続けると、上記のタームを格納する`CONTAINS`インデックスは、`ason`、`ordan`、`avel`、`son`、`rdan`、`vel`なども格納します。これにより、文字列の接尾辞に対するクエリが可能になります。`SPARSE`モードは、64ブロックのタームごとにTokenTreeが構築され、各タームのすべてのTokenTreeを1つにマージするという点で`PREFIX`と異なります。このデータのコピーは、タイムスタンプなどの大きな範囲を効率的に反復処理するために使用されます。インデックスの`mode`は、インデックス作成時に列ごとに設定可能です。
TokenTree(Builder)
TokenTreeは、よく知られているB+木の実装であり、ユースケースに合わせて最適化されています。特に、トークン（long値）をSSTable内の位置のセット（これもlong値）に関連付けるように最適化されています。long値のセットを使用することで、トークンのハッシュ衝突の可能性に対応できますが、データ構造は、このような衝突が発生する可能性が低い場合に最適化されています。
書き込み一回の環境に最適化するために、TokenTreeBuilderは、ツリーの構築中に内部ノードを完全にロードし、データ構造を一括ロードするために最適化されたよく知られたアルゴリズムを使用します。
TokenTreeは、特定のタームに一致するトークンとファイル位置を反復処理し、その反復処理をスキップする手段を提供します。これは、クエリ時に頻繁に使用される操作です。
IndexMemtable
IndexMemtableは、memtableに保持されているメモリ内データのインデックス作成を処理します。IndexMemtableは、列ごとにTrieMemIndexまたはSkipListMemIndexを管理します。どちらのインデックスタイプが使用されるかは、データに依存します。TrieMemIndexはリテラル型に使用されます。`AsciiType`と`UTF8Type`はデフォルトでリテラル型ですが、インデックス作成時に`is_literal`オプションを使用して任意の列をリテラル型として設定できます。リテラル型以外の場合、SkipListMemIndexが使用されます。TrieMemIndexは、文字のようなデータに対するプレフィックスクエリを効率的にサポートできる実装です。逆に、`SkipListMemIndex`は、数値などの他のCassandraデータ型に適しています。
TrieMemIndexは、`com.goooglecode.concurrenttrees`パッケージの`ConcurrentRadixTree`または`ConcurrentSuffixTree`を使用して構築されます。2つのどちらを選択するかは、インデックスモード（`PREFIX`またはその他のモード）と`CONTAINS`モードに基づいて決定されます。
SkipListMemIndexは、`java.util.concurrent.ConcurrentSkipListSet`の上に構築されます。
クエリ
内部の`IndexExpression`表現をSASIの`Operation`および`Expression`ツリーに変換し、ツリーを最適化して作業量を削減し、クエリ自体を実行する`QueryPlan`は、SASIのクエリ実装の中核を担います。和集合と積集合の操作を効率的に実行するために、SASIはCassandraの`MergeIterator`に似たイテレータをいくつか提供していますが、SASIの用途に合わせて調整され、より多くの機能が含まれています。`RangeUnionIterator`は、その名前が示すように、クエリに一致するトークン/キーのセットに対して集合和を実行し、クエリを満たすために必要なデータだけを各セットから読み取ります。`RangeIntersectionIterator`も同様に、データに対して集合積集合を実行します。
QueryPlan
検索クエリごとにインスタンス化される`QueryPlan`は、SASIのクエリ実装の中核です。その作業は、分析と実行の2つの段階に分けることができます。
分析フェーズでは、`QueryPlan`は、`IndexExpression`のCassandra内部表現から変換します。これは、ORや括弧を使用した式のグループ化を含むクエリのエンコードもサポートするように変更されています（詳細については、以下のCassandraの内部変更セクションを参照してください）。このプロセスは、`Operation`のツリーを生成します。これには、`Expression`が含まれている場合があり、これらはすべて、より効率的なクエリの代替表現を提供します。
実行中、`QueryPlan`は、`Operation`ツリーから作成された`DecoratedKey`生成イテレータを使用します。これらのキーはディスクから読み取られ、`Operation`ツリーを使用して、クエリを満たしていることを確認するための最終チェックが再度実行されます。目的の量のマッチングデータが見つかった時点、または、それ以上マッチングデータがない時点で、結果セットは既存の内部コンポーネントを介してコーディネーターに返されます。
クエリの数（合計/失敗/タイムアウト）とそのレイテンシは、テーブル/カラムファミリごとに保持されます。
SASIは、SSTableをまたがって同じインデックスのタームを同時に反復処理することもサポートしています。並行性係数は、`cassandra.search_concurrency_factor`システムプロパティによって制御されます。デフォルトは`1`です。
QueryController
各`QueryPlan`は、実行フェーズ全体で使用される`QueryController`を参照します。`QueryController`には、リソース（インデックス）の適切なクリーンアップを管理および確実にすることと、ユーザーがレンジスライスタイムアウトを介して指定したクエリごとの時間制限を厳密に実施するという2つの役割があります。すべてのインデックスには`QueryController`を介してアクセスするため、後で安全に解放できます。`QueryController`の`checkpoint`関数は、実行パスの特定の場所で呼び出され、時間制限が確実に実施されます。
QueryPlanの最適化
分析フェーズでは、`QueryPlan`はクエリに対していくつかの潜在的な最適化を実行します。これらの最適化の目標は、実行フェーズで実行される作業量を削減することです。
実行される最も単純な最適化は、論理積（`AND`）で結合された複数の式を、3つ以上の`Expression`を持つ単一の`Operation`に圧縮することです。たとえば、`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`の子に関係なく、結果を透過的にマージするために必要なロジックを実装します。
`QueryPlan`によって実行される最適化に参加することに加えて、`Operation`は、クエリによって返された行を取得し、実際に一致するかどうかを最終的に検証する役割も担います。この`satisfiesBy`操作は、特定のクエリの`Operation`ツリーのルートから再帰的に実行されます。これらのチェックは、特定の行のデータに対して直接実行されます。 `satisfiesBy`の仕組みの詳細については、コード内のドキュメントを参照してください。
Range(Union|Intersection)Iterator
抽象クラス`RangeIterator`は、SASIが実行パスのさまざまな層で実行する2つの主要な操作、つまり集合の積集合と和集合に対する統一されたインターフェースを提供します。これらの操作は、いずれかの集合から要素を不必要に読み取ることを防ぐために、反復または「ストリーミング」方式で実行されます。積集合と和集合の両方の場合において、アルゴリズムは、用語またはトークンの順序など、同じソート順を使用してデータが事前にソートされていることを利用します。
`RangeUnionIterator`は、ソートマージ結合アルゴリズムの「マージ結合」部分を、外部結合または和集合のプロパティと共に実行します。これは、多数のイテレータ（和集合する集合）のパフォーマンスを向上させるためのいくつかの最適化を使用して実装されています。具体的には、イテレータは、データに重複する範囲の多くのサブグループがある可能性が高い場合と、すべての範囲が互いに重複する可能性が低い場合を利用します。詳細については、javadocを参照してください。
`RangeIntersectionIterator`自体は`RangeIterator`のサブクラスではありません。これは、`RangeIterator`をサブクラス化する`AbstractIntersectionIterator`を含むいくつかのクラスのコンテナです。SASIは、積集合操作を実行する2つの方法と、データのいくつかのプロパティに基づいてそれらの間で適応的に選択する機能をサポートしています。
`BounceIntersectionIterator`と`BOUNCE`戦略は、`RangeUnionIterator`と同様に「マージ結合」を実行しますが、その性質は内部結合に似ており、同じ値はデータ固有のマージ関数（例：後でSSTableで検索するためにリスト内の2つのトークンをマージする）によってマージされます。実装の詳細については、javadocを参照してください。
`LookupIntersectionIterator`と`LOOKUP`戦略は、連想データ構造の検索、またはデータベース用語で「ハッシュルックアップ」に類似した異なる操作を実行します。実装の詳細については、javadocを参照してください。
2つのイテレータ、つまり`ADAPTIVE`戦略の選択は、積集合される集合の最小範囲と最大範囲のデータセットサイズの比率に基づいています。最小範囲の要素数を最大範囲の要素数で割った数が`0.01`以下の場合、`ADAPTIVE`戦略は`LookupIntersectionIterator`を選択し、そうでない場合は`BounceIntersectionIterator`が選択されます。
SASIIndexクラス
上記のコンポーネントは、`Index`を実装し、SASIインデックスを含むテーブルごとにインスタンス化される`SASIIndex`クラスによってまとめられています。これは、`sasi.conf.DataTracker`と`sasi.conf.view.View`コンポーネントを介してテーブルのすべてのインデックスを管理し、`PerSSTableIndexWriter`を介してSSTableのすべてのインデックスの書き込みを制御し、`Searcher`で検索を開始します。これらのクラスは、前述のインデックスコンポーネントをCassandraのSSTableライフサイクルと結び付け、Memtableのフラッシュ時にだけでなく、SSTableのコンパクション時にもインデックスが書き込まれるようにします。クエリの場合、`Searcher`は`QueryPlan`に委任し、SASIによって公開されるレイテンシメトリックなどを更新するだけです。
