时间、空间、对象多维属性 海量数据任意多维 高效检索 - 阿里云RDS PostgreSQL最佳实践

14 minute read

背景

人类或者其他对象的活动产生了海量的时间、空间数据,如果有科技能实现回到过去,过去的世界状态会是什么样的?

实际上这个需求在数据库中也存在。

对象数据分类

一类为静止数据(相对静止,比如建筑物),一类为动态数据(比如人类活动,物联网传感器的活动)。

搜索需求分类

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》

Heap, one square = one page:  
+---------------------------------------------+  
|c____u_____X___u___X_________u___cXcc______u_|  
+---------------------------------------------+  
Rows marked c match customers pkey condition.  
Rows marked u match username condition.  
Rows marked X match both conditions.  
  
  
Bitmap scan from customers_pkey:  
+---------------------------------------------+  
|100000000001000000010000000000000111100000000| bitmap 1  
+---------------------------------------------+  
One bit per heap page, in the same order as the heap  
Bits 1 when condition matches, 0 if not  
  
Bitmap scan from ix_cust_username:  
+---------------------------------------------+  
|000001000001000100010000000001000010000000010| bitmap 2  
+---------------------------------------------+  
Once the bitmaps are created a bitwise AND is performed on them:  
  
+---------------------------------------------+  
|100000000001000000010000000000000111100000000| bitmap 1  
|000001000001000100010000000001000010000000010| bitmap 2  
 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&  
|000000000001000000010000000000000010000000000| Combined bitmap  
+-----------+-------+--------------+----------+  
            |       |              |  
            v       v              v  
Used to scan the heap only for matching pages:  
+---------------------------------------------+  
|___________X_______X______________X__________|  
+---------------------------------------------+  
The bitmap heap scan then seeks to the start of each page and reads the page:  
  
+---------------------------------------------+  
|___________X_______X______________X__________|  
+---------------------------------------------+  
seek------->^seek-->^seek--------->^  
            |       |              |  
            ------------------------  
            only these pages read  

例如:

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》](../201608/20160827_01.md)

例子

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毫秒。

9、采用原始SQL,性能如何呢? - PostgreSQL 多索引bitmapAnd bitmapOr skip scan

直写SQL,不使用CTID合并扫描。

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'   
  and (   
    c1 in (1,2,3,4,100,200,99,88,77,66,55)  
      or  
    c2 < 10  
    )  
  and  
  pos <-> point '(0,0)' < 5;  
  
  
 Bitmap Heap Scan on postgres.tbl  (cost=35022.06..44857.06 rows=2525 width=73) (actual time=205.542..214.547 rows=13 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)) 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))  
   Filter: ((tbl.pos <-> '(0,0)'::point) < '5'::double precision)  
   Rows Removed by Filter: 7834  
   Heap Blocks: exact=6983  
   Buffers: shared hit=14343  
   ->  BitmapAnd  (cost=35022.06..35022.06 rows=7581 width=0) (actual time=203.620..203.620 rows=0 loops=1)  
         Buffers: shared hit=7360  
         ->  BitmapOr  (cost=1618.58..1618.58 rows=153936 width=0) (actual time=71.660..71.660 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=14.861..14.861 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=56.797..56.797 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=125.255..125.255 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.160 ms  
 Execution time: 216.797 ms  
(22 rows)  

COOL!!!,也是意料之中的,因为我们前面已经解释了,出去KNN条件,其他条件已经将结果收敛到7000多条了,所以完全没有必要使用KNN的索引(符合KNN条件的记录数有60687条,所以使用KNN索引扫描都花了195毫秒)。

结果验证:

select * 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  
    )    
  and    
  pos <-> point '(0,0)' < 5;    
  
   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)  

分区索引例子

假设我们还是以上查询条件,同时我们使用了分区索引,那么能达到什么样的效果呢?

(这里为了演示分区索引带来的极端效果,所以这么干的,实际上现实情况可能收敛得没有这么严重,例如按天、按ID HASH等进行收敛。只要能收敛,就一样能达到很好的效果。)

postgres=# create index idx_tbl_4 on tbl using gist (pos) 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  
    )  ;  
  
CREATE INDEX  
Time: 8359.330 ms (00:08.359)  

重构极端KNN优化函数

create or replace function ff(point, float8, int) returns setof record as $$                                                          
declare  
  v_rec record;  
  v_limit int := $3;  
begin  
  set local enable_seqscan=off;   -- 强制索引, 扫描行数够就退出.  
  for v_rec in   
    select *,  
    (pos <-> $1) as dist  
    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  
    )  
    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;  
    end if;  
    v_limit := v_limit -1;  
  end loop;  
end;  
$$ language plpgsql strict volatile;  

查询性能:

postgres=# select * from ff(point '(0,0)', 5, 10000000) as t(id int, info text, crt_time timestamp, pos point, c1 int, c2 int, c3 int, dist float8);   
   id    |               info               |          crt_time          |                  pos                   |  c1  |  c2  | c3  |       dist          
