时间、空间、对象 海量极速多维检索 - 阿里云RDS PostgreSQL最佳实践
时间：2022-08-07 19:30:00
标签
PostgreSQL , 时间 , 空间 , 对象属性 , 多维度检索 , 海量 , 空间索引 , 数据分区 , 块级索引BRIN , 多级索引 , GIN倒排索引 , JSON索引 , 多列索引 , 多索引扫描合并 , bitmapAnd , bitmapOr , 物理扫描 , ctid扫描 , intersect , partial index , partition index
背景
人类或其他物体的活动产生了大量的时间和空间数据。如果有科技能回到过去，过去的世界状态会是什么？
事实上，这种需求也存在于数据库中。
对象数据分类
一种是静态数据(相对静态，如建筑物)，另一种是动态数据(如人类活动、物联网传感器活动)。
搜索需求分类
1、时空快照数据搜索
我们可以这样来理解，有一些对象产生数据的频率较低，例如建筑物，道路等相对较为惰性的对象，可能几年都不会变化一次，那么这类对象产生的数据写入到数据库中，我们按时间范围（例如2017-07-01到2017-07-02）去查询，你可能查不到这类对象的数据。因为它们在这个时间段就没有数据写入到数据库中。
如果要查询过去某个时间点所有对象的最终状态，可以用以下方法毫秒构建所有对象的最终状态:
《PostgreSQL 海量时序数据(实时统计分析任何滑动窗口) - 跟踪传感器、人群、物体等对象
2.搜索时空行为数据
时空行为数据是指运动对象产生的FEED数据，例如人类的活动。
例如，我们应该分析某一时期在某一地区活动的人群特征。周末大学附近是否经常有皮条客。
时空快照不在本文讨论范畴，有需要可以参考我前面写的文章。我们接下来说说时空行为数据搜索。
数据结构
包含时间、空间、对象描述三种属性的数据。
非结构化数据结构：
create table test(
id int8,
crt_time timestamp, -- 时间
pos geometry, -- 位置
obj jsonb -- 对象描述
);
对象描述除了使用JSON，也可以使用结构化的数据(例如)：
create table test(
id int8,
crt_time timestamp, -- 时间
pos geometry, -- 位置
c1 int, -- 一些属性的例子
c2 int,
c3 text,
c4 float8,
c5 int,
c6 date,
c7 text,
c8 int,
c9 int,
c10 int
);
时空行为查询SQL例子如下
select * from test
where
pos <-> ? < ?
and crt_time between ? and ?
and ( (c1 = ? and c2 between ? and ?) or c10=?)
...
;
优化思路
首先是一些散的知识点，如下：
1、时序块级索引
crt_time字段表示数据生成的时间，是一个时序字段，在PostgreSQL堆存储中，存储与这个字段的值线性相关性特别好。
所以使用块级索引是特别适合的。
我在一个TPC-H的测试中，使用BRIN块级索引代替分区表，在大范围搜索时，性能甚至超越了分区表的性能。
create index idx_test_1 on test using brin(crt_time);
应用案例
《PostgreSQL 物联网黑科技 - 瘦身几百倍的索引(BRIN index)》
2、空间索引
空间检索，自然要用上空间索引，在PostgreSQL中有3种方法可以实现空间搜索。
1、GIST索引，针对geometry类型的索引。
create index idx_test_2 on test using gist(pos);
这个索引支持空间KNN搜索，空间位置判断等。
2、SPGIST索引，针对geometry类型的索引。
create index idx_test_2 on test using spgist(pos);
这个索引支持空间KNN搜索，空间位置判断等。
3、GEOHASH和BTREE索引，将经纬度转换为GEOHASH，对HASH VALUE创建BTREE索引。使用表达式索引即可。
create index idx_test_3 on test using btree( ST_GeoHash(pos,15) );
这个索引支持prefix搜索（从而实现编码后的地理位置信息网格包含的关系）。属于LOSSY索引，需要二次过滤。
GiST、SPGiST 空间索引可以获得最精确的位置信息，比GEOHASH要好，但是查询时需要注意，下面是优化方法，性能可以提升几个数量级。
《GIS附近查找性能优化 - PostGIS long lat geometry distance search tuning using gist knn function》
3、GIN 倒排索引
对于对象属性字段JSONB，或者是结构化的对象属性多个字段。使用GIN倒排即可。
例如
create extension btree_gin;
非结构化索引：
create index idx_test_4 on test using gin( obj );
结构化索引
create index idx_test_4 on test using gin( c1,c2,c3,c4,c5,c6,c7,c8,c9 );
4、bitmapAnd bitmapOr
前面对所有查询维度，根据数据的类型不同以及查询需求的差异，选择了不同的索引接口。
但是这么多索引，能同时使用吗？PostgreSQL为多个索引提供了bitmapAnd, bitmapOr接口，可以将多个索引搜索合并起来，减少扫描的数据库数量。
原理如下：
《PostgreSQL bitmapAnd, bitmapOr, bitmap index scan, bitmap heap scan》
例如：
select * from test where
c1 ...
and crt_time between ? and ?
and test->>'c1' in (?, ? ...);
会根据统计信息，自动使用对应的索引，如果有必要，会使用多个索引进行bitmapAnd 或 bitmapOr的合并扫描，SKIP不需要扫描的PAGE，对于命中的PAGE进行RECHECK。
5、堆表存储分级、分区
存储分级，可以分为一级或者多级：
1、一级分区：
例如按时间进行分区。
create table test(
id int8,
crt_time timestamp, -- 时间
pos geometry, -- 位置
obj jsonb -- 对象描述
)
PARTITION BY range (crt_time)
;
create table test_201701 PARTITION OF test for values FROM ('2017-01-01') TO ('2017-02-01');
......
2、多级分区
例如按时间，再按GEOHASH进行范围分区。
create table test_201701 PARTITION OF test for values FROM ('2017-01-01') TO ('2017-02-01') partition by range(st_geohash(pos,15));
...
create table test_201701_prefix1 PARTITION OF test for values FROM ('xxxx1') TO ('xxxx2'); -- 在地图上生成BOX（GRID），找到对应的边界，用边界作为分区条件
使用分区后，查询条件带有分区键（例如时间、空间范围）时可以落到对应分区，从而减少数据扫描。
再针对对象属性建立GIN索引，可以实现极端高效的查询。
6、索引分级、分区
与数据类似，在不使用分区表的情况下，索引也是支持分区逻辑的，例如
《分区索引的应用和实践 - 阿里云RDS PostgreSQL最佳实践》
例子
空间索引 + 时间分区
create index idx_20170101 on tbl using gist (pos) where crt_time between '2017-01-01' and '2017-01-02';
...
create index idx_20170102 on tbl using gist (pos) where crt_time between '2017-01-02' and '2017-01-03';
...
使用以上分区索引，在输入时间段进行空间搜索时，可以快速定位数据。
select * from tbl
where crt_time between '2017-01-01' and '2017-01-02' -- 时间条件
and (pos <-> ?) < ? -- 与某被搜索点的距离条件
and ? -- 其他条件
order by pos <-> ? -- 按距离远近排序
limit ?; -- 输出若干条
甚至可以加入更多层级的索引分区，比如某个维度（对象属性）是常用搜索条件，例如店铺类别（假设可枚举，或是一个较小范围的数量）。
create index idx_20170101_mod0 on tbl using gist (pos) where crt_time between '2017-01-01' and '2017-01-02' and dtype=0;
...
create index idx_20170101_mod1 on tbl using gist (pos) where crt_time between '2017-01-01' and '2017-01-02' and dtype=1;
...
使用以上分区索引，在输入时间段以及某些特定条件进行空间搜索时，可以快速定位数据。
select * from tbl
where crt_time between '2017-01-01' and '2017-01-02' -- 时间条件
and (pos <-> ?) < ? -- 与某被搜索点的距离条件
and dtype=0 -- 对象条件
and ? -- 其他条件
order by pos <-> ? -- 按距离远近排序
limit ?; -- 输出若干条
注意，以上SQL可以有极端性能优化的方法，参见：
《GIS附近查找性能优化 - PostGIS long lat geometry distance search tuning using gist knn function》
索引本身的组织形式，或者说索引结构，可以按逻辑分区进行重构，类似以上创建索引的方法，覆盖所有的条件。
7、CTID intersect array JOIN SCAN
前面说了多个索引，或者GIN索引的内部会自动进行BitmapAnd，BitmapOr合并扫描，实际上我们在SQL中，也可以明确进行这类扫描。
每个条件筛选出对应的CTID
使用intersect，UNION生成最终复合条件的CTID。（intersect对应and条件, union对应or条件。）
生成ctid的array, 使用ctid扫描用法如下
《在PostgreSQL中实现update | delete limit》
例子
1、创建对象FEED数据表
postgres=# create table tbl (id int, info text, crt_time timestamp, pos point, c1 int , c2 int, c3 int );
CREATE TABLE
2、写入5000万测试数据
postgres=# insert into tbl select generate_series(1,50000000), md5(random()::text), clock_timestamp(), point(180-random()*180, 90-random()*90), random()*10000, random()*5000, random()*1000;
INSERT 0 50000000
3、创建对象索引
postgres=# create index idx_tbl_1 on tbl using gin (info, c1, c2, c3);
CREATE INDEX
4、创建时间索引
postgres=# create index idx_tbl_2 on tbl using btree (crt_time);
CREATE INDEX
5、创建空间索引
postgres=# create index idx_tbl_3 on tbl using gist (pos);
CREATE INDEX
6、生成数据layout，方便后面的查询
postgres=# select min(crt_time),max(crt_time),count(*) from tbl;
min | max | count
----------------------------+----------------------------+----------
2017-07-22 17:59:34.136497 | 2017-07-22 18:01:27.233688 | 50000000
(1 row)
7、创建KNN极端查询函数
create or replace function ff(point, float8, int) returns setof tid as $$
declare
v_rec record;
v_limit int := $3;
begin
set local enable_seqscan=off; -- 强制索引, 扫描行数够就退出.
for v_rec in
select *,
(pos <-> $1) as dist,
ctid
from tbl
order by pos <-> $1
loop
if v_limit <=0 then
-- raise notice '已经取足数据';
return;
end if;
if v_rec.dist > $2 then
-- raise notice '满足条件的点已输出完毕';
return;
else
return next v_rec.ctid;
end if;
v_limit := v_limit -1;
end loop;
end;
$$ language plpgsql strict volatile;
postgres=# select * from ff(point '(100,100)',100,100) ;
ff
-------------
(407383,11)
(640740,9)
(26073,51)
(642750,34)
...
(100 rows)
Time: 1.061 ms
8、ctid合并检索
输出满足以下条件的记录
(
c1 in (1,2,3,4,100,200,99,88,77,66,55)
or
c2 < 10
)
and
pos <-> point '(0,0)' < 5
and
crt_time between '2017-07-22 17:59:34' and '2017-07-22 17:59:40';
首先进行条件分解，了解一下每个条件有多少记录，以及使用索引扫描的时间开销。
1、54907条。
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl where c1 in (1,2,3,4,100,200,99,88,77,66,55);
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on postgres.tbl (cost=820.07..65393.94 rows=54151 width=73) (actual time=23.842..91.911 rows=54907 loops=1)
Output: id, info, crt_time, pos, c1, c2, c3
Recheck Cond: (tbl.c1 = ANY ('{1,2,3,4,100,200,99,88,77,66,55}'::integer[]))
Heap Blocks: exact=52778
Buffers: shared hit=52866
-> Bitmap Index Scan on idx_tbl_1 (cost=0.00..806.54 rows=54151 width=0) (actual time=14.264..14.264 rows=54907 loops=1)
Index Cond: (tbl.c1 = ANY ('{1,2,3,4,100,200,99,88,77,66,55}'::integer[]))
Buffers: shared hit=88
Planning time: 0.105 ms
Execution time: 94.606 ms
(10 rows)
2、95147条。
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl where c2<10;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on postgres.tbl (cost=835.73..112379.10 rows=99785 width=73) (actual time=69.243..179.388 rows=95147 loops=1)
Output: id, info, crt_time, pos, c1, c2, c3
Recheck Cond: (tbl.c2 < 10)
Heap Blocks: exact=88681
Buffers: shared hit=88734
-> Bitmap Index Scan on idx_tbl_1 (cost=0.00..810.79 rows=99785 width=0) (actual time=53.612..53.612 rows=95147 loops=1)
Index Cond: (tbl.c2 < 10)
Buffers: shared hit=53
Planning time: 0.094 ms
Execution time: 186.201 ms
(10 rows)
3、149930条。（PostgreSQL使用了bitmapOr进行合并扫描，快速的得到结果）
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl where c1 in (1,2,3,4,100,200,99,88,77,66,55) or c2 <10;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on postgres.tbl (cost=1694.23..166303.58 rows=153828 width=73) (actual time=98.988..266.852 rows=149930 loops=1)
Output: id, info, crt_time, pos, c1, c2, c3
Recheck Cond: ((tbl.c1 = ANY ('{1,2,3,4,100,200,99,88,77,66,55}'::integer[])) OR (tbl.c2 < 10))
Heap Blocks: exact=134424
Buffers: shared hit=134565
-> BitmapOr (cost=1694.23..1694.23 rows=153936 width=0) (actual time=73.763..73.763 rows=0 loops=1)
Buffers: shared hit=141
-> Bitmap Index Scan on idx_tbl_1 (cost=0.00..806.54 rows=54151 width=0) (actual time=16.733..16.733 rows=54907 loops=1)
Index Cond: (tbl.c1 = ANY ('{1,2,3,4,100,200,99,88,77,66,55}'::integer[]))
Buffers: shared hit=88
-> Bitmap Index Scan on idx_tbl_1 (cost=0.00..810.79 rows=99785 width=0) (actual time=57.029..57.029 rows=95147 loops=1)
Index Cond: (tbl.c2 < 10)
Buffers: shared hit=53
Planning time: 0.149 ms
Execution time: 274.548 ms
(15 rows)
4、60687条。（我们使用了KNN的变态性能优化方法，依旧需要195毫秒）
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from ff(point '(0,0)',5,1000000);
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Function Scan on postgres.ff (cost=0.25..10.25 rows=1000 width=6) (actual time=188.563..192.114 rows=60687 loops=1)
Output: ff
Function Call: ff('(0,0)'::point, '5'::double precision, 1000000)
Buffers: shared hit=61296
Planning time: 0.029 ms
Execution time: 195.097 ms
(6 rows)
如果不使用KNN优化，看看需要多久。
惊不惊喜、意不意外，极端优化性能提升了1个数量级。
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl where pos<-> point '(0,0)' < 5 ;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
Seq Scan on postgres.tbl (cost=0.00..1416667.00 rows=16666667 width=73) (actual time=0.016..6393.542 rows=60687 loops=1)
Output: id, info, crt_time, pos, c1, c2, c3
Filter: ((tbl.pos <-> '(0,0)'::point) < '5'::double precision)
Rows Removed by Filter: 49939313
Buffers: shared hit=666667
Planning time: 0.090 ms
Execution time: 6397.087 ms
(7 rows)
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl where pos<-> point '(0,0)' < 5 order by pos<-> point '(0,0)';
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------
Index Scan using idx_tbl_3 on postgres.tbl (cost=0.42..2623952.79 rows=16666667 width=81) (actual time=0.088..83076.718 rows=60687 loops=1)
Output: id, info, crt_time, pos, c1, c2, c3, (pos <-> '(0,0)'::point)
Order By: (tbl.pos <-> '(0,0)'::point)
Filter: ((tbl.pos <-> '(0,0)'::point) < '5'::double precision)
Rows Removed by Filter: 49939313
Buffers: shared hit=50454244
Planning time: 0.097 ms
Execution time: 83080.970 ms
(8 rows)
5、2640751条。
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl where crt_time between '2017-07-22 17:59:34' and '2017-07-22 17:59:40';
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------
Index Scan using idx_tbl_2 on postgres.tbl (cost=0.56..90860.33 rows=2462443 width=73) (actual time=0.017..444.194 rows=2640751 loops=1)
Output: id, info, crt_time, pos, c1, c2, c3
Index Cond: ((tbl.crt_time >= '2017-07-22 17:59:34'::timestamp without time zone) AND (tbl.crt_time <= '2017-07-22 17:59:40'::timestamp without time zone))
Buffers: shared hit=42430
Planning time: 0.140 ms
Execution time: 567.451 ms
(6 rows)
使用所有的索引，逐个条件扫描，并得到ctid，然后进行CTID扫描，我们可以拆解来看：
首先我们看一下时间、对象属性的合并查询，哇，COOL!!!，由于时使用了bitmapAnd, bitmapOr，使得SKIP了大多数的数据块，因此扫描时间比单一索引扫描要短。
注意到这一步操作，记录数直接降到了7847条。
postgres=# explain (analyze,verbose,timing,costs,buffers) select ctid from tbl
where crt_time between '2017-07-22 17:59:34' and '2017-07-22 17:59:40'
and (
c1 in (1,2,3,4,100,200,99,88,77,66,55)
or
c2 < 10
);
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on postgres.tbl (cost=35025.85..44822.94 rows=7576 width=6) (actual time=205.577..214.821 rows=7847 loops=1)
Output: ctid
Recheck Cond: (((tbl.c1 = ANY ('{1,2,3,4,100,200,99,88,77,66,55}'::integer[])) OR (tbl.c2 < 10)) AND (tbl.crt_time >= '2017-07-22 17:59:34'::timestamp without time zone) AND (tbl.crt_time <= '2017-07-22 17:59:40'::timestamp without time zone))
Heap Blocks: exact=6983
Buffers: shared hit=14343
-> BitmapAnd (cost=35025.85..35025.85 rows=7581 width=0) (actual time=204.048..204.048 rows=0 loops=1)
Buffers: shared hit=7360
-> BitmapOr (cost=1621.11..1621.11 rows=153936 width=0) (actual time=70.279..70.279 rows=0 loops=1)
Buffers: shared hit=141
-> Bitmap Index Scan on idx_tbl_1 (cost=0.00..806.54 rows=54151 width=0) (actual time=15.860..15.860 rows=54907 loops=1)
Index Cond: (tbl.c1 = ANY ('{1,2,3,4,100,200,99,88,77,66,55}'::integer[]))
Buffers: shared hit=88
-> Bitmap Index Scan on idx_tbl_1 (cost=0.00..810.79 rows=99785 width=0) (actual time=54.418..54.418 rows=95147 loops=1)
Index Cond: (tbl.c2 < 10)
Buffers: shared hit=53
-> Bitmap Index Scan on idx_tbl_2 (cost=0.00..33402.60 rows=2462443 width=0) (actual time=127.101..127.101 rows=2640751 loops=1)
Index Cond: ((tbl.crt_time >= '2017-07-22 17:59:34'::timestamp without time zone) AND (tbl.crt_time <= '2017-07-22 17:59:40'::timestamp without time zone))
Buffers: shared hit=7219
Planning time: 0.203 ms
Execution time: 216.697 ms
(20 rows)
然后我们看看KNN的扫描时长：
注意到符合KNN距离条件的数据有60687条，所以我会引出CTID合并扫描与原始扫描方法性能对比问题的解释。
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from ff(point '(0,0)',5,1000000);
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Function Scan on postgres.ff (cost=0.25..10.25 rows=1000 width=6) (actual time=188.563..192.114 rows=60687 loops=1)
Output: ff
Function Call: ff('(0,0)'::point, '5'::double precision, 1000000)
Buffers: shared hit=61296
Planning time: 0.029 ms
Execution time: 195.097 ms
(6 rows)
最后，我们将这几个合并成CTID
select * from ff(point '(0,0)',5,1000000)
intersect
select ctid from tbl
where crt_time between '2017-07-22 17:59:34' and '2017-07-22 17:59:40'
and (
c1 in (1,2,3,4,100,200,99,88,77,66,55)
or
c2 < 10
);
ff
------------
(1394,8)
(3892,50)
(6124,45)
(7235,8)
(7607,45)
(11540,8)
(13397,31)
(14266,36)
(18149,7)
(19256,44)
(24671,62)
(26525,64)
(30235,48)
(13 rows)
Time: 463.012 ms
最终章，得到最终记录。
select * from tbl where ctid = any
(
array( -- array start
select * from ff(point '(0,0)',5,1000000) intersect select ctid from tbl
where crt_time between '2017-07-22 17:59:34' and '2017-07-22 17:59:40'
and (
c1 in (1,2,3,4,100,200,99,88,77,66,55)
or
c2 < 10
)
) -- array end
);
id | info | crt_time | pos | c1 | c2 | c3
---------+----------------------------------+----------------------------+----------------------------------------+------+------+-----
104558 | c4699c933d4e2d2a10d828c4ff0b3362 | 2017-07-22 17:59:34.362508 | (4.20534582808614,2.43749532848597) | 99 | 4858 | 543
291950 | 1c2901689ab1eb7653d8ad972f7aa376 | 2017-07-22 17:59:34.776808 | (2.5384977646172,1.09820357523859) | 3 | 2131 | 360
459345 | 9e46548f29d914019ce53a589be8ebac | 2017-07-22 17:59:35.148699 | (0.715781506150961,3.1486327573657) | 1 | 1276 | 8
542633 | c422d6137f9111d5c2dc723b40c7023f | 2017-07-22 17:59:35.334278 | (0.0631888210773468,2.2334903664887) | 4968 | 3 | 245
570570 | fc57bfc6b7781d89b17c90417bd306f7 | 2017-07-22 17:59:35.39653 | (3.14926156774163,1.04107855819166) | 88 | 2560 | 561
865508 | 34509c7f7640afaf288a5e1d38199701 | 2017-07-22 17:59:36.052573 | (3.12869547866285,2.34822122845799) | 2 | 65 | 875
1004806 | afe9f88cbebf615a7ae5f41180c4b33f | 2017-07-22 17:59:36.362027 | (1.13972157239914,3.28763140831143) | 3 | 1639 | 208
1069986 | 6b9f27bfde993fb0bae3336ac010af7a | 2017-07-22 17:59:36.507775 | (4.51995821669698,2.08761331625283) | 2 | 200 | 355
1361182 | 7c4c1c208c2b2b21f00772c43955d238 | 2017-07-22 17:59:37.155127 | (1.7334086727351,2.18367457855493) | 9742 | 0 | 232
1444244 | 41bf6f8e4b89458c13fb408a7db05284 | 2017-07-22 17:59:37.339594 | (0.52773853763938,2.16670122463256) | 1 | 2470 | 820
1850387 | 6e0011c6db76075edd2aa7f81ec94129 | 2017-07-22 17:59:38.243091 | (0.0168232340365648,0.420973123982549) | 100 | 4395 | 321
1989439 | 6211907ac254a4a3ca54f90822a2095e | 2017-07-22 17:59:38.551637 | (0.0274275150150061,0.490507003851235) | 1850 | 5 | 74
2267673 | 898fdd54dcc5b14c27cf1c8b9afe2471 | 2017-07-22 17:59:39.170035 | (0.394239127635956,2.86229319870472) | 2892 | 6 | 917
(13 rows)
Time: 462.715 ms
最终耗时462毫秒。
