倒排索引

概述

倒排索引原理介绍

  1. 基本概念 倒排索引由两部分组成：

    • 词典（Dictionary）：存储所有文档集合中出现过的唯一单词（或短语）的列表。
    • 倒排表（Posting List）：对于词典中的每个单词，都有一个与之对应的倒排列表，记录了包含这个单词的所有文档的文档ID以及单词在文档中出现的位置信息。

  2. 构建过程

    • 分词（Tokenization）：将文档内容分割成单词或短语的过程。
    • 标准化（Normalization）：对分词结果进行处理，如转小写、去除停用词、词干提取等。
    • 构建词典：将处理后的单词加入词典，并为每个单词分配一个唯一的ID。
    • 构建倒排列表：对于每个文档，记录下文档中所有单词的ID和位置信息，并将这些信息与词典中的单词ID关联起来,形成倒排列表。

  3. 查询过程 当用户提交一个查询请求时，搜索引擎会执行以下步骤：

    • 查询解析：将用户的查询语句分解成单词或短语。
    • 查找词典：在词典中查找这些单词或短语的ID。
    • 检索倒排列表：根据单词ID，从倒排列表中检索包含这些单词的所有文档ID。
    • 合并结果：根据查询语句中的逻辑（如AND、OR、NOT等），合并不同单词的检索结果，确定最终的文档列表。

  4. 应用场景 倒排索引主要用于全文搜索领域，如搜索引擎、文档检索系统等，它能够快速响应用户的查询请求，提供高效的检索服务。

功能介绍

利用倒排索引可以根据关键词快速定位包含它的行，达到查询加速的目的。同时如上面原理介绍，词典和倒排表会产生额外的 Lakehouse 的存储。

  1. 全文检索能力 支持了字符串类型的全文检索，支持了match_all、match_any、match_phrase、match_phrase_prefix、match_regexp函数。Lakehouse在部分场景下like也会使用倒排索引，但是仍然推荐您使用全文检索函数。

  2. 查询加速

    • 支持字符串、数值类型的 =, !=, >, >=, <, <= 快速过滤 (仅支持keyword分词的字符串类型)
    • 支持数组类型的array_contains和arrays_overlap 快速过滤

  3. 支持完善的逻辑组合

    • 支持AND、OR、NOT下推

  4. 灵活、快速的索引管理

    • 创建倒排索引：支持在创建表时定义倒排索引，支持在已有的表上增加倒排索引。如果是在已有表创建的索引，对存量数据也需要添加倒排索引，可以执行构建索引命令。
    • 构建倒排索引：对存量数据也需要添加倒排索引，构建索引会启动一个SQL任务，需要消耗计算资源。
    • 列出所有倒排索引：查看一张表上的所有倒排索引。
    • 查看倒排索引详情：查看索引的详情包括大小等。
    • 删除倒排索引：执行drop index会立即成功，会删除掉index的元数据信息。但是不会立即删除索引存储信息。

支持的数据类型和分词器

倒排索引目前支持的数据类型：

  • 数值类型 (TINYINT、SMALLINT、INT)
  • 日期类型（DATE、TIMESTAMP）
  • 数组类型 (ARRAY)
  • 字符串类型 (STRING、VARCHAR、CHAR) 当倒排索引字段为字符串类型时，您需要指定分词器(analyzer)。目前支持的分词类型为:
    • keyword: 此类型的字段不会进行分词。整个字符串被视为单一的词根，并存储在倒排索引中。搜索时，需要提供完整的字段值以实现精确匹配。
    • english: 专为英文设计的分词器，仅识别连续的ASCII字母和数字，并将文本统一转换为小写。适合处理英文内容，忽略非字母数字字符。
    • chinese: 中文文本分词插件，识别中文和英文字符，同时过滤掉标点符号，并将英文字母转换为小写。适用于中英文混合文本的处理。中文分词器还支持分词模式设置mode：max_word 会切出尽可能多的分词，同一个单词可能会出现多次；smart表示智能分词，一般一个单词仅出现一次，默认为smart模式。
    • unicode: 基于Unicode文本分割算法的分词器，能够识别多种语言的文本边界，有效将文本分割成单词，并将字母转换为小写。适合多语言环境下的文本处理。

使用tokenize(input[, option])函数来测试分词。使用tokenize测试分词样例如下：

