Improving Joins in Pandas

Abstract

Pandas ist ein unter Datenwissenschaftlern sehr beliebtes Werkzeug zur Datenanalyse und -manipulation. Datenwissenschaftler müssen häufig Rohdaten aus potenziell heterogenen Datenquellen kombinieren. Derzeit verbringen sie bis zu 90 % ihrer Zeit mit dem Bereinigen, Integrieren und Transformieren von Daten. Pandas bietet zwar bestimmte Funktionalitäten eines Datenbanksystems, z.B. unterstützt es mit seiner Data Frame-Abstraktion eine tabellarische Datendarstellung und einige gängige Operationen darauf, aber die wichtigste Datenbankoperation – die Ausführung von Joins – wird derzeit nur sehr rudimentär unterstützt. Es werden nur zweiseitige Joins unterstützt, wobei der Benutzer die Join-Reihenfolge angeben muss, wenn mehr als zwei Relationen kombiniert werden sollen. Je nach Join-Reihenfolge kann die Ausführungszeit jedoch drastisch variieren. Herkömmliche Datenbanksysteme verwenden Abfrageoptimierer, um eine bessere Verknüpfungsreihenfolge zu finden. Diese Optimierer berücksichtigen jedoch nicht die strukturellen Eigenschaften einer Abfrage und verlassen sich stattdessen auf Kardinalitätsschätzungen der an einer Abfrage beteiligten Relationen. Im Laufe der Jahre haben Forscher der Datenbanktheorie dekompositionsbasierte Methoden für die Abfrageauswertung vorgeschlagen. Während die Auswertung konjunktiver Abfragen im Allgemeinen NP-vollständig ist, wurde gezeigt, dass es Algorithmen gibt, die die Unterklasse der azyklischen Abfragen und eine Verallgemeinerung davon in polynomieller Zeit beantworten können. Darüber hinaus wurden für das Problem der exponentiellen Zwischenergebnisgrößen bei Join-Abfragen sogenannte "worst-case optimal join" Algorithmen vorgeschlagen. Sie können dadurch kategorisiert werden, dass ihre Zeitkomplexität immer innerhalb der größtmöglichen Ausgabengröße liegt. Wir erweitern Pandas um eine Funktion, die eine Liste von Data Frame-Objekten akzeptiert und einen natürlichen Join durch Anwendung verschiedener Optimierungen aus der Datenbanktheorie durchführt, abhängig von der Art der Join-Abfrage. Wir konzentrieren uns auf azyklische Abfragen und die "Dreiecks"-Abfrage als einfachste Form einer zyklischen Abfrage, die beide in der Praxis sehr häufig vorkommen, wobei letztere hauptsächlich in Graphdatenbanken zu finden ist. Unsere empirische Evaluierung hat gezeigt, dass wir die meisten azyklischen Abfragen mit dem sogenannten Yannakakis-Algorithmus deutlich besser ausführen können als mit einer Basislösung. Allerdings konnten wir die Ausführungszeit nur für eine von drei Dreiecksabfragen mit einem auf Partitionierung basierenden "worst-case optimal join" Algorithmus verbessern.

Pandas is a very popular tool among data scientists for data analysis and manipulation. Data scientists often need to combine raw data from potentially heterogeneous data sources. Currently, they spend up to 90 % of their time cleaning, integrating and transforming data. While Pandas provides certain functionalities of a database system, e.g. it supports a tabular data representation with its DataFrame abstraction and some common operations on it, the most important database operation, namely the execution of joins, is currently only supported in a very rudimentary way. Only two-way joins are supported, with the user having to specify the join order if more than two relations are to be combined. However, depending on the join order, the execution time can diverge drastically. Traditional database systems use query optimizers to find a better join order. However, these optimizers do not take the structural properties of a query into account, instead relying on cardinality estimates of the relations involved in a query. Over the years, database theory researchers have proposed decomposition-based methods for query evaluation. While conjunctive query evaluation is in general NP-complete, it has been shown that there are algorithms that can answer the subclass of acyclic queries and a generalization thereof in polynomial time. Furthermore, worst-case optimal join algorithms have been proposed for the problem of exponential intermediate result sizes in join queries. They can be categorized by the fact that their time complexity is always within the largest possible output size. We extend Pandas with a function that accepts a list of DataFrame objects and performs a natural join by applying different optimizations from database theory, depending on the type of join query. We focus on acyclic queries and the "triangle" query as the simplest form of a cyclic query, both of which are very common in practice, the latter being found mainly in graph databases. Our empirical evaluation shows that we can execute most acyclic queries significantly better with the so-called Yannakakis algorithm, compared to a baseline. However, we were only able to improve the execution time for one out of three triangle queries using a partitioning-based worst-case optimal join algorithm.