Bajo rendimiento al usar índices espaciales en MySQL

13

Vuelva a publicar una pregunta que se hizo en Stack Overflow cuando se sugirió que este sería un mejor foro.

Estoy intentando un pequeño experimento para impulsar un conjunto de datos que no es geoespacial pero que se ajusta bastante bien y encuentro los resultados algo inquietantes. El conjunto de datos son datos genómicos, por ejemplo, el Genoma Humano, donde tenemos una región de ADN donde elementos como los genes ocupan coordenadas específicas de inicio y parada (nuestro eje X). Tenemos múltiples regiones de ADN (cromosomas) que ocupan el eje Y. El objetivo es recuperar todos los elementos que intersecan dos coordenadas X a lo largo de una sola coordenada Y, por ejemplo, LineString (START 1, END 2).

La teoría parecía sólida, así que la introduje en un proyecto genómico basado en MySQL existente y se me ocurrió una estructura de tabla como:

CREATE TABLE `spatial_feature` (
  `spatial_feature_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `external_id` int(10) unsigned NOT NULL,
  `external_type` int(3) unsigned NOT NULL,
  `location` geometry NOT NULL,
  PRIMARY KEY (`spatial_feature_id`),
  SPATIAL KEY `sf_location_idx` (`location`)
) ENGINE=MyISAM;

external_idrepresenta el identificador de la entidad que hemos codificado en esta tabla y external_typecodifica la fuente de esta. Todo se veía bien e introduje algunos datos preliminares (30,000 filas) que parecían funcionar bien. Cuando esto aumentó más allá de la marca de 3 millones de filas, MySQL se negó a usar el índice espacial y fue más lento cuando se vio obligado a usarlo (40 segundos frente a 5 segundos usando un escaneo de tabla completo). Cuando se agregaron más datos, el índice comenzó a usarse, pero la penalización de rendimiento persistió. Al forzar el índice, la consulta se redujo a 8 segundos. La consulta que estoy usando se ve así:

select count(*)
from spatial_feature
where MBRIntersects(GeomFromText('LineString(7420023 1, 7420023 1)'), location);

Los datos que entran en esto son muy densos a lo largo de las dimensiones Y (piense en ello como si hubiera registrado la posición de cada edificio, cabina telefónica, buzón y paloma en un camino muy largo). He realizado pruebas de cómo se comportan los índices R con estos datos en Java, así como otros en el campo los han aplicado con éxito a formatos de archivo plano. Sin embargo, nadie los ha aplicado a las bases de datos AFAIK, que es el objetivo de esta prueba.

¿Alguien ha visto un comportamiento similar al agregar grandes cantidades de datos a un modelo espacial que no es muy disparejo a lo largo de un eje en particular? El problema persiste si revierto el uso de coordenadas. Estoy ejecutando la siguiente configuración si eso es una causa

  • MacOS 10.6.6
  • MySQL 5.1.46
andeyatz
fuente

Respuestas:

5

MySQL, como PostGIS, almacena sus datos de índice espacial en una estructura de árbol R para que pueda encontrar cosas rápidamente. Un árbol R, como un árbol B, está organizado de tal manera que está optimizado para recuperar solo una pequeña fracción de los datos totales en la tabla. En realidad, es más rápido ignorar el índice de consultas que necesitan leer una gran sección de la tabla para devolver datos o realizar una gran unión, un caso clásico que da lugar a muchos foros de base de datos [carteles] quejándose de una consulta que devuelve la mitad de sus datos. tabla "no utiliza el nuevo índice que acaba de crear".

De http://rickonrails.wordpress.com/2009/03/30/big-ole-mysql-spatial-table-optimization-tricks/

Si puede ajustar todos los datos de su tabla en la memoria, su rendimiento es bueno. Si / cuando necesita comenzar a hacer lecturas de disco, el rendimiento se deteriora rápidamente. ¿Estaba haciendo patrones de uso de memoria de su instancia de mysql para los dos casos: 30k filas frente a 3000k filas?

tmarthal
fuente
Creo que esto podría estar más cerca del problema. TBH es el índice R que quiero; las otras matemáticas espaciales son una buena ventaja, ya que eso tendría que hacerse en la capa API bajo el sistema anterior. Intenté un poco de ajuste, pero el aumento de los buffers clave no ayudó (otros buffers no ayudarán aquí, como el buffer de tabla, ya que es una consulta de 1 tabla en mi servidor personal). Lo extraño es que MySQL golpea mi máquina en el suelo cuando se ejecutan las consultas (100% durante la ejecución de la consulta). Dicho esto su haciendo un escaneo completo de tabla, así que quizás no es tan extraña
andeyatz
5

Algo debe estar mal con su instalación de mysql o la configuración de .ini. Acabo de probar un índice geoespacial en mi Mac anterior (10.6.8 / MySQL 5.2). Esa configuración es similar a la suya y probé el gran volcado de geodatos ( 9 millones de registros ). Hice esta consulta:

SET @radius = 30;
SET @center = GeomFromText('POINT(51.51359 7.465425)');
SET @r = @radius/69.1;
SET @bbox = CONCAT('POLYGON((', 
  X(@center) - @r, ' ', Y(@center) - @r, ',', 
  X(@center) + @r, ' ', Y(@center) - @r, ',', 
  X(@center) + @r, ' ', Y(@center) + @r, ',', 
  X(@center) - @r, ' ', Y(@center) + @r, ',', 
  X(@center) - @r, ' ', Y(@center) - @r, '))' 
);

SELECT geonameid, SQRT(POW( ABS( X(point) - X(@center)), 2) + POW( ABS(Y(point) - Y(@center)), 2 ))*69.1 
AS distance
FROM TABLENAME AS root
WHERE Intersects( point, GeomFromText(@bbox) ) 
AND SQRT(POW( ABS( X(point) - X(@center)), 2) + POW( ABS(Y(point) - Y(@center)), 2 )) < @r 
ORDER BY distance; 

Tomó solo 0.0336 segundos.

Utilizo la consulta anterior, por ejemplo, para comparaciones entre tablas donde la tabla de la que provienen solo los valores lat / lng para @center tiene un ÍNDICE simple de city_latitude / city_longitude y el 9-12 Mio. La tabla de geonames.org tiene un índice geoespacial.

Y solo quería agregar que cuando alguien inserta los datos grandes en una tabla, podría ser más eficiente agregar el índice después de INSERTAR. Si no, tomará más tiempo por cada fila que agregue ... [pero eso no es importante]

sebilasse
fuente
Wow, eso es realmente bueno. Ahora no estoy seguro de lo que estaba haciendo mal en mis propias pruebas. Una cosa que podría estar causando un problema es la naturaleza de mis conjuntos de datos en comparación con los conjuntos de datos geoespaciales más tradicionales. Dicho esto, solo estoy adivinando y no tengo base para esto. Es brillante ver que no necesita forzar el índice en la memoria para obtener la velocidad.
andeyatz 05 de
La cláusula WHERE con el radio podría estar filtrando una buena parte de la tabla del uso de un índice.
tmarthal
2

¿Has pensado en dividirlo en dos columnas 1D en lugar de una sola columna 2D?

El optimizador podría estar ahogando todos los datos similares y tener dos columnas con mayor variedad podría ayudar.

Lo que también puede verificar es el orden en que se verifican los artículos. Tuve un problema en Oracle Spatial donde buscaba en Apellido y un filtro IN_REGION. Oracle decidió que la forma más rápida era usar el apellido y luego hacer una verificación de la región. Déjame decirte que hacer un control regional de todos los Robinson en Cleveland es lento . Recuerdo que tuve que pasar un argumento específico de Oracle para obligarlo a usar el índice espacial primero.

Mark Robinson
fuente
Desafortunadamente, 1 dimensión está mucho menos poblada que otra dimensión. Para poner esto en contexto, el genoma humano tiene 24 cromosomas únicos (22 pares y los dos cromosomas sexuales) junto con una bolsa de datos que se ha reunido en diferentes niveles. Lo que significa que si asigna elementos al caso de uso básico que son solo 24 identificadores únicos en una dimensión. La esperanza original era que el índice R-tree hubiera podido realizar no solo más comprobaciones de rango de superposición de rendimiento, sino también diferenciar entre estas regiones en una sola consulta.
andeyatz 01 de