标量向量查询

标量向量查询将 Top-K l2_distance 检索的查询向量改由一个标量子查询提供;当被检索列上存在 IVF-FLAT 或 HNSW 向量索引时,MatrixOne 会用近似最近邻(ANN)扫描替代全表扫描来回答该查询。

概述

向量 Top-K 查询通常以字面量形式给出查询向量,例如:

SELECT id FROM items ORDER BY l2_distance(v, '[1,0,0]') LIMIT 2;

当查询向量保存在另一张表中时,可以改由一个至多返回一行的标量子查询提供查询向量列:

SELECT id FROM items
ORDER BY l2_distance(v, (SELECT v FROM query_vectors WHERE id = 'q'))
LIMIT 2;

如果被检索列上建有 IVF-FLAT 或 HNSW 向量索引,MatrixOne 会将这种查询形态改写为近似最近邻(ANN)扫描,与字面量查询向量使用相同的执行计划。对 IVF-FLAT 索引,EXPLAIN 输出中会出现 ivf_search 节点(并出现 Scalar Vector Query 字样)。当标量子查询不返回任何行、或返回 NULL 时,不会进行 ANN 扫描,而是按原关系排序输出,因此缺少提供方时回退到正确的非索引结果而不是报错。

改写遵循与字面量形式相同的选项约束:

  • 系统变量 probe_limit 限制 IVF-FLAT 探测的列表数量,与字面量向量检索一致。

  • BY RANK WITH OPTION 'mode=pre' 保持 ANN 扫描;BY RANK WITH OPTION 'mode=force' 绕过 ANN 扫描,与 IVF 向量查询排名选项的语义保持一致。

  • 提供方子查询可以出现在 CTE 或派生表中;每个出现位置独立改写,两个使用不同过滤条件的出现位置互不干扰。

  • 整条语句可以通过 PREPARE/EXECUTE 预备和执行;重新绑定提供方键值、LIMIT 或 NULL 提供方,行为与重新执行查询相同。

  • 当提供方表带有快照限定,例如 (SELECT v FROM query_vectors {snapshot='快照名'} WHERE id = 1) 时,提供方行按快照时间读取,ANN 搜索与该时间限定保持一致:同一语句中混用当前提供方与快照提供方不会被合并。

并非所有形态都会被改写。可能返回多行的提供方子查询被有意保持原样,仍然抛出标量子查询基数错误。作用于被检索表自身的标量子查询(SELECT ... FROM items ref WHERE ref.id = ...)只要至多返回一行,同样参与改写。

语法

SELECT ... FROM indexed_table
ORDER BY l2_distance(vector_column, (SELECT query_vector FROM provider WHERE ...))
LIMIT k [OFFSET n];

参数

  • vector_column 是带有 IVF-FLAT 或 HNSW 索引的向量列。

  • 提供方向量的标量子查询至多返回一行;多行仍产生标量子查询错误。

  • k 是 Top-K 数量;OFFSET 在排序后生效。

示例

以下语句可以在全新的 MatrixOne 实例上连续执行。IVF-FLAT 部分使用 experimental_ivf_index 和 probe_limit,HNSW 部分使用 experimental_hnsw_index。

DROP DATABASE IF EXISTS scalar_vector_demo;
CREATE DATABASE scalar_vector_demo;
USE scalar_vector_demo;
SET experimental_ivf_index = 1;
SET probe_limit = 1;
CREATE TABLE items(id VARCHAR(32) PRIMARY KEY, v VECF64(3) NOT NULL);
INSERT INTO items VALUES ('a','[0,0,0]'),('b','[1,0,0]'),('c','[3,0,0]');
CREATE INDEX ix USING IVFFLAT ON items(v) LISTS=1 OP_TYPE 'vector_l2_ops';
CREATE TABLE query_vectors(id VARCHAR(32) PRIMARY KEY, v VECF64(3));
INSERT INTO query_vectors VALUES ('q','[1,0,0]'),('n',NULL);

以下两条查询返回相同的前两行最近邻;在索引存在时,第二条走 ANN 扫描。EXPLAIN 输出包含 Scalar Vector Query 与 ivf_search 节点:

EXPLAIN SELECT id FROM items ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id='q')) LIMIT 2;
SELECT id FROM items ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id='q')) LIMIT 2;
SELECT id FROM items ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id='q')) LIMIT 1 OFFSET 1;
SELECT id FROM items ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id='q')) LIMIT 2 BY RANK WITH OPTION 'mode=pre';
SELECT id FROM items ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id='q')) LIMIT 2 BY RANK WITH OPTION 'mode=force';

提供方行缺失或提供方向量为 NULL 时都不进入 ANN 路径;结果是基于回退关系的普通有序结果,同样支持 OFFSET:

