Schlechte Leistung bei der Verwendung von räumlichen Indizes in MySQL

13

Erneutes Posten einer Frage zu Stack Overflow, wenn vorgeschlagen wurde, dass dies ein besseres Forum wäre.

Ich versuche ein kleines Experiment, um einen Datensatz zu verschieben, der nicht georäumlich ist, aber recht gut dazu passt, und finde die Ergebnisse etwas beunruhigend. Der Datensatz besteht aus genomischen Daten, z. B. dem menschlichen Genom, in dem sich eine DNA-Region befindet, in der Elemente wie Gene bestimmte Start- und Stoppkoordinaten (unsere X-Achse) einnehmen. Wir haben mehrere DNA-Regionen (Chromosomen), die die Y-Achse einnehmen. Das Ziel ist es, alle Elemente, die zwei X-Koordinaten entlang einer einzigen Y-Koordinate schneiden, zurückzubringen, z. B. LineString (START 1, END 2).

Die Theorie schien solide zu sein, also habe ich sie in ein bestehendes MySQL-basiertes Genomprojekt verschoben und eine Tabellenstruktur wie:

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_idStellt den Bezeichner der Entität dar, die wir in diese Tabelle external_typecodiert haben und codiert die Quelle davon. Alles sah gut aus und ich gab einige vorläufige Daten (30.000 Zeilen) ein, die gut zu funktionieren schienen. Als dies über die 3-Millionen-Zeilen-Marke hinausging, lehnte MySQL die Verwendung des räumlichen Index ab und war langsamer, als er dazu gezwungen wurde (40 Sekunden gegenüber 5 Sekunden bei einem vollständigen Tabellenscan). Wenn weitere Daten hinzugefügt wurden, wurde der Index verwendet, aber die Leistungseinbußen blieben bestehen. Durch das Erzwingen des Indexes wurde die Abfrage auf 8 Sekunden reduziert. Die Abfrage, die ich verwende, sieht folgendermaßen aus:

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

Die darin enthaltenen Daten sind entlang der Y-Dimension sehr dicht (denken Sie daran, dass Sie die Position jedes Gebäudes, jeder Telefonzelle, jedes Briefkastens und jeder Taube auf einer sehr langen Straße aufgezeichnet haben). Ich habe getestet, wie sich R-Indizes mit diesen Daten in Java verhalten, und andere im Feld haben sie mit Erfolg auf Flat-File-Formate angewendet. Jedoch hat niemand sie auf Datenbanken AFAIK angewendet, die das Ziel dieses Tests sind.

Hat jemand ein ähnliches Verhalten beim Hinzufügen großer Datenmengen zu einem räumlichen Modell beobachtet, das entlang einer bestimmten Achse nicht sehr unterschiedlich ist? Das Problem bleibt bestehen, wenn ich die Koordinatenverwendung umkehre. Ich führe das folgende Setup aus, wenn das eine Ursache ist

  • MacOS 10.6.6
  • MySQL 5.1.46
andeyatz
quelle

Antworten:

5

MySQL speichert wie PostGIS seine räumlichen Indexdaten in einer R-Tree-Struktur, damit es schnell nach Dingen suchen kann. Ein R-Baum ist wie ein B-Baum so organisiert, dass nur ein kleiner Teil der Gesamtdaten in der Tabelle abgerufen werden kann. Tatsächlich ist es schneller, den Index für Abfragen zu ignorieren, die einen großen Abschnitt der Tabelle lesen müssen, um Daten zurückzugeben, oder einen riesigen Join auszuführen. Dies ist ein klassischer Fall, bei dem sich viele Datenbankforen [Poster] über eine Abfrage beschweren, die die Hälfte ihrer Werte zurückgibt Tabelle "verwendet nicht den neuen Index, den sie gerade erstellt haben."

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

Wenn Sie alle Ihre Tabellendaten in den Speicher einpassen können, ist Ihre Leistung gut. Wenn Sie mit dem Lesen von Datenträgern beginnen müssen, wird die Leistung schnell beeinträchtigt. Haben Sie in den beiden folgenden Fällen Speicherverwendungsmuster für Ihre MySQL-Instanz durchgeführt: 30.000 Zeilen vs. 3.000.000 Zeilen?

