[gregoff]

Nu fick jag en svårare nöt att knäcka. Jag har en tabell som innehåller ca 400.000 rader och alla (nästan) har en latitud/longitud koordinat. Jag vill då skriva frågor som innebär att lista de närmaste raderna inom en viss radie utifrån en given punkt. Exempel:

SELECT *, ( 3959 * ACOS( COS( RADIANS(AAA) ) * COS( RADIANS( LAT ) ) * COS( RADIANS( LONG ) - RADIANS(OOO) ) + SIN( RADIANS(AAA) ) * SIN( RADIANS( LAT ) ) ) ) AS distance FROM tabellen_ifråga HAVING distance < X ORDER BY distance

Där är AAA latituden, OOO är longituden och X är avståndet (radien) utifrån utgångspunkten.

Problemet är inte frågan i sig (utan den får de svar den ska ha), utan mitt problem är prestandan. Att köra ovannämnda fråga kan ta ca 1 sekund och i vissa fall kan jag behöva att köra den 3 gånger på en sidvisning.

Tabeller ser ut enl. nedan:

ID - PK
LONG - VARCHAR(15) - INDEX
LAT - VARCHAR(15) - INDEX

Exempel på en koordinat kan vara:
LONG: -84.093177
LAT: 35.922934

Jag kör MySQL 5.1.58 och MyISAM som db-motor (standard)

Vad kan jag göra? Jag kör detta på en vanlig VPS hos Glesys med Debian 6, 64-bit

Tips mottages gladligen!

[tartareandesire]

Jag brukar köra en betydligt enklare avståndsformel i databasqueryn och först därefter räkna mer exakt avstånd på de utvalda. Trigonometriska funktioner är tunga.

[gregoff]

Ursprungligen postat av tartareandesire

Jag brukar köra en betydligt enklare avståndsformel i databasqueryn och först därefter räkna mer exakt avstånd på de utvalda. Trigonometriska funktioner är tunga.

Har du något exempel? Det exakta avståndet räknar jag ändå ut med php, så det är bara rätt urval jag behöver att utgå ifrån.

[Magnus_A]

Pröva gärna postgresql och ta fram avstånd direkt med ST_Distance i postgis.

[gregoff]

Ursprungligen postat av Magnus_A

Pröva gärna postgresql och ta fram avstånd direkt med ST_Distance i postgis.

Har tyvärr inte möjlighet att byta sql-databas.

[abergman]

Vad har du för prestanda på den maskinen? Har du provat att lägga på mer power och se om det blir något större förändring?

[Westman]

Varför köra den flera gånger, är det med olika X?

[gregoff]

På en VPS hos Glesys kan man välja antal kärnor man vill ha, men inte hur "snabba" dom ska vara. Av eller på, typ.

Ursprungligen postat av abergman

Vad har du för prestanda på den maskinen? Har du provat att lägga på mer power och se om det blir något större förändring?

[andreasp]

Själva grundproblemet här är att din query inte kan använda några index -- och blir därför väldigt slö eftersom den måste söka igenom hela tabellen och applicera din formel på alla rader. En snabbare CPU/biffigare server är knappast lösningen på problemet. 400 000 rader som är indexerade kräver inte någon extrem hårdvara att söka igenom snabbt.

En lösning skulle kunna vara typ:
SELECT *, <lång formel> AS distance FROM tabellen_ifråga WHERE (lat BETWEEN A AND B) AND (lon BETWEEN C AND D) HAVING distance < X ORDER BY distance

Där A, B, C och D är yttre gränser för platser som inte är intressanta. Om gränserna uppskattas vettigt så borde de skära bort den största delen av alla rader effektivt, och sen kan resten sökas igenom med den "tunga" formeln. Det är viktigt att lat/lon är indexerade så att de kan sökas effektivt (som du har skrivit att de redan är). Är inte helt säker på hur bra jämförelserna blir när du lagrar LAT/LONG som VARCHAR (minustecknet kan ställa till problem), det vore nog lämpligare (och garanterat effektivare) med en numerisk datatyp.

MySQL känns i det här fallet inte som den bästa lösningen på problemet. Som Magnus_A skriver så skulle PostgreSQL/PostGIS lösa problemet väldigt enkelt med ett spatial index och ST_Distance. MySQL har även en liknande spatial extension, som inte är speciell komplett, och är inte säker på att den kan lösa problemet effektivt överhuvudtaget (men jag kan ha fel!).

MongoDB har även stöd för spatial indexes och distans-queries, om du kunde lägga dina koordinater där och göra själva distans-sökningen där skulle det kunna vara ett alternativ.

Jag är rädd att det inte finns någon riktigt bra lösning med MySQL förutom någon slags workaround som ovan, som både är krånligare, mindre effektiv och framför allt: fulare!

[gregoff]

Känns ändå som att detta gav mig lite ledtrådar.

Istället för att använda en jobbig formel (som troligen är ganska krävande) så skulle man kanske kunna använda sig av en kvadrat istället för radie. Exempelvis att man ställer frågan utifrån LAT plus/minus X och LONG plus/minus X (med hjälp av t.ex. BETWEEN). Att jag får lite mer svar än jag skulle fått med den jobbiga formeln gör inte så mycket för det kan jag enkelt sortera bort med en liknande php-formel.

Kanske kunde vara något för mig att testa.

Kan nog vara värt att testa att konvertera columnen till lämplig datatyp med innan man gör något annat först.

Ursprungligen postat av andreasp

Själva grundproblemet här är att din query inte kan använda några index -- och blir därför väldigt slö eftersom den måste söka igenom hela tabellen och applicera din formel på alla rader. En snabbare CPU/biffigare server är knappast lösningen på problemet. 400 000 rader som är indexerade kräver inte någon extrem hårdvara att söka igenom snabbt.

En lösning skulle kunna vara typ:
SELECT *, <lång formel> AS distance FROM tabellen_ifråga WHERE (lat BETWEEN A AND B) AND (lon BETWEEN C AND D) HAVING distance < X ORDER BY distance

Där A, B, C och D är yttre gränser för platser som inte är intressanta. Om gränserna uppskattas vettigt så borde de skära bort den största delen av alla rader effektivt, och sen kan resten sökas igenom med den "tunga" formeln. Det är viktigt att lat/lon är indexerade så att de kan sökas effektivt (som du har skrivit att de redan är). Är inte helt säker på hur bra jämförelserna blir när du lagrar LAT/LONG som VARCHAR (minustecknet kan ställa till problem), det vore nog lämpligare (och garanterat effektivare) med en numerisk datatyp.

MySQL känns i det här fallet inte som den bästa lösningen på problemet. Som Magnus_A skriver så skulle PostgreSQL/PostGIS lösa problemet väldigt enkelt med ett spatial index och ST_Distance. MySQL har även en liknande spatial extension, som inte är speciell komplett, och är inte säker på att den kan lösa problemet effektivt överhuvudtaget (men jag kan ha fel!).

MongoDB har även stöd för spatial indexes och distans-queries, om du kunde lägga dina koordinater där och göra själva distans-sökningen där skulle det kunna vara ett alternativ.

Jag är rädd att det inte finns någon riktigt bra lösning med MySQL förutom någon slags workaround som ovan, som både är krånligare, mindre effektiv och framför allt: fulare!