Zweidimensionale Suche

7 Aufrufe
Direkt zur ersten ungelesenen Nachricht

Egon Schmid

ungelesen,
01.04.2010, 20:33:4101.04.10
an
Hallo!

Ich habe in einer Datenbank-Tabelle "coords" Koordinaten gespeichert...

coords {
double x
double y
}

Nun sollen so Suchabfragen wie

- finde den nï¿œchstliegenden Punkt zu (x0,y0):
min((x0-x)ᅵ+(y0-y)ᅵ)
- finde alle Punkte, die im um (x0,y0) in einem Abstand <= r liegen:
(x0-x)ᅵ+(y0-y)ᅵ <= rᅵ

Man kann zwar die Formel in SQL ausdrï¿œcken, aber das wï¿œrde alle Punkte
abgrasen und dann nach Abstand sortieren.

Wie kann man so eine Suche smart gestalten, ohne den SQL-Server zu quï¿œlen?

Ein erster Ansatz: die Suche auf ein Quadrat einschrï¿œnken:
x0-r < x AND x < x0+r AND y0-r < y AND y < y0+r

viele Grᅵᅵe

Egon Schmid

Egon Schmid

ungelesen,
01.04.2010, 21:23:1701.04.10
an
Vielleicht ist das eine Idee:

Man teilt die Karte in Quadrate auf, und ordnet jeden Punkt seinem
Quadrat zu.

Dazu fügt man der Tabelle ein Feld "area" hinzu, das indiziert ist. So
könnte man die SQL-Suche auf die umliegenden Quadrate einschränken.

Das Verfahren könnte man auch als "Rasterfahndung" bezeichnen. :D

Wird es so praktiziert, oder gibt's noch bessere Methoden?

Viele Grüße

Egon Schmid

Niels Braczek

ungelesen,
01.04.2010, 21:42:5801.04.10
an
Egon Schmid schrieb:

> Ein erster Ansatz: die Suche auf ein Quadrat einschränken:


> x0-r < x AND x < x0+r AND y0-r < y AND y < y0+r

Dieser Ansatz ist fast optimal.

(x BETWEEN AND x0-r AND x0+r) AND (y BETWEEN y0-r AND < y0+r)

Das Ergebnis kann dann clientseitig verfeinert werden. Allerdings
funktioniert der Quadrat-Ansatz nur in hinreichender Entfernung von den
Polen.

MfG
Niels

--
| http://www.kolleg.de · Das Portal der Kollegs in Deutschland |
| http://www.bsds.de · BSDS Braczek Software- und DatenSysteme |
| Webdesign · Webhosting · e-Commerce · Joomla! Content Management |
------------------------------------------------------------------

Bernd Hohmann

ungelesen,
02.04.2010, 07:26:3902.04.10
an
Egon Schmid wrote:

> Ich habe in einer Datenbank-Tabelle "coords" Koordinaten gespeichert...

> [...]
> Wie kann man so eine Suche smart gestalten, ohne den SQL-Server zu quälen?

http://dev.mysql.com/doc/refman/5.5/en/spatial-extensions.html ?

Bernd

--
Life was much easier when Apple and Blackberry were just fruits.

Sam Kang

ungelesen,
02.04.2010, 08:55:3702.04.10
an
Egon Schmid schrieb:

> Man teilt die Karte in Quadrate auf, und ordnet jeden Punkt seinem
> Quadrat zu.
>
> Dazu fügt man der Tabelle ein Feld "area" hinzu, das indiziert ist. So
> könnte man die SQL-Suche auf die umliegenden Quadrate einschränken.

Das ist eine ältere Methode die von "Beamtensystemen" bekannt sind.


> Wird es so praktiziert, oder gibt's noch bessere Methoden?

Eigentlich nur in legacy Systemen. Du musst vorher die Nachbarkacheln für eine
IN Klausel berechnen, auf die dann geprüft wird. Das ist in den meisten Fällen
nicht optimaler. Die alten Daten der NOAA und des CIA im VPF sind so aufgebaut.


Dein erster Ansatz

x0-r <= x AND x <= x0+r AND y0-r <= y AND y <= y0+r

funktioniert recht optimal wenn x *oder* y einen INDEX hat - beides nützt nichts.

