MySQL-Datenbank-Anfragen optimieren: Zu jeder Query passt ein MultiIndex

Veröffentlicht am von
Pressemeldung der Firma Launix

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.



Firmenkontakt und Herausgeber der Meldung:
Launix
Anhalter Str. 8
02730 Ebersbach-Neugersdorf
Telefon: +49 (3586) 3086446
Telefax: nicht vorhanden
https://launix.de



Dateianlagen:
    • Firmenlogo (2015-11-12)
Bei uns bekommen Sie maßgeschneiderte Software zu einem fairen Preis. Lassen Sie sich über eine mögliche Zusammenarbeit beraten! Gute Gründe für Individual-Software. Organisieren Sie Ihre Daten wie Ihre Prozesse nun mal sind. Keine Umstellung, keine Einarbeitung in Standardsoftware, es passt einfach.


Weiterführende Links

Für die oben stehende Pressemitteilung ist allein der jeweils angegebene Herausgeber (siehe Firmenkontakt oben) verantwortlich. Dieser ist in der Regel auch Urheber des Pressetextes, sowie der angehängten Bild-, Ton-, Video-, Medien- und Informationsmaterialien. Die Huber Verlag für Neue Medien GmbH übernimmt keine Haftung für die Korrektheit oder Vollständigkeit der dargestellten Meldung. Auch bei Übertragungsfehlern oder anderen Störungen haftet sie nur im Fall von Vorsatz oder grober Fahrlässigkeit. Die Nutzung von hier archivierten Informationen zur Eigeninformation und redaktionellen Weiterverarbeitung ist in der Regel kostenfrei. Bitte klären Sie vor einer Weiterverwendung urheberrechtliche Fragen mit dem angegebenen Herausgeber. Eine systematische Speicherung dieser Daten sowie die Verwendung auch von Teilen dieses Datenbankwerks sind nur mit schriftlicher Genehmigung durch die Huber Verlag für Neue Medien GmbH gestattet.