时间、空间、对象海量极速多维检索 - 阿里云RDS PostgreSQL最佳实践-阿里云开发者社区

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

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

参考

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

时间、空间、对象海量极速多维检索 - 阿里云RDS PostgreSQL最佳实践

标签

背景

对象数据分类

搜索需求分类

数据结构

优化思路

1、时序块级索引

2、空间索引

3、GIN 倒排索引

4、bitmapAnd bitmapOr

5、堆表存储分级、分区

6、索引分级、分区

7、CTID intersect array JOIN SCAN

例子

1、创建对象FEED数据表

2、写入5000万测试数据

3、创建对象索引

4、创建时间索引

5、创建空间索引

6、生成数据layout，方便后面的查询

7、创建KNN极端查询函数

8、ctid合并检索

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

分区索引例子

优化思路小结

参考

关系型数据库

热门文章

最新文章

相关产品

相关课程

相关电子书

相关实验场景

推荐镜像

时间、空间、对象 海量极速多维检索 - 阿里云RDS PostgreSQL最佳实践

标签

背景

对象数据分类

搜索需求分类

数据结构

优化思路

1、时序块级索引

2、空间索引

3、GIN 倒排索引

4、bitmapAnd bitmapOr

5、堆表存储分级、分区

6、索引分级、分区

7、CTID intersect array JOIN SCAN

例子

1、创建对象FEED数据表

2、写入5000万测试数据

3、创建对象索引

4、创建时间索引

5、创建空间索引

6、生成数据layout，方便后面的查询

7、创建KNN极端查询函数

8、ctid合并检索

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

分区索引例子

优化思路小结

参考

关系型数据库

热门文章

最新文章

相关产品

相关课程

相关电子书

相关实验场景

推荐镜像

时间、空间、对象海量极速多维检索 - 阿里云RDS PostgreSQL最佳实践