--使用keyword分词
SELECT TOKENIZE('Lakehouse的倒排索引', map('analyzer', 'keyword')) as token;
+--------------------+
|        token       |
+--------------------+
| ["Lakehouse的倒排索引"] |
+--------------------+
--使用english分词
SELECT TOKENIZE('Lakehouse的倒排索引', map('analyzer', 'english')) as token;
+---------------+
|        token  |
+---------------|
| ["lakehouse"] |
+---------------+
--使用chinese分词
SELECT TOKENIZE('Lakehouse的倒排索引', map('analyzer', 'chinese')) as token;
+--------------------+
|        token       |
+--------------------+
| ["lakehouse","的","倒排","索引"] |
+--------------------+
--使用unicode分词
SELECT TOKENIZE('Lakehouse的倒排索引', map('analyzer', 'unicode')) as token;
+---------------+
|        token  |
+---------------|
| ["lakehouse","的","倒","排","索引"] |
+---------------+
--使用chinese smart模式
SELECT TOKENIZE('北京市人民广场', map('analyzer', 'chinese')) as token;
+---------------------+
|        token        |
+---------------------+
| ["北京市","人民广场"] |
+---------------------+
--使用chinese max_word模式分词
SELECT TOKENIZE('北京市人民广场', map('analyzer', 'chinese', 'mode', 'max_word')) as token;
+---------------------+
|        token        |
+---------------------+
| ["北京","北京市","京市","人民","人民广场","广场"] |
+---------------------+
--使用unicode分词
SELECT TOKENIZE('東京タワーは美しいですね。',map('analyzer', 'unicode')) as token;
+--------------------------------+
|              token             |
+--------------------------------+
| ["東京タワー","は","美しい","です","ね"] |
+--------------------------------+
--使用english分词
SELECT TOKENIZE('市长热线12345，电子信箱 Mail@abc.com，网址 http://1.2.3.4', map('analyzer', 'english')) as token;
+----------------------------------+
|               token              |
+----------------------------------+
| ["12345","mail","abc","com","http","1","2","3","4"] |
+----------------------------------+

创建倒排索引

建表时定义索引

语法

CREATE TABLE table_name(
  columns_definition,
  INDEX index_name (column_name) INVERTED [COMMENT 'comment'] [PROPERTIES(...)]
);

columns_definition：定义表的字段信息，最后一个字段定义后必须使用逗号

INDEX：关键字

index_name：自定义index的名称

column_name：需要添加索引的字段名称

INVERTED：关键字，表示倒排索引

COMMENT：指定index的说明信息

PROPERTIES：指定INDEX的参数，支持的属性包括指定分词器(analyzer)。数值和日期类型不需要指定properties，如果是字符串类型则必须指定分词器(analyzer)

案例

CREATE TABLE inverted_index_test(
  id int,
  name string,
  INDEX id_index (id) INVERTED,
  INDEX name_index (name) INVERTED PROPERTIES('analyzer'='keyword')
);

已有表上创建倒排索引

语法

CREATE INVERTED INDEX [IF NOT EXISTS] index_name ON TABLE 
[schema].table_name(col_name)
[COMMENT 'comment']
[PROPERTIES('analyzer'='analyzer_name', 'mode'='smart|max_word')]

INVERTED: 索引类型，倒排索引

index_name: 索引名称，位于schema下，schema下索引名称不能重复

col_name：列名只支持单列

PROPERTIES：指定INDEX的参数 对于数值类型日期类型和数组类型，不需要单独设置。 对于字符串类型，参数列表如下

  1. 指定分词器(analyzer): 必选参数，可选值为
  • keyword: 此类型的字段不会进行分词。整个字符串被视为单一的词根，并存储在倒排索引中。搜索时，需要提供完整的字段值以实现精确匹配。
  • english: 专为英文设计的分词器，仅识别连续的ASCII字母和数字，并将文本统一转换为小写。适合处理英文内容，忽略非字母数字字符。
  • chinese: 中文文本分词插件，识别中文和英文字符，同时过滤掉标点符号，并将英文字母转换为小写。适用于中英文混合文本的处理。中文分词器还支持分词模式设置mode：max_word 会切出尽可能多的分词，同一个单词可能会出现多次；smart表示智能分词，一般一个单词仅出现一次，默认为smart模式。
  • unicode: 基于Unicode文本分割算法的分词器，能够识别多种语言的文本边界，有效将文本分割成单词，并将字母转换为小写。适合多语言环境下的文本处理。
  1. 指定是否支持短语模式（support_phrase): 默认为false，当设置为true的时候，存储每个token在在文本的位置，可以进一步加速match_phrase等需要判断token是否连续的函数的查询速度

