173
空間索引(GiST、BRIN、R-Tree)選擇、優化 - 阿裏雲RDS PostgreSQL最佳實踐
標簽
PostgreSQL , Greenplum , PostGIS , GiST , R-Tree , BRIN , 相關性 , 網格 , BOX , K-Mean
背景
空間數據的搜索需求通常包括：
1、平麵、三維、多維對象 幾何相交、不相交、相鄰。
2、平麵、三維、多維對象的方位判斷（相交或嚴格在左邊、右邊、上邊、下邊），類似數值的大於、小於、大於等於、小於等於。
3、平麵、三維、多維對象 包含 另一個對象
4、平麵、三維、多維對象 等於 另一個對象
5、平麵、三維、多維對象 與另一個對象的（邊、最近、中心點的）距離，按距離排序輸出滿足條件的行，輸出距離在XX以內的行。
操作符如下
https://postgis.net/docs/manual-2.3/reference.html
&& — 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中存儲數據的實際行號。
這種索引結構在排序、範圍查詢(大於、小於、大於等於、小於等於)、精確查詢（等於）的場景中非常有效。
但是它沒有辦法支持空間搜索中提到的幾何對象的搜索需求（相交，包含，距離等）。
R-Tree
將空間數據按長方形組織，大的長方形套小的長方形。頂層是最大的長方形，接下來是很多小的長方形，再接下來更小，不停的切成多個層次。類似B-Tree的根、分支、葉子結構。
很早以前PostgreSQL中支持R-Tree，但是後來被更好的GiST接口取代了。
GiST
GiST是一個通用的索引接口，全稱Generalized Search Trees。不僅僅適合空間數據類型的檢索，同樣適合其他數據類型。
在GIS數據的GiST索引實現中，將空間數據按“在另一邊(上、下、左、右)”，“相交”，“包含”使用R-Tree結構組織。
同時，GIS索引能夠支持在一個索引結構中，存儲平麵、三維、多維的數據。這是很了不起的功能。
BRIN
BRIN是塊級索引(9.5以上版本)，存儲每個（或每連續幾個）塊的邊界值，例如：
數值類型：存儲每個BLOCK（或每連續若幹BLOCK）包含的記錄中，最大值和最小值。（理論上還可以擴展BRIN索引的功能，例如包含記錄數、平均值、SUM等信息，但是索引會更重）
幾何類型：存儲每個BLOCK（或每連續若幹BLOCK）包含的記錄中，能夠包含下這些幾何對象的最小的BOX。例如這些記錄中（最左下的點、最右上的點 造成的BOX）。
《PostgreSQL 物聯網黑科技 - 瘦身幾百倍的索引(BRIN index)》
GiST和BRIN 如何選擇
GiST和BRIN索引分別支持什麼空間搜索需求？
1、GiST索引支持什麼查詢需求？
除了前麵提到的哪些幾何操作符（相交、包含、方位、距離、距離排序等），還有大量的函數支持索引的使用。
詳見
https://postgis.net/docs/manual-2.3/reference.html
2、BRIN索引支持什麼查詢需求？
BRIN索引中存儲的信息量比較有限，實際上就是包含每個（每連續幾個）BLOCK中所有幾何數據的最小BOX（或多維BOX）。
現在能使用BRIN來優化 包含、相交、不相交 的幾何搜索。
&&, ~ and @ operators can be used for the 2D cases (both for "geometry" and for "geography"),
&&& operator can be used for the 3D geometries.
GiST和BRIN索引的overhead
索引都會引入Overhead，那麼哪個引入的OVERHEAD比較大呢？
GiST索引引入的overhead比較大，它需要存儲的信息量較大，支持更多的搜索需求。
舉例
創建PostGIS擴展。
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
Buffers: shared hit=6 read=21117 written=2
-> 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)
Buffers: shared hit=6 read=173
Planning time: 0.187 ms
Execution time: 136.564 ms
(12 rows)
BRIN，3.2秒。
注意到，recheck階段移除了9977113行，也就是說數據的空間線性不好。後麵講優化。
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
Buffers: shared hit=819 read=123465 written=238
-> 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)
Buffers: shared hit=819 read=8
Planning time: 0.250 ms
Execution time: 3278.503 ms
(13 rows)
注意為了讓BRIN索引得到好的查詢效率，需要在數據編排上麵優化。比如標量數據需要時序化（即提高物理存儲和邏輯值的線性相關性）。而空間數據則需要網格化，因為BRIN的空間數據存儲的是範圍的BOX。
下麵再來看如何優化。
5.2 KNN檢索，查詢某個點方圓100（單位與SRID有關）以內的點，並按由近到遠的順序輸出。
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 數據優化數據規劃
為了讓BRIN索引得到好的查詢效率，需要在數據編排上麵優化。比如標量數據需要時序化（即提高物理存儲和邏輯值的線性相關性）。而空間數據則需要網格化，因為BRIN的空間數據存儲的是範圍的BOX。
PostGIS提供了幾種數據聚集的窗口函數，可以將數據按網格聚集起來。按照這種方法重排數據，可以讓BRIN索引得到很好的查詢效率。
我之前寫過一篇文檔，講空間數據的聚集。《蜂巢的藝術與技術價值 - PostgreSQL PostGIS's hex-grid》，如果數據按GRID組織，是不是BRIN索引就很好了呢。
數據重排，方法很多：
1、可以用到的數據空間聚集函數如下：
https://postgis.net/docs/manual-dev/ST_ClusterKMeans.html
https://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
Buffers: shared hit=825 read=321
-> 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)
Buffers: shared hit=825 read=2
Planning time: 0.402 ms
Execution time: 77.244 ms
(13 rows)
重排後，響應時間從3278毫秒縮短到了77毫秒。
給力。
索引創建方法舉例
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。
但是請注意BRIN要得到好的過濾效果，請對數據按BOX進行重排。這樣得到的效果比GIST還要好。
3、如果你很在意空間，或者在意數據寫入的OVERHEAD，建議BRIN（考慮到空間相關性的前提下）。
阿裏雲相關數據庫產品
小結
PostgreSQL 1000萬空間數據的GiST, BRIN索引對比：
1、空間對比，BRIN存儲的是塊級BOX邊界，非常節省空間。
2、寫入時延對比，BRIN對寫入幾乎沒有影響。
3、創建索引時延對比，創建BRIN索引特別快。
4、包含查詢響應時間對比，BRIN索引，在數據物理存儲空間線性的情況下，包含查詢、KNN檢索性能都特別好。
5、KNN檢索性能對比，BRIN的KNN檢索，通過包含以及SORT來實現。比GIST略差。
總之BRIN特別適合空間數據連續分布的數據，適合高速範圍搜索（即使點查也至少返回一個數據塊）。建議用戶的GIS軌跡數據（曆史靜態數據），可以按時間分區，按GEOHASH重排，使用BRIN索引。
而GIST適合任意分布的數據，支持更多的空間檢索需求，並且在點查方麵效果很好，但是空間占用大，給寫入帶來的overhead更大。適合更新頻繁的當前狀態數據的高效率檢索。
參考
https://postgis.net/docs/manual-dev/using_postgis_dbmanagement.html
https://postgis.net/docs/manual-dev/ST_ClusterKMeans.html
https://postgis.net/docs/manual-dev/ST_ClusterDBSCAN.html
https://en.wikipedia.org/wiki/K-means_clustering
《蜂巢的藝術與技術價值 - PostgreSQL PostGIS's hex-grid》
《PostgreSQL 物聯網黑科技 - 瘦身幾百倍的索引(BRIN index)》
最後更新：2017-08-20 17:06:33