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

digoal 2017-06-20

240

作者

digoal

日期

2017-06-20

背景

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

通常数据的查询会带位置距离搜索，同时还会伴随其他属性的过滤，其他属性的过滤：例如时间范围，区域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(10000random(), 10000random()) 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));
```

极限优化

《HTAP数据库 PostgreSQL 场景与性能测试之 47 - (OLTP) 空间应用 - 高并发空间位置更新、多属性KNN搜索并测（含空间索引）末端配送、新零售类项目》

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;

范围扫描复合优化

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

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

例子

```
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;

这样的查询效率并不高。
```

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

对于有范围扫描的场景，应该如何应对呢？

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;
```

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

内核优化

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

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

GIS领域朋友的建议

收到来自PostgreSQL社区GIS领域朋友的建议，为了防止给学习GIS的同学带来误导(为了测试方便，文中大量使用了内置的几何point类型，并非GIS类型。)，请参考如下建议。

感谢。

``` select DropGeometryColumn ('cb','geom'); drop table if exists cb;

create table cb( objectid int not null, --共享单车编号 c1 int, -- 0表示未使用，其它表示已使用
c2 int, -- 共享单车属于哪家运营公司 constraint pk_cb_objectid primary key (objectid) );

--GIS必须明确指出地图单位是什么

--民用GPS小数6位精度(6位大约为10米级精度,8位已经是亚米级精度)已经很高了,再多没有意义

--c3 point -- 共享单车当前位置, point在文章里只能算是自定义类型(实际上是PostgreSQL内置的几何点类型),这会给参考您文章的学习GIS的同学造成困扰

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

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

--这样的查询条件在测试没问题,但是别人看了会造成困扰，因为没有地图单位,这个1000距离不知道是什么东西

--新版本的postgis文档中已经没有ST_GeomFromText ('POINT(121.403833486783 31.1425794813889)', 4326)这样的函数了,虽然还支持,未来可能会删除

--请使用ST_SetSRID(ST_GeomFromText ('POINT(121.403833486783 31.1425794813889)'),4326)或ST_GeomFromText ('SRID=4326;POINT(121.403833486783 31.1425794813889)')

--发现好几篇您写的关于gis的文章都有类似的问题,希望关于gis方面的文章严格按postgis标准

--创建空间字段,根据空间参考不同,地图单位可能为米、度或其它，统称地图单位

select AddGeometryColumn ('cb','geom',4326,'POINT',2); -- 共享单车当前位置,GPS采用4326 ,类型为点,二维坐标

--创建空间索引 create index gidx_cb_geom on cb using gist(geom); create index gidx_cb_geomgraphy on cb using gist((geom::geography));

--坐标范围限制在中国[73.406586, 3.408477, 135.085831, 53.880950] do $$ declare vStart bigint; declare vEnd bigint; declare MAXVALE bigint; declare INTERVAL bigint; begin MAXVALE := 20000000; INTERVAL := 1000; vStart := 1 ;vEnd := INTERVAL; loop
-- 20家公司比较符合市场现状,更能反应实际情况 insert into cb select id,(random()1)::integer, (random()(20-1)+1)::integer, ST_SetSRID(ST_Point( round((random()(135.085831-73.406586)+73.406586)::numeric,6), round((random()(53.880950-3.408477)+3.408477)::numeric,6) ),4326) from generate_series(vStart,vEnd) as id; raise notice '%', vEnd; vStart := vEnd + 1; vEnd := vEnd + INTERVAL; if( vEnd > MAXVALE ) then return; end if; end loop; end$$;

--ix,iy为gps经度和纬度(单位为度)

--idistance为搜索距离(单位为米)

drop function if exists spatialQuery(ix float,iy float,idistance float); create or replace function spatialQuery(ix float,iy float,idistance float) returns table(oobjectid integer,oc1 integer,oc2 integer,odistance float,ogeom geometry) as $$ declare vrecord record; vcurrentpoint geometry; vspheroid spheroid; begin vspheroid := 'SPHEROID["WGS84",6378137,298.257223563]' ; --WGS84椭球体参数定义 vcurrentpoint := ST_SetSRID(ST_Point(ix,iy),4326); -- --查找圆心为vcurrentpoint,半径idistance米范围内未使用的共享单车,并按距离排序,只返回1千行 return query ( with cte as( select * from cb where ST_DWithin(geom::geography ,vcurrentpoint::geography,idistance,true) ) select objectid,c1,c2,ST_DistanceSpheroid(geom,vcurrentpoint,vspheroid),geom from cte where c1=0 order by ST_DistanceSpheroid(geom,vcurrentpoint,vspheroid) limit 1000 ); end; $$ language plpgsql;

select * from spatialQuery(102,24,5000);

--查询计划

explain (analyze,verbose,costs,buffers,timing) with cte as( select * from cb where ST_DWithin(geom::geography ,ST_SetSRID(ST_Point(102,24),4326)::geography,5000,true) ) select objectid,c1,c2,ST_DistanceSpheroid(geom,ST_SetSRID(ST_Point(102,24),4326),'SPHEROID["WGS84",6378137,298.257223563]'),geom from cte where c1=0 order by ST_DistanceSpheroid(geom,ST_SetSRID(ST_Point(102,24),4326),'SPHEROID["WGS84",6378137,298.257223563]') limit 1000; ```

小结

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

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

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

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

文章转载自digoal，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

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

作者

日期

标签

背景

gist空间复合索引

PostGIS例子

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

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

范围扫描复合优化

内核优化

GIS领域朋友的建议

小结

PostgreSQL 许愿链接

9.9元购买3个月阿里云RDS PostgreSQL实例

PostgreSQL 解决方案集合

德哥 / digoal's github - 公益是一辈子的事.

评论