15. Indexación espacial¶
Como se ha visto, los índices son una de las tres funcionalidades clave de una base de datos espacial. Los índices hacen que sea posible usar una base de datos espacial para conjuntos de datos grandes. Sin los índices, cualquier búsqueda de un elemento requeriría un «escáner secuencial» de cada registro en la base de datos. El indexado acelera la búsqueda organizando los datos en un árbol de búsqueda que puede ser atravesado rápidamente para encontrar un registro concreto.
Los índices espaciales son uno de los grandes valores de PostGIS. En el ejemplo anterior, realizar uniones espaciales requiere comparar la una con la otra ambas tablas completas. Esto puede ser muy costoso: unir dos tablas de 10.000 registros cada una requerirá 100.000.000 comparaciones; con índices el coste podría ser tan bajo como 20.000 comparaciones.
Nuestro fichero de carga de datos ya contiene índices espaciales para todas las tablas, por lo que para demostrar la eficacia de los índices, vamos a eliminarlos primero.
Lancemos una query sobre nyc_census_blocks sin nuestro índice espacial.
El primer paso es eliminar el índice.
DROP INDEX nyc_census_blocks_geom_idx;
Nota
La sentencia DROP INDEX elimina un índice ya existente de la base de datos. Para más información, mirar la documentación de PostgreSQL.
Ahora, fíjate en el medidor «Timing» en la esquina inferior derecha de la ventana de consultas de pgAdmin y ejecuta lo siguiente. Nuestra consulta busca a través de cada uno de los bloques del censo para identificar los bloques que contienen paradas de metro que empiezen por la letra «B».
SELECT count(blocks.blkid)
FROM nyc_census_blocks blocks
JOIN nyc_subway_stations subways
ON ST_Contains(blocks.geom, subways.geom)
WHERE subways.name LIKE 'B%';
count
---------------
46
La tabla nyc_census_blocks es muy pequeña (solo unos pocos miles de registros) así que, incluso sin un índice, la consulta solo tarda 300 ms en mi ordenador de pruebas.
Ahora añadimos el índice espacial de nuevo y volvemos a lanzar la consulta.
CREATE INDEX nyc_census_blocks_geom_idx
ON nyc_census_blocks
USING GIST (geom);
Nota
La cláusula USING GIST le dice a PostgreSQL que use la estructura general de índices (GIST, por sus siglas en inglés) para construir el índice. Si sale un error parecido a ERROR: index row requires 11340 bytes, maximum size is 8191 al crear el índice, lo más probable es que no se haya añadido la cláusula USING GIST.
En mi ordenador de pruebas el tiempo baja hasta los 50 ms. Cuanto más grande sea la tabla, mayor será la mejora en la velocidad relativa de una consulta que utiliza un índice.
15.1. Cómo funcionan los Índices Espaciales¶
Los índices de las bases de datos estándar crean un árbol jerárquico basado en los valores de la columna que se está indexando. Los índices espaciales son un poco diferentes –no pueden indexar los elementos geográficos, si no que indexan las cajas de los mismos.
In the figure above, the number of lines that intersect the yellow star is one, the red line. But the bounding boxes of features that intersect the yellow box is two, the red and blue ones.
La forma en que la base de datos responde de una forma eficiente a la pregunta «¿qué lineas intersecan con la estrella amarilla?» es responder primero «¿qué cajas intersecan con la caja amarilla?» usando el índice (lo cual es muy rápido) y entonces hace el cálculo exacto de «¿qué lineas intersecan con la estrella amarilla?» sólo con aquellas que han sido devueltas de la primera consulta.
Para tablas grandes, este sistema de «dos pasos» de evaluar el índice aproximado primero y después determinar el resultado exacto puede reducir de una forma drástica los cálculos necesarios para responder a una consulta.
Tanto PostGIS como Oracle Spatial comparten la misma estructura de índice espacial R-Tree» 1. Los R-Trees separan los datos en rectángulos, y sub-rectángulos y sub-sub-rectángulos, etc. Es una estructura de índices autoajustable que automáticamente maneja densidades de datos variables, distintas cantidades de superposiciones de objetos y tamaños de objeto.
15.2. Funciones con Indexación Espacial¶
Sólo una parte de las funciones usan un índices espacial de forma automática, en caso de estar disponible.
Los cuatro primeros son los más utilizados en consultas y ST_DWithin es muy importante para hacer consultas tipo «dentro de una distancia» o «dentro de un radio» consiguiendo un rendimiento óptimo por el índice.
Para añadir aceleración por índices a otras funciones que no están en esta lista (la más habitual, ST_Relate) hay que añadir una clausula de indexación como la descrita debajo.
15.3. Index-Only Queries¶
La mayoría de las funciones usadas comunmente en PostGIS (ST_Contains, ST_Intersects, ST_DWithin, etc) incluyen un filtrado por índice automáticamente. Pero algunas funciones (p. ej.: ST_Relate) no incluyen este filtrado.
To do a bounding-box search using the index (and no filtering), make use of the && operator. For geometries, the && operator means «bounding boxes overlap or touch» in the same way that for numbers the = operator means «values are the same».
Let’s compare an index-only query for the population of the “West Village” to a more exact query. Using && our index-only query looks like the following:
SELECT Sum(popn_total)
FROM nyc_neighborhoods neighborhoods
JOIN nyc_census_blocks blocks
ON neighborhoods.geom && blocks.geom
WHERE neighborhoods.name = 'West Village';
49821
Ahora, hagamos la misma consulta usando la función ST_Intersects, que es más exacta.
SELECT Sum(popn_total)
FROM nyc_neighborhoods neighborhoods
JOIN nyc_census_blocks blocks
ON ST_Intersects(neighborhoods.geom, blocks.geom)
WHERE neighborhoods.name = 'West Village';
26718
A much lower answer! The first query summed up every block whose bounding box intersects the neighborhood’s bounding box; the second query only summed up those blocks that intersect the neighborhood itself.
15.4. Analyzing¶
The PostgreSQL query planner intelligently chooses when to use or not to use indexes to evaluate a query. Counter-intuitively, it is not always faster to do an index search: if the search is going to return every record in the table, traversing the index tree to get each record will actually be slower than just sequentially reading the whole table from the start.
Knowing the size of the query rectangle is not enough to pin down whether a query will return a large number or small number of records. Below, the red square is small, but will return many more records than the blue square.
In order to figure out what situation it is dealing with (reading a small part of the table versus reading a large portion of the table), PostgreSQL keeps statistics about the distribution of data in each indexed table column. By default, PostgreSQL gathers statistics on a regular basis. However, if you dramatically change the contents of your table within a short period of time, the statistics will not be up-to-date.
To ensure the statistics match your table contents, it is wise the to run the ANALYZE command after bulk data loads and deletes in your tables. This force the statistics system to gather data for all your indexed columns.
The ANALYZE command asks PostgreSQL to traverse the table and update its internal statistics used for query plan estimation (query plan analysis will be discussed later).
ANALYZE nyc_census_blocks;
15.5. Vacuuming¶
It’s worth stressing that just creating an index is not enough to allow PostgreSQL to use it effectively. VACUUMing must be performed whenever a large number of UPDATEs, INSERTs or DELETEs are issued against a table. The VACUUM command asks PostgreSQL to reclaim any unused space in the table pages left by updates or deletes to records.
Vacuuming is so critical for the efficient running of the database that PostgreSQL provides an «autovacuum» facility by default.
Autovacuum both vacuums (recovers space) and analyzes (updates statistics) on your tables at sensible intervals determined by the level of activity. While this is essential for highly transactional databases, it is not advisable to wait for an autovacuum run after adding indices or bulk-loading data. Whenever a large batch update is performed, you should manually run VACUUM.
Vacuuming and analyzing the database can be performed separately as needed. Issuing VACUUM command will not update the database statistics; likewise issuing an ANALYZE command will not recover unused table rows. Both commands can be run against the entire database, a single table, or a single column.
VACUUM ANALYZE nyc_census_blocks;
15.6. Function List¶
geometry_a && geometry_b: Returns TRUE if A’s bounding box overlaps B’s.
geometry_a = geometry_b: Returns TRUE if A’s bounding box is the same as B’s.
ST_Intersects(geometry_a, geometry_b): Returns TRUE if the Geometries/Geography «spatially intersect» - (share any portion of space) and FALSE if they don’t (they are Disjoint).
Footnotes