tmarthal
quelle
Ich denke, das könnte näher am Problem liegen. TBH ist der R-Index, den ich will; Die andere räumliche Mathematik ist ein netter Bonus, da dies in der API-Ebene unter dem alten System erfolgen müsste. Ich habe versucht, ein wenig zu optimieren, aber das Erhöhen der Schlüsselpuffer hat nicht geholfen (andere Puffer helfen hier nicht wie Tabellenpuffer, da es sich um eine 1-Tabellen-Abfrage auf meinem persönlichen Server handelt). Seltsam ist, dass MySQL meine Maschine in den Boden hämmert, wenn die Abfragen ausgeführt werden (100% während des Abfragelaufs). Das heißt, es wird ein vollständiger Tabellenscan durchgeführt, also ist es vielleicht nicht so seltsam
andeyatz
5

Irgendetwas muss mit Ihrer MySQL-Installation oder den INI-Einstellungen nicht stimmen. Habe gerade einen Geodatenindex auf meinem alten Mac (10.6.8 / MySQL 5.2) getestet. Diese Konfiguration ähnelt Ihrer und ich habe den großen Geodaten-Dump ( 9 Millionen Datensätze ) getestet . Ich habe diese Abfrage durchgeführt:

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; 

Es dauerte nur 0,0336 Sekunden.

Ich benutze die obige Abfrage zB für Vergleiche zwischen Tabellen, in denen die Tabelle, aus der nur die Lat / Lng-Werte für @center stammen, einen einfachen INDEX von city_latitude / city_longitude und die 9-12 Mio. hat. Tabelle von geonames.org hat einen Geodatenindex.

Und ich wollte nur hinzufügen, dass es möglicherweise performanter ist, den Index nach INSERT hinzuzufügen, wenn jemand die großen Datenmengen in eine Tabelle einfügt. Wenn nicht, dauert es länger für jede Zeile, die Sie hinzufügen ... [aber das ist nicht wichtig]

Sebilasse
quelle
Wow das ist wirklich gut. Jetzt bin ich mir nicht sicher, was ich in meinen eigenen Tests falsch gemacht habe. Eine Sache, die ein Problem verursachen könnte, ist die Art meiner Datensätze im Vergleich zu herkömmlicheren Geodatensätzen. Das heißt, ich rate nur und habe keine Grundlage dafür. Es ist großartig zu sehen, dass Sie den Index nicht in den Speicher zwingen müssen, um die Geschwindigkeit zu ermitteln.
Andeyatz
Die WHERE-Klausel mit dem Radius könnte einen guten Teil der Tabelle aus der Verwendung eines Index herausfiltern.
Tmarthal
2

Haben Sie darüber nachgedacht, es in zwei 1D-Spalten anstelle einer einzelnen 2D-Spalte aufzuteilen?

Das Optimierungsprogramm könnte an all den ähnlichen Daten ersticken, und es könnte hilfreich sein, zwei Spalten mit größerer Vielfalt zu haben.

Möglicherweise überprüfen Sie auch die Reihenfolge, in der die Elemente überprüft werden. Ich hatte ein Problem in Oracle Spatial, bei dem ich nach Nachname und einem IN_REGION-Filter gesucht habe. Oracle hat entschieden, dass es am schnellsten geht, den Nachnamen zu verwenden und dann eine Regionsprüfung durchzuführen. Lassen Sie mich Ihnen sagen, dass die Überprüfung aller Robinson in Cleveland in der Region nur langsam vonstatten geht . Ich erinnere mich, dass ich ein Oracle-spezifisches Argument übergeben musste, um es zu zwingen, zuerst den räumlichen Index zu verwenden.

Mark Robinson
quelle
Leider ist eine Dimension weitaus weniger bevölkert als eine andere. Um dies in einen Zusammenhang zu bringen, verfügt das menschliche Genom über 24 einzigartige Chromosomen (22 Paare und die beiden Geschlechtschromosomen) sowie eine Vielzahl von Daten, die auf verschiedenen Ebenen zusammengestellt wurden. Das heißt, wenn Sie dem Basisanwendungsfall Elemente zuordnen, die nur 24 eindeutige Bezeichner in einer Dimension enthalten. Die ursprüngliche Hoffnung war, dass der R-Tree-Index nicht nur leistungsfähigere Überlappungsbereichsprüfungen durchführen, sondern auch zwischen diesen Bereichen in einer einzigen Abfrage unterscheiden konnte.
Andeyatz