Fehlerfrei programmieren mit FOP

Fehlerfrei programmieren – das klingt reißerisch. Bedenkt man es genau, sollte es aber definitiv das Ziel jeder Software-Programmierung sein, diese fehlerfrei durchzuführen. Ähnlich wie beispielsweise ein Lackierer mit entsprechender Ausrüstung, Reinräumen und Sorgfalt dafür sorgen kann, dass sein Werk einwandfreie Qualität aufweist, ist es auch in der Software-Entwicklung möglich.
„Fehlerfrei programmieren mit FOP“ weiterlesen

Wie die Softwareentwicklung in der OpenSource-Szene funktioniert (Projektmanagement)

Proprietär oder OpenSource?

Neben kommerzieller proprietärer Software wie dem Betriebssystem und der Office-Suite von Microsoft oder der Adobe-Produktfamilie gibt es inzwischen eine Reihe von weit verbreiteter OpenSource-Software wie zum Beispiel den Linux-Kernel, Open-/Libreoffice, Inkskape, WordPress, MySQL, Apache und viele mehr. Gemeinsam haben diese Projekte, dass der Quellcode unter einer freien Lizenz stehen. Eine freie Lizenz ist eine Lizenz, die es Dritten erlaubt, den Code zu beliebigen Zwecken zu verwenden und somit zum Beispiel das Projekt weiterzuentwickeln oder Einzelheiten anzupassen. Strengere Lizenzen wie die GPL erzwingen sogar, dass nach einer Anpassung der Code offen bleiben muss, also alle Verbesserungen den Benutzern der Software bereitgestellt werden müssen. Für den Anwender hat das den Vorteil, dass eine Software nicht „eingestellt“ werden kann, sondern er notfalls die Software weiterpflegen kann. Ebenfalls macht man sich damit von einztelnen Herstellern unabhängig und kann Support von beliebigen Firmen, wie zum Beispiel bei der Softwareschmiede Launix kaufen. „Wie die Softwareentwicklung in der OpenSource-Szene funktioniert (Projektmanagement)“ weiterlesen

Node.js vs PHP+Apache

PHP und Apache – die verbreitetste Technologie, um Web-Anwendungen umzusetzen. Nicht selten stecken beide Tools viel Kritik bezüglich ihrer Performance ein. Doch auch bezüglich des Sprachendesigns muss vor allem PHP viel hinnehmen. In diesem Blog-Eintrag werden die Hauptkritikpunkte zusammengefasst. Im großen und ganzen kann man das Ökosystem um PHP als eine Sammlung von inkonsistenten 1:1-Wrappern zu C-Bibliotheken bezeichnen. „Node.js vs PHP+Apache“ weiterlesen

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

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.