385
空間複合索引加速空間搜索
標簽
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;
範圍掃描複合優化
還是前麵的例子，當驅動列的過濾條件不是等於，而是範圍時，效果為什麼不好呢？
因為需要掃描整個範圍以及下級分支，而索引的塊是離散塊，所以掃描效率並不高。
例子
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;
或者使用內核優化，讓內核支持分區索引。
內核優化
分區索引，按時間進行分區，建立分區索引。
在掃描時，自動檢索對應的索引分區。達到 分區表+獨立索引 同樣的效果。
小結
1、如果要構建複合索引，那麼為了達到最好的效果，所有的驅動列使用等值查詢是最好的，使用範圍查詢會導致大範圍的搜索。
2、如果需要使用複合索引進行排序，那麼要麼按所有字段排序，要麼按驅動列等值條件+suffix列排序。
3、為了減少索引掃描的離散度，建議使用cluster對數據按索引進行重排。
最後更新：2017-06-24 16:01:47