说明

执行CREATE INDEX仅对新增数据有效，对已有数据进行索引请使用BUILD INDEX命令。

案例

CREATE TABLE inverted_index_test(
  id int,
  name string
);

CREATE INVERTED INDEX id_index ON TABLE 
public.inverted_index_test(name)
PROPERTIES('analyzer'='unicode')

管理倒排索引

构建索引

对存量数据添加倒排索引。

语法

-- 语法 1，默认给全表的存量数据加上倒排索引
BUILD INDEX index_name ON [schema].table_name;
-- 语法 2，可指定partition，可指定一个或多个,支持=, !=, >, >=, <, <=
BUILD INDEX index_name ON table_name WHERE partition_name1 = '1' and partition_name2 = '2';
  • index_name：指定要添加倒排索引名称
  • 支持指定分区构建：可以指定一个或者多个

说明

执行BUILD INDEX是一个同步任务，执行过程会消耗计算资源。查看进度可以通过Job Profile查看。

当分区表数据量较大时，建议以分区为粒度依次创建索引。

案例

BUILD INDEX bulkload_data_index ON public.bulkload_data ;

列出表上所有的倒排索引

命令用于列出指定表中已创建的倒排索引。

语法

SHOW INDEX FROM [schema].table_name;

案例

 show index from public.bulkload_data;
+---------------------+------------+
|     index_name      | index_type |
+---------------------+------------+
| bulkload_data_index | inverted   |
+---------------------+------------+

查看倒排索引详情

本命令用于列出指定表中已创建的倒排索引的详情，添加上extended关键字可以查看倒排索引大小。

语法

DESC INDEX [EXTENDED]  index_name;

案例

desc index bulkload_data_index;
+--------------------+-------------------------+
|     info_name      |       info_value        |
+--------------------+-------------------------+
| name               | bulkload_data_index     |
| creator            | system_admin            |
| created_time       | 2024-05-27 16:11:23.928 |
| last_modified_time | 2024-05-27 16:11:23.928 |
| comment            |                         |
| index_type         | inverted                |
| table_name         | bulkload_data           |
| table_column       | data                    |
+--------------------+-------------------------+

desc index extended  bulkload_data_index;
+--------------------------+--------------------------+
|        info_name         |        info_value        |
+--------------------------+--------------------------+
| name                     | bulkload_data_index      |
| creator                  | system_admin             |
| created_time             | 2024-05-27 16:11:23.928  |
| last_modified_time       | 2024-05-27 16:11:23.928  |
| comment                  |                          |
| properties               | (("analyzer","unicode")) |
| index_type               | inverted                 |
| table_name               | bulkload_data            |
| table_column             | data                     |
| index_size_in_data_file  | 0                        |
| index_size_in_index_file | 0                        |
| total_index_size         | 0                        |
+--------------------------+--------------------------+

删除倒排索引

语法

DROP INDEX [IF EXISTS] index_name;

参数说明：

  • DROP INDEX：删除索引的关键字。
  • IF EXISTS：可选参数，如果指定的索引不存在，则不报错。
  • index_name：要删除的索引名称。

说明

执行drop index会立即成功，会删除掉index的元数据信息。但是不会立即删除索引存储信息。

使用倒排索引查询

倒排索引函数

函数中要求分词和表保持一致，否则无法使用倒排索引加速查询。不指定option参数时会自动映射字段已有索引中的分词。

tokenize

语法：

tokenize(input[, option])

功能： 分词，返回值为array

示例：

SELECT tokenize('a b', map('analyzer', 'english'));
-- 返回: ["a", "b"]

match_all

语法：

match_all(input, query[, option])

功能： 匹配所有，先将query分词，再将input分词，需要保证input的分词结果包含所有query分词结果，返回bool

示例：

SELECT match_all('a b c', 'b a', map('analyzer', 'english'));
-- 返回: true

match_any

语法：

match_any(input, query[, option])

