小众话题 | 线性降维(Hilbert & Z-Order)
P
digoal约 18 分钟
digoal约 18 分钟参考文档点击文末阅读原文打开; 推荐《最好的PostgreSQL学习镜像》;
小众话题 | 向量检索优化 - 线性化降维(Hilbert & Z-Order)
一个向量, 多个浮点数组成的数组. 一个向量, 代表的可能是一张图片、一个文本、一个视频、一段音频、一个消费者的特征值. 向量召回, 就是要在一堆向量中找到与之相似(在向量空间中两者距离相近)的一条或多条向量.
如果向量只有1个值(一个值的数组), 要找相邻的值排序即可.通过对数据进行排序, 可以减少扫描的block数.
下面做个简单的测试, 使用PolarDB 11作为测试环境(因为里面内置了postgis、vector插件, 方便做后面的测试)
docker pull registry.cn-hangzhou.aliyuncs.com/polardb_pg/polardb_pg_local_instance:11
mkdir ~/data_volumn
cd ~/data_volumn
PWD=`pwd`
docker run -d -it -v $PWD:/var/polardb -P --shm-size=1g --cap-add=SYS_PTRACE --cap-add SYS_ADMIN --privileged=true --name polardb registry.cn-hangzhou.aliyuncs.com/polardb_pg/polardb_pg_local_instance:11 bash
docker exec -ti polardb bash
建表, 写入随机测试数据
postgres=# create table tbl (id int, x int);
postgres=# insert into tbl select generate_series(1,1000), random()*10000;
postgres=# create extension btree_gist;
postgres=# select * from tbl order by x <-> 10 limit 10;
id | x
-----+----
881 | 12
883 | 17
187 | 24
753 | 27
871 | 30
934 | 35
140 | 37
696 | 38
765 | 39
810 | 40
(10 rows)
对数据表进行排序之前, 召回10条相近记录, 需要访问10个block
postgres=# create index on tbl using gist (x gist_int4_ops);
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl order by x <-> 10 limit 10;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.15..0.72 rows=10 width=12) (actual time=0.294..0.428 rows=10 loops=1)
Output: id, x, ((x <-> 10))
Buffers: shared hit=10
-> Index Scan using tbl_x_idx on public.tbl (cost=0.15..172.15 rows=3000 width=12) (actual time=0.287..0.417 rows=10 loops=1)
Output: id, x, (x <-> 10)
Order By: (tbl.x <-> 10)
Buffers: shared hit=10 -- 10个数据块
Planning Time: 0.234 ms
Execution Time: 0.884 ms
(9 rows)
排序之后, 召回10条相近记录, 只需要访问3个block
postgres=# cluster tbl using tbl_x_idx ;
CLUSTER
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl order by x <-> 10 limit 10;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.15..0.73 rows=10 width=12) (actual time=0.094..0.102 rows=10 loops=1)
Output: id, x, ((x <-> 10))
Buffers: shared hit=3
-> Index Scan using tbl_x_idx on public.tbl (cost=0.15..176.15 rows=3000 width=12) (actual time=0.091..0.098 rows=10 loops=1)
Output: id, x, (x <-> 10)
Order By: (tbl.x <-> 10)
Buffers: shared hit=3 -- 3个数据块
Planning Time: 0.220 ms
Execution Time: 0.176 ms
(9 rows)
一维比较好解决, 二维呢, 三维呢, N维呢? 使用vector插件可以进行测试, 这里看到召回10条记录居然要访问305个数据块. 当然这个还和索引扫描方法有关, 它可能用了一些层级节点阈值, 存在扫描放大现象. 具体可参考:《头大! 索引扫描和全表扫描结果不一样, 这向量数据库还能用? 教你一招大幅提升召回率(recall)》
create extension vector;
postgres=# create table tbl1 (id int, v vector(4));
CREATE TABLE
postgres=# insert into tbl1 select generate_series(1,10000), array[random()*100, random()*100, random()*100, random()*100];
INSERT 0 10000
postgres=# create index on tbl1 using hnsw (v vector_cosine_ops);
CREATE INDEX
postgres=# select * from tbl1 order by array[37.6141,97.975,19.2775,62.1464]::vector(4) <=> v limit 10;
id | v
------+-----------------------------------
1 | [37.6141,97.975,19.2775,62.1464]
8667 | [28.2559,77.8027,17.753,49.717]
3631 | [29.1506,83.8823,14.3858,54.0148]
9092 | [21.678,54.6034,13.0832,37.1472]
9189 | [22.5271,64.2418,8.93046,41.502]
2504 | [30.8499,82.5926,20.9857,57.6203]
2091 | [38.6659,88.5916,18.3049,63.7643]
1631 | [29.3574,76.9156,13.2026,56.0934]
6619 | [31.1499,99.1323,14.4678,64.0255]
2916 | [21.866,61.8333,7.31612,36.6906]
(10 rows)
-- 需要访问305个数据块
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl1 order by array[37.6141,97.975,19.2775,62.1464]::vector(4) <=> v limit 10;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=16.60..17.02 rows=10 width=44) (actual time=1.432..1.503 rows=10 loops=1)
Output: id, v, (('[37.6141,97.975,19.2775,62.1464]'::vector(4) <=> v))
Buffers: shared hit=305
-> Index Scan using tbl1_v_idx on public.tbl1 (cost=16.60..437.60 rows=10000 width=44) (actual time=1.428..1.495 rows=10 loops=1)
Output: id, v, ('[37.6141,97.975,19.2775,62.1464]'::vector(4) <=> v)
Order By: (tbl1.v <=> '[37.6141,97.975,19.2775,62.1464]'::vector(4))
Buffers: shared hit=305
Planning Time: 0.258 ms
Execution Time: 1.914 ms
(9 rows)
试试cluster 向量字段? 不行, 暂不支持.
postgres=# \set VERBOSITY verbose
postgres=# cluster tbl1 using tbl1_v_idx ;
ERROR: 0A000: cannot cluster on index "tbl1_v_idx" because access method does not support clustering
LOCATION: check_index_is_clusterable, cluster.c:469
但是我并不想放弃这个优化思路, 想起postgis里面geom 排序支持z-order, hilbert encode, 实际上也是要解决在二维、三维、四维空间中的相邻数据尽量能挨着存放和排序.
Z-Order 到 Hilbert encode
PostGIS相关的请参考:
《PostgreSQL PostGIS 3 - 从min(x) 到 z-order 到 Hilbert Geometry Sorting - PostGIS空间排序算法优化》
DuckDB社区插件也支持了这两种编解码:
https://duckdb.org/community_extensions/extensions/lindel.html
DuckDB Extension Linearization/Delinearization, Z-Order, Hilbert and Morton Curves
https://github.com/rustyconover/duckdb-lindel-extension
Z-Order , Hilbert encode 简单来说就是把二维、三维、四维空间中的数据进行线性化编码(降到一维), 尽量让在高维坐标中相邻的数据在一维中也是相邻的.
语言可能不好理解, 看上面那篇PostGIS的文章, 里面有图示(一种分形).
下面举个例子, 在PolarDB中生成GIS数据, 在DuckDB中使用lindel插件进行降维编码.
postgres=# create extension postgis;
postgres=# \dx
List of installed extensions
Name | Version | Schema | Description
---------+---------+------------+------------------------------------------------------------
plpgsql | 1.0 | pg_catalog | PL/pgSQL procedural language
postgis | 3.3.2 | public | PostGIS geometry and geography spatial types and functions
(2 rows)
创建一个测试表, 写入一些二维点数据
CREATE SEQUENCE points_seq;
CREATE TABLE points AS
SELECT (ST_Dump
( ST_GeneratePoints(
ST_MakeEnvelope(-10000,-10000,10000,10000,3857),
10000)
)).geom AS geom,
nextval('points_seq') AS pk;
postgres=# \d points
Table "public.points"
Column | Type | Collation | Nullable | Default
--------+----------+-----------+----------+---------
geom | geometry | | |
pk | bigint | | |
数据示例
postgres=# select pk,st_astext (geom) from points limit 10;
pk | st_astext
----+-----------------------------------------------
1 | POINT(2046.9292021305216 -3373.426043401106)
2 | POINT(5930.101901972043 -1016.7117529644161)
3 | POINT(-8791.247155450288 7104.906537997097)
4 | POINT(-3026.3358190835197 -5731.074083289735)
5 | POINT(-1166.4084269407747 -1046.954423930089)
6 | POINT(-4647.931525145741 -8226.307784689665)
7 | POINT(8853.436058918976 6542.550667522851)
8 | POINT(4306.354422606586 2419.8207430936222)
9 | POINT(154.6859954243105 -6601.437947304093)
10 | POINT(-1997.4782002091627 9670.805719782824)
(10 rows)
postgres=# select pk,st_astext (geom) from points order by geom limit 10;
pk | st_astext
------+----------------------------------------------
4840 | POINT(-9918.969328660702 -9902.51258756666)
1777 | POINT(-9789.858034969277 -9258.926358916211)
7350 | POINT(-9850.953601268611 -9402.424860189722)
9228 | POINT(-9763.043060460435 -9522.945422236975)
8725 | POINT(-9905.710468527577 -9723.551369226476)
7349 | POINT(-9669.995098351306 -9679.94414306956)
9571 | POINT(-9551.889403495285 -9604.506526693262)
9650 | POINT(-9569.741022599856 -9514.054216674813)
4092 | POINT(-9351.031561213398 -9459.210178923264)
2378 | POINT(-9390.75256698484 -9350.547754297293)
(10 rows)
postgres=# select pk,st_x(geom),st_y(geom) from points order by geom limit 10;
pk | st_x | st_y
------+-------------------+-------------------
4840 | -9918.9693286607 | -9902.51258756666
1777 | -9789.85803496928 | -9258.92635891621
7350 | -9850.95360126861 | -9402.42486018972
9228 | -9763.04306046044 | -9522.94542223697
8725 | -9905.71046852758 | -9723.55136922648
7349 | -9669.99509835131 | -9679.94414306956
9571 | -9551.88940349528 | -9604.50652669326
9650 | -9569.74102259986 | -9514.05421667481
4092 | -9351.0315612134 | -9459.21017892326
2378 | -9390.75256698484 | -9350.54775429729
(10 rows)
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from points order by geom <-> st_setsrid('POINT(2046.9292021305216 -3373.426043401106)'::geometry, 3857) limit 10;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.15..1.14 rows=10 width=48) (actual time=0.215..0.281 rows=10 loops=1)
Output: geom, pk, ((geom <-> '0101000020110F0000DB67C380B7FB9F40DB545C22DA5AAAC0'::geometry))
Buffers: shared hit=13
-> Index Scan using points_geom_idx on public.points (cost=0.15..993.15 rows=10000 width=48) (actual time=0.212..0.275 rows=10 loops=1)
Output: geom, pk, (geom <-> '0101000020110F0000DB67C380B7FB9F40DB545C22DA5AAAC0'::geometry)
Order By: (points.geom <-> '0101000020110F0000DB67C380B7FB9F40DB545C22DA5AAAC0'::geometry)
Buffers: shared hit=13
Planning Time: 0.396 ms
Execution Time: 0.375 ms
(9 rows)
复制points表的数据创建一个表b, 方便在DuckDB中获取geometry中的x,y坐标的值
postgres=# create table b as select pk,st_x(geom),st_y(geom) from points;
SELECT 10000
下载duckdb
$ sudo apt update
$ sudo apt-get install -y unzip
$ wget https://github.com/duckdb/duckdb/releases/download/v1.1.3/duckdb_cli-linux-aarch64.zip
$ unzip duckdb_cli-linux-aarch64.zip
启动duckdb, 安装lindel社区版插件
$ ./duckdb -unsigned
D install lindel from community;
加载lindel和postgres_scanner插件, 可以直接查看polardb中的数据
D load lindel;
D load postgres_scanner;
D ATTACH 'dbname=postgres user=postgres host=127.0.0.1' AS db (TYPE POSTGRES, SCHEMA 'public');
D show all tables;
┌──────────┬─────────┬───────────────────┬─────────────────────────────────────────────────────────────────────────────────┬─────────────────────────────────────────────────────────────────┬───────────┐
│ database │ schema │ name │ column_names │ column_types │ temporary │
│ varchar │ varchar │ varchar │ varchar[] │ varchar[] │ boolean │
├──────────┼─────────┼───────────────────┼─────────────────────────────────────────────────────────────────────────────────┼─────────────────────────────────────────────────────────────────┼───────────┤
│ db │ public │ b │ [pk, st_x, st_y] │ [BIGINT, DOUBLE, DOUBLE] │ false │
│ db │ public │ geography_columns │ [f_table_catalog, f_table_schema, f_table_name, f_geography_column, coord_dim… │ [VARCHAR, VARCHAR, VARCHAR, VARCHAR, INTEGER, INTEGER, VARCHAR] │ false │
│ db │ public │ geometry_columns │ [f_table_catalog, f_table_schema, f_table_name, f_geometry_column, coord_dime… │ [VARCHAR, VARCHAR, VARCHAR, VARCHAR, INTEGER, INTEGER, VARCHAR] │ false │
│ db │ public │ points │ [geom, pk] │ [VARCHAR, BIGINT] │ false │
│ db │ public │ spatial_ref_sys │ [srid, auth_name, auth_srid, srtext, proj4text] │ [INTEGER, VARCHAR, INTEGER, VARCHAR, VARCHAR] │ false │
└──────────┴─────────┴───────────────────┴─────────────────────────────────────────────────────────────────────────────────┴─────────────────────────────────────────────────────────────────┴───────────┘
D select * from db.public.points limit 1;
┌────────────────────────────────────────────────────┬───────┐
│ geom │ pk │
│ varchar │ int64 │
├────────────────────────────────────────────────────┼───────┤
│ 0101000020110F0000DB67C380B7FB9F40DB545C22DA5AAAC0 │ 1 │
└────────────────────────────────────────────────────┴───────┘
D select * from db.public.b limit 10;
┌───────┬─────────────────────┬─────────────────────┐
│ pk │ st_x │ st_y │
│ int64 │ double │ double │
├───────┼─────────────────────┼─────────────────────┤
│ 1 │ 2046.9292021305216 │ -3373.426043401106 │
│ 2 │ 5930.101901972043 │ -1016.7117529644161 │
│ 3 │ -8791.247155450288 │ 7104.906537997097 │
│ 4 │ -3026.3358190835197 │ -5731.074083289735 │
│ 5 │ -1166.4084269407747 │ -1046.954423930089 │
│ 6 │ -4647.931525145741 │ -8226.307784689665 │
│ 7 │ 8853.436058918976 │ 6542.550667522851 │
│ 8 │ 4306.354422606586 │ 2419.8207430936222 │
│ 9 │ 154.6859954243105 │ -6601.437947304093 │
│ 10 │ -1997.4782002091627 │ 9670.805719782824 │
├───────┴─────────────────────┴─────────────────────┤
│ 10 rows 3 columns │
└───────────────────────────────────────────────────┘
使用hilbert_encode编码
D select hilbert_encode([st_x,st_y]::float8[2]) from db.public.b limit 10;
┌────────────────────────────────────────────────────────────────┐
│ hilbert_encode(CAST(main.list_value(st_x, st_y) AS DOUBLE[2])) │
│ uint128 │
├────────────────────────────────────────────────────────────────┤
│ 127608752162646127659035910886103386144 │
│ 127608600396254020636859338435356020469 │
│ 269387826632122111161499541049910756343 │
│ 212679308838130456808137536323600312212 │
│ 212679117197097433560796766092979103075 │
│ 212679705391475717685004347839034177465 │
│ 42538539184024747040393003352679344376 │
│ 42538128274153391388285904385947417177 │
│ 127608238159324586877755442014620839076 │
│ 269387313151091807817853115678229737739 │
├────────────────────────────────────────────────────────────────┤
│ 10 rows │
└────────────────────────────────────────────────────────────────┘
使用hilbert, morton编码后的一维数据进行排序输出
D select pk,st_x,st_y from db.public.b order by hilbert_encode([st_x,st_y]::float8[2]) limit 10;
┌───────┬────────────────────┬────────────────────┐
│ pk │ st_x │ st_y │
│ int64 │ double │ double │
├───────┼────────────────────┼────────────────────┤
│ 5078 │ 72.43789926041916 │ 118.71162647869822 │
│ 7365 │ 59.4230436957249 │ 465.20852425262547 │
│ 8499 │ 175.6661026420159 │ 380.61949738890735 │
│ 7583 │ 305.254628856966 │ 348.8339311680217 │
│ 7016 │ 302.6602970092209 │ 416.1972847658997 │
│ 9914 │ 332.21399934878104 │ 142.64991568645596 │
│ 4546 │ 426.6989131781308 │ 170.8931459700304 │
│ 6453 │ 1882.1819301626942 │ 31.64334953282248 │
│ 189 │ 3478.7032917559986 │ 31.874500265965484 │
│ 9263 │ 3213.7468681523965 │ 16.872169000159186 │
├───────┴────────────────────┴────────────────────┤
│ 10 rows 3 columns │
└─────────────────────────────────────────────────┘
D select pk,st_x,st_y from db.public.b order by hilbert_encode([st_x,st_y]::float8[2]) desc limit 10;
┌───────┬─────────────────────┬────────────────────┐
│ pk │ st_x │ st_y │
│ int64 │ double │ double │
├───────┼─────────────────────┼────────────────────┤
│ 8107 │ -230.30462086940778 │ 0.5383064252119726 │
│ 1967 │ -18.695736857660883 │ 8383.007411265573 │
│ 7272 │ -19.91718415774435 │ 9290.459806792942 │
│ 6176 │ -31.73736394274791 │ 8462.892955423287 │
│ 931 │ -503.8557217585558 │ 9254.052858145205 │
│ 4955 │ -487.26352426102363 │ 9572.568372761976 │
│ 6358 │ -472.49123983166896 │ 8217.403930369455 │
│ 5957 │ -449.1333241464256 │ 8423.069440462115 │
│ 6498 │ -421.1240317651735 │ 9186.301866376614 │
│ 4929 │ -396.12700551319654 │ 9105.90925123649 │
├───────┴─────────────────────┴────────────────────┤
│ 10 rows 3 columns │
└──────────────────────────────────────────────────┘
D select pk,st_x,st_y from db.public.b order by morton_encode([st_x,st_y]::float8[2]) limit 10;
┌───────┬────────────────────┬────────────────────┐
│ pk │ st_x │ st_y │
│ int64 │ double │ double │
├───────┼────────────────────┼────────────────────┤
│ 3305 │ 1.0069831673025942 │ 4788.83047162117 │
│ 5078 │ 72.43789926041916 │ 118.71162647869822 │
│ 7365 │ 59.4230436957249 │ 465.20852425262547 │
│ 8499 │ 175.6661026420159 │ 380.61949738890735 │
│ 9914 │ 332.21399934878104 │ 142.64991568645596 │
│ 4546 │ 426.6989131781308 │ 170.8931459700304 │
│ 7583 │ 305.254628856966 │ 348.8339311680217 │
│ 7016 │ 302.6602970092209 │ 416.1972847658997 │
│ 6462 │ 13.21548247864284 │ 1572.3748193363938 │
│ 6993 │ 10.492876773651002 │ 4103.208900602886 │
├───────┴────────────────────┴────────────────────┤
│ 10 rows 3 columns │
└─────────────────────────────────────────────────┘
D select pk,st_x,st_y from db.public.b order by morton_encode([st_x,st_y]::float8[2]) desc limit 10;
┌───────┬────────────────────┬────────────────────┐
│ pk │ st_x │ st_y │
│ int64 │ double │ double │
├───────┼────────────────────┼────────────────────┤
│ 4840 │ -9918.969328660702 │ -9902.51258756666 │
│ 8725 │ -9905.710468527577 │ -9723.551369226476 │
│ 9228 │ -9763.043060460435 │ -9522.945422236975 │
│ 7350 │ -9850.953601268611 │ -9402.424860189722 │
│ 1777 │ -9789.858034969277 │ -9258.926358916211 │
│ 8288 │ -9602.090756957286 │ -9901.04485069812 │
│ 1861 │ -9462.765139683632 │ -9807.24769691753 │
│ 749 │ -9323.37419944201 │ -9800.903424097594 │
│ 8148 │ -9293.070846288942 │ -9743.151342574443 │
│ 7349 │ -9669.995098351306 │ -9679.94414306956 │
├───────┴────────────────────┴────────────────────┤
│ 10 rows 3 columns │
└─────────────────────────────────────────────────┘
可以观察到编码后排序输出的顺序和PostGIS按geom字段排序的结果差不多. (实际上前面也提到了PostGIS早期版本使用z-order编码排序, 3.0开始使用了hilbert编码排序.)
最后尝试一下使用hilbert编码vector(4)的值, 然后排序写回PolarDB
D select v::float4[] from db.public.tbl1 limit 10;
┌──────────────────────────────────────┐
│ CAST(v AS FLOAT[]) │
│ float[] │
├──────────────────────────────────────┤
│ [37.6141, 97.975, 19.2775, 62.1464] │
│ [39.974, 1.25646, 34.3809, 84.2677] │
│ [15.8222, 25.3363, 74.1734, 48.6075] │
│ [22.3855, 12.1765, 19.7362, 94.9552] │
│ [43.0783, 81.472, 59.4053, 49.3705] │
│ [94.0546, 6.32902, 79.7679, 16.7633] │
│ [23.248, 31.3126, 56.5406, 42.2587] │
│ [87.1805, 74.6751, 79.8728, 85.1555] │
│ [93.9526, 42.0192, 30.2203, 33.9266] │
│ [43.2757, 64.6012, 18.1943, 59.0979] │
├──────────────────────────────────────┤
│ 10 rows │
└──────────────────────────────────────┘
D select id,v::float4[] from db.public.tbl1 order by hilbert_encode(v::float4[4]) limit 10;
┌───────┬────────────────────────────────────────┐
│ id │ CAST(v AS FLOAT[]) │
│ int32 │ float[] │
├───────┼────────────────────────────────────────┤
│ 293 │ [1.90566, 8.1806, 47.132, 0.440405] │
│ 1925 │ [0.75996, 83.2958, 43.118, 1.55816] │
│ 603 │ [0.573426, 50.3894, 62.1799, 1.04364] │
│ 2453 │ [0.942698, 53.9329, 70.0511, 1.11403] │
│ 4718 │ [31.0281, 95.7201, 0.878549, 1.73586] │
│ 1829 │ [40.8958, 53.7539, 1.7224, 1.95291] │
│ 9680 │ [41.8442, 89.2243, 0.0358663, 1.65982] │
│ 8684 │ [47.0484, 24.8857, 1.47623, 1.18898] │
│ 7451 │ [11.3917, 19.3322, 1.62581, 0.658556] │
│ 7340 │ [88.0247, 94.5786, 22.0108, 0.103545] │
├───────┴────────────────────────────────────────┤
│ 10 rows 2 columns │
└────────────────────────────────────────────────┘
D CALL postgres_execute('db', 'create table tbl2 (id int, v vector(4))');
┌─────────┐
│ Success │
│ boolean │
├─────────┤
│ 0 rows │
└─────────┘
PolarDB里面的表新建后, 需要刷新一下, 否则在duckdb里面看不到元数据.
D DETACH db;
D ATTACH 'dbname=postgres user=postgres host=127.0.0.1' AS db (TYPE POSTGRES, SCHEMA 'public');
D insert into db.public.tbl2 select id,v::float4[] from db.public.tbl1 order by hilbert_encode(v::float4[4]);
检查一下写入tbl2的数据是否和期望的顺序一样?
D select * from db.public.tbl2 limit 10;
┌───────┬────────────────────────────────────────┐
│ id │ v │
│ int32 │ varchar │
├───────┼────────────────────────────────────────┤
│ 293 │ [1.90566, 8.1806, 47.132, 0.440405] │
│ 1925 │ [0.75996, 83.2958, 43.118, 1.55816] │
│ 603 │ [0.573426, 50.3894, 62.1799, 1.04364] │
│ 2453 │ [0.942698, 53.9329, 70.0511, 1.11403] │
│ 4718 │ [31.0281, 95.7201, 0.878549, 1.73586] │
│ 1829 │ [40.8958, 53.7539, 1.7224, 1.95291] │
│ 9680 │ [41.8442, 89.2243, 0.0358663, 1.65982] │
│ 8684 │ [47.0484, 24.8857, 1.47623, 1.18898] │
│ 7451 │ [11.3917, 19.3322, 1.62581, 0.658556] │
│ 7340 │ [88.0247, 94.5786, 22.0108, 0.103545] │
├───────┴────────────────────────────────────────┤
│ 10 rows 2 columns │
└────────────────────────────────────────────────┘
在PolarDB中使用这个用hilbert编码重排后的tbl2
postgres=# select * from tbl2 limit 10;
id | v
------+-------------------------------------
293 | [1.90566,8.1806,47.132,0.440405]
1925 | [0.75996,83.2958,43.118,1.55816]
603 | [0.573426,50.3894,62.1799,1.04364]
2453 | [0.942698,53.9329,70.0511,1.11403]
4718 | [31.0281,95.7201,0.878549,1.73586]
1829 | [40.8958,53.7539,1.7224,1.95291]
9680 | [41.8442,89.2243,0.0358663,1.65982]
8684 | [47.0484,24.8857,1.47623,1.18898]
7451 | [11.3917,19.3322,1.62581,0.658556]
7340 | [88.0247,94.5786,22.0108,0.103545]
(10 rows)
postgres=# create index on tbl2 using hnsw (v vector_cosine_ops);
CREATE INDEX
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl2 order by array[37.6141,97.975,19.2775,62.1464]::vector(4) <=> v limit 10;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=16.60..17.02 rows=10 width=44) (actual time=0.649..0.671 rows=10 loops=1)
Output: id, v, (('[37.6141,97.975,19.2775,62.1464]'::vector(4) <=> v))
Buffers: shared hit=295
-> Index Scan using tbl2_v_idx on public.tbl2 (cost=16.60..437.60 rows=10000 width=44) (actual time=0.646..0.666 rows=10 loops=1)
Output: id, v, ('[37.6141,97.975,19.2775,62.1464]'::vector(4) <=> v)
Order By: (tbl2.v <=> '[37.6141,97.975,19.2775,62.1464]'::vector(4))
Buffers: shared hit=295
Planning Time: 0.469 ms
Execution Time: 0.836 ms
(9 rows)
目前看效果并不明显, 但相信这个方向还可以继续探索. 这里看到召回10条记录还要访问295个数据块. 和索引扫描方法有关, 它可能用了一些层级节点阈值, 存在扫描放大现象. 具体可参考:《头大! 索引扫描和全表扫描结果不一样, 这向量数据库还能用? 教你一招大幅提升召回率(recall)》
目前DuckDB线性化降维插件还有一些不足: 当前的编码结果最大仅支持到UHUGEINT, 支持最多16个UTINYINT进行编码
Encoding Functions
hilbert_encode(ARRAY[INPUT_TYPE, 1-16])morton_encode(ARRAY[INPUT_TYPE, 1-16])
Output is limited to a 128-bitUHUGEINT. The input array size is validated to ensure it fits within this limit.
UTINYINT | UTINYINT2: USMALLINT3-4: UINTEGER4-8: UBIGINT8-16: UHUGEINT | |
USMALLINT | USMALLINT2: UINTEGER3-4: UBIGINT4-8: UHUGEINT | |
UINTEGER | UINTEGER2: UBIGINT3-4: UHUGEINT | |
UBIGINT | UBIGINT2: UHUGEINT | |
FLOAT | UINTEGER2: UBIGINT3-4: UHUGEINT | |
DOUBLE | UBIGINT2: UHUGEINT |
理论上数据如果可以按相邻存储, 那么索引效率, 数据搜索的block数都可以下降.
参考
《从一维编排到多维编排，从平面存储到3D存储 - 数据存储优化之路》
《头大! 索引扫描和全表扫描结果不一样, 这向量数据库还能用? 教你一招大幅提升召回率(recall)》
https://github.com/pgvector/pgvector
https://duckdb.org/community_extensions/extensions/lindel.html
DuckDB Extension Linearization/Delinearization, Z-Order, Hilbert and Morton Curves
https://github.com/rustyconover/duckdb-lindel-extension
https://duckdb.org/docs/extensions/postgres
文末彩蛋:国产数据库周边生态
当然一款数据库要流行起来, 除了自己要强大, 还离不开生态. 用好周边生态工具, 管理水平战胜90%老司机!!! 下面简单介绍一下国产数据库周边生态.
1、管控软件
鸣嵩(前阿里云数据库总经理 / 研究员)等大佬们创业创办的云猿生, 核心产品是KubeBlocks. 他们的理念是让管理数据库和搭积木一样简单, 如果你要管理很多套并且种类(OLTP\OLAP\NoSQL\KV\TS\MQ等)很多的数据库产品, 推荐首选.
https://github.com/apecloud/kubeblocks
PG中文社区核心委员唐成老师的公司乘数开源的Clup, 专用管理PostgreSQL和PolarDB的集群管理软件, 如果你要管理很多套数据库, 推荐选择. 并且Clup还提供了企业版、自研的连接池、分布式存储、一体机、备份平台等, 是企业用户推荐之选.
https://www.csudata.com/
若航老司机开源的pigsty, 集成了300多个PG插件的PG集群和PolarDB集群管理软件, 如果你要管理很多套PG或PolarDB数据库, 且对插件有特别多的需求, 推荐选择.
https://pigsty.cc/zh/
2、审计监控诊断优化
翟总(曾经是我背后的男人)到海信聚好看后研发的 DBdoctor, 采用ebpf技术, 在对数据库几乎没有影响的情况下实时监控数据库和服务器的各项指标, 发现和诊断问题根因非常方便.
https://www.dbdoctor.cn/
天舟老哥的核心产品Bytebase 是位于您和数据库之间的中间件。它是数据库 DevOps 的 GitLab/GitHub，专为开发人员、DBA 和平台工程师打造。
https://bytebase.cc/docs/introduction/what-is-bytebase/
PawSQL, SQL优化和诊断产品.
D-Smart, Oracle老前辈白老大出品, 专注企业级市场, 将业界顶级DBA经验的产品化作品, 产品功能包括数据库监控、诊断、优化等.
https://www.modb.pro/db/567140
3、国产数据库IDE
IDE是开发者的必备工具，例如社区有pgAdmin, 国产IDE则可以看看老程序猿达刚老师的DeskUI:
https://www.deskui.com
4、数据同步&迁移&备份恢复
NineData, 老领导出去创业做的产品, 产品涵盖了数据同步、迁移、备份、比对、devops、chatDBA等.
https://www.ninedata.cloud/home
DSG, 非常老牌的数据库同步迁移企业级产品, 支持各种数据库的异构和同构迁移, 用他们的话说, 没有dsg搞不定的迁移, 比goldengate还牛.
https://www.dsgdata.com/
公开课
如果你对PolarDB学习感兴趣可以阅读这个公开课系列:
除了PolarDB还非常值得关注的几款PG栈国产数据库:
HaloDB(基于PG兼容PostgreSQL、Oracle、MySQL. http://www.halodbtech.com/ )、 IvorySQL(基于开源PG兼容PG、Oracle. https://www.ivorysql.org/zh-cn/ )、 ProtonBase(云原生分布式数仓. https://protonbase.com/ )、 成都文武数据库（https://ww-it.cn）
参考文档点击阅读原文获得
感谢关注我的github (https://github.com/digoal/blog) 及视频号: