空间复合索引加速空间搜索-阿里云开发者社区

开发者社区> 阿里云数据库> 正文
登录阅读全文

空间复合索引加速空间搜索

简介:

标签

PostgreSQL , PostGIS , 复合索引 , btree_gist , 共享单车


背景

随着移动互联网的普及,空间数据已经成为大多数企业数据的标配,例如出行、快递、等。

通常数据的查询会带位置距离搜索,同时还会伴随其他属性的过滤,其他属性的过滤:例如时间范围,区域ID的过滤,物流公司ID的过滤。

空间索引和BTREE索引在PostgreSQL中属于两种索引(PostgreSQL支持btree,hash,gin,gist,sp-gist,brin,rum,bloom,zoomdb等多种索引方法)。

怎么使得查询效率达到最优呢?

gist空间复合索引

例子

数据库中存储了3个关键字段,一个表示共享单车的公司(mobike, ofo, ...),一个表示共享单车是否在使用中,还有一个字段表示共享单车当前的位置。

构建测试表,三个字段,两个INT类型,一个POINT类型,用户可能需要根据point查询近邻数据,同时过滤掉c1,c2的某一些值。

测试表以及测试数据如下

postgres=# create table cb(  
c1 int,  -- 0表示未使用,1表示已使用  
c2 int,  -- 共享单车属于哪家运营公司  
c3 point  -- 共享单车当前位置  
);  
CREATE TABLE  
  
  
postgres=# insert into cb select random()*1, random()*1000 , point(10000*random(), 10000*random()) from generate_series(1,10000000);  
INSERT 0 10000000  
  
  
postgres=# select * from cb limit 10;  
 c1 | c2  |                 c3                    
----+-----+-------------------------------------  
  0 | 981 | (8099.59028847516,9043.13919134438)  
  1 | 256 | (9331.68333489448,2223.74511882663)  
  1 | 510 | (2517.2486435622,8716.1894608289)  
  0 | 398 | (2658.8175073266,2361.14453990012)  
  0 | 989 | (8130.69586176425,1361.2649217248)  
  0 | 344 | (2282.57383685559,9480.9684343636)  
  1 | 944 | (8550.47187302262,2814.43384941667)  
  0 | 418 | (3858.46449527889,5060.3136094287)  
  0 | 196 | (4103.45280077308,1458.2177111879)  
  0 | 344 | (3681.96283001453,1260.5628464371)  
(10 rows)  

搜索某个点附近1000距离内,属于某个公司的,没有使用的共享单车。

查询语句如下

select * from cb where c1=0 and c2=100 and c3 <@ circle '((23,3175),1000)' order by c3 <-> point(23,3175) limit 1000;  

创建空间复合索引

postgres=# set maintenance_work_mem='32GB';  
SET  
  
postgres=# create extension btree_gist;  
CREATE EXTENSION  
  
postgres=# create index idx1 on cb using gist(c1,c2,c3);  
CREATE INDEX  

性能如下

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from cb where c1=0 and c2=100 and c3 <@ circle '((23,3175),1000)' order by c3 <-> point(23,3175) limit 1000;  
                                                         QUERY PLAN                                                            
-----------------------------------------------------------------------------------------------------------------------------  
 Limit  (cost=0.42..9.55 rows=5 width=32) (actual time=0.125..0.355 rows=93 loops=1)  
   Output: c1, c2, c3, ((c3 <-> '(23,3175)'::point))  
   Buffers: shared hit=106  
   ->  Index Only Scan using idx1 on public.cb  (cost=0.42..9.55 rows=5 width=32) (actual time=0.124..0.344 rows=93 loops=1)  
         Output: c1, c2, c3, (c3 <-> '(23,3175)'::point)  
         Index Cond: ((cb.c1 = 0) AND (cb.c2 = 100) AND (cb.c3 <@ '<(23,3175),1000>'::circle))  
         Order By: (cb.c3 <-> '(23,3175)'::point)  
         Heap Fetches: 93  
         Buffers: shared hit=106  
 Planning time: 0.110 ms  
 Execution time: 0.387 ms  