SELECT id FROM items WHERE id='a' ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id='missing')) LIMIT 2;
SELECT COUNT(*) FROM (SELECT id FROM items ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id='missing')) LIMIT 2) t;
SELECT id FROM items WHERE id='a' ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id='n')) LIMIT 2;
SELECT COUNT(*) FROM (SELECT id FROM items ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id='n')) LIMIT 2) t;
SELECT COUNT(*) FROM (SELECT id FROM items ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id='n')) LIMIT 0) t;

两个 CTE selector 各自带自己的提供方和过滤条件;两者独立进行 ANN 扫描:

WITH a AS (SELECT CONCAT(id,'') AS id FROM items ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id='q')) LIMIT 2),
b AS (SELECT CONCAT(id,'') AS id FROM items ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id='q')) LIMIT 2)
SELECT a.id,b.id FROM a JOIN b ON a.id=b.id ORDER BY a.id;
WITH a AS (SELECT CONCAT(id,'') AS id FROM items WHERE id>'a' ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id='q')) LIMIT 2),
b AS (SELECT CONCAT(id,'') AS id FROM items WHERE id<'c' ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id='missing')) LIMIT 2)
SELECT a.id,b.id FROM a JOIN b ON a.id=b.id ORDER BY a.id;

预备语句在每次 EXECUTE 时重新绑定提供方键值和 LIMIT;提供方数据变化后无需重新 PREPARE 即可生效:

PREPARE p FROM 'SELECT id FROM items WHERE id=''a'' ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id=?)) LIMIT ?';
SET @id='q';
SET @k=0;
EXECUTE p USING @id,@k;
SET @k=2;
EXECUTE p USING @id,@k;
SET @id='n';
EXECUTE p USING @id,@k;
SET @id='missing';
EXECUTE p USING @id,@k;
SET @id='q';
EXECUTE p USING @id,@k;
SET @k=0;
EXECUTE p USING @id,@k;
DEALLOCATE PREPARE p;
PREPARE nested FROM 'SELECT * FROM (SELECT id FROM items ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id=?)) LIMIT 2) t LIMIT ? OFFSET 1';
SET @k=0;
EXECUTE nested USING @id,@k;
SET @k=5;
EXECUTE nested USING @id,@k;
UPDATE query_vectors SET v='[3,0,0]' WHERE id='q';
EXECUTE nested USING @id,@k;
DEALLOCATE PREPARE nested;

可能返回多行的提供方子查询不会被改写;它将照常抛出标量子查询基数错误:

-- Expected-Success: false
SELECT id FROM items ORDER BY l2_distance(v,(SELECT v FROM items ref WHERE ref.id IN ('a','b'))) LIMIT 2;
DROP DATABASE scalar_vector_demo;

上面的 items ref 形态只要至多返回一行仍然会参与改写,例如 SELECT id FROM items ORDER BY l2_distance(v,(SELECT v FROM items ref WHERE ref.id='b')) LIMIT 2;。上例刻意选取两行以展示未改写的回退行为。ref 只是关联别名,不是保留字。

HNSW

同一改写对 HNSW 索引同样生效。启用 HNSW 索引后,用 VECF32 列重复上述查询形态,计划输出的是 ANN 节点而非 ivf_search:

SET @saved_hnsw=@@experimental_hnsw_index;
SET experimental_hnsw_index=1;
CREATE DATABASE scalar_vector_demo;
USE scalar_vector_demo;
CREATE TABLE items(id BIGINT PRIMARY KEY, v VECF32(3) NOT NULL);
INSERT INTO items VALUES (1,'[0,0,0]'),(2,'[1,0,0]'),(3,'[3,0,0]');
CREATE INDEX ix USING HNSW ON items(v) OP_TYPE 'vector_l2_ops' M 4 EF_CONSTRUCTION 16 EF_SEARCH 16;
CREATE TABLE query_vectors(id BIGINT PRIMARY KEY, v VECF32(3));
INSERT INTO query_vectors VALUES (1,'[1,0,0]'),(2,'[3,0,0]'),(3,NULL);
EXPLAIN SELECT id FROM items ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id=1)) LIMIT 2;
SELECT id FROM items ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id=1)) LIMIT 2;
SELECT id FROM items WHERE id=1 ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id=99)) LIMIT 2;
SELECT COUNT(*) FROM (SELECT id FROM items ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id=99)) LIMIT 2) t;
SELECT COUNT(*) FROM (SELECT id FROM items ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id=3)) LIMIT 2) t;
PREPARE p FROM 'SELECT id FROM items ORDER BY l2_distance(v,(SELECT v FROM query_vectors WHERE id=?)) LIMIT ?';
SET @id=1;
SET @k=2;
EXECUTE p USING @id,@k;
SET @id=2;
EXECUTE p USING @id,@k;
SET @k=0;
EXECUTE p USING @id,@k;
SET @k=2;
UPDATE query_vectors SET v='[0,0,0]' WHERE id=2;
EXECUTE p USING @id,@k;
DEALLOCATE PREPARE p;
SET experimental_hnsw_index=@saved_hnsw;
DROP DATABASE scalar_vector_demo;

参考文档