Mysql kann dann schnell wie immer [TM] den Bereich zwischen x0-r und x0+r
mittels Index (hier Index auf x) finden und braucht dann nur die y Werte
einsortieren die von den beiden anderen Bedingungen erfüllt werden.

Bei kleinen Abständen funktioniert das sehr gut.

Bei der Sortierung nach Abstand kannst dann noch die Wurzel weglassen.
ein

ORDER BY ((x0-x)*(x0-x)+(y0-y)*(y0-y))

reicht völlig aus.

Von den Spatial Funktionen MySqls würde ich Abstand nehmen - die sind grottig
ungepflegt. Wenn du sowas brauchst ist ein System wie PostGis besser da es
auch Projektionen kennt und vollständige räumliche Untersützung bietet.

Sam


--
Sufficiently advanced incompetence is indistinguishable from malice
(J. Porter Clark)

Sam Kang

ungelesen,
02.04.2010, 08:31:1202.04.10
an
Niels Braczek schrieb:

> Egon Schmid schrieb:
>
>> Ein erster Ansatz: die Suche auf ein Quadrat einschränken:
>> x0-r < x AND x < x0+r AND y0-r < y AND y < y0+r
>
> Dieser Ansatz ist fast optimal.
>
> (x BETWEEN AND x0-r AND x0+r) AND (y BETWEEN y0-r AND < y0+r)

Nö. Die Ausdrücke sind nicht äquivalent. Da stehet nicht:

x0-r <= x AND x <= x0+r AND y0-r <= y AND y <= y0+r

Dieser Ausdruck wäre dann äquivalent zu

(x BETWEEN x0-r AND x0+r) AND (y BETWEEN y0-r AND < y0+r)

ist aber weder schneller noch langsamer weil er die gleiche Query erzeugt.

> Das Ergebnis kann dann clientseitig verfeinert werden. Allerdings
> funktioniert der Quadrat-Ansatz nur in hinreichender Entfernung von den
> Polen.

Wie kommst du darauf? Ein Kartesisches Rechts-Hoch, X-Y Koordinatensystem hat
keine Pole!

Claus Reibenstein

ungelesen,
02.04.2010, 09:00:3202.04.10
an
Egon Schmid schrieb:

> coords {
> double x
> double y
> }
>
> Nun sollen so Suchabfragen wie
>

> - finde den nächstliegenden Punkt zu (x0,y0):
> [...]
>
> Wie kann man so eine Suche smart gestalten, ohne den SQL-Server zu quälen?
>
> Ein erster Ansatz: die Suche auf ein Quadrat einschränken:


> x0-r < x AND x < x0+r AND y0-r < y AND y < y0+r

Genau. Wenn Du dann noch je einen Index über x und y legst, sollte das
sogar einigermaßen performant sein.

Gruß. Claus

Claus Reibenstein

ungelesen,
02.04.2010, 09:01:2502.04.10
an
Niels Braczek schrieb:

> (x BETWEEN AND x0-r AND x0+r) AND (y BETWEEN y0-r AND < y0+r)

Da ist ein AND zu viel :-)

Gruß. Claus

Claus Reibenstein

ungelesen,
02.04.2010, 09:05:0102.04.10
an
Bernd Hohmann schrieb:

> Egon Schmid wrote:
>
>> Ich habe in einer Datenbank-Tabelle "coords" Koordinaten gespeichert...
>> [...]

>> Wie kann man so eine Suche smart gestalten, ohne den SQL-Server zu quï¿œlen?
>
> http://dev.mysql.com/doc/refman/5.5/en/spatial-extensions.html ?

Wohl eher nicht: Egons Frage bezieht sich auf normale ebene Geometrie.

Gruᅵ. Claus

Egon Schmid

ungelesen,
06.04.2010, 06:26:4906.04.10
an
>> Ein erster Ansatz: die Suche auf ein Quadrat einschränken:
>> x0-r < x AND x < x0+r AND y0-r < y AND y < y0+r
>
> Genau. Wenn Du dann noch je einen Index über x und y legst, sollte das
> sogar einigermaßen performant sein.

Mein Gedanke war, welchem Algorithmus MySQL bei dem Filter

(x BETWEEN x0-r AND x0+r) AND (y BETWEEN y0-r AND < y0+r)

verwendet. Vermutlich wird erst

(x BETWEEN x0-r AND x0+r)

ausgeführt. Die Daten liegen dann nach x sortiert vor.
Wenn dann