---------+----------------------------------+----------------------------+----------------------------------------+------+------+-----+-------------------  
 1850387 | 6e0011c6db76075edd2aa7f81ec94129 | 2017-07-22 17:59:38.243091 | (0.0168232340365648,0.420973123982549) |  100 | 4395 | 321 | 0.421309141034319  
 1989439 | 6211907ac254a4a3ca54f90822a2095e | 2017-07-22 17:59:38.551637 | (0.0274275150150061,0.490507003851235) | 1850 |    5 |  74 |  0.49127323294376  
 1444244 | 41bf6f8e4b89458c13fb408a7db05284 | 2017-07-22 17:59:37.339594 | (0.52773853763938,2.16670122463256)    |    1 | 2470 | 820 |  2.23004532710301  
  542633 | c422d6137f9111d5c2dc723b40c7023f | 2017-07-22 17:59:35.334278 | (0.0631888210773468,2.2334903664887)   | 4968 |    3 | 245 |  2.23438404136508  
  291950 | 1c2901689ab1eb7653d8ad972f7aa376 | 2017-07-22 17:59:34.776808 | (2.5384977646172,1.09820357523859)     |    3 | 2131 | 360 |  2.76586731309247  
 1361182 | 7c4c1c208c2b2b21f00772c43955d238 | 2017-07-22 17:59:37.155127 | (1.7334086727351,2.18367457855493)     | 9742 |    0 | 232 |  2.78803520274409  
 2267673 | 898fdd54dcc5b14c27cf1c8b9afe2471 | 2017-07-22 17:59:39.170035 | (0.394239127635956,2.86229319870472)   | 2892 |    6 | 917 |  2.88931598221975  
  459345 | 9e46548f29d914019ce53a589be8ebac | 2017-07-22 17:59:35.148699 | (0.715781506150961,3.1486327573657)    |    1 | 1276 |   8 |  3.22896754478952  
  570570 | fc57bfc6b7781d89b17c90417bd306f7 | 2017-07-22 17:59:35.39653  | (3.14926156774163,1.04107855819166)    |   88 | 2560 | 561 |  3.31688000783581  
 1004806 | afe9f88cbebf615a7ae5f41180c4b33f | 2017-07-22 17:59:36.362027 | (1.13972157239914,3.28763140831143)    |    3 | 1639 | 208 |  3.47958123047986  
  865508 | 34509c7f7640afaf288a5e1d38199701 | 2017-07-22 17:59:36.052573 | (3.12869547866285,2.34822122845799)    |    2 |   65 | 875 |  3.91188935630676  
  104558 | c4699c933d4e2d2a10d828c4ff0b3362 | 2017-07-22 17:59:34.362508 | (4.20534582808614,2.43749532848597)    |   99 | 4858 | 543 |  4.86069100130757  
 1069986 | 6b9f27bfde993fb0bae3336ac010af7a | 2017-07-22 17:59:36.507775 | (4.51995821669698,2.08761331625283)    |    2 |  200 | 355 |  4.97877009299311  
(13 rows)  
  
Time: 0.592 ms  

SO COOL!!!,从200多毫秒,优化到了0.几个毫秒。

优化思路小结

回顾优化方法,

1、对不同的数据类型,构建不同的索引。

例如空间gist或spgist索引、时间btree或brin索引、对象多种属性(倒排)gin索引。

索引的目的是降低数据扫描的范围。

2、方法5,提到了数据分区,数据分区的目的是让数据有意识的组织,这里指的意识是根据搜索的需求进行有意识的组织。例如时间是必要查询条件,或者常用查询条件,那么可以对数据按时间切分(分区),从而降低扫描的量。

3、方法6,提到了索引分区,目的和方法5类似,只是在索引层面进行了这样的分布,从而在索引扫描时,直接提高数据的命中率。

4、方法7,CTID合并扫描,与PostgreSQL 多索引的bitmapAnd, bitmapOr扫描的思想类似,bitmapAnd/bitmapOr是跳过不需要扫描的BLOCK,而方法7的ctid合并扫描则是跳过不需要扫描的行。

将多个索引扫描得到的CTID进行合并。跳过不需要扫描的行号。

如果某个过滤条件可以将CTID(记录数)降到很低(其他条件为AND条件)的情况下,则没有必要使用CTID合并扫描,其他条件使用FILTER即可(增加一点点CPU开销)。

5、以无法为有法,以无限为有限,此乃武术最高境界。

在PostgreSQL中,实现了多索引的bitmapAnd, bitmapOr扫描,极大的提高了多个条件(索引)带来的数据命中率。

《PostgreSQL bitmapAnd, bitmapOr, bitmap index scan, bitmap heap scan》

并且PostgreSQL有很好的CBO估算机制,使得PG不会要一味的使用上所有的索引进行BITMAP合并扫描。这也是为什么章节“采用原始SQL,性能如何呢? - PostgreSQL 多索引bitmapAnd bitmapOr skip scan”性能更优秀的原因。

6、极端的优化是什么样的?

采样方法5或在方法6,以可以固定的条件作为分区键,对数据或索引进行分区。

对于其他条件,可以使用PostgreSQL中多索引的bitmapAnd, bitmapOr扫描,提高多个输入条件(索引)带来的数据命中率。

我们可以看到,在5000万数据中,按时间、空间、对象属性进行多维检索,性能提升到了0.592毫秒。

7、对于空间数据,除了使用GiST索引,我们还有一个更省成本的索引BRIN索引,按st_geohash规整数据后,过滤性非常棒。建议一定要看一下,你会开阔更多的优化思路的:

《PostGIS空间索引(GiST、BRIN、R-Tree)选择、优化 - 阿里云RDS PostgreSQL最佳实践》

《PostgreSQL BRIN索引的pages_per_range选项优化与内核代码优化思考》

《Greenplum 空间(GIS)数据检索 b-tree & GiST 索引实践 - 阿里云HybridDB for PostgreSQL最佳实践》

《通过空间思想理解GiST索引的构造》

参考

《多字段,任意组合条件查询(无需建模) - 毫秒级实时圈人 最佳实践》

Flag Counter

digoal’s 大量PostgreSQL文章入口