我读书少，啥是迭代式索引扫描? 向量数据库又又又进化了?!
digoal约 8 分钟参考文档点击文末阅读原文打开; 推荐《最好的PostgreSQL学习镜像》;
第一次听说: 啥是迭代式索引扫描? 向量数据库进化了?!
pgvector发布v0.8.0, 这个版本的亮点是: 迭代式索引扫描方法!
什么是迭代式索引扫描方法呢? 它解决什么场景的问题? 先来看一封邮件
Hi, Currently, index scans that order by an operator (for instance, location <-> POINT(0, 0)) and have a filter for the same expression (location <-> POINT(0, 0) < 2) can end up scanning much more of the index than is necessary.
Here's a complete example:
CREATE TABLE stores (location point); INSERT INTO stores SELECT POINT(0, i) FROM generate_series(1, 100000) i;
CREATE INDEX ON stores USING gist (location);
EXPLAIN (ANALYZE, COSTS OFF) SELECT * FROM stores
WHERE location <-> POINT(0, 0) < 2
ORDER BY location <-> POINT(0, 0) LIMIT 10;
Once the second tuple returned from the index has a distance >= 2, the scan
should be able to end (as it's an ascending order scan). Instead, it scans
the entire index, filtering out the next 99,998 rows.
Limit (actual time=0.166..32.573 rows=1 loops=1)
-> Index Only Scan using stores_location_idx on stores (actualtime=0.165..32.570 rows=1 loops=1)
Order By: (location <-> '(0,0)'::point)
Filter: ((location <-> '(0,0)'::point) < '2'::double precision)
Rows Removed by Filter: 99999
This can be especially costly for vector index scans (this was found while working on an upcoming feature for pgvector).
上面提到问题(多扫描了99999行)的根源是index排序<->和filter的<是2个操作符, executor并不知道已经排序返回的情况下filter可以在第一次判断false后面就没有满足条件的tuple了, 而是扫描了整个索引.
通常的解决办法有2种:
1、用cte 包一层. 带来的后果是可能返回的数据比实际需要的少. 或者里面的limit要比外面的limit一些. 例如: 要返回M行, with a (select ... order by ... limit N) select ... where ... order by ... limit M; 实际使用时N要大于M
2、游标. 这个倒是可以严格返回M行, 但是写法复杂, 需要业务进行判断.
下面的文章中有以上2种方法的相应例子: 见 https://github.com/digoal/blog
《PostgreSQL GiST Order by 距离 + 距离范围判定 + limit 骤变/骤降优化与背景原因》 《PostgreSQL 优化器案例之 - order by limit 索引选择问题》 《GIS附近查找性能优化 - PostGIS long lat geometry distance search tuning using gist knn function》 《HTAP数据库 PostgreSQL 场景与性能测试之 6 - (OLTP) 空间应用 - KNN查询（搜索附近对象，由近到远排序输出）》
迭代式索引扫描方法
迭代式索引扫描方法解决了前面提到的index排序和filter操作符“分开没有协作”带来的额外扫描问题. 带来的效果类似游标的方法, 找到符合记录条数就会结束索引扫描, 而不会产生额外的索引扫描. 另外还有2个参数可以控制最多扫描多少条索引条目(思路类似于gin_fuzzy_search_limit参数, 避免扫描行术过多带来性能瓶颈).
Added in 0.8.0
With approximate indexes, queries with filtering can return less results since filtering is applied after the index is scanned. Starting with 0.8.0, you can enable iterative index scans, which will automatically scan more of the index until enough results are found (or it reaches hnsw.max_scan_tuples or ivfflat.max_probes).
Iterative scans can use strict or relaxed ordering.
Strict ensures results are in the exact order by distance
SET hnsw.iterative_scan = strict_order; -- 严格按索引排序
Relaxed allows results to be slightly out of order by distance, but provides better recall
SET hnsw.iterative_scan = relaxed_order; -- 松散顺序
# or
SET ivfflat.iterative_scan = relaxed_order;
With relaxed ordering, you can use a materialized CTE to get strict ordering
WITH relaxed_results AS MATERIALIZED (
SELECT id, embedding <-> '[1,2,3]' AS distance FROM items WHERE category_id = 123 ORDER BY distance LIMIT 5
) SELECT * FROM relaxed_results ORDER BY distance;
For queries that filter by distance, use a materialized CTE and place the distance filter outside of it for best performance (due to the current behavior of the Postgres executor)
WITH nearest_results AS MATERIALIZED (
SELECT id, embedding <-> '[1,2,3]' AS distance FROM items ORDER BY distance LIMIT 5
) SELECT * FROM nearest_results WHERE distance < 5 ORDER BY distance; -- 返回可能少于5条
Note: Place any other filters inside the CTE
Iterative Scan Options
Since scanning a large portion of an approximate index is expensive, there are options to control when a scan ends.
HNSW
Specify the max number of tuples to visit (20,000 by default)
SET hnsw.max_scan_tuples = 20000; -- 这是另一个限定词, 最多扫描这么多行, 避免召回结果太多. 思路类似于gin_fuzzy_search_limit
Note: This is approximate and does not affect the initial scan
Specify the max amount of memory to use, as a multiple of work_mem (1 by default)
SET hnsw.scan_mem_multiplier = 2;
Note: Try increasing this if increasing hnsw.max_scan_tuples does not improve recall
IVFFlat
Specify the max number of probes
SET ivfflat.max_probes = 100;
Note: If this is lower than ivfflat.probes, ivfflat.probes will be used
在PolarDB中部署pgvector很简单
使用如下容器环境:
《PolarDB PG 15 编译安装 & pg_duckdb 插件 + OSS 试用》
# 进入容器
cd /data
git clone --depth 1 -b v0.8.0 https://github.com/pgvector/pgvector
USE_PGXS=1 make install
create extension vector ;
postgres=# \dx
List of installed extensions
Name | Version | Schema | Description
---------------------+---------+------------+------------------------------------------------------
pg_duckdb | 0.2.0 | public | DuckDB Embedded in Postgres
plpgsql | 1.0 | pg_catalog | PL/pgSQL procedural language
polar_feature_utils | 1.0 | pg_catalog | PolarDB feature utilization
vector | 0.8.0 | public | vector data type and ivfflat and hnsw access methods
(4 rows)
参考
《PostgreSQL GiST Order by 距离 + 距离范围判定 + limit 骤变/骤降优化与背景原因》 《PostgreSQL 优化器案例之 - order by limit 索引选择问题》 《GIS附近查找性能优化 - PostGIS long lat geometry distance search tuning using gist knn function》 《HTAP数据库 PostgreSQL 场景与性能测试之 6 - (OLTP) 空间应用 - KNN查询（搜索附近对象，由近到远排序输出）》
今日荐书
彩蛋:国产数据库周边生态
当然一款数据库要流行起来, 除了自己要强大, 还离不开生态. 用好周边生态工具, 管理水平战胜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) 及视频号:
再发个招聘广告, 上市公司全国招牌PG、MySQL数据库专家: