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

RDS MySQL Serverless 基础系列，0.5-2RCU 50GB

标签

PostgreSQL , Greenplum , PostGIS , GiST , R-Tree , BRIN , 相关性 , 网格 , BOX , K-Mean

背景

1、平面、三维、多维对象 几何相交、不相交、相邻。

2、平面、三维、多维对象的方位判断（相交或严格在左边、右边、上边、下边），类似数值的大于、小于、大于等于、小于等于。

3、平面、三维、多维对象 包含 另一个对象

4、平面、三维、多维对象 等于 另一个对象

5、平面、三维、多维对象 与另一个对象的（边、最近、中心点的）距离，按距离排序输出满足条件的行，输出距离在XX以内的行。

http://postgis.net/docs/manual-2.3/reference.html#Operators

&& — Returns TRUE if A's 2D bounding box intersects B's 2D bounding box.
&&(geometry,box2df) — Returns TRUE if a geometry's (cached) 2D bounding box intersects a 2D float precision bounding box (BOX2DF).
&&(box2df,geometry) — Returns TRUE if a 2D float precision bounding box (BOX2DF) intersects a geometry's (cached) 2D bounding box.
&&(box2df,box2df) — Returns TRUE if two 2D float precision bounding boxes (BOX2DF) intersect each other.
&&& — Returns TRUE if A's n-D bounding box intersects B's n-D bounding box.
&&&(geometry,gidx) — Returns TRUE if a geometry's (cached) n-D bounding box intersects a n-D float precision bounding box (GIDX).
&&&(gidx,geometry) — Returns TRUE if a n-D float precision bounding box (GIDX) intersects a geometry's (cached) n-D bounding box.
&&&(gidx,gidx) — Returns TRUE if two n-D float precision bounding boxes (GIDX) intersect each other.
&< — Returns TRUE if A's bounding box overlaps or is to the left of B's.
&<| — Returns TRUE if A's bounding box overlaps or is below B's.
&> — Returns TRUE if A' bounding box overlaps or is to the right of B's.
<< — Returns TRUE if A's bounding box is strictly to the left of B's.
<<| — Returns TRUE if A's bounding box is strictly below B's.
= — Returns TRUE if A's bounding box is the same as B's. Uses double precision bounding box.
>> — Returns TRUE if A's bounding box is strictly to the right of B's.
@ — Returns TRUE if A's bounding box is contained by B's.
@(geometry,box2df) — Returns TRUE if a geometry's 2D bounding box is contained into a 2D float precision bounding box (BOX2DF).
@(box2df,geometry) — Returns TRUE if a 2D float precision bounding box (BOX2DF) is contained into a geometry's 2D bounding box.
@(box2df,box2df) — Returns TRUE if a 2D float precision bounding box (BOX2DF) is contained into another 2D float precision bounding box.
|&> — Returns TRUE if A's bounding box overlaps or is above B's.
|>> — Returns TRUE if A's bounding box is strictly above B's.
~ — Returns TRUE if A's bounding box contains B's.
~(geometry,box2df) — Returns TRUE if a geometry's 2D bonding box contains a 2D float precision bounding box (GIDX).
~(box2df,geometry) — Returns TRUE if a 2D float precision bounding box (BOX2DF) contains a geometry's 2D bonding box.
~(box2df,box2df) — Returns TRUE if a 2D float precision bounding box (BOX2DF) contains another 2D float precision bounding box (BOX2DF).
~= — Returns TRUE if A's bounding box is the same as B's.
<-> — Returns the 2D distance between A and B.
|=| — Returns the distance between A and B trajectories at their closest point of approach.
<#> — Returns the 2D distance between A and B bounding boxes.
<<->> — Returns the n-D distance between the centroids of A and B bounding boxes.
<<#>> — Returns the n-D distance between A and B bounding boxes.


PostgreSQL 支持的索引种类

《PostgreSQL 9种索引的原理和应用场景》

B-Tree

B-Tree毫无疑问是最简单，最容易理解的索引，按顺序将KEY分成几个层次（根、分支、叶子）组织起来，在VALUE中存储数据的实际行号。

GiST

GiST是一个通用的索引接口，全称Generalized Search Trees。不仅仅适合空间数据类型的检索，同样适合其他数据类型。

BRIN

BRIN是块级索引(9.5以上版本)，存储每个（或每连续几个）块的边界值，例如：

《PostgreSQL 物联网黑科技 - 瘦身几百倍的索引(BRIN index)》

GiST和BRIN 如何选择

GiST和BRIN索引分别支持什么空间搜索需求？

1、GiST索引支持什么查询需求？

http://postgis.net/docs/manual-2.3/reference.html

2、BRIN索引支持什么查询需求？

BRIN索引中存储的信息量比较有限，实际上就是包含每个（每连续几个）BLOCK中所有几何数据的最小BOX（或多维BOX）。

&&, ~ and @ operators can be used for the 2D cases (both for "geometry" and for "geography"),

&&& operator can be used for the 3D geometries.


create extension postgis;


postgres=# create table gis_idx_test(id int, info text, pos geometry) with (autovacuum_enabled=off,toast.autovacuum_enabled=off);
CREATE TABLE


1、写入速度对比，（写入1000万随机POINT）：

GiST，219秒。

postgres=# \timing
Timing is on.

create index idx_gis_idx_test on gis_idx_test using gist (pos);
insert into gis_idx_test select id, md5(random()::text), ST_SetSRID(ST_Point(180-random()*360, 90-random()*180),4326) from generate_series(1,10000000) t(id);

INSERT 0 10000000
Time: 219213.503 ms


BRIN（每个BLOCK统计一个BOX），33秒。

drop index idx_gis_idx_test;
truncate gis_idx_test;
create index idx_gis_idx_test on gis_idx_test using brin (pos) with (pages_per_range =1);
insert into gis_idx_test select id, md5(random()::text), ST_SetSRID(ST_Point(180-random()*360, 90-random()*180),4326) from generate_series(1,10000000) t(id);

INSERT 0 10000000
Time: 32621.684 ms


2、无索引插入速度，30秒。BRIN索引对插入几乎没有影响。

drop index idx_gis_idx_test;
truncate gis_idx_test;
insert into gis_idx_test select id, md5(random()::text), ST_SetSRID(ST_Point(180-random()*360, 90-random()*180),4326) from generate_series(1,10000000) t(id);

INSERT 0 10000000
Time: 29696.020 ms


3、创建速度对比（1000万随机POINT）：

GiST，164秒。

drop index idx_gis_idx_test;
create index idx_gis_idx_test on gis_idx_test using gist (pos);

CREATE INDEX
Time: 163988.002 ms


BRIN，3.5秒。

drop index idx_gis_idx_test;
create index idx_gis_idx_test on gis_idx_test using brin (pos) with (pages_per_range =1);

CREATE INDEX
Time: 3491.662 ms


4、空间对比（1000万随机POINT）：

GiST，522MB。

postgres=# \di+ idx_gis_idx_test
List of relations
Schema |       Name       | Type  |  Owner   |    Table     |  Size  | Description
--------+------------------+-------+----------+--------------+--------+-------------
public | idx_gis_idx_test | index | postgres | gis_idx_test | 522 MB |
(1 row)


BRIN，5MB。

                                     List of relations
Schema |         Name         | Type  |  Owner   |      Table      |  Size   | Description
--------+----------------------+-------+----------+-----------------+---------+-------------
public | idx_gis_idx_test     | index | postgres | gis_idx_test    | 5136 kB |


5、检索速度对比：

5.1 包含查询，查询在某个多边形中的所有POINT。

GiST，136毫秒。

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from gis_idx_test where st_within (pos, ST_SetSRID(ST_MakePolygon(st_setsrid(ST_GeomFromText('LINESTRING(0 0, 15 0, 7.5 10, 0 0)'),4326)),4326));
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on public.gis_idx_test  (cost=344.25..33368.43 rows=3333 width=68) (actual time=9.180..135.562 rows=11392 loops=1)
Output: id, info, pos
Recheck Cond: ('0103000020E61000000100000004000000000000000000000000000000000000000000000000002E4000000000000000000000000000001E40000000000000244000000000000000000000000000000000'::geometry ~ gis_idx_test.pos)
Filter: _st_contains('0103000020E61000000100000004000000000000000000000000000000000000000000000000002E4000000000000000000000000000001E40000000000000244000000000000000000000000000000000'::geometry, gis_idx_test.pos)
Rows Removed by Filter: 11495
Heap Blocks: exact=20944
->  Bitmap Index Scan on idx_gis_idx_test  (cost=0.00..343.42 rows=10000 width=0) (actual time=5.550..5.550 rows=22887 loops=1)
Index Cond: ('0103000020E61000000100000004000000000000000000000000000000000000000000000000002E4000000000000000000000000000001E40000000000000244000000000000000000000000000000000'::geometry ~ gis_idx_test.pos)
Planning time: 0.187 ms
Execution time: 136.564 ms
(12 rows)


