[MySQL] Verkeerd gebruik index bij order by

[dik_voormekaar]

Ik heb een probleem dat MySQL de index niet goed gebruikt.
Ik heb een tabel 'geoname' met ongemeer 7 miljoen records, en wil zoeken op het dichtsbijzijnde record.
Daartoe heb ik onder andere de indexen 'latitude' en 'longitude' gemaakt.
Deze wordt ook gebruikt als ik normaal zoek dmv. 'between a and b' (en is dan ook snel), maar niet als ik er een order by achter zet. Het zoeken duurt dan veel langer. Dit komt m.i. door de filesort.

Even de tabel:

SQL:

CREATE TABLE geoname ( 
geonameid int, 
name varchar(200), 
latitude decimal(10,7), 
longitude decimal(10,7), 
fclass char(1), 
fcode varchar(10), 
country varchar(2), 
population int, 
elevation int, 
moddate date,
PRIMARY KEY     (`geonameid`),
KEY `name`      (`name`(10)),
KEY `country`   (`country`,`admin1`(4),`admin2`(4)),
KEY `fclass`    (`fclass`,`fcode`(4),`country`),
KEY `fcode`     (`fcode`(4),`country`),
KEY `latitude`  (`latitude`),
KEY `longitude` (`longitude`),
KEY `moddate`   (`moddate`) 
) ENGINE=MyISAM  CHARACTER SET utf8; 

Als ik de volgende query draai:

SQL:

select * from geoname 
where latitude between 52 and 52.2 and longitude between 5.9 and 6.1

De explain hiervan is:

code:

Id Select_type Table Type Possible_keys Key Key_len Ref Rows Extra 
1 SIMPLE geoname range latitude,longitude longitude 7  10081 Using where

Echter, deze query geeft :

SQL:

select * from geoname 
where latitude between 52 and 52.2 and longitude between 5.9 and 6.1 
order by abs(latitude-52)+abs(longitude-6.0) 
limit 1

De explain hiervan is:

code:

Id Select_type Table Type Possible_keys Key Key_len Ref Rows Extra 
1 SIMPLE geoname range latitude,longitude longitude 7  10081 Using where; Using filesort

Je ziet dus dat bij de tweede query er een filesort zit. Hierdoor duurt de query erg lang.
Hoe kan ik dit verbeteren?

[cariolive23]

Je sorteert op een berekening, daar kun je in MySQL geen index op maken, MySQL kent geen functionele indexen. Je zou de berekening vooraf kunnen doen en het resultaat in een aparte kolom kunnen opslaan, daar kun je namelijk wel een index op maken. Dit kun je met triggers onderhouden.

Je zou ook kunnen overstappen op PostgreSQL, dan is een functionele index geen enkel probleem.

Ps. Waarom twee aparte indexen op latitude en longitude? De query is waarschijnlijk beter af met één index waar beide kolommen in staan.

[dik_voormekaar]

De berekening vooraf doen gaat natuurlijk niet, want elke keer zoek je naar een andere coordinaat...
Dat is dan in PostgreSQL toch ook een probleem, met een functionele index ?

[cariolive23]

PostgreSQL heeft PostGIS, een extensie speciaal voor geografie. Daar zijn dus ook speciale indexen voor en dit werkt razendsnel. Dit kun je zelf installeren in PostgreSQL, stelt niks voor.

[JaQ]

Ik begrijp niet direct waarom je een order by nodig hebt om het dichtstbijzijnde record te vinden? (oftewel: waarom doe je die order by?)

[dik_voormekaar]

JaQ schreef op zaterdag 17 april 2010 @ 20:57:
Ik begrijp niet direct waarom je een order by nodig hebt om het dichtstbijzijnde record te vinden? (oftewel: waarom doe je die order by?)

Hoe zou je dat dan doen?

[JaQ]

dik_voormekaar schreef op zaterdag 17 april 2010 @ 21:04:
Hoe zou je dat dan doen?

Ik zou niet weten hoe ik dat zou moeten oplossen in mysql, ik ben geen mysql kenner. Waarschijnlijk zou ik een slow-by-slow procedure overhouden die waarden gaat vergelijken. iig niet echt fraai. Dus heb ik even gegoogled

Een database met gis ondersteuning (van postgres en oracle weet ik zeker dat die er is) heb je speciale "distance" functies waarmee je dit zou kunnen oplossen.

Hier staat ook een oplossing: http://forums.mysql.com/read.php?20,197159,197182#msg-197182 iig is je zoekterm nearest neighbor.

