Giá trị của việc lập chỉ mục

PostgreSQL cung cấp toán tử khoảng cách tuyến tính đơn giản <-> (khoảng cách tuyến tính). Chúng tôi sẽ sử dụng điều này để tìm các điểm gần nhất với một vị trí nhất định.

PostgreSQL cung cấp dữ liệu cho toán tử khoảng cách tuyến tính đơn giản và không thực hiện tối ưu hóa và không có chỉ mục, chúng tôi thấy kế hoạch thực thi sau:

time psql -qtAc "

EXPLAIN (ANALYZE ON, BUFFERS ON)
SELECT name, location
FROM geonames
ORDER BY location <-> '(29.9691,-95.6972)'
LIMIT 5;

"  <-- closing quote

                                      QUERY PLAN
-----------------------------------------------------------------------------------------------------------
Limit  (cost=418749.15..418749.73 rows=5 width=38) 
        (actual time=2553.970..2555.673 rows=5 loops=1)
  Buffers: shared hit=100 read=272836
  ->  Gather Merge  (cost=418749.15..1580358.21 rows=9955954 width=38) 
                    (actual time=2553.969..2555.669 rows=5 loops=1)
        Workers Planned: 2
        Workers Launched: 2
        Buffers: shared hit=100 read=272836
        ->  Sort  (cost=417749.12..430194.06 rows=4977977 width=38)
                 (actual time=2548.220..2548.221 rows=4 loops=3)
              Sort Key: ((location <-> '(29.9691,-95.6972)'::point))
              Sort Method: top-N heapsort  Memory: 25kB
              Worker 0:  Sort Method: top-N heapsort  Memory: 26kB
              Worker 1:  Sort Method: top-N heapsort  Memory: 25kB
              Buffers: shared hit=100 read=272836
              ->  Parallel Seq Scan on geonames  (cost=0.00..335066.71 rows=4977977 width=38) 
                                        (actual time=0.040..1637.884 rows=3982382 loops=3)
                    Buffers: shared hit=6 read=272836
Planning Time: 0.493 ms
Execution Time: 2555.737 ms

real    0m2.595s
user    0m0.011s
sys    0m0.015s

và đây là kết quả:(kết quả giống nhau cho tất cả các yêu cầu, vì vậy chúng tôi sẽ bỏ qua chúng sau.)

name	vị trí
Cây bách	(29.96911, -95.69717)
Nhà thờ Baptist Cypress Pointe	(29,9732, -95,6873)
Bưu điện Cypress	(29,9743, -95,67953)
Giếng nước nóng	(29,95689, -95,68189)
Sân bay Dry Creek	(29.98571, -95.68597)

Vì vậy, 418749.73 là chi phí TỐI ƯU HÓA để đánh bại và phải mất hai giây rưỡi (2555.673) để thực hiện truy vấn đó. Đây thực sự là một kết quả rất tốt, sử dụng PostgreSQL mà không có tối ưu hóa nào so với bảng 11 triệu hàng. Đây cũng là lý do tại sao chúng tôi chọn tập dữ liệu lớn hơn, vì sẽ có sự khác biệt rất nhỏ khi sử dụng các chỉ mục so với dưới 10 triệu hàng. Quét tuần tự song song thật tuyệt vời, nhưng đó là một bài viết khác.

Thêm chỉ mục GiST

Chúng tôi bắt đầu quá trình tối ưu hóa bằng cách thêm chỉ mục GiST. Bởi vì truy vấn mẫu của chúng tôi có

LIMIT

khoản 5 mục, chúng tôi có tính chọn lọc rất cao. Điều này sẽ khuyến khích người lập kế hoạch sử dụng một chỉ mục, vì vậy chúng tôi sẽ cung cấp một chỉ mục hoạt động khá tốt với dữ liệu hình học.

time psql -qtAc "CREATE INDEX idx_gist_geonames_location ON geonames USING gist(location);"

Hành động tạo chỉ mục có một chút chi phí.

CREATE INDEX
real    3m1.988s
user    0m0.011s
sys     0m0.014s

Và sau đó chạy lại cùng một truy vấn.

time psql -qtAc "

EXPLAIN (ANALYZE ON, BUFFERS ON)
SELECT name, location
FROM geonames
ORDER BY location <-> '(29.9691,-95.6972)'
LIMIT 5;

                                      QUERY PLAN
