Wartość indeksowania
PostgreSQL zapewnia prosty liniowy operator odległości <-> (odległość liniowa). Wykorzystamy to, aby znaleźć punkty, które są najbliżej danej lokalizacji.
PostgreSQL zapewnia prosty liniowy operator odległości danych i nie przeprowadzając optymalizacji i nie mając indeksów, widzimy następujący plan wykonania:
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
a oto wyniki:(te same wyniki dla wszystkich żądań, więc pominiemy je później).
| nazwa | lokalizacja |
|---|---|
| Cyprys | (29.96911,-95.69717) |
| Kościół baptystów Cypress Pointe | (29.9732,-95.6873) |
| Cypress Post Office | (29.9743,-95.67953) |
| Gorące studnie | (29.95689,-95.68189) |
| Lotnisko Dry Creek | (29,98571,-95,68597) |
Tak więc 418749,73 to koszt do pokonania OPTIMIZERA, a wykonanie tego zapytania zajęło dwie i pół sekundy (2555.673). W rzeczywistości jest to bardzo dobry wynik, używając PostgreSQL bez żadnych optymalizacji w odniesieniu do tabeli z 11 milionami wierszy. Dlatego też wybraliśmy większy zestaw danych, ponieważ różnica przy użyciu indeksów byłaby bardzo minimalna w stosunku do mniej niż 10 milionów wierszy. Równoległe skanowanie sekwencyjne jest fantastyczne, ale to kolejny artykuł.
Dodawanie indeksu GiST
Proces optymalizacji rozpoczynamy od dodania indeksu GiST. Ponieważ nasze przykładowe zapytanie ma
LIMIT
klauzula 5 pozycji, mamy bardzo wysoką selektywność. Zachęci to planistę do korzystania z indeksu, więc udostępnimy taki, który całkiem dobrze współpracuje z danymi geometrycznymi.
time psql -qtAc "CREATE INDEX idx_gist_geonames_location ON geonames USING gist(location);"
Tworzenie indeksu wiąże się z pewnym kosztem.
CREATE INDEX
real 3m1.988s
user 0m0.011s
sys 0m0.014s
A następnie ponownie uruchom to samo zapytanie.
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
W tym przypadku widzimy dość radykalną poprawę. Szacunkowy koszt zapytania to tylko 1,16! Porównaj to z pierwotnym kosztem niezoptymalizowanego zapytania w 418749,73. Rzeczywisty czas potrzebny na wykonanie zapytania wyniósł 0,939 milisekundy (dziewięć dziesiątych milisekundy), co w porównaniu z 2,5 sekundy oryginalnego zapytania. Ten wynik zabrał mniej czasu na zaplanowanie, uzyskał znacznie lepsze oszacowanie i zabrał około 3 rzędy wielkości mniej czasu działania.
Zobaczmy, czy możemy zrobić lepiej.
Dodawanie indeksu 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
A potem ponownie uruchamiamy to samo zapytanie.
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
Wow! Teraz przy użyciu indeksu SP-GiST zapytanie kosztowało tylko 1,09 i zostało wykonane w 0,358 milisekundy (jedna trzecia milisekundy).
Przyjrzyjmy się niektórym rzeczom dotyczącym samych indeksów i zobaczmy, jak układają się one w stos na dysku.
Porównania indeksów
| nazwa indeksu | czas utworzenia | oszacowanie | czas zapytania | indexsize | czas planu |
|---|---|---|---|---|---|
| nieindeksowane | 0S | 418749.73 | 2555.673 | 0 | .493 |
| idx_gist_genames_location | 3M 1S | 1,16 | 0.939 ms | 868 MB | 0.786 |
| idx_spgist_genames_location | 1M 25S | 1.09 | 0.358 ms | 523 MB | 0.122 |
Wnioski
Widzimy więc, że SP-GiST jest dwukrotnie szybszy od wykonywanego GiST, 8x szybszy w planowaniu i około 60% rozmiaru na dysku. I (w związku z tym artykułem) obsługuje również przeszukiwanie indeksu KNN od PostgreSQL 12. W przypadku tego typu operacji mamy wyraźnego zwycięzcę.
Załączniki
Konfigurowanie danych
W tym artykule użyjemy danych dostarczonych przez GeoNames Gazetteer.
Ta praca jest objęta licencją Creative Commons Uznanie autorstwa 4.0
Dane są dostarczane „tak jak są” bez gwarancji lub jakiejkolwiek reprezentacji dokładność, terminowość lub kompletność.
Utwórz strukturę
Proces rozpoczynamy od utworzenia katalogu roboczego i odrobiny 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
Wyczyść i skonfiguruj
Wszystko, co robimy od wewnątrz 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;