[ Voor 13% gewijzigd door JaQ op 17-04-2010 21:25 . Reden: link toegevoegd ]

[dik_voormekaar]

Overigens heb ik net de twee aparte indexen op latitude en longitude omgezet naar een enkele waar beide velden in staan. Gek genoeg krijg ik ook 'filesort' in de explain, maar de query is wel snel ?!?

[Cartman!]

Je kunt het sorten ook verplaatsen naar je code ipv. het in je query te doen. Gewoon wat benchmarks uitvoeren en je weet of het sneller is

[dik_voormekaar]

Dat had ik ook al geprobeerd. (Dele hele resultset opgehaald met de betweens, en dan zoeken naar de dichtsbijzijnde). Gaat wel sneller, maar ik wilde graag die order by erbij hebben.

[Cartman!]

Maar waarom? Snelheid lijkt me het belangrijkste ding voor je. Overigens heeft de order toch helemaal geen zin? Ik neem aan dat je wilt sorteren op de afstand van userinput tot de plekken die je uit je db haalt. Ik weet niet hoe nauwkeurig de berekening is die je nu doet maar je resultaat levert iig. geen afstand op van het verschil (wat opzich niet erg is als je dat niet nodig hebt).

[Wolfboy]

dik_voormekaar schreef op zaterdag 17 april 2010 @ 20:33:
De berekening vooraf doen gaat natuurlijk niet, want elke keer zoek je naar een andere coordinaat...
Dat is dan in PostgreSQL toch ook een probleem, met een functionele index ?

Dat klopt, met Postgres kan je een index over een functie aanmaken die dit dus voor je kan oplossen. Al zou je dan beter PostGIS kunnen gebruiken.

Overigens heeft MySQL zelf ook wel wat GIS extensies, al heb ik geen idee hoe volwassen die zijn: http://dev.mysql.com/doc/...n/spatial-extensions.html

[Wolfboy]

dik_voormekaar schreef op zaterdag 17 april 2010 @ 21:46:
Dat had ik ook al geprobeerd. (Dele hele resultset opgehaald met de betweens, en dan zoeken naar de dichtsbijzijnde). Gaat wel sneller, maar ik wilde graag die order by erbij hebben.

Subquery pakken dan, als je resultset al erg klein is dan maakt dat weinig verschil in snelheid. De sort zal dan wel een filesort zijn maar over de paar geselecteerde rijen, in plaats van alles.

[pedorus]

dik_voormekaar schreef op zaterdag 17 april 2010 @ 21:24:
Overigens heb ik net de twee aparte indexen op latitude en longitude omgezet naar een enkele waar beide velden in staan. Gek genoeg krijg ik ook 'filesort' in de explain, maar de query is wel snel ?!?

Dat lijkt me helemaal niet gek. Van die 2 aparte indexen, kan er maar 1 tegelijkertijd nuttig gebruikt worden. Bij die gecombineerde index hoeft niet steeds meer naar recordniveau gegaan te worden om te kijken of een record matcht. De order by die je hebt kan niet afgehandeld worden met een index, dus die zal altijd een filesort opleveren.

[dik_voormekaar]

Cartman! schreef op zondag 18 april 2010 @ 15:48:
Maar waarom? Snelheid lijkt me het belangrijkste ding voor je. Overigens heeft de order toch helemaal geen zin? Ik neem aan dat je wilt sorteren op de afstand van userinput tot de plekken die je uit je db haalt. Ik weet niet hoe nauwkeurig de berekening is die je nu doet maar je resultaat levert iig. geen afstand op van het verschil (wat opzich niet erg is als je dat niet nodig hebt).

Snelheid is inderdaad het belangrijkste. De berekening is niet helemaal correct inderdaad, maar die kan ik altijd later nog exacter toevoegen.
Ik ga eens goed naar de extensies lijken, PostGIS en die spatial extensie voor MySQL.

[Cartman!]

Ik kan je verklappen dat die (echte) berekening in je query best wel zwaar kan zijn. De )naar mijn mening) mooiste oplossing als je in MySQL geen spatial extensie hebt is om een box te berekenen van je radius en daarop limit in je query (latitude, longitude). In je code reken je dan de afstanden uit voor je results en alles wat buiten de radius valt maar wel in de box die gooi je uit je array van resultaten. Zo heb je een simpele query en weinig berekeningen voor de afstand. Als je de afstand niet hoef te laten zien dan kun je ook een binnenste box gebruiken van je cirkel, dan hoef je alleen de randgevallen nog maar uit te rekenen