Indizierung und Performanztests mit R's data.table
Einführung
Viele R-Nutzer verwenden bereits bei der Arbeit mit großen Datenmengen das Package data.table, welches vom nativen data.frame abstammt und als verbesserte, effizientere Version dessen angesehen werden kann. So bietet data.table nicht nur syntaktische Vorteile, sondern auch eine von Haus aus bessere Performanz bei diversen Funktionen wie bspw. dem Einlesen oder Sortieren von Daten. Darüber hinaus ermöglicht data.table noch weitere Möglichkeiten, Datenmengen aufzubereiten, wodurch typische Operationen, wie bspw. Filter oder Aggregation, weiterhin (teilweise sogar sehr stark) beschleunigt werden können.
Die einfachste Variante, Daten aufzubereiten, ist eine bloße Sortierung nach ein oder mehreren Spalten, wie es bei data.frame auch schon möglich ist. Zwei weitere Varianten kommen hier nun mit data.table hinzu, namentlich die Funktionen setkey und setindex. Diese Funktionen erlauben eine manuelle Indizierung eines Datensatzes, aber auch eine Möglichkeit zur automatischen Indizierung zur Laufzeit ist gegeben und standardmäßig bei data.table aktiviert. Eine Indizierung wird intern von data.table für effizientere Berechnungen genutzt. So hat beispielsweise eine standardgemäße data.table auf einem Testdatensatz für eine simple Aggregationsabfrage der Form DT[A==1, sum(B)] eine Laufzeit von 90 ms beansprucht, während dieselbe Operation nach Indizierung der data.table mittels setkey auf Spalte A nur noch eine Laufzeit von 3 ms brauchte.
Offensichtlich sind Laufzeitgewinne in dieser Größenordnung nur merklich, wenn man mit großen Datenmengen und einer sehr hohen Anzahl solcher Operationen arbeitet, die von einer Aufbereitung denn auch wirklich profitieren. Dieser Beitrag soll sich also vorwiegend den unterschiedlichen Aufbereitungsvarianten widmen und deren Effekt auf die Performanz üblicher Operationen auf data.table untersuchen. Insbesondere werden also auch Einschränkungen und Grenzen aufgezeigt und unterschiedliche Strategien für den Umgang mit R’s data.table besprochen. Gestützt wird die Untersuchung durch Laufzeitmessungen auf einem Testdatensatz.
Aufbereitung einer data.table
Zunächst folgt ein Überblick über die Aufbereitungsvarianten setorder [1], setkey und setindex [2]. Genauere Informationen u. a. zu Syntax und Funktionsparameter können aus den jeweiligen Einträgen der R-Dokumentation entnommen werden (setkey und setindex sind in der Dokumentation zusammengefasst). Wer sich genauer im Source-Code umschauen möchte, der sei auf das entsprechende Git-Repository verwiesen [3]. Im File setkey.R findet man die Funktionsdefinitionen aller drei Aufbereitungsvarianten.
- setorder sortiert einen Datensatz.
- setindex sortiert nicht effektiv, sondern berechnet einen Vektor, der einer Sortierung entspricht und als Attribut
indexder data.table gespeichert wird. Ein solcher Index wird auch als Sekundärindex bezeichnet. Es sind beliebig viele Sekundärindizes für eine data.table möglich, die jeweils 4 Bytes pro Datenreihe an Speicher benötigen. - setkey vereint die Funktionsweise von setorder und setindex. Die Daten werden sortiert und die Schlüsselspalten über das Attribut
sortedals sortiert markiert. Solch ein Index wird auch Primärindex bzw. Schlüssel genannt. Da Daten nur in einer Weise sortiert vorliegen können, kann es auch nur einen Schlüssel geben.
Ein kurzer Blick in die Dokumentation bzw. den Source-Code verrät, dass setindex lediglich ein Aufruf von setkey ist, allerdings wird hierbei der Parameter physical=FALSE gesetzt. Dies verhindert die physikalische Sortierung im RAM, wie es sonst standardmäßig bei setkey und setorder passieren würde.
Wendet man bspw. ein setorder(DT, A, B, C) auf eine data.table DT an, so wird DT zuerst nach A, innerhalb A nach B und innerhalb B wiederum nach C sortiert. Im Falle von setkey und setindex können wir zusätzlich das Ergebnis überprüfen und mittels key(DT) bzw. indices(DT) eine Liste der bisher erzeugten Indizes ausgeben lassen. Der Primärindex setkey(DT, A, B, C) sowie der Sekundärindex setindex(DT, A, B, C) würden beide als "A__B__C" notiert.
Wie eingangs erwähnt, ist bei data.table standardmäßig die automatische Generierung von Sekundärindizes (im Weiteren als autoindex bezeichnet) aktiviert. Bei Bedarf lässt sich diese Option auch ausschalten. Ansonsten folgt autoindex demselben Prinzip wie setindex, generiert also ebenso Sekundärindizes. Ausgehend von der allgemeinen data.table Syntax DT[i, j, by] wird automatisch ein Index erzeugt, wenn i einer Kondition der Form A==a oder A %in% a gleicht. Die verbose Option von data.table gibt darüber Auskunft, wenn ein Index erzeugt wird. Bei der Verwendung von autoindex sollte man aber bedenken, dass die Indexerzeugung ebenfalls Zeit beansprucht. Das kann den ersten Aufruf einer Operation entsprechend etwas verlangsamen. Zudem kann man sich noch bewusst machen, dass autoindex Indizes “verkehrtherum” erzeugt.
Beispiele für Indexgenerierung mittels autoindex:
DT[A==a] # erzeugt "A"
DT[A %in% a] # erzeugt "A"
DT[A==a & B==b & C==c] # erzeugt "C__B__A"
DT[C==c & B==b & A==a] # erzeugt "A__B__C"
DT[A!=a] # erzeugt keinen Index!
DT[A!=a & B==b] # erzeugt keinen Index!
Wurde bereits ein Index erzeugt, der aus zwei oder mehreren Spalten besteht, wird mittels autoindex keine weitere Permutation desselben Index erzeugt. Führt man also von den obigen Beispielen die Zeilen 3 und 4 hintereinander aus, würde der Index "A__B__C" nicht mehr erzeugt werden. Durch den Aufruf mittels setindex könnte man dies zwar erzwingen, es ist aber im allgemeinen NICHT sinnvoll. Wegen der Funktionsweise von data.table sind nämlich alle folgend generierten Permutationen existierender Indizes redundant. Eine Operation, die einen vorhandenen Index nutzt, würde auch jede andere Permutation desselben Index nutzen. Entscheidend ist nur, welcher Index zuerst generiert wurde. Ob ein Index (obgleich Primär- oder Sekundärindex) von einer Operation verwendet wurde und, falls ja, welcher, teilt ebenfalls die verbose Option mit. Dabei haben Primärindizes immer Vorrang vor Sekundärindizes.
Wichtig: Die Reihenfolge der Spalten bei einer Indizierung kann in einem speziellen Fall für die Laufzeit durchaus einen Unterschied machen. Was für eine Bedeutung das auch für den autoindex hat, wird im Beitrag später erläutert (siehe Abschnitt Spezialfall: setorder + autoindex).
Getestete Operationen und Grenzen einer Indizierung
Nachdem die Theorie hinter der Aufbereitung einer data.table grob erläutert wurde, soll dieser Abschnitt einen Überblick über die getesteten Operationskategorien geben und kurz darauf eingehen, inwiefern eine Indizierung in den einzelnen Kategorien sinnvoll sein wird. Dazu sind in folgender Tabelle zunächst die untersuchten Operationskategorien gelistet.
| Operationskategorie | Beispiel |
|---|---|
| Filter (column) | DT[, .(A,B)] |
| Filter (row index) | DT[c(1,2)] |
| Filter (conditional) | DT[A==a & B==b] |
| Aggregate | DT[, sum(C), by=.(A,B)] |
| Aggregate (conditional) | DT[A==a & B==b, sum(C)] |
| Merge | merge(DT1, DT2, by=”A”) DT1[DT2, on=”A”] (data.table Syntax) |
| Delete | DT[!(A == a & B==b)] |
| Update | DT[, C := round(exp(C), 2)] |
| Update (condtional) | DT[A==a & B==b, C := round(exp(C), 2)] |
Anmerkung: Indizes werden teilweise durch Operationen auf dem Datensatz beeinflusst. So verschwindet ein Primärindex komplett, wenn der Datensatz neusortiert wird. Update-Operationen auf einer Primärindexspalte bewirken, dass diese und alle nachfolgenden Spalten des Index die Markierung verlieren, dass diese sortiert sind. Ein Schlüssel "A__B__C" wird bei Update von "B" also zum Schlüssel "A". Dagegen verschwinden alle Sekundärindizes komplett, sobald man Datenzeilen nach dem Prinzip DT <- DT[A != a] löscht oder die Daten neusortiert. Ein Update einer Spalte löscht alle Indizes, die die aktualisierte Spalte beinhalteten.
Welche dieser Operationen können bei ihrer Berechnung nun überhaupt einen Index zur Hand nehmen? Die Funktionsweise von autoindex lässt die Antwort auf diese Frage erahnen (und auch die Tests haben bestätigt), dass fast ausschließlich solche Operationen Indizes nutzen, die selber mittels autoindex einen Index generieren würden. In obiger Tabelle sind es also genau jene, die als conditional gekennzeichnet wurden und deren Konditionen der autoindex-Syntax genügen. Allerdings gibt es noch zwei aufgrund ihrer Funktionsweise relativ intuitive Ausnahmen von dieser Regel, worauf auch verbose hindeutet: Bei Merge werden Primär- als auch Sekundärindizes genutzt, bei Aggregate nur Primärindizes, in beiden Fällen geschieht dies anhand des Parameters by=.
Scheinbar erübrigen sich durch diese Erkenntnisse die Tests in den Kategorien Filter (column), Filter (row index), Delete und Update, zumindest beim Einsatz von Indizierungen. Die Testergebnisse werden diese Erkenntnis auch weitgehend stützen und aufzeigen, wie sehr eine Aufbereitung positiv oder auch negativ ins Gewicht fällt.
Testsetup, Testvorgehen und Testvalidität
Bevor in den nächsten Abschnitten die Testergebnisse präsentiert werden, soll der Leser hier die Möglichkeit bekommen, das gesamte Testverfahren nachzuvollziehen.
Getestet wurde auf einem System mit 16 GB Arbeitsspeicher und einer 8-Kern-CPU á 2,3 GHz. Die Testdatei war etwa 5 GB groß und umfasste 45 Mio. Zeilen auf 20 Spalten. Darunter waren u. a. die Spalten:
- ID, N1, N2: Zahlen [1 bis 100], gleichverteilt
- W1: Strings [“hello”, “world”, “helloworld”], gleichverteilt
- W2: Strings [“lorem”, “ipsum”], gleichverteilt
Für die Tests in den konditionellen Operationskategorien wurde die Option autoindex ausgeschaltet. Schließlich galt es zunächst die reinen Laufzeiten der Operationen zu untersuchen, nachdem bereits eine Aufbereitung stattfand. Grundsätzlich sind aber die Laufzeiten bei autoindex ab dem zweiten Operationsaufruf identisch zu denen bei der entsprechenden Verwendung von setindex. Trotzdem wurden aber die Operationskonditionen immer so gewählt, dass sie stets der autoindex-Syntax genügten, weil so die Verwendung von vorhandenen Indizes gewährleistet wurde.
Eine Kondition beinhaltete dabei bis zu drei Spalten, wie zum Beispiel der Filter DT[ID==1 & W1=="hello" & W2=="lorem"]. Der Datensatz lag dabei unmodifiziert oder in einer aufbereiteten Form vor, wo ebenfalls eine Sortierung bzw. Indizierung nach bis zu drei Spalten genutzt wurde. Entsprechend wird für die Einfachheit im Folgenden von der Wertigkeit einer Operation/Kondition bzw. Aufbereitung gesprochen. Die Wahl der Spalten sowie deren Reihenfolge in Konditionen und Aufbereitungen wurde zudem weitgehend aneinander angepasst. So wurde bspw. die 3-wertige Operation DT[ID==1 & W1=="hello" & W2=="lorem"] nur auf den Sortierungen/Indizierungen "ID", "ID__W1" und "ID__W1__W2" angewandt. Andere Reihenfolgen wurden nur vereinzelt getestet.
Umgekehrt wurden genauso auf einer festgewählten Aufbereitung mehrere unterschiedlich-wertige Operationen getestet, zum Beispiel die Filteroperationen DT[ID==1], DT[ID==1 & W1=="hello"] und DT[ID==1 & W1=="hello" & W2=="lorem"] auf einer Aufbereitung nach "ID". Die Laufzeiten der Operationen wurden mittels system.time ermittelt. Es wurde nun für jede Operationskategorie zu jeder Aufbereitungswertigkeit ein separater Laufzeitdurchschnitt berechnet, indem die Wertigkeit der Aufbereitung festgewählt und dann alle Operationen der Operationskategorie ausgeführt wurden. Damit sollte untersucht werden, ob sich innerhalb einer Operationskategorie der Effekt einer bestimmten Aufbereitung auf mehreren Operationen bemerkbar macht.
Konkretes Beispiel für die Berechnung eines Durchschnittswerts:
# 1. Datensatz aufbereiten
setorder(DT, ID)
# 2. Laufzeittests der Operationen
a <- system.time(DT[ID==1])
b <- system.time(DT[ID==1 & W1=="hello"])
c <- system.time(DT[ID==1 & W1=="hello" & W2=="lorem"])
# 3. Ermitteln und Festhalten des Durchschnittswerts in Statistik
avg <- (a+b+c)/3
Wichtig: Die Laufzeit einer Abfrage kann je nach Kondition sehr unterschiedlich ausfallen. Erstens läuft beim Vergleich zweier gleich-wertiger Operation normalerweise diejenige schneller, die das kleinere Ergebnis produziert bzw. auf einem kleineren Teil des Datensatzes arbeitet. Zweitens erhöht sich die Laufzeit einer Operation aber auch mit ihrer Wertigkeit, obwohl dadurch im Vergleich zu einer ähnlichen nieder-wertigeren Operation ein kleineres Ergebnis produziert bzw. auf einem kleineren Datensatz gearbeitet wird. Darüber hinaus muss man im Hinterkopf behalten, dass Operationen, die Strings einsetzen, für gewöhnlich langsamer laufen als andere, gleich-wertige Operationen, die lediglich Integer oder Wahrheitswerte nutzen. Insgesamt können durch die Testergebnisse also letztendlich keine absoluten Aussagen getroffen werden, sondern lediglich Effekte und Tendenzen aufgedeckt.
Laufzeitergebnisse und erste Beobachtungen
In diesem Abschnitt soll nun ein Überblick über die Testergebnisse gegeben werden. Eine genauere Betrachtung zum Effekt der unterschiedlichen Aufbereitungsvarianten setorder, setkey und setindex wird dann im nachfolgenden Abschnitt gegeben.
Folgende Grafik fasst die berechneten durchschnittlichen Laufzeiten, wie im vorigen Abschnitt beschrieben, zusammen. Alle Angaben sind Durchschnittswerte in Millisekunden. Jede Zeile repräsentiert hier eine Operationskategorie. Die Spalten unterteilen die Messergebnisse in die jeweilige Aufbereitungsart. Da in den Operationskategorien Filter (column) und Filter (row index) die Laufzeiten trotz Aufbereitung nahezu konstant geblieben sind, wurden diese in der Grafik ausgelassen. Befindet sich in einer Zelle ein Eintrag mit zwei Zahlen (bspw. 3824 - 4974), so bezieht sich der erste Durchschnittswert auf den Fall einer 1-wertigen Aufbereitung und der zweite auf eine 3-wertige Aufbereitung.
Zunächst kann man festhalten, dass ein Sekundärindex vergleichsweise wesentlich schneller berechnet wird als eine Aufbereitung mittels setorder und setkey, die beide eine tatsächliche Sortierung miteinschließen. setorder und setkey hingegen sind etwa gleich langsam.
Wie zu erwarten war, sind in den Kategorien Delete und Update kaum positive Effekte durch Aufbereitungen verzeichnet worden. Teilweise hat sich die durchschnittliche Laufzeit durch eine 1-wertige Aufbereitung mittels setorder und setkey sogar etwas verschlechtert.
Operationen in den Kategorien Merge und Aggregate liefen dagegen schneller, nachdem der Datensatz mittels setorder und setkey nach den entsprechenden Schlüssel- bzw. Gruppierungsspalten aufbereitet wurde. Hier liegt allerdings die Vermutung nahe, dass der stärkste Laufzeitgewinn allein durch die Sortierung erzielt wird, denn schließlich zeigte die sekundäre Indizierung mittels setindex keinen positiven Einfluss. Weiterhin gibt es Fälle, bei denen Aggregate trotz Nutzung eines Primärschlüssels merkwürdigerweise sehr viel langsamer lief als sonst (rot gekennzeichnet, später mehr dazu).
Einzig bei den konditionellen Operationskategorien konnten alle Aufbereitungsvarianten überzeugen. Hier fällt auf, dass der Durchschnittswert, der mit einer höher-wertigeren Aufbereitung korrespondiert, in allen Fällen geringer war als der entsprechende Durchschnittswert der 1-wertigen Aufbereitung.
Ist die Wahl einer höher-wertigeren Aufbereitung somit für jede Operation sinnvoll? Diese Frage soll im nächsten Abschnitt beantwortet werden.
Genauere Analyse
In diesem Abschnitt wird der Effekt einer Aufbereitung nochmals genauer untersucht. Dabei waren v. a. folgende Fragen interessant: Welche Auswirkung hat eine gegebene Aufbereitung auf eine anders-wertige Operation? Und inwiefern spielt die Spaltenreihenfolge der Aufbereitung eine Rolle? Aufgrund der Vielfalt an Testoperationen, die entstehen, wenn man die Konditions- bzw. Aufbereitungsspalten permutiert, wurden nur die hier beschriebenen Fälle bis hin zu 3-wertigen Operationen/Aufbereitungen betrachtet.
setorder
In den Tests zeigte sich, dass sich eine Sortierung im Allgemeinen positiv auf die Laufzeit von Operationen auswirkte, solange Spalten von Aufbereitung und Operation zumindest teilweise miteinander übereinstimmten. Die Permutation der Spalten von Aufbereitung und Operation war hierbei scheinbar nebensächlich. Im besten Fall aber stimmten Wertigkeit und Spalten von Aufbereitung und Operation genau überein.
Höher-wertige Aufbereitungen hatten weiterhin einen stärkeren positiven Effekt auf nieder-wertigere Operationen als es andersherum der Fall war. Konkretes Beispiel (Angaben in Millisekunden):
| Operation | unmod. | setorder(DT, (ID) |
setorder(DT, ID,W1,W2) |
|---|---|---|---|
| DT[ID==1] | 313 | 227 | 246 |
| DT[ID==1 & W1==’world’ & W2==’ipsum’] | 1346 | 1337 | 877 |
Es konnten ansonsten keine negativen Effekte von setorder beobachtet werden, sodass setorder zwar nicht die größten Performanzgewinne einbringt, allerdings relativ sicher einsetzbar ist. Arbeitet man mit höher-wertigen Operationen, empfiehlt sich in jedem Fall auch eine entsprechend höher-wertige Sortierung.
setindex
Durchschnittlich war die Laufzeit der konditionellen Operationen bei der Verwendung von 3-wertigen Sekundärindizes niedriger als bei der Verwendung von 3-wertigen Sortierungen. Doch das ist etwas trügerisch, denn der Einsatz von Sekundärindizes ist sehr eingeschränkt. Ein Sekundärindex wird nur bei konditionellen Operationen eingesetzt und auch nur dann, wenn Wertigkeit und Spalten von Aufbereitung und Kondition komplett miteinander übereinstimmen, abweichende Permutationen sind aber auch hier erlaubt. Im Falle der normalerweise recht langsamen 3-wertigen Operationen ergaben sich dadurch bei Verwendung des richtigen Index sehr niedrige Laufzeiten, was den Durchschnitt somit senkte. Konkretes Beispiel (Angaben in Millisekunden):
| Operation | unmod. | setindex(DT, ID) |
setindex(DT, ID,W1,W2) |
|---|---|---|---|
| DT[ID==1] | 313 | 195 | 323 |
| DT[ID==1 & W1==’world’ & W2==’ipsum’] | 1346 | 1367 | 96 |
Grundsätzlich bietet sich der Einsatz mehrerer sekundärer Indizes an (wie es oftmals auch bei autoindex geschehen würde). Allerdings können sich zu viele Indizes auch wieder negativ auf die Laufzeit mancher Operationen auswirken. Konkretes Beispiel (Angaben in Millisekunden):
| Operation | setindex(DT, ID) | setindex(DT, ID) + 10 weitere Indizes |
|---|---|---|
| DT[, .(ID)] | 230 | 961 |
| DT[ID==1, N1:=10*N1] | 113 | 825 |
Insgesamt bietet sich setindex also nur für konditionelle Operationen und auch nur dann an, wenn Konditionen gleichbleibend sind oder eine kleine Auswahl an Indizes ausreichend ist.
setkey
setkey erreichte in fast allen Operationskategorien die besten durchschnittlichen Laufzeiten. Hier werden der Vorteil von Sortierung und Indizierung kombiniert. Der Primärindex wird allerdings nur in zwei Fällen genutzt.
- Fall: Wertigkeit und Spalten von Index und Operation stimmen komplett überein, voneinander abweichende Permutationen sind dabei erlaubt.
- Fall: Es liegt ein höher-wertigerer Index vor und die Operation operiert auf einer Permutation des Index, die ausschließlich aus den Anfangsspalten des Index besteht.
Eine Indizierung "A__B" wirkt somit ausschließlich bei Operationen auf "A__B", "B__A" (Fall 1) und "A" (Fall 2). In den restlichen Fällen erbt setkey die Aspekte von setorder, allerdings werden durch den Primärindex wesentlich bessere Durchschnittswerte bei den Laufzeiten erzielt. Konkretes Beispiel aus dem Test (Angaben in Millisekunden):
| Operation | unmod. | setkey(DT, ID) |
setkey(DT, ID,W1,W2) |
|---|---|---|---|
| DT[ID==1] | 313 | 40 | 41 |
| DT[ID==1 & W1==’world’ & W2==’ipsum’] | 1346 | 1340 | 6 |
setkey erscheint vermeintlich als durchweg bessere Version von setorder. In den Tests zeigte sich aber nun ein Spezialfall in der Operationskategorie Aggregate, wo setkey im Vergleich zu setorder versagt. Aggregationsoperation der Wertigkeit größer als 1, die einen Primärindex nutzen (d. h. der Index ist gleich- oder höher-wertig) laufen wesentlich langsamer ab als wenn nur ein 1-wertiger Primärindex genutzt wird. Konkretes Beispiel (Angaben in Millisekunden):
| Operation | undmod. | setkey(DT, ID) |
setkey(DT, ID,N2) |
setkey(DT, ID,N2,W1) |
|---|---|---|---|---|
| DT[, sum(N1), by=ID] | 693 | 214 | 216 | 208 |
| DT[, sum(N1), by=.(ID,N2)] | 818 | 518 | 1065 | 1037 |
| DT[, sum(N1), by=.(ID,N2,W1)] | 905 | 663 | 625 | 1791 |
Möchte man also bei Aggregate Primärindizes ausnutzen, so beschränkt sich der Einsatz auf 1-wertige Aufbereitungen bzw. Operationen.
Zwischenfazit: Stellt für den Anwendungszweck einer Person die Einschränkung von setkey bezüglich Aggregate kein Hindernis dar, so ist setkey den anderen beiden Aufbereitungsvarianten überlegen. Man sollte aber im Hinterkopf behalten, dass es nur einen Primärindex (bzw. nur eine Sortierung) geben kann, dafür allerdings mehrere Sekundärindizes. Demzufolge sind je nach Anwendung auch Mischformen empfehlenswert, also die Kombination von Primärindex/Sortierung und mehreren Sekundärindizes. Hierauf wird auch im folgenden Abschnitt nochmal eingegangen.
Weitere Strategien
In diesem Abschnitt sollen noch andere Herangehensweisen erläutert werden, um Operationen auf Datenmengen möglichst schneller zu machen.
setorder + setindex = setkey?
Wie im vorigen Abschnitt erläutert, kombiniert setkey Sortierung und Indizierung. Was passiert also, wenn wir die Sortierung mittels setorder und die Indizierung mittels setindex kombinieren? Die Wahl der Spalten sowie deren Reihenfolge für Aufbereitung und Operationen wurde hierbei wie immer angepasst. Konkretes Beispiel (Angaben in Millisekunden):
| Operation | unmod. | setkey(DT, ID,W1,W2 |
setorder(DT, ID,W1,W2) + setindex(DT, ID,W1) |
|---|---|---|---|
| DT[ID==1] | 313 | 41 | 234 |
| DT[ID==1 & W1==’world’] | 790 | 11 | 13 |
| DT[ID==1 & W1==’world’ & W2==’ipsum’] | 1346 | 6 | 906 |
Aus der Tabelle geht hervor, dass die Kombination von setorder und setindex sowohl die Vorteile als auch Einschränkungen beider Welten vereint. In den Fällen, in denen keine Indizierung wirkt, kann noch von der Sortierung profitiert werden (vergleiche hierfür mit Tabelle zu setorder). Falls aber eine Indizierung greift, wird diese durch die zugrundeliegende Sortierung noch weiter beschleunigt, die Laufzeiten erreichen hier das Niveau von setkey.
autoindex
Wie bereits erwähnt, kostet beim erstmaligen Aufruf einer konditionellen Operation die automatische Generierung eines Index zusätzliche Zeit. Folgeoperationen sind dann allerdings schneller (auf Niveau von setindex). Um genau zu sein, verwendet eine Operation aber schon beim ersten Aufruf den bereits generierten Index. In manchen Fällen, überwiegt der Performanzgewinn den initialen Overhead. Konkretes Beispiel (Angaben in Millisekunden):
| Operation | unmod. | autoindex (1. Aufruf) |
Folgeaufrufe |
|---|---|---|---|
| DT[ID==1] | 313 | 517 | 221 |
| DT[ID==1 & W1==’world’] | 790 | 617 | 134 |
| DT[ID==1 & W1==’world’ & W2==’ipsum’] | 1346 | 687 | 111 |
Spezialfall: setorder + autoindex
Wie im vorigen Abschnitt erläutert, war die Reihenfolge der Spalten bei der Sortierung bzw. Indizierung für die Laufzeit von Operationen größtenteils irrelevant. Hier handelt es sich aber nun um einen Fall, bei dem dies nicht so ist. Doch zunächst sollte man sich nochmal die Funktionsweise von autoindex klarmachen. Eine Operation DT[A==a & B==b] erzeugt keinen Index "A__B", sondern "B__A". Wenn wir also weiterhin wie im obigen Beispiel setorder + setindex intuitiv anhand der Operationskondition sortieren, aber dieses mal nicht zusätzlich noch auf die manuelle, sondern auf die automatische Indizierung mittels autoindex zurückgreifen, dann liegen letztendlich Sortierung und Indizierung in umgekehrter Reihenfolge vor! Und genau das ist der Fall, bei dem die Operation im Vergleich zum harmonischen Fall setorder + setindex etwas an Performanz verliert. Möchte man also alles an Performanz rausholen, sollte bei der Kombination von Sortierung und Indizierung auf dieselbe Reihenfolge der Spalten beider Aufbereitungen geachtet werden. Konkretes Beispiel (Angaben in Millisekunden):
| Operation | unmod. | setorder(DT, ID,W1,W2) + autoindex (1. Aufruf) |
Folgeaufrufe |
|---|---|---|---|
| DT[ID==1] | 313 | 170 | 45 |
| DT[ID==1 & W1==’world’] | 790 | 486 | 99 |
| DT[ID==1 & W1==’world’ & W2==’ipsum’] | 1346 | 569 | 102 |
Ad-hoc Index und Filterkette
Hier sollen noch zwei Strategien angesprochen werden, die ohne eine tatsächliche Aufbereitung der Daten funktionieren. Beide Strategien sind mit den in diesem Beitrag besprochenen Aufbereitungsvarianten kombinierbar.
Zum einen gibt es die Möglichkeit bei Operationen einen flüchtigen Index zu berechnen, den sogenannten ad-hoc Index. Dieser wird einzig für die Operation berechnet und dann wieder verworfen. Das klingt zunächst wenig effizient, kann sich aber in einigen Fällen im Vergleich zum alleinigen Gebrauch von autoindex auszahlen. Der ad-hoc Index wird über den Parameter on= genutzt. Die Syntax kann dabei bspw. wie folgt aussehen DT[.(a,b), on=.(A,B)], was äquivalent zu der Standardschreibweise DT[A==a & B==b] ist. Praktisch bei seiner Verwendung ist hierbei, dass entweder ein ad-hoc Index oder aber ein bereits existenter Primär- bzw. Sekundärindex benutzt wird. Gerade wenn man verhindern möchte, dass für jede vereinzelte Abfrage ein neuer Index durch autoindex generiert wird, eignet sich der Einsatz.
Zum anderen bietet die Verkettung von Filtern eine weitere Option. Eine Filteroperation DT[A==a & B==b] kann nämlich auch als Verkettung DT[A==a][B==b] berechnet werden. Dies kann den anfangs beschriebenen Problemen vorbeugen: Das Aufteilen der Bedingung verhindert die Anwendung langsamer, höher-wertiger Operationen und die Wahl eines geeigneten Anfangsglieds kann bewirken, dass schnell auf einem kleineren Datensatz gerechnet wird. Dies hat also als Voraussetzung, dass man bereits genauere Kenntnisse über die Daten besitzt. Verkettung sollte aber dann auch nur eingesetzt werden, wenn man weiß, dass für den unverketteten Fall kein Index vorliegt und man auch wie beim ad-hoc Index auf die automatische Generierung eines Index mittels autoindex verzichten möchte.
Ein Beispiel für ein Messergebnis ist im folgenden zusammengefasst (Angaben in Millisekunden):
| Operation | unmod. | ad-hoc | Verkettung |
|---|---|---|---|
| DT[ID==1] | 313 | 370 | 313 |
| DT[ID==1 & W1==’world’] | 790 | 489 | 385 |
| DT[ID==1 & W1==’world’ & W2==’ipsum’] | 1346 | 548 | 395 |
| DT[IW2==’ipsum’ & W1==’world’ & ID==1] | 1701 | 520 | 3864 |
Ad-hoc hat in allen Testfällen gute Laufzeiten im Vergleich zum Standardaufruf derjeweiligen Operation, nur im 1-wertigen Fall überwiegt der Overhead. Verkettung läuft in allen Fällen noch schneller als ad-hoc bis auf den Fall, wo das Anfangsglied nicht gut gewählt wird und somit nach dem ersten Glied noch 50% der Daten vorhanden sind anstatt 1% wie in den anderen Fällen.
Zusammenfassung
Grundsätzlich kann man sagen, dass eine unaufbereitete data.table niemals empfehlenswert ist. Es gibt aber keine allgemeine Lösung, die jeden Nutzer zufriedenstellen wird. Je nach Anwendungsfall sollte man sich also für mindestens eine Art der Aufbereitung entscheiden. Für Operationen der Kategorie Aggregate und Merge eignen sich hierbei besonders Sortierungen mittels setorder oder setkey. Für konditionelle Abfragen sind vor allem Indizierungen sinnvoll. Während eine Sortierung oft allgemein schon die Performanz erhöht, muss man bei Indizes bedenken, dass deren Anwendbarkeit stark von der Syntax der Operationskondition abhängt. Wer es allerdings schafft, Indizes sinnvoll anzuwenden, wird große Performanzgewinne erzielen können. Wer sich hierbei weniger Sorgen über manuelle Indizierungen machen möchte, ist mit autoindex gut bedient. Mit dem ad-hoc Index stellt sich eine Möglichkeit dar, die automatische Erzeugung von Indizes zu umgehen, aber trotzdem noch effizient zu arbeiten und im besten Fall sogar auf vorhandene Indizes zurückzugreifen. Die Verkettung von Filtern kann ebenfalls in das Gesamtbild integriert werden, sofern man bereits über großes Wissen über den Datensatz verfügt.
Handlungsempfehlung auf Basis der Testergebnisse
Nutzer, die nur vereinzelte Operationen auf kurzweiligen Datenmengen ausführen, sollten sich weniger Gedanken um eine gute Aufbereitung machen. Selbst autoindex kann die Performanz einer vereinzelten Abfrage erhöhen. Hier empfiehlt sich zum Beispiel die Nutzung von ad-hoc Indizes oder auf den Daten so zu arbeiten, wie sie schon vorliegen.
Arbeitet man hingegen längerfristig mit einem Datensatz, auf dem man wiederholte Operationen mit immer selben Konditionen ausführt, so empfiehlt sich in jedem Fall zunächst eine Sortierung mindestens mittels setorder. Kombinieren kann man dies dann noch mit einer kleinen Auswahl an erforderlichen Sekundärindizes.
Hat man hingegen den Fall, dass man sehr viele Operationen mit unterschiedlichen Konditionen auf einem Datensatz ausführen möchte, so bietet sich in jedem Fall eine Sortierung mittels setkey an. Am besten sollte eine höher-wertige Aufbereitung gewählt werden, damit auch nieder-wertigere Operationen von der Aufbereitung profitieren. Für die variablen Konditionen kann man dann bspw. zum ad-hoc Index greifen, wenn man sich sicher ist, dass man von einer längerfristigen Indexerzeugung mittels autoindex oder setindex nicht profitieren würde.
Links
[1] https://www.rdocumentation.org/packages/data.table/versions/1.12.8/topics/setorder
[2] https://www.rdocumentation.org/packages/data.table/versions/1.12.8/topics/setkey
[3] https://github.com/Rdatatable/data.table/tree/master/R