(y BETWEEN y0-r AND < y0+r)

ausgeführt wird, ist die Suche nur schnell, wenn diese nach y sortiert
vorliegen, was nicht der Fall ist. Somit müssen alle diese Daten
sortiert oder überprüft werden.

Ich denke, dass bei einem "Beamtensystemen", wo jeder Punkt einem
Bereich (Quadrat oder noch besser Sechseck) zugeordnet wird, schneller wäre.

Ich hab eine 60 MB grosse SQL-Datei von der OpenGeoDB (->
http://fa-technik.adfc.de/code/opengeodb/) runtergeladen, wo sämtliche
Informationen der Deutschlandkarte vorhanden sind, und werde es damit
mal testen.

Das Ausführen der INSERTs dauert allerdings einige Stunden :) Es läuft
derzeit immer noch...

Viele Grüße

Egon Schmid

Claus Reibenstein

ungelesen,
06.04.2010, 07:53:5706.04.10
an
Egon Schmid schrieb:

>>> Ein erster Ansatz: die Suche auf ein Quadrat einschränken:
>>> x0-r < x AND x < x0+r AND y0-r < y AND y < y0+r
>>
>> Genau. Wenn Du dann noch je einen Index über x und y legst, sollte das
>> sogar einigermaßen performant sein.
>
> Mein Gedanke war, welchem Algorithmus MySQL bei dem Filter
>
> (x BETWEEN x0-r AND x0+r) AND (y BETWEEN y0-r AND < y0+r)
>
> verwendet.

Das kommt darauf an, wie Deine Daten und Indizes aussehen. MySQL macht
hier einige Optimierung, die in der Dokumentation recht ausführlich
beschrieben werden.

> Vermutlich wird erst
>
> (x BETWEEN x0-r AND x0+r)
>
> ausgeführt. Die Daten liegen dann nach x sortiert vor.

Ich glaube kaum, dass MySQL die Daten irgendwie sortiert, so lange kein
ORDER BY angegeben wird. Ich glaube ebensowenig, dass die Prüfung in
zwei getrennten Schritten erfolgt. Das ergäbe bestenfalls dann einen
Sinn, wenn nur ein Index existiert.

Existieren beide Indizes, wird vermutlich erst deren Schnittmenge
gebildet. Existiert keiner, muss sowieso ein Full Table Scan erfolgen,
und der wird sicher nicht 2x durchgeführt.

Gruß. Claus

Axel Schwenke

ungelesen,
06.04.2010, 09:12:5606.04.10
an
Claus Reibenstein <4spame...@kabelmail.de> wrote:
> Egon Schmid schrieb:

>
>> Mein Gedanke war, welchem Algorithmus MySQL bei dem Filter
>>
>> (x BETWEEN x0-r AND x0+r) AND (y BETWEEN y0-r AND < y0+r)
>>
>> verwendet.
>
> Das kommt darauf an, wie Deine Daten und Indizes aussehen. MySQL macht
> hier einige Optimierung, die in der Dokumentation recht ausführlich
> beschrieben werden.

s/ausführlich/spärlich/

Zumindest IMHO.
Aber die wahre DoCCumentation ist ja ohnehin in den .cc Files ;)

>> Vermutlich wird erst
>>
>> (x BETWEEN x0-r AND x0+r)
>>
>> ausgeführt. Die Daten liegen dann nach x sortiert vor.
>
> Ich glaube kaum, dass MySQL die Daten irgendwie sortiert, so lange kein
> ORDER BY angegeben wird. Ich glaube ebensowenig, dass die Prüfung in
> zwei getrennten Schritten erfolgt. Das ergäbe bestenfalls dann einen
> Sinn, wenn nur ein Index existiert.

Kommt drauf an. Sortiert wird in dieser Phase der Query-Abarbeitung in
der Tat nicht. Aber wenn ein Index auf `x` verwendet wird, dann fallen
potentielle Ergebniszeilen in der Tat sortiert nach `x` an.

> Existieren beide Indizes, wird vermutlich erst deren Schnittmenge
> gebildet.

Das wäre dann
http://dev.mysql.com/doc/refman/5.1/en/index-merge-intersection.html

Allerdings spricht das Manual hier strikt von reference condition
(also ein Vergleich des indizierten Tupels mit einer Konstante).
Obiges ist aber eine range condition.