----------------------------------------------------------------------------------
Limit  (cost=0.42..1.16 rows=5 width=38) (actual time=0.797..0.881 rows=5 loops=1)
  Buffers: shared hit=5 read=15
  ->  Index Scan using idx_gist_geonames_location on geonames  
            (cost=0.42..1773715.32 rows=11947145 width=38) 
            (actual time=0.796..0.879 rows=5 loops=1)
        Order By: (location <-> '(29.9691,-95.6972)'::point)
        Buffers: shared hit=5 read=15
Planning Time: 0.768 ms
Execution Time: 0.939 ms

real    0m0.033s
user    0m0.011s
sys     0m0.013s

Trong trường hợp này, chúng tôi thấy một số cải thiện đáng kể. Chi phí ước tính của truy vấn chỉ là 1,16! So sánh chi phí đó với chi phí ban đầu của truy vấn chưa được tối ưu hóa tại 418749,73. Thời gian thực được thực hiện là 0,939 mili giây (chín phần mười mili giây), so với 2,5 giây của truy vấn ban đầu. Kết quả này mất ít thời gian hơn để lập kế hoạch, ước tính tốt hơn đáng kể và thời gian chạy ít hơn khoảng 3 bậc.

Hãy xem liệu chúng ta có thể làm tốt hơn không.

Thêm chỉ mục SP-GiST

time psql -qtAc "CREATE INDEX idx_spgist_geonames_location ON geonames USING spgist(location);"

CREATE INDEX 

real    1m25.205s
user    0m0.010s
sys        0m0.015s

Và sau đó chúng tôi chạy lại cùng một truy vấn.

time psql -qtAc "

EXPLAIN (ANALYZE ON, BUFFERS ON)
SELECT name, location
FROM geonames
ORDER BY location <-> '(29.9691,-95.6972)'
LIMIT 5;

                                      QUERY PLAN
-----------------------------------------------------------------------------------
 Limit  (cost=0.42..1.09 rows=5 width=38) (actual time=0.066..0.323 rows=5 loops=1)
   Buffers: shared hit=47
   ->  Index Scan using idx_spgist_geonames_location on geonames  
            (cost=0.42..1598071.32 rows=11947145 width=38) 
            (actual time=0.065..0.320 rows=5 loops=1)
         Order By: (location <-> '(29.9691,-95.6972)'::point)
         Buffers: shared hit=47
 Planning Time: 0.122 ms
 Execution Time: 0.358 ms
(7 rows)

real    0m0.040s
user    0m0.011s
sys        0m0.015s

Ồ! Hiện đang sử dụng chỉ mục SP-GiST, chi phí truy vấn chỉ là 1,09 và được thực thi trong 0,358 mili giây (một phần ba mili giây).

Hãy cùng xem xét một số điều về bản thân các chỉ mục và xem cách chúng xếp chồng lên nhau trên đĩa.

So sánh chỉ mục

tên chỉ mục	thời gian tạo	ước tính	thời gian truy vấn	indexsize	lập kế hoạch thời gian
unindexed	0S	418749.73	2555.673	0	. 493
idx_gist_geonames_location	3M 1S	1.16	. 939 mili giây	868 MB	. 786
idx_spgist_geonames_location	1 triệu 25 triệu	1,09	. 358 mili giây	523 MB	. 122

Kết luận

Vì vậy, chúng ta thấy rằng SP-GiST có tốc độ gấp đôi GiST khi thực thi, nhanh hơn gấp 8 lần so với kế hoạch và khoảng 60% kích thước trên đĩa. Và (liên quan đến bài viết này) nó cũng hỗ trợ tìm kiếm chỉ mục KNN kể từ PostgreSQL 12. Đối với loại hoạt động này, chúng tôi có một người chiến thắng rõ ràng.

Phụ lục

Thiết lập dữ liệu

Đối với bài viết này, chúng tôi sẽ sử dụng dữ liệu do GeoNames Gazetteer cung cấp.
Tác phẩm này được cấp phép theo Giấy phép Creative Commons Attribution 4.0
Dữ liệu được cung cấp “nguyên trạng” mà không có bảo hành hoặc bất kỳ đại diện nào của tính chính xác, kịp thời hoặc đầy đủ.

Tạo cấu trúc

Chúng tôi bắt đầu quá trình này bằng cách tạo một thư mục làm việc và một chút ETL.

# change to our home directory
cd
mkdir spgist
cd spgist
# get the base data.  
# This file is 350MB.  It will unpack to 1.5GB
# It will expand to 2GB in PostgreSQL,
#    and then you will still need some room for indexes
#  All together, you will need about 
#  3GB of space for this exercise
#  for about 12M rows of data.

psql -qtAc "

