Wie lässt sich diese SQL-Abfrage für einen rechteckigen Bereich optimieren?

Question

Ich versuche, die folgende Abfrage zu optimieren, aber es ist mir nicht klar, welcher Index oder Indizes am besten wäre. Ich speichere Kacheln in einer zweidimensionalen Ebene und frage nach rechteckigen Bereichen dieser Ebene ab. Die Tabelle hat, für die Zwecke dieser Frage, die folgenden Spalten:

• id: ein ganzzahliger Primärschlüssel
• world_id: ein ganzzahliger Fremdschlüssel, der als Namensraum für eine Teilmenge von Kacheln dient
• tileY: die Y-Koordinate als Ganzzahl
• tileX: die ganzzahlige X-Koordinate
• value: der Inhalt dieser Kachel, ein varchar, wenn es wichtig ist.

Ich habe die folgenden Indizes:

• "ywot_tile_pkey" PRIMARY KEY, btree (id)
• "ywot_tile_world_id_key" UNIQUE, btree (world_id, "tileY", "tileX")
• "ywot_tile_world_id" btree (world_id)

Und dies ist die Abfrage, die ich zu optimieren versuche:

ywot=> EXPLAIN ANALYZE SELECT * FROM "ywot_tile" WHERE ("world_id" = 27685  AND "tileY" <= 6  AND "tileX" <= 9  AND "tileX" >= -2  AND "tileY" >= -1 );                                                                    QUERY PLAN                                                                 -------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on ywot_tile  (cost=11384.13..149421.27 rows=65989 width=168) (actual time=79.646..80.075 rows=96 loops=1)
   Recheck Cond: ((world_id = 27685) AND ("tileY" <= 6) AND ("tileY" >= (-1)) AND ("tileX" <= 9) AND ("tileX" >= (-2)))
   ->  Bitmap Index Scan on ywot_tile_world_id_key  (cost=0.00..11367.63 rows=65989 width=0) (actual time=79.615..79.615 rows=125 loops=1)
         Index Cond: ((world_id = 27685) AND ("tileY" <= 6) AND ("tileY" >= (-1)) AND ("tileX" <= 9) AND ("tileX" >= (-2)))
 Total runtime: 80.194 ms

Die Welt ist also fixiert, und wir fragen nach einem rechteckigen Bereich von Kacheln. Einige weitere Informationen, die relevant sein könnten:

• Es können alle Kacheln für eine abgefragte Region vorhanden sein oder auch nicht
• Die Höhe und Breite eines abgefragten Rechtecks beträgt normalerweise etwa 10x10-20x20
• Für ein beliebiges (Welt, X) oder (Welt, Y) Paar kann es eine unbegrenzte Anzahl von übereinstimmenden Kacheln geben, aber der ungünstigste Fall liegt derzeit bei etwa 10.000, und normalerweise sind es viel weniger.

• Neue Kacheln werden weitaus seltener erstellt als bestehende aktualisiert (Änderung des "Wertes"), und das wiederum ist weitaus seltener als das bloße Lesen wie in der obigen Abfrage.

  Das Einzige, was ich mir vorstellen kann, wäre ein Index für (Welt, X) und (Welt, Y). Ich vermute, dass die Datenbank in der Lage wäre, diese beiden Mengen zu nehmen und sie zu schneiden. Das Problem ist, dass es eine Möglicherweise eine unbegrenzte Anzahl von Übereinstimmungen für einen der beiden Fälle. Gibt es eine andere Art von Index, die besser geeignet wäre?

Answer 1

Clustern Sie die Tabelle auf "ywot_tile_world_id_key", der Primärschlüssel scheint einfach eine künstliche ID zu sein. Wenn Sie mehr eindeutige vertikale als horizontale Werte haben, sollten Sie die Reihenfolge umkehren (world-id, y, x). Entfernen Sie auch den Einzelindex für world-id, er wird durch den zusammengesetzten Index dupliziert.

Answer 2

GIST für Ihre X,Y ähnlich wie PostGIS. In der Tat könnte man sogar die PostGIS-Erweiterung für Postgresql verwenden und so eine ganze Menge für sein Geld bekommen

Answer 3

Das habe ich dann gemacht. Die Abfragen sind jetzt ~20ms anstelle von 80, was eine anständige Verbesserung ist, wenn auch nicht erstaunlich.

1. Das Modul btree_gist wurde geladen
2. Der folgende Index wurde erstellt: CREATE INDEX CONCURRENTLY ywot_tile_boxes ON ywot_tile USING gist (world_id, box(point("tileX","tileY"),point("tileX","tileY")));
3. Ich habe die Abfragen so geändert, dass sie wie folgt aussehen: SELECT * FROM "ywot_tile" WHERE world_id = 27685 AND box(point("tileX","tileY"),point("tileX","tileY")) && box(point(-2,-1),point(9,6));

Für weitere Vorschläge wären wir Ihnen sehr dankbar.