> Existiert keiner, muss sowieso ein Full Table Scan erfolgen,
> und der wird sicher nicht 2x durchgeführt.

In der Tat.

Ein typischer Ausführungsplan wäre ein Rangescan auf dem Index über
(`x`[, ...]) oder (`y`[, ...]) - je nachdem welcher existiert und ob
der Optimizer ihn für selektiv hält. Die restlichen Bedingungen werden
dann nach einem Blick auf restliche Indexteile (gut) oder nach einem
Blick auf die komplette Row (schlecht) geprüft. Man würde also am
besten einen Index (`x`, `y`) und eventuell noch einen zweiten auf
(`y`, `x`) haben. Dann kann MySQL die Bedingung "liegt im Quadrat
(x0 +/- r, y0 +/- r)" direkt aus dem Index lesen.

Die spatial extensions wurden ja schon genannt und passen auch. Für
den Test, ob ein Punkt innerhalb eines Koordinatenrechtecks liegt,
ist es auch egal ob flach oder sphärisch.

I erinnere mich dunkel, daß Kris Köhntopp mal spatiale Indizes für
eine zweidimensionale Suche ausprobiert und das eine oder andere Haar
in der Suppe gefunden hat. Er hat das sicher gebloggt...


XL

Sam Kang

ungelesen,
06.04.2010, 10:22:2106.04.10
an
Claus Reibenstein schrieb:

> Existieren beide Indizes, wird vermutlich erst deren Schnittmenge
> gebildet.


Warum sollte mysql das tun? Mysql nimmt den ersten möglichen Index und fertig.

CREATE TABLE IF NOT EXISTS `xyt` (
`x` double NOT NULL,
`y` double NOT NULL,
`t` varchar(255) NOT NULL,
KEY x (x),
KEY y (y)
)

ein

EXPLAIN SELECT * FROM `xyt` WHERE (x between -1 and 1) and (y between -1 and 1)

liefert dann:

id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE xyt range x,y x 8 NULL 1 Using where


Was anderes hätte mich gewundert.

Axel Schwenke

ungelesen,
06.04.2010, 13:37:4306.04.10
an
Sam Kang <s...@907.earth.tc> wrote:
> Claus Reibenstein schrieb:
>
>> Existieren beide Indizes, wird vermutlich erst deren Schnittmenge
>> gebildet.
>
> Warum sollte mysql das tun?

Weil es effizienter ist? Warum wohl glaubst du, wurden die
Index-Merge access-Methoden implementiert?

> Mysql nimmt den ersten möglichen Index und fertig.

Keineswegs. Der Optimizer schaut sich die geeigneten Indizes
an und nimmt anschließend den, der (geschätzt) selektiver ist.

> Was anderes hätte mich gewundert.

Also der MySQL-Optimizer ist ja sicher um einiges von "perfekt"
entfernt. Aber so simpel wie du vermutest, ist er dann doch nicht.


XL

Claus Reibenstein

ungelesen,
06.04.2010, 17:34:0206.04.10
an
Sam Kang schrieb:

> EXPLAIN SELECT * FROM `xyt` WHERE (x between -1 and 1) and (y between -1 and 1)
>
> liefert dann:
>
> id select_type table type possible_keys key key_len ref rows Extra
> 1 SIMPLE xyt range x,y x 8 NULL 1 Using where

