无标题 | Apache Cassandra 文档中文

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 创建，这旨在提高对大型、密集数字范围（如每毫秒插入的数据的时间戳）的查询性能。有关 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 支持 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 的写入一次、不可变、有序数据模型，在将 memtable 刷新到磁盘的同时构建索引，这就是 “SSTable 附加辅助索引” 这个名称的由来。

SASI 索引数据结构在 SSTable 正在写入时在内存中构建，并在 SSTable 写入完成之前刷新到磁盘。每个索引文件的写入只需要对磁盘进行顺序写入。在某些情况下，会执行部分刷新，并在以后将其缝合在一起，以减少内存使用量。这些数据结构针对此用例进行了优化。

利用 Cassandra 的有序数据模型，在查询时，会缩小候选索引的范围以进行搜索，从而最大限度地减少执行的工作量。然后，使用一种高效的方法执行搜索，该方法根据需要从磁盘流式传输数据。

索引

对于每个 SSTable，SASI 都会为每个索引列写入一个索引文件。这些文件的数据使用 OnDiskIndexBuilder 在内存中构建。一旦刷新到磁盘，数据就会使用 OnDiskIndex 类读取。这些由表示索引项的字节组成，这些字节按高效写入或搜索的方式组织。它们保存的键和值分别表示 SSTable 中的令牌和位置，这些键和值按每个索引项存储在 TokenTreeBuilder 中（用于写入）和 TokenTree 中（用于查询）。这些索引文件在写入磁盘后被内存映射，以便更快地访问。对于索引 memtable 中的数据，SASI 使用其 IndexMemtable 类。

OnDiskIndex(Builder)

每个 OnDiskIndex 都是修改后的后缀数组数据结构的实例。 OnDiskIndex 由页面大小的排序项块和指向这些项关联数据的指针组成，以及数据本身，也存储在一个或多个页面大小的块中。 OnDiskIndex 结构为数组树，其中每一层描述下一层的项，最后一层是项本身。 PointerLevel 及其 PointerBlock 包含项和指向以这些项结尾的其他块的指针。 DataLevel 是最后一层，其 DataBlock 包含项并指向数据本身，包含在 TokenTree 中。

写入 OnDiskIndex 的项根据其 mode 不同而不同：PREFIX、CONTAINS 或 SPARSE。在 PREFIX 和 SPARSE 情况下，每个 OnDiskIndex 中只写入一次项的精确值。例如，当使用 PREFIX 索引和项 Jason、Jordan、Pavel 时，所有三个项都将包含在索引中。 CONTAINS 索引会为每个项的每个后缀递归地写入附加项。继续上面的例子，存储先前项的 CONTAINS 索引还将存储 ason、ordan、avel、son、rdan、vel 等。这允许对字符串的后缀进行查询。 SPARSE 模式与 PREFIX 不同，对于每 64 个项块，都会构建一个 TokenTree，将每个项的 TokenTree 合并到一个中。此数据副本用于有效地迭代大量范围，例如时间戳。索引 mode 在索引创建时可针对每列进行配置。

TokenTree(Builder)

TokenTree 是众所周知的 B+ 树的实现，已针对其用例进行了修改。特别是，它针对将令牌（长整型）与 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

每个搜索查询实例化的 QueryPlan 是 SASI 查询实现的核心。它的工作可以分为两个阶段：分析和执行。

在分析阶段，QueryPlan 从 Cassandra 的 IndexExpression 内部表示进行转换，该表示也已修改为支持对包含 OR 和使用括号对表达式进行分组的查询进行编码（有关更多详细信息，请参阅下面的 Cassandra 内部更改部分）。此过程会生成一个 Operation 树，该树又可能包含 Expression，所有这些都提供了查询的另一种更有效的方式。

在执行阶段，QueryPlan 使用从 Operation 树创建的 DecoratedKey 生成迭代器。这些键从磁盘读取，并使用 Operation 树再次进行最终检查以确保它们满足查询。在找到所需数量的匹配数据或没有更多匹配数据时，结果集将通过现有的内部组件返回给协调器。

每个表/列族都会维护查询数量（总计/失败/超时）及其延迟。

SASI 还支持跨 SSTable 并发迭代同一索引的项。并发因子由 cassandra.search_concurrency_factor 系统属性控制。默认值为 1。

QueryController

每个 QueryPlan 都引用一个 QueryController，该控制器在整个执行阶段使用。 QueryController 有两个职责：管理和确保资源（索引）的正确清理，以及严格执行每个查询的时间限制，该时间限制由用户通过范围切片超时指定。所有索引都是通过 QueryController 访问的，以便它们以后可以由它安全地释放。 QueryController 的 checkpoint 函数在执行路径的特定位置调用，以确保执行时间限制。

QueryPlan 优化

在分析阶段，QueryPlan 对查询执行了一些可能的优化。这些优化的目标是减少执行阶段执行的工作量。

执行的最简单的优化是将多个通过逻辑交集（AND）连接的表达式压缩成一个具有三个或更多 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 类可以有零个、一个或两个 Operation 作为子节点，以及无限数量的表达式。用于执行查询的迭代器（在下面的 `Range(Union|Intersection)Iterator'' 部分中讨论）实现了必要的逻辑，以透明地合并结果，而不管 `Operation 的子节点是什么。

除了参与 QueryPlan 执行的优化之外，Operation 还负责获取由查询返回的行，并执行最终验证以确保它确实匹配。此 satisfiesBy 操作从给定查询的 Operation 树的根节点递归执行。这些检查直接在给定行中的数据上执行。有关 satisfiesBy 工作原理的更多详细信息，请参阅代码中的文档。

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 公开的延迟指标。

Cassandra 内部更改

为了支持上述更改并将它们集成到 Cassandra 中，对 Cassandra 本身进行了一些小的内部更改。这些更改将在下面描述。

SSTable 写入生命周期通知

SSTableFlushObserver 是一个类似于观察者模式的接口，其子类可以注册以接收有关写入 SSTable 生命周期的事件的通知。子类可以在刷新开始和结束时收到通知，以及在即将写入下一行和下一列时收到通知。上面讨论的 SASI 的 PerSSTableIndexWriter 是当前唯一的子类。

限制和注意事项

以下是可以将来更新中解决但在此存储库中不可用或当前未实现的项目。

集群必须配置为使用生成 LongToken` 的分区器，例如 `Murmur3Partitioner`。其他现有的不生成 LongToken 的分区器，例如 `ByteOrderedPartitioner` 和 `RandomPartitioner`，将无法与 SASI 一起使用。



在此版本中，不等和 OR 支持已被删除，同时对 Cassandra 本身进行了更改以支持它们。



贡献者



Pavel Yaskevich


Jordan West


Michael Kjellman


Jason Brown


Mikhail Stepura