CREATE TABLE IF NOT EXISTS geonames (
geonameid           integer primary key
,name               text 
,asciiname          text 
,alternatenames     text 
,latitude           numeric(13,5) 
,longitude          numeric(13,5)
,feature_class      text 
,feature_code       text 
,country            text 
,cc2                text 
,admin1             text 
,admin2             bigint 
,admin3             bigint 
,admin4             bigint 
,population         bigint 
,elevation          bigint 
,dem                bigint 
,timezone           text 
,modification date  );

COMMENT ON COLUMN geonames.geonameid          
 IS ' integer id of record in geonames database';
COMMENT ON COLUMN geonames.name               
 IS ' name of geographical point (utf8) varchar(200)';
COMMENT ON COLUMN geonames.asciiname          
 IS ' name of geographical point in plain ascii characters, varchar(200)';
COMMENT ON COLUMN geonames.alternatenames     
 IS ' alternatenames, comma separated, ascii names automatically transliterated, 
    convenience attribute from alternatename table, varchar(10000)';
COMMENT ON COLUMN geonames.latitude           
 IS ' latitude in decimal degrees (wgs84)';
COMMENT ON COLUMN geonames.longitude          
 IS ' longitude in decimal degrees (wgs84)';
COMMENT ON COLUMN geonames.feature_class      
 IS ' http://www.geonames.org/export/codes.html, char(1)';
COMMENT ON COLUMN geonames.feature_code       
 IS ' http://www.geonames.org/export/codes.html, varchar(10)';
COMMENT ON COLUMN geonames.country            
 IS ' ISO-3166 2-letter country code, 2 characters';
COMMENT ON COLUMN geonames.cc2                
 IS ' alternate country codes, comma separated, ISO-3166 2-letter country code, 
    200 characters';
COMMENT ON COLUMN geonames.admin1             
 IS ' fipscode (subject to change to iso code), see exceptions below, 
    see file admin1Codes.txt for display names of this code; varchar(20)';
COMMENT ON COLUMN geonames.admin2             
 IS ' code for the second administrative division, a county in the US, 
    see file admin2Codes.txt; varchar(80) ';
COMMENT ON COLUMN geonames.admin3             
 IS ' code for third level administrative division, varchar(20)';
COMMENT ON COLUMN geonames.admin4             
 IS ' code for fourth level administrative division, varchar(20)';
COMMENT ON COLUMN geonames.population         
 IS ' bigint (8 byte int) ';
COMMENT ON COLUMN geonames.elevation          
 IS ' in meters, integer';
COMMENT ON COLUMN geonames.dem                
 IS ' digital elevation model, srtm3 or gtopo30, average elevation of 3''x3'' 
    (ca 90mx90m) or 30''x30'' (ca 900mx900m) area in meters, integer. 
    srtm processed by cgiar/ciat.';
COMMENT ON COLUMN geonames.timezone           
 IS ' the iana timezone id (see file timeZone.txt) varchar(40)';
COMMENT ON COLUMN geonames.modification       
 IS ' date of last modification in yyyy-MM-dd format';

"  #<-- Don't forget the closing quote

ETL

wget http://download.geonames.org/export/dump/allCountries.zip
unzip allCountries.zip

# do this, and go get a coffee.  This took nearly an hour
#   there will be a few lines that fail, they don't really matter much
IFS=$'\n'

for line in $(<allCountries.txt)
do

    echo -n "$line" | 
        psql -qtAc

    "COPY geonames FROM STDIN WITH CSV DELIMITER E'\t';"

2> errors.txt
done

Dọn dẹp và thiết lập

Mọi thứ khác chúng tôi làm từ bên trong psql:

psql

-- This command requires the installation
--  of postgis2 from your OS package manager.
-- For OS/X that was `port install postgresql12-postgis2`
-- it will be something similar on most platforms.
-- (e.g. apt-get install postgresql12-postgis2, 
--  yum -y install postgresql12-postgis2, etc.)
CREATE EXTENSION postgis;
CREATE EXTENSION postgis_topology;

ALTER TABLE geonames ADD COLUMN location point;

-- Go get another cup of coffee, this is going to rewrite the entire table with the new geo column.
UPDATE geonames SET location = ('(' || latitude || ', ' || longitude || ')')::point;

DELETE FROM geonames WHERE latitude IS NULL or longitude IS NULL;
-- DELETE 32   -- In my case, this ETL anomoly was too small
--  to bother fixing the records

-- Bloat removal from the update and delete operations
CLUSTER geonames USING geonames_pkey;

PostgreSQL 12:Triển khai K-Nearest Neighbor Space Partitioned Generated Tree Indexes