(11 rows)  

PostGIS例子

对于一个这样的PostGIS相关的QUERY,优化如下

explain (analyze,verbose,timing,costs,buffers)   
select xxx1,xxx2,xxx3,st_asbinary(geo) as geo,  
  ST_Transform (ST_GeomFromText ('POINT(121.403833486783 31.1425794813889)', 4326), 26986) <-> ST_Transform (geo, 26986) as distance2Center  
  from tbl  
  where xxx1='1' and xxx2='xxx'   
  and ST_Transform (geo, 26986) && ST_Buffer(ST_Transform(ST_GeomFromText('POINT(121.403833486783 31.1425794813889)', 4326), 26986), 300)  
  order by ST_Transform (ST_GeomFromText ('POINT(121.403833486783 31.1425794813889)', 4326), 26986) <-> ST_Transform (geo, 26986) asc  
  
对于这个查询,使用这个索引是最好的  
  
create index idx1 on tbl using gist(xxx1, xxx2, ST_Transform (geo, 26986));  

极限优化

create or replace function ff1(geometry, 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 *,  
    ST_Distance ( $1, loc_box ) as dist   
    from cloudpoint_test_agg   
    -- where xxx1='1' and xxx2='xxx'
    order by loc_box <-> $1           -- 按距离顺序由近到远返回  
  loop  
    if v_limit <=0 then               -- 判断返回的记录数是否达到LIMIT的记录数  
      raise notice '已经取足limit设置的 % 条数据, 但是距离 % 以内的点可能还有.', $3, $2;  
      return;  
    end if;  
    if v_rec.dist > $2 then       -- 判断距离是否大于请求的距离   
      raise notice '距离 % 以内的点已输出完毕', $2;  
      return;  
    else  
      return next v_rec;  
    end if;  
    v_limit := v_limit - array_length(v_rec.loc_agg, 1);  -- 扣减grid内的point个数  
  end loop;  
end;  
$$ language plpgsql strict volatile; 

如果不使用空间复合索引,性能会差很多

如下,同样的数据:

postgres=# create table cc (like cb);  
CREATE TABLE  
postgres=# insert into cc select * from cb;  
INSERT 0 10000000  
  
仅仅创建c3的空间索引  
  
postgres=# create index idx2 on cc using gist(c3);  
CREATE INDEX  

查询性能如下

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from cc where c1=0 and c2=100 and c3 <@ circle '((23,3175),1000)' order by c3 <-> point(23,3175) limit 1000;  
                                                              QUERY PLAN                                                                
--------------------------------------------------------------------------------------------------------------------------------------  
 Limit  (cost=12552.41..12552.42 rows=5 width=32) (actual time=153.300..153.317 rows=93 loops=1)  
   Output: c1, c2, c3, ((c3 <-> '(23,3175)'::point))  
   Buffers: shared hit=60543  
   ->  Sort  (cost=12552.41..12552.42 rows=5 width=32) (actual time=153.298..153.306 rows=93 loops=1)  
         Output: c1, c2, c3, ((c3 <-> '(23,3175)'::point))  
         Sort Key: ((cc.c3 <-> '(23,3175)'::point))  
         Sort Method: quicksort  Memory: 32kB  
         Buffers: shared hit=60543  
         ->  Bitmap Heap Scan on public.cc  (cost=236.92..12552.35 rows=5 width=32) (actual time=52.341..153.244 rows=93 loops=1)  
               Output: c1, c2, c3, (c3 <-> '(23,3175)'::point)  
               Recheck Cond: (cc.c3 <@ '<(23,3175),1000>'::circle)  
               Filter: ((cc.c1 = 0) AND (cc.c2 = 100))  
               Rows Removed by Filter: 160633  
               Heap Blocks: exact=58622  
               Buffers: shared hit=60543  
               ->  Bitmap Index Scan on idx2  (cost=0.00..236.92 rows=10000 width=0) (actual time=39.223..39.223 rows=160726 loops=1)  
                     Index Cond: (cc.c3 <@ '<(23,3175),1000>'::circle)  
                     Buffers: shared hit=1921  
 Planning time: 0.116 ms  
 Execution time: 153.373 ms  
(20 rows)  
  
postgres=# set enable_seqscan=off;  
SET  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from cc where c1=0 and c2=100 and c3 <@ circle '((23,3175),1000)' order by c3 <-> point(23,3175) limit 1000;  
                                                          QUERY PLAN                                                            
------------------------------------------------------------------------------------------------------------------------------  
 Limit  (cost=0.42..14296.43 rows=5 width=32) (actual time=0.998..210.033 rows=93 loops=1)  
   Output: c1, c2, c3, ((c3 <-> '(23,3175)'::point))  
   Buffers: shared hit=162645  
   ->  Index Scan using idx2 on public.cc  (cost=0.42..14296.43 rows=5 width=32) (actual time=0.996..210.008 rows=93 loops=1)  
         Output: c1, c2, c3, (c3 <-> '(23,3175)'::point)  
         Index Cond: (cc.c3 <@ '<(23,3175),1000>'::circle)  
         Order By: (cc.c3 <-> '(23,3175)'::point)  
         Filter: ((cc.c1 = 0) AND (cc.c2 = 100))  
         Rows Removed by Filter: 160633  
         Buffers: shared hit=162645  
 Planning time: 0.109 ms  
 Execution time: 210.079 ms  
(12 rows)  

性能差的原因是rows remove by filter,因为仅仅通过空间扫描的过滤,大量的行是不满足条件的,所以导致了大量的无用功。

btree复合索引(geohash+其他过滤条件)

如果你使用的是geohash,而不是geometry类型,当你的地理位置并非边界地址时,相邻的数据的geohash的某些prefix可能是相同的,因此geohash可以使用btree索引。

create table test (  
c1 int, -- 共享单车是否已被租用  
c2 int, -- 共享单车运营公司  
c3 text  -- 共享单车位置(geohash)  
);  
  
create index idx on test using btree(c1,c2,c3);  

再次优化,cluster,减少索引扫描的离散度。

cluster test using idx;  

范围扫描复合优化

还是前面的例子,当驱动列的过滤条件不是等于,而是范围时,效果为什么不好呢?

因为需要扫描整个范围以及下级分支,而索引的块是离散块,所以扫描效率并不高。

pic

例子

create table test(c1 int, c2 int, c3 timestamp, c4 point);  
  
create index idx on test using gist(c3,c2,c4);  
  
select * from test where c3 between '2017-01-01' and '2017-01-02' and c2=1 order by c4;  
  
这样的查询效率并不高。  

而前面的例子对应的是驱动列的点扫描,所以效率很好。

pic

对于有范围扫描的场景,应该如何应对呢?

1、使用分区表,例如使用C3字段作为分区列,按时间进行分区。建立索引时将C3列摘除。

create table test_20170101 (like test, check c3 between '2017-01-01' and '2017-01-02');  
  
create index idx on test_20170101 using gist (c2, c4);  
  
select * from test_20170101 where c2=1 order by c4;  

或者使用内核优化,让内核支持分区索引。

内核优化

分区索引,按时间进行分区,建立分区索引。

在扫描时,自动检索对应的索引分区。达到 分区表+独立索引 同样的效果。

小结

1、如果要构建复合索引,那么为了达到最好的效果,所有的驱动列使用等值查询是最好的,使用范围查询会导致大范围的搜索。

2、如果需要使用复合索引进行排序,那么要么按所有字段排序,要么按驱动列等值条件+suffix列排序。

3、为了减少索引扫描的离散度,建议使用cluster对数据按索引进行重排。

《索引顺序扫描引发的堆扫描IO放大背后的统计学原理与解决办法 - PostgreSQL index scan enlarge heap page scans when index and column correlation small.》

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
阿里云数据库
使用钉钉扫一扫加入圈子
+ 订阅

帮用户承担一切数据库风险,给您何止是安心!

官方博客
链接