BRIN，3.2秒。

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from gis_idx_test where st_within (pos, ST_SetSRID(ST_MakePolygon(st_setsrid(ST_GeomFromText('LINESTRING(0 0, 15 0, 7.5 10, 0 0)'),4326)),4326));
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on public.gis_idx_test  (cost=2631.83..35656.01 rows=3333 width=68) (actual time=67.964..3277.244 rows=11392 loops=1)
Output: id, info, pos
Recheck Cond: ('0103000020E61000000100000004000000000000000000000000000000000000000000000000002E4000000000000000000000000000001E40000000000000244000000000000000000000000000000000'::geometry ~ gis_idx_test.pos)
Rows Removed by Index Recheck: 9977113
Filter: _st_contains('0103000020E61000000100000004000000000000000000000000000000000000000000000000002E4000000000000000000000000000001E40000000000000244000000000000000000000000000000000'::geometry, gis_idx_test.pos)
Rows Removed by Filter: 11495
Heap Blocks: lossy=123457
->  Bitmap Index Scan on idx_gis_idx_test  (cost=0.00..2631.00 rows=10000 width=0) (actual time=67.473..67.473 rows=1234570 loops=1)
Index Cond: ('0103000020E61000000100000004000000000000000000000000000000000000000000000000002E4000000000000000000000000000001E40000000000000244000000000000000000000000000000000'::geometry ~ gis_idx_test.pos)
Planning time: 0.250 ms
Execution time: 3278.503 ms
(13 rows)


5.2 KNN检索，查询某个点方圆100（单位与SRID有关）以内的点，并按由近到远的顺序输出。

《PostGIS 空间数据学习建议》

GiST 支持距离索引，距离排序。BRIN暂时不支持（但是它支持包含，因此我们可以构造一个圆形来实现同等效果，过滤后的数据再排序输出）。

GiST

postgres=# set enable_bitmapscan=off;
SET
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from gis_idx_test where ST_DWithin (pos, ST_SetSRID(ST_Point(70,10),4326), 1) order by pos <-> ST_SetSRID(ST_Point(70,10),4326);
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Index Scan using idx_gis_idx_test on public.gis_idx_test  (cost=0.42..1097597.75 rows=133333 width=76) (actual time=0.139..2.362 rows=476 loops=1)
Output: id, info, pos, (pos <-> '0101000020E610000000000000008051400000000000002440'::geometry)
Index Cond: (gis_idx_test.pos && '0103000020E6100000010000000500000000000000004051400000000000002240000000000040514000000000000026400000000000C0514000000000000026400000000000C05140000000000000224000000000004051400000000000002240'::geometry)
Order By: (gis_idx_test.pos <-> '0101000020E610000000000000008051400000000000002440'::geometry)
Filter: (('0101000020E610000000000000008051400000000000002440'::geometry && st_expand(gis_idx_test.pos, '1'::double precision)) AND _st_dwithin(gis_idx_test.pos, '0101000020E610000000000000008051400000000000002440'::geometry, '1'::double precision))
Rows Removed by Filter: 130
Buffers: shared hit=617
Planning time: 0.181 ms
Execution time: 2.445 ms
(9 rows)