Leider sind die Spalten verrutscht :-(

Wenn Du EXPLAIN nicht mit ';', sondern mit '\G' abschließt, gibt es
dieses Problem nicht.

Gruß. Claus

Kristian Köhntopp

ungelesen,
09.04.2010, 10:02:3009.04.10
an
On 2010-04-06 12:26:49 +0200, Egon Schmid said:
> Ich hab eine 60 MB grosse SQL-Datei von der OpenGeoDB (->
> http://fa-technik.adfc.de/code/opengeodb/) runtergeladen, wo sämtliche
> Informationen der Deutschlandkarte vorhanden sind, und werde es damit
> mal testen.
>
> Das Ausführen der INSERTs dauert allerdings einige Stunden :) Es läuft
> derzeit immer noch...

InnoDB, AUTOCOMMIT = 1. Vor dem source DE.sql ein BEGIN WORK machen,
danach ein COMMIT. Dann geht es sehr viel schneller.

Mit diesen Daten und einem Beispielort kann man experimentieren.

root@localhost [geodb]> select td.loc_id, td.text_val, tn.name from
geodb_textdata as td join geodb_type_names as tn on td.text_type =
tn.type_id where td.text_val = 'Kiel' and tn.name = 'Name';
+--------+----------+------+
| loc_id | text_val | name |
+--------+----------+------+
| 469 | Kiel | Name |
| 19236 | Kiel | Name |
+--------+----------+------+
2 rows in set (0.00 sec)

Zum Beispiel finden wir mal alles, was um den Beispielort herum liegt:

root@localhost [geodb]> explain select co.loc_id, td.text_val from
geodb_coordinates as co join geodb_textdata as td on co.loc_id =
td.loc_id join geodb_type_names as tn on td.text_type = tn.type_id
where lat = 54.3333 and lon = 10.1333 and tn.name = 'Name'\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: co
type: index_merge
possible_keys: coord_loc_id_idx,coord_lon_idx,coord_lat_idx
key: coord_lat_idx,coord_lon_idx
key_len: 9,9
ref: NULL
rows: 1
Extra: Using intersect(coord_lat_idx,coord_lon_idx); Using where
*************************** 2. row ***************************
id: 1
select_type: SIMPLE
table: tn
type: ref
possible_keys: type_id,tid_tnames_idx,name_tnames_idx
key: name_tnames_idx
key_len: 767
ref: const
rows: 1
Extra: Using where; Using index
*************************** 3. row ***************************
id: 1
select_type: SIMPLE
table: td
type: ref
possible_keys: text_lid_idx,text_type_idx
key: text_lid_idx
key_len: 4
ref: geodb.co.loc_id
rows: 2344
Extra: Using where
3 rows in set (0.00 sec)

Wie man sieht wird ein index_merge (intersect) verwendet, wenn man mit
festen Koordinaten arbeitet. Hier das Ergebnis:

root@localhost [geodb]> select co.loc_id, td.text_val from
geodb_coordinates as co join geodb_textdata as td on co.loc_id =
td.loc_id join geodb_type_names as tn on td.text_type = tn.type_id
where lat = 54.3333 and lon = 10.1333 and tn.name = 'Name'\G
*************************** 1. row ***************************
loc_id: 469
text_val: Kiel
*************************** 2. row ***************************
loc_id: 19236
text_val: Kiel
*************************** 3. row ***************************
loc_id: 106037
text_val: Friedrichsort
*************************** 4. row ***************************
loc_id: 106033
text_val: Gaarden
*************************** 5. row ***************************
loc_id: 106032
text_val: Hasseldieksdamm
*************************** 6. row ***************************
loc_id: 106036
text_val: Holtenau
*************************** 7. row ***************************
loc_id: 106038
text_val: Kroog
*************************** 8. row ***************************
loc_id: 106043
text_val: Moorsee, Holstein
*************************** 9. row ***************************
loc_id: 106040
text_val: Schilksee
*************************** 10. row ***************************
loc_id: 106039
text_val: Suchsdorf
*************************** 11. row ***************************
loc_id: 106034
text_val: Vieburg
*************************** 12. row ***************************
loc_id: 106035
text_val: Wellingdorf
*************************** 13. row ***************************
loc_id: 106031
text_val: Wik
13 rows in set (0.01 sec)

Eine Umkreissuche (BETWEEN) sieht wesentlich schlechter aus - Axel
Schwenke hat das ja bereits erläutert:

root@localhost [geodb]> explain select co.loc_id, td.text_val from
geodb_coordinates as co join geodb_textdata as td on co.loc_id =
td.loc_id join geodb_type_names as tn on td.text_type = tn.type_id
where lat between 54.3 and 54.4 and lon between 10.1 and 10.2 and
tn.name = 'Name'\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: tn
type: ref
possible_keys: type_id,tid_tnames_idx,name_tnames_idx
key: name_tnames_idx
key_len: 767
ref: const
rows: 1
Extra: Using where; Using index
*************************** 2. row ***************************
id: 1
select_type: SIMPLE
table: td
type: ref
possible_keys: text_lid_idx,text_type_idx
key: text_type_idx
key_len: 4
ref: geodb.tn.type_id
rows: 2344
Extra:
*************************** 3. row ***************************
id: 1
select_type: SIMPLE
table: co
type: ref
possible_keys: coord_loc_id_idx,coord_lon_idx,coord_lat_idx
key: coord_loc_id_idx
key_len: 4
ref: geodb.td.loc_id
rows: 303
Extra: Using where
3 rows in set (0.00 sec)

Hier die Laufzeit:

root@localhost [geodb]> select co.loc_id, td.text_val from
geodb_coordinates as co join geodb_textdata as td on co.loc_id =
td.loc_id join geodb_type_names as tn on td.text_type = tn.type_id
where lat between 54.3 and 54.4 and lon between 10.1 and 10.2 and
tn.name = 'Name'\G
*************************** 1. row ***************************
loc_id: 469
text_val: Kiel
*************************** 2. row ***************************
loc_id: 19236
text_val: Kiel
*************************** 3. row ***************************
loc_id: 18070
text_val: Heikendorf
*************************** 4. row ***************************
loc_id: 21024
text_val: Mönkeberg
*************************** 5. row ***************************
loc_id: 13571
text_val: Altenholz
*************************** 6. row ***************************
loc_id: 106021
text_val: Düsternbrook
*************************** 7. row ***************************
loc_id: 106024
text_val: Ellerbek
*************************** 8. row ***************************
loc_id: 106026
text_val: Elmschenhagen
*************************** 9. row ***************************
loc_id: 106037
text_val: Friedrichsort
*************************** 10. row ***************************
loc_id: 106033
text_val: Gaarden
*************************** 11. row ***************************
loc_id: 106023
text_val: Hassee
*************************** 12. row ***************************
loc_id: 106032
text_val: Hasseldieksdamm
*************************** 13. row ***************************
loc_id: 106036
text_val: Holtenau
*************************** 14. row ***************************
loc_id: 106044
text_val: Kronsburg / Rönne
*************************** 15. row ***************************
loc_id: 106038
text_val: Kroog
*************************** 16. row ***************************
loc_id: 106043
text_val: Moorsee, Holstein
*************************** 17. row ***************************
loc_id: 106025
text_val: Pries
*************************** 18. row ***************************
loc_id: 106040
text_val: Schilksee
*************************** 19. row ***************************
loc_id: 106039
text_val: Suchsdorf
*************************** 20. row ***************************
loc_id: 106034
text_val: Vieburg
*************************** 21. row ***************************
loc_id: 106035
text_val: Wellingdorf
*************************** 22. row ***************************
loc_id: 106031
text_val: Wik
*************************** 23. row ***************************
loc_id: 106766
text_val: Friedrichsberg, Holstein
*************************** 24. row ***************************
loc_id: 106784
text_val: Kitzeberg
*************************** 25. row ***************************
loc_id: 106785
text_val: Möltenort
*************************** 26. row ***************************
loc_id: 106803
text_val: Dreikronen, Schwentine
*************************** 27. row ***************************
loc_id: 106877
text_val: Knoop
*************************** 28. row ***************************
loc_id: 106878
text_val: Stift
*************************** 29. row ***************************
loc_id: 106946
text_val: Kopperpahl
*************************** 30. row ***************************
loc_id: 106953
text_val: Rammsee
30 rows in set (0.50 sec)

Wir können versuchen, mit einem RTREE dabei zu gehen. Dazu brauchen wir
die Daten in MyISAM:

root@localhost [geodb]> create table co like geodb_coordinates;
Query OK, 0 rows affected (0.18 sec)

root@localhost [geodb]> alter table co engine = myisam;
Query OK, 0 rows affected (0.18 sec)
Records: 0 Duplicates: 0 Warnings: 0

root@localhost [geodb]> insert into co select * from geodb_coordinates;
Query OK, 60645 rows affected (0.50 sec)
Records: 60645 Duplicates: 0 Warnings: 0

Wir müssen außerdem eine Spalte latlon als POINT anlegen und einen
SPATIAL index auf diesen Point setzen:

root@localhost [geodb]> alter table co add column latlon point not
null, add spatial index (latlon);
Query OK, 60645 rows affected (0.83 sec)
Records: 60645 Duplicates: 0 Warnings: 0

Die lat und lon Daten müssen nach latlon konvertiert werden:

-- 5.1.35 or later
root@localhost [geodb]> update co set latlon = point(lat, lon);
Query OK, 60645 rows affected (1.45 sec)
Rows matched: 60645 Changed: 60645 Warnings: 0
-- older MySQL: update co set latlon = GeomFromText(concat('Point(',
lat,',',lon)));

