Baixo desempenho ao usar índices espaciais no MySQL

13

Re-publique uma pergunta feita no Stack Overflow quando foi sugerido que este seria um fórum melhor.

Estou tentando um pequeno experimento para empurrar um conjunto de dados que não é geoespacial, mas que se encaixa muito bem e estou achando os resultados um tanto perturbadores. O conjunto de dados é genômico, por exemplo, o genoma humano, onde temos uma região do DNA onde elementos como genes ocupam coordenadas específicas de início e parada (nosso eixo X). Temos várias regiões do DNA (cromossomos) que ocupam o eixo Y. O objetivo é recuperar todos os itens que cruzam duas coordenadas X ao longo de uma única coordenada Y, por exemplo, LineString (START 1, END 2).

A teoria parecia sólida, então eu a coloquei em um projeto de genoma baseado em MySQL existente e criei uma estrutura de tabela 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 o identificador da entidade que codificamos nesta tabela e external_typecodifica a fonte disso. Tudo parecia bom e introduzi alguns dados preliminares (30.000 linhas) que pareciam funcionar bem. Quando isso ultrapassou a marca de 3 milhões de linhas, o MySQL se recusou a usar o índice espacial e ficou mais lento quando foi forçado a usá-lo (40 segundos vs. 5 segundos usando uma varredura de tabela completa). Quando mais dados foram adicionados, o índice começou a ser usado, mas a penalidade de desempenho persistiu. Forçar o desligamento do índice reduziu a consulta para 8 segundos. A consulta que estou usando se parece com:

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

Os dados que entram nisso são muito densos ao longo das dimensões Y (pense como se você tivesse registrado a posição de cada prédio, caixa telefônica, caixa postal e pombo em uma estrada muito longa). Fiz testes de como o R-Indexes se comporta com esses dados em Java, assim como com outros no campo, os aplicaram a formatos de arquivo simples com êxito. No entanto, ninguém os aplicou aos bancos de dados AFAIK, que é o objetivo deste teste.

Alguém aí viu um comportamento semelhante ao adicionar grandes quantidades de dados a um modelo espacial que não é muito díspar ao longo de um eixo específico? O problema persiste se eu reverter o uso de coordenadas. Estou executando a seguinte configuração, se isso é uma causa

  • MacOS 10.6.6
  • MySQL 5.1.46
andeyatz
fonte

Respostas:

5

O MySQL, como o PostGIS, armazena seus dados de índice espacial em uma estrutura em árvore R para que possa encontrar rapidamente as coisas. Uma árvore R, como uma árvore B, é organizada de tal maneira que é otimizada para recuperar apenas uma pequena fração do total de dados na tabela. Na verdade, é mais rápido ignorar o índice para consultas que precisam ler uma seção grande da tabela para retornar dados ou realizar uma junção enorme, um caso clássico que dá origem a muitos [pôsteres] de fóruns de bancos de dados queixam-se de uma consulta que retorna metade da sua tabela "sem usar o novo índice que eles acabaram de criar".

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

Se você pode ajustar todos os dados da tabela na memória, seu desempenho é bom. Se / quando você precisar começar a fazer leituras de disco, o desempenho rapidamente será ruim. Você estava executando padrões de uso de memória da sua instância mysql para os dois casos: 30k linhas vs. 3000k linhas?

tmarthal
fonte
Eu acho que isso poderia estar mais perto do problema. TBH é o índice R que eu quero; a outra matemática espacial é um bônus interessante, pois isso teria que ser feito na camada da API no sistema antigo. Eu tentei um pouco de ajuste, mas aumentar os buffers de chave não ajudou (outros buffers não ajudarão aqui, como o buffer de tabela, pois é uma consulta de 1 tabela no meu servidor pessoal). O que é estranho é que o MySQL martela minha máquina no chão quando as consultas são executadas (100% durante a execução da consulta). Dito seu fazer uma varredura completa da tabela talvez por isso, não é tão estranho
andeyatz
5

Algo deve estar errado com a instalação do mysql ou as configurações .ini. Acabei de testar um índice geoespacial no meu antigo mac (10.6.8 / MySQL 5.2). Essa configuração é semelhante à sua e testei o grande despejo de dados geográficos ( 9 milhões de registros ). Eu fiz 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; 

Foram necessários apenas 0,0336 seg.

Eu uso a consulta acima, por exemplo, para comparações entre tabelas em que a tabela de onde vêm apenas os valores de lat / lng para @center tem um INDEX simples de city_latitude / city_longitude e 9-12 Mio. A tabela de geonames.org possui um índice geoespacial.

E eu só queria acrescentar que, quando alguém insere o big data em uma tabela, pode ser mais eficiente adicionar o índice após INSERT. Caso contrário, levará mais tempo para cada linha que você adicionar ... [mas isso não é importante]

sebilasse
fonte
Uau, isso é realmente bom. Agora não tenho certeza do que estava fazendo de errado em meus próprios testes. Uma coisa que pode estar causando um problema é a natureza dos meus conjuntos de dados em comparação com os conjuntos de dados geoespaciais mais tradicionais. Dito isto, estou apenas adivinhando e não tenho base para isso. É brilhante ver que você não precisa forçar o índice na memória para obter a velocidade.
precisa saber é o seguinte
A cláusula WHERE com o raio pode filtrar uma boa parte da tabela do uso de um índice.
tmarthal
2

Você já pensou em dividi-lo em duas colunas 1D em vez de uma única coluna 2D?

O otimizador pode estar bloqueando todos os dados semelhantes e ter duas colunas com maior variedade pode ajudar.

O que você também pode verificar é a ordem em que os itens são verificados. Eu tive um problema no Oracle Spatial, onde estava pesquisando sobrenome e um filtro IN_REGION. A Oracle decidiu que a maneira mais rápida era usar o sobrenome e depois verificar a região. Deixe-me dizer-lhe, fazer uma verificação na região de todos os Robinson em Cleveland é lento . Lembro que tive que passar um argumento específico do Oracle para forçá-lo a usar o índice espacial primeiro.

Mark Robinson
fonte
Infelizmente, uma dimensão é muito menos povoada que outra. Para colocar isso em contexto, o genoma humano possui 24 cromossomos únicos (22 pares e os dois cromossomos sexuais), juntamente com um conjunto de dados que foram reunidos em diferentes níveis. O que significa que, se você mapear elementos para o caso de uso básico, são apenas 24 identificadores exclusivos em uma dimensão. A esperança original era que o índice da árvore R fosse capaz de executar não apenas verificações de intervalo sobrepostas de maior desempenho, mas também diferenciar essas regiões em uma única consulta.
andeyatz