BRIN，（根据后面的章节，对数据重排后的性能）

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from gis_idx_test_brin where ST_DWithin (pos, ST_SetSRID(ST_Point(70,10),4326), 1) order by pos <-> ST_SetSRID(ST_Point(70,10),4326);
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------
Sort  (cost=4818.33..4818.42 rows=37 width=77) (actual time=57.087..57.144 rows=476 loops=1)
Output: id, info, pos, ((pos <-> '0101000020E610000000000000008051400000000000002440'::geometry))
Sort Key: ((gis_idx_test_brin.pos <-> '0101000020E610000000000000008051400000000000002440'::geometry))
Sort Method: quicksort  Memory: 91kB
Buffers: shared hit=836
->  Bitmap Heap Scan on public.gis_idx_test_brin  (cost=2560.18..4817.37 rows=37 width=77) (actual time=55.785..56.898 rows=476 loops=1)
Output: id, info, pos, (pos <-> '0101000020E610000000000000008051400000000000002440'::geometry)
Recheck Cond: (gis_idx_test_brin.pos && '0103000020E6100000010000000500000000000000004051400000000000002240000000000040514000000000000026400000000000C0514000000000000026400000000000C05140000000000000224000000000004051400000000000002240'::geometry)
Rows Removed by Index Recheck: 852
Filter: (('0101000020E610000000000000008051400000000000002440'::geometry && st_expand(gis_idx_test_brin.pos, '1'::double precision)) AND _st_dwithin(gis_idx_test_brin.pos, '0101000020E610000000000000008051400000000000002440'::geometry, '1'::double precision))
Rows Removed by Filter: 130
Heap Blocks: lossy=18
Buffers: shared hit=836
->  Bitmap Index Scan on idx_gis_idx_test_brin  (cost=0.00..2560.17 rows=556 width=0) (actual time=55.700..55.700 rows=180 loops=1)
Index Cond: (gis_idx_test_brin.pos && '0103000020E6100000010000000500000000000000004051400000000000002240000000000040514000000000000026400000000000C0514000000000000026400000000000C05140000000000000224000000000004051400000000000002240'::geometry)
Buffers: shared hit=818
Planning time: 0.313 ms
Execution time: 57.232 ms
(18 rows)


BRIN 数据优化数据规划

PostGIS提供了几种数据聚集的窗口函数，可以将数据按网格聚集起来。按照这种方法重排数据，可以让BRIN索引得到很好的查询效率。

1、可以用到的数据空间聚集函数如下：

http://postgis.net/docs/manual-dev/ST_ClusterKMeans.html

http://postgis.net/docs/manual-dev/ST_ClusterDBSCAN.html

2、可以用geohash的VALUE进行重排。

geohash重排举例。

postgres=# create table gis_idx_test_brin(like gis_idx_test);
CREATE TABLE
postgres=# insert into gis_idx_test_brin select * from gis_idx_test order by st_geohash(pos);
INSERT 0 10000000
postgres=# create index idx_gis_idx_test_brin on gis_idx_test_brin using brin (pos) with (pages_per_range =1);
CREATE INDEX
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from gis_idx_test_brin where st_within (pos, ST_SetSRID(ST_MakePolygon(st_setsrid(ST_GeomFromText('LINESTRING(0 0, 15 0, 7.5 10, 0 0)'),4326)),4326));
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on public.gis_idx_test_brin  (cost=2631.83..35656.01 rows=3333 width=68) (actual time=56.683..76.280 rows=11392 loops=1)
Output: id, info, pos
Recheck Cond: ('0103000020E61000000100000004000000000000000000000000000000000000000000000000002E4000000000000000000000000000001E40000000000000244000000000000000000000000000000000'::geometry ~ gis_idx_test_brin.pos)
Rows Removed by Index Recheck: 2952
Filter: _st_contains('0103000020E61000000100000004000000000000000000000000000000000000000000000000002E4000000000000000000000000000001E40000000000000244000000000000000000000000000000000'::geometry, gis_idx_test_brin.pos)
Rows Removed by Filter: 11495
Heap Blocks: lossy=319
->  Bitmap Index Scan on idx_gis_idx_test_brin  (cost=0.00..2631.00 rows=10000 width=0) (actual time=56.550..56.550 rows=3190 loops=1)
Index Cond: ('0103000020E61000000100000004000000000000000000000000000000000000000000000000002E4000000000000000000000000000001E40000000000000244000000000000000000000000000000000'::geometry ~ gis_idx_test_brin.pos)
Planning time: 0.402 ms
Execution time: 77.244 ms
(13 rows)


索引创建方法举例

1、GiST

The syntax for building a GiST index on a "geometry" column is as follows:

CREATE INDEX [indexname] ON [tablename] USING GIST ( [geometryfield] );


The above syntax will always build a 2D-index. To get the an n-dimensional index supported in PostGIS 2.0+ for the geometry type, you can create one using this syntax