Ein kleiner Test:

root@localhost [geodb]> select astext(latlon) from co limit 10;
+------------------------------------------+
| astext(latlon) |
+------------------------------------------+
| POINT(54.7833 9.43333) |
| POINT(54.7833 9.43333) |
| POINT(54.3333 10.1333) |
| POINT(54.3333 10.1333) |
| POINT(53.8667 10.7) |
| POINT(53.8667 10.7) |
| POINT(54.0667 9.98333) |
| POINT(54.0667 9.98333) |
| POINT(54.1474367521367 9.11139581196581) |
| POINT(54.15 9.28333) |
+------------------------------------------+
10 rows in set (0.02 sec)

Die Tabelle sieht jetzt so aus:

root@localhost [geodb]> show create table co\G
*************************** 1. row ***************************
Table: co
Create Table: CREATE TABLE `co` (
`loc_id` int(11) NOT NULL,
`coord_type` int(11) NOT NULL,
`lat` double DEFAULT NULL,
`lon` double DEFAULT NULL,
`coord_subtype` int(11) DEFAULT NULL,
`valid_since` date DEFAULT NULL,
`date_type_since` int(11) DEFAULT NULL,
`valid_until` date NOT NULL,
`date_type_until` int(11) NOT NULL,
`latlon` point NOT NULL,
KEY `coord_loc_id_idx` (`loc_id`),
KEY `coord_lon_idx` (`lon`),
KEY `coord_lat_idx` (`lat`),
KEY `coord_type_idx` (`coord_type`),
KEY `coord_stype_idx` (`coord_subtype`),
KEY `coord_since_idx` (`valid_since`),
KEY `coord_until_idx` (`valid_until`),
SPATIAL KEY `latlon` (`latlon`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8
1 row in set (0.00 sec)

Wir definieren unseren Suchumkreis einmal als @poly Variable. Danach
wird einiges einfacher:

root@localhost [geodb]> set @poly = 'Polygon((54.3 10.1, 54.4 10.1,
54.4 10.2,54.3 10.2, 54.3 10.1 ))';
Query OK, 0 rows affected (0.00 sec)