功能： 匹配任意，input的分词结果包含query分词结果的任意元素即可，返回bool

示例：

SELECT match_any('a b c', 'd a', map('analyzer', 'english'));
-- 返回: true

match_phrase

语法：

match_phrase(input, query[, option])

功能： 匹配短语，在match_all的基础上，匹配的结果顺序要和query分词结果的顺序要一致且连续

示例：

SELECT match_phrase('a b c', 'a b', map('analyzer', 'english'));
-- 返回: true

SELECT match_phrase('a b c', 'a c', map('analyzer', 'english'));
-- 返回: false (因为'a'和'c'在原文中不连续)

match_phrase_prefix

语法：

match_phrase_prefix(input, query[, option])

功能： 匹配短语前缀，input的分词结果，前n-1个匹配规则和match_phrase相同，最后一个元素符合前缀匹配

示例：

SELECT match_phrase_prefix('a b cd', 'b c', map('analyzer', 'english'));
-- 返回: true

match_regexp

语法：

match_regexp(input, query[, option])

功能： 匹配正则表达式，将input的分词结果，使用query的正则表达式匹配，有任意匹配即可

示例：

SELECT match_regexp('a b cd', 'c.*', map('analyzer', 'english'));
-- 返回: true

查询示例

创建倒排索引的表

CREATE TABLE bulkload_data(
   id INT,
   data STRING,
   INDEX id_index (id) INVERTED,
   INDEX data_index (data) INVERTED PROPERTIES('analyzer'='unicode')
);

插入测试数据：

INSERT INTO bulkload_data VALUES
(1, 'Lakehouse provides distributed storage'),
(2, 'Inverted index accelerates full text search'),
(3, 'Lakehouse supports multiple data types'),
(4, 'Full text search with inverted index'),
(5, 'Data analytics on Lakehouse platform');

全文检索示例：

--匹配所有，包含Lakehouse和storage
SELECT id, data FROM bulkload_data WHERE match_all(data, 'Lakehouse storage');
+----+---------------------------------------+
| id |                 data                  |
+----+---------------------------------------+
| 1  | Lakehouse provides distributed storage |
+----+---------------------------------------+

--匹配任意，包含search或analytics
SELECT id, data FROM bulkload_data WHERE match_any(data, 'search analytics');
+----+-------------------------------------------+
| id |                   data                    |
+----+-------------------------------------------+
| 2  | Inverted index accelerates full text search |
| 4  | Full text search with inverted index      |
| 5  | Data analytics on Lakehouse platform      |
+----+-------------------------------------------+

--匹配短语，包含full text search且连续
SELECT id, data FROM bulkload_data WHERE match_phrase(data, 'full text search');
+----+-------------------------------------------+
| id |                   data                    |
+----+-------------------------------------------+
| 2  | Inverted index accelerates full text search |
| 4  | Full text search with inverted index      |
+----+-------------------------------------------+

等值查询示例：

--使用倒排索引加速id列的等值查询
SELECT id, data FROM bulkload_data WHERE id = 3;
+----+------------------------------------------+
| id |                   data                   |
+----+------------------------------------------+
| 3  | Lakehouse supports multiple data types   |
+----+------------------------------------------+

--使用倒排索引加速id列的范围查询
SELECT id, data FROM bulkload_data WHERE id >= 4;
+----+--------------------------------------+
| id |                 data                 |
+----+--------------------------------------+
| 4  | Full text search with inverted index |
| 5  | Data analytics on Lakehouse platform |
+----+--------------------------------------+

使用注意事项

倒排索引无法优化场景

  • 在大多数情况下，倒排索引并不会显著提高执行时间为亚秒的查询的性能
  • 不支持外部表
  • 仅支持数据类型一致的查询，比如
--可以查询加速的，表中数据类型string
where string_col='10086';
--对需要匹配的值进行转化
where string_col=cast(10086 as string);

--无法查询加速的，因为对表列进行了强制转化
where cast(string_col as int)=10086 ;

计费说明

  • 存储资源：倒排索引会在数据文件之外额外创建倒排索引文件，索引文件和数据文件将按照存储大小统一收集存储费用。
Bloomfilter Index
Lakehouse 索引最佳实践指南
Yunqi © 2024 Yunqi, Inc. All Rights Reserved.

联系我们
预约咨询
微信咨询
电话咨询