Neulich führte ich eine Query aus, die mehr als 9 Sekunden rechnete. Die Query bestand aus einem Join zweier Tabellen: Eine Liste von Items und einem Zeitverlauf je Item. Vom Schema sah das ungefähr so aus:

Item(ShopID, SubID, Title)
ItemPrice(ShopID, SubID, Price, Timestamp)

Die Query sah ungefähr so aus:
SELECT Title, (SELECT Price FROM ItemPrice p WHERE i.ShopID = p.ShopID AND i.SubID = p.SubID ORDER BY Timestamp DESC LIMIT 1) AS Price FROM Item i

Auf gutdeutsch also: Liste alle Items mit ihrem neuesten Preis auf.

Die Krux mit den Joins?

Hat man etwa 9.000 Items und ca. 11.000 Preisänderungen, würde die Query sofort lahm werden. Doch woran liegt das?

Zum einen gibt es hier eine Nested Query. Es gibt zwar eine allgemeine Methode, beliebige Sub-Queries in Joins umzuwandeln (Paper von Thomas Neumann auf der BTW15, Hamburg), allerdings kann diese Methode nicht mit der ORDER BY und dem LIMIT-Klausel umgehen. Der Ausführungsplan der Query ist also klar: Zuerst wird die Item-Tabelle gescannt und für jede ihrer Zeilen wird die Sub-Query ausgeführt. Grundessenz einer Query-Optimierung hier ist also, dass die Subquery möglichst ohne Zeitaufwand stattfindet (am besten Lookup-Index).

Das nächste Problem ist die unklare Schlüssel-Situation, denn hier bilden zwei Schlüssel den Primär-Index. Ein Index müsste also beide Schlüssel enthalten.

Der MultiIndex

Es gibt grundsätzlich zwei Arten von Indizes: Den Hash-Index und den BTree. Der Hash-Index ist eine Hash-Table, aus der man idealerweise mit einem Aufwand O(1) Items herauspicken kann, deren Zugriffs-Schlüssel man kennt. Der BTree hingegen ist eine Art sortierter Listen-Baum. Der BTree kann weit mehr als der Hash-Index: Items mit einem exakten Key finden, Items, deren Key zwischen zwei Werten liegt oder einfach die Items in sortierter Reihenfolge auslesen.

Weitet man einen Index auf mehrere Dimensionen aus, spielt sich etwas interessantes ab: Beim Hash-Index kann man nur noch Werte abfragen, bei denen man die Werte aller Zugriffs-Schlüssel kennt. Der BTree hingegen hat folgende Features:

• Ist mein Index 4-dimensional, ich kenne aber nur die ersten 2 Schlüssel-Werte, kann ich trotzdem einen Lookup durchführen
• Ist mein Index 4-dimensional, ich kenne aber nur die ersten 2 Schlüssel-Werte, kann ich auf dem dritten Schlüssel Bereichs-Anfragen (von-bis) durchführen
• Ist mein Index 4-dimensional, ich kenne aber nur die ersten 2 Schlüssel-Werte, kann ich den dritten Schlüssel sortiert auslesen

Technisch gesehen ist der multidimensionale BTree also eine Liste, die nach den Schlüsseln sortiert ist. Der Aufwand für eine BTree-Anfrage ist O(log(n)).

Effiziente Verwendung des MultiIndex

Jeder Index verbraucht Speicher in der Datenbank. Deshalb sollte man sparsam mit Indizes umgehen. Doch folgende Richtlinien helfen bei einem guten Index-Aufbau:

1. Für eine Query, die über 3 Attribute joint, legt man für diese 3 Attribute den Index an
2. Die Attribute, die im Join mit „=“ verglichen werden (EquiJoin), werden an den Anfang des Index gestellt
3. Das Attribut, nach dem sortiert wird oder Bereichs-Abfragen stattfinden, kommt hinten hin
4. Hat man einen Index über die Spalten (a,b,c) und einen Index über die Spalten (a,b), kann der (a,b)-Index entfallen, da der (a,b,c)-Index diese Anfragen auch durchführen kann.
5. Die Spalten, die in Queries mit „=“ verglichen werden, sind im Index vertauschbar. Das kann man nutzen, um 4. optimal auszunutzen.

Zurück zum Beispiel

Um die Query im oberen Beispiel also effizient abarbeiten zu können, ist folgender Index empfehlenswert:
Index(ShopID, SubID, Timestamp)

Die beiden Equi-Joins ShopID und SubID sind normale O(log(n))-Lookups auf dem Index. Hat man diese Range eingeschränkt, besteht die Range nur noch aus einer nach Timestamp sortierten Liste des über ShopID und SubID festgelegten Items. Aufgrund der ORDER-BY-DESC-Klausel weiß der Index nun, dass er aus der sortierten Liste das letzte Item zuerst auslesen muss. Die LIMIT-1-Klausel bricht beim Auslesen des ersten Items ab. Effektiv wurde also O(log(n)) Zeit in der inneren Schleife verbraucht.

Fazit

Zu jeder noch so komplizierten Query lässt sich ein Multi-Index finden, der die Joins optimiert. Software von Launix wird also auch bei großen Datenmengen effizient laufen.