Wird unser SPATIAL Index denn auch verwendet? Wir testen:

root@localhost [geodb]> explain select co.loc_id from co where
mbrcontains(geomfromtext(@poly), co.latlon)\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: co
type: range
possible_keys: latlon
key: latlon
key_len: 34
ref: NULL
rows: 11
Extra: Using where
1 row in set (0.00 sec)

In der richtigen Suche müssen wir einen STRAIGHT_JOIN forcen, weil
sonst die Join-Order und die Indexverwendung nicht stimmt:

root@localhost [geodb]> explain select straight_join co.loc_id,
td.text_val from co as co join geodb_textdata as td on co.loc_id =
td.loc_id join geodb_type_names as tn on td.text_type = tn.type_id
where tn.name = 'Name' and mbrcontains(geomfromtext(@poly), co.latlon)\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: co
type: range
possible_keys: coord_loc_id_idx,latlon
key: latlon
key_len: 34
ref: NULL
rows: 11
Extra: Using where
*************************** 2. row ***************************
id: 1
select_type: SIMPLE
table: td
type: ref
possible_keys: text_lid_idx,text_type_idx
key: text_lid_idx
key_len: 4
ref: geodb.co.loc_id
rows: 2344
Extra:
*************************** 3. row ***************************
id: 1
select_type: SIMPLE
table: tn
type: ref
possible_keys: type_id,tid_tnames_idx,name_tnames_idx
key: type_id
key_len: 4
ref: geodb.td.text_type
rows: 1
Extra: Using where
3 rows in set (0.00 sec)

Und hier die Ausgabe:

