Il valore dell'indicizzazione
PostgreSQL fornisce un semplice operatore di distanza lineare <->
(distanza lineare). Lo useremo per trovare i punti più vicini a una determinata posizione.
PostgreSQL fornisce un semplice operatore di distanza lineare i dati e, senza ottimizzazioni e senza indici, vediamo il seguente piano di esecuzione:
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
ed ecco i risultati:(gli stessi risultati per tutte le richieste, quindi li ometteremo in seguito.)
nome | posizione |
---|---|
Cipresso | (29.96911,-95.69717) |
Cypress Pointe Baptist Church | (29.9732,-95.6873) |
Ufficio postale di Cypress | (29.9743,-95.67953) |
Pozzi caldi | (29.95689,-95.68189) |
Aeroporto di Dry Creek | (29.98571,-95.68597) |
Quindi, 418749.73 è il costo OPTIMIZER da battere e ci sono voluti due secondi e mezzo (2555.673) per eseguire quella query. Questo è in realtà un ottimo risultato, utilizzando PostgreSQL senza alcuna ottimizzazione rispetto a una tabella di 11 milioni di righe. Questo è anche il motivo per cui abbiamo selezionato un set di dati più ampio, poiché ci sarebbero differenze minime utilizzando gli indici rispetto a meno di 10 milioni di righe. Le scansioni sequenziali parallele sono fantastiche, ma questo è un altro articolo.
Aggiunta dell'indice GiST
Iniziamo il processo di ottimizzazione aggiungendo un indice GiST. Perché la nostra query di esempio ha un
LIMIT
clausola di 5 articoli, abbiamo una selettività molto alta. Ciò incoraggerà il pianificatore a utilizzare un indice, quindi ne forniremo uno che funzioni abbastanza bene con i dati geometrici.
time psql -qtAc "CREATE INDEX idx_gist_geonames_location ON geonames USING gist(location);"
L'atto di creare l'indice ha un po' di spese.
CREATE INDEX
real 3m1.988s
user 0m0.011s
sys 0m0.014s
E poi esegui di nuovo la stessa query.
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
In questo caso, vediamo un miglioramento piuttosto drammatico. Il costo stimato della query è solo 1,16! Confrontalo con il costo originale della query non ottimizzata a 418749.73. Il tempo effettivo impiegato è stato di 0,939 millisecondi (nove decimi di millisecondo), rispetto ai 2,5 secondi della query originale. Questo risultato ha richiesto meno tempo per la pianificazione, ha ottenuto una stima nettamente migliore e ha richiesto circa 3 ordini di grandezza in meno di runtime.
Vediamo se possiamo fare di meglio.
Aggiunta di un indice 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
E poi eseguiamo di nuovo la stessa query.
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
Oh! Ora, utilizzando un indice SP-GiST, la query costa solo 1,09 ed è eseguita in 0,358 millisecondi (un terzo di millisecondo).
Esaminiamo alcune cose sugli indici stessi e vediamo come si accumulano l'uno sull'altro sul disco.
Confronti di indici
nome indice | tempo di creazione | stima | tempo di query | dimensione indice | pianifica il tempo |
---|---|---|---|---|---|
non indicizzato | 0S | 418749.73 | 2555.673 | 0 | .493 |
idx_gist_geonames_location | 3M 1S | 1.16 | .939 ms | 868 MB | .786 |
idx_spgist_geonames_location | 1M 25S | 1.09 | .358 ms | 523 MB | .122 |
Conclusioni
Quindi, vediamo che SP-GiST è il doppio della velocità di GiST in esecuzione, 8 volte più veloce da pianificare e circa il 60% della dimensione su disco. E (rilevante per questo articolo) supporta anche la ricerca nell'indice KNN a partire da PostgreSQL 12. Per questo tipo di operazione, abbiamo un chiaro vincitore.
Appendici
Configurazione dei dati
Per questo articolo, utilizzeremo i dati forniti dal GeoNames Gazetteer.
Questo lavoro è concesso in licenza con una licenza Creative Commons Attribution 4.0
I dati sono forniti "così come sono" senza alcuna garanzia o rappresentazione di accuratezza, tempestività o completezza.
Crea la struttura
Iniziamo il processo creando una directory di lavoro e un po' di 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
Pulisci e configura
Tutto il resto che facciamo da 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;