CREATE INDEX [indexname] ON [tablename] USING GIST ([geometryfield] gist_geometry_ops_nd);


2、BRIN

The syntax for building a BRIN index on a "geometry" column is as follows:

CREATE INDEX [indexname] ON [tablename] USING BRIN ( [geometryfield] );


The above syntax will always build a 2D-index. To get a 3d-dimensional index, you can create one using this syntax

CREATE INDEX [indexname] ON [tablename] USING BRIN ([geometryfield] brin_geometry_inclusion_ops_3d);


You can also get a 4d-dimensional index using the 4d operator class

CREATE INDEX [indexname] ON [tablename] USING BRIN ([geometryfield] brin_geometry_inclusion_ops_4d);


These above syntaxes will use the default number or block in a range, which is 128. To specify the number of blocks you want to summarise in a range, you can create one using this syntax

CREATE INDEX [indexname] ON [tablename] USING BRIN ( [geometryfield] ) WITH (pages_per_range = [number]);


Also, keep in mind that a BRIN index will only store one index value for a large number of rows. If your table stores geometries with a mixed number of dimensions, it's likely that the resulting index will have poor performance. You can avoid this drop of performance by choosing the operator class whith the least number of dimensions of the stored geometries

Also the "geography" datatype is supported for BRIN indexing. The syntax for building a BRIN index on a "geography" column is as follows:

CREATE INDEX [indexname] ON [tablename] USING BRIN ( [geographyfield] );


如何选择GiST和BRIN索引

1、如果有kNN或者距离排序的查询需求。你只能使用 GiST索引。

2、如果有几何特性（包含、在左边、右边、上、下等查询）可以使用GiST也可以使用BRIN。

小结

PostgreSQL 1000万空间数据的GiST, BRIN索引对比：

1、空间对比，BRIN存储的是块级BOX边界，非常节省空间。

2、写入时延对比，BRIN对写入几乎没有影响。

3、创建索引时延对比，创建BRIN索引特别快。

4、包含查询响应时间对比，BRIN索引，在数据物理存储空间线性的情况下，包含查询、KNN检索性能都特别好。

5、KNN检索性能对比，BRIN的KNN检索，通过包含以及SORT来实现。比GIST略差。

参考

http://postgis.net/docs/manual-dev/using_postgis_dbmanagement.html#brin_indexes

http://postgis.net/docs/manual-dev/ST_ClusterKMeans.html

http://postgis.net/docs/manual-dev/ST_ClusterDBSCAN.html

https://en.wikipedia.org/wiki/K-means_clustering

《蜂巢的艺术与技术价值 - PostgreSQL PostGIS's hex-grid》

《PostgreSQL 物联网黑科技 - 瘦身几百倍的索引(BRIN index)》

|
6天前
|
SQL Java 关系型数据库
MYSQL--JDBC优化
MYSQL--JDBC优化
13 1
|
24天前
|
SQL 缓存 关系型数据库

【5月更文挑战第20天】下次老板问你MySQL如何优化时，你可以这样说，老板默默给你加工资
38 3
|
2天前
|
SQL 缓存 关系型数据库
MySQL慢查询优化实践问答
MySQL慢查询优化实践问答
31 4
|
3天前
|

mysql索引优化
【6月更文挑战第16天】mysql索引优化
6 2
|
5天前
|

【6月更文挑战第14天】如何优化MySQL 8.0的性能？
22 5
|
7天前
|

mysql优化
【6月更文挑战第12天】mysql优化
18 3
|
8天前
|

72 3
|
12天前
|
SQL 关系型数据库 MySQL
MySQL大数据量分页查询方法及其优化
MySQL大数据量分页查询方法及其优化
17 4
|
13天前
|
SQL 关系型数据库 MySQL
MySQL数据库——SQL优化（3/3）-limit 优化、count 优化、update 优化、SQL优化 小结
MySQL数据库——SQL优化（3/3）-limit 优化、count 优化、update 优化、SQL优化 小结
17 0
|
13天前
|
SQL 关系型数据库 MySQL
MySQL数据库——SQL优化（2/3）-order by 优化、group by 优化
MySQL数据库——SQL优化（2/3）-order by 优化、group by 优化
13 0

相关产品

• 云数据库 RDS MySQL 版
• 云原生数据库 PolarDB

更多

更多

更多

更多