root@localhost [geodb]> select straight_join co.loc_id, td.text_val
from co as co join geodb_textdata as td on co.loc_id = td.loc_id join
geodb_type_names as tn on td.text_type = tn.type_id where tn.name =
'Name' and mbrcontains(geomfromtext(@poly), co.latlon)\G
*************************** 1. row ***************************
loc_id: 18070
text_val: Heikendorf
*************************** 2. row ***************************
loc_id: 21024
text_val: Mönkeberg
*************************** 3. row ***************************
loc_id: 106021
text_val: Düsternbrook
*************************** 4. row ***************************
loc_id: 106024
text_val: Ellerbek
*************************** 5. row ***************************
loc_id: 106037
text_val: Friedrichsort
*************************** 6. row ***************************
loc_id: 106033
text_val: Gaarden
*************************** 7. row ***************************
loc_id: 106032
text_val: Hasseldieksdamm
*************************** 8. row ***************************
loc_id: 106036
text_val: Holtenau
*************************** 9. row ***************************
loc_id: 106038
text_val: Kroog
*************************** 10. row ***************************
loc_id: 106043
text_val: Moorsee, Holstein
*************************** 11. row ***************************
loc_id: 106040
text_val: Schilksee
*************************** 12. row ***************************
loc_id: 106039
text_val: Suchsdorf
*************************** 13. row ***************************
loc_id: 106034
text_val: Vieburg
*************************** 14. row ***************************
loc_id: 106035
text_val: Wellingdorf
*************************** 15. row ***************************
loc_id: 106031
text_val: Wik
*************************** 16. row ***************************
loc_id: 106785
text_val: Möltenort
*************************** 17. row ***************************
loc_id: 106877
text_val: Knoop
*************************** 18. row ***************************
loc_id: 106878
text_val: Stift
*************************** 19. row ***************************
loc_id: 13571
text_val: Altenholz
*************************** 20. row ***************************
loc_id: 106025
text_val: Pries
*************************** 21. row ***************************
loc_id: 106803
text_val: Dreikronen, Schwentine
*************************** 22. row ***************************
loc_id: 106026
text_val: Elmschenhagen
*************************** 23. row ***************************
loc_id: 106023
text_val: Hassee
*************************** 24. row ***************************
loc_id: 106044
text_val: Kronsburg / Rönne
*************************** 25. row ***************************
loc_id: 106766
text_val: Friedrichsberg, Holstein
*************************** 26. row ***************************
loc_id: 106946
text_val: Kopperpahl
*************************** 27. row ***************************
loc_id: 106953
text_val: Rammsee
*************************** 28. row ***************************
loc_id: 106784
text_val: Kitzeberg
*************************** 29. row ***************************
loc_id: 469
text_val: Kiel
*************************** 30. row ***************************
loc_id: 19236
text_val: Kiel
30 rows in set (0.00 sec)

Christian Kirsch

ungelesen,
28.04.2010, 07:33:1028.04.10
an
Claus Reibenstein schrieb:

> Bernd Hohmann schrieb:
>
>> Egon Schmid wrote:
>>
>>> Ich habe in einer Datenbank-Tabelle "coords" Koordinaten gespeichert...
>>> [...]
>>> Wie kann man so eine Suche smart gestalten, ohne den SQL-Server zu quälen?

>> http://dev.mysql.com/doc/refman/5.5/en/spatial-extensions.html ?
>
> Wohl eher nicht: Egons Frage bezieht sich auf normale ebene Geometrie.

MySQLs Spatial Extensions doch auch? Siehe

http://dev.mysql.com/doc/refman/5.5/en/gis-class-geometry.html:

"All calculations are done assuming Euclidean (planar) geometry."

For what it's worth: Dieser Kram war m.W. noch nie besonders gut. Dass
man nur euklidische Koordinatensysteme benutzen kann, ist nur ein Aspekt
dessen.

Claus Reibenstein

ungelesen,
28.04.2010, 09:32:4928.04.10
an
Christian Kirsch schrieb:

> Claus Reibenstein schrieb:
>
>> Bernd Hohmann schrieb:
>>

>>> http://dev.mysql.com/doc/refman/5.5/en/spatial-extensions.html ?
>>
>> Wohl eher nicht: Egons Frage bezieht sich auf normale ebene Geometrie.
>
> MySQLs Spatial Extensions doch auch? Siehe
>
> http://dev.mysql.com/doc/refman/5.5/en/gis-class-geometry.html:
>
> "All calculations are done assuming Euclidean (planar) geometry."

Lies den Satz mal in dem Kontext, in welchem er steht. Lies auch den
nächsten Abschnitt.

Gruß. Claus

Allen antworten
Dem Autor antworten
Weiterleiten
0 neue Nachrichten