On extending postgreSQL with the skyline operator

Abstract

Im Bereich der multikriteriellen Optimierung ist das Design einer geeigneten Zielfunktion aus Anwendersicht eine Herausforderung.<br />Der Skyline Operator filtert aus einer potentiell großen Datenmenge interessante Tupel heraus. Ein Tupel gehört genau dann zur Skyline, wenn es nicht durch ein anderes dominiert wird, d.h. es gibt kein Tupel, das in allen Kriterien zumindest gleich gut ist und in zumindest einem besser ist. Unabhängig wie die Präferenzen innerhalb der Attribute gewählt werden, sind nur jene Tupel, die unter einer monotonen Scoring-Funktion am besten bewertet werden, Teil der Skyline. Mit anderen Worten, die Skyline schließt alle Tupel aus, die niemand als Favorit hat. Das Konzept der Skyline ist auch unter dem Namen Pareto Optimalität und ihre Berechnung als Maximum Vektor Problem bekannt.<br />Ziel dieser Diplomarbeit ist PostgreSQL, ein Open Source relationales Datenbankmanagementsystem (RDBMS), um den Skyline Operator zu erweitern und Skyline Algorithmen im RDBMS Kontext zu evaluieren. Das Endziel ist eine Skyline-Abfrage-Optimierung zu entwickeln, die automatisch gute Abfragepläne bezüglich I/O, Zeit und Speicherverbrauch erstellt. Diese Arbeit ebnet den Boden für weitere Forschung und verpflanzt den Skyline Operator von standalone Implementierungen in sein natürliches Habitat, das RDBMS. Unsere Implementierung bietet verschiedene physische Operatoren, um die Skyline zu berechnen, allen voran: BNL, SFS und eine Variante von LESS. Zusätzlich erweitern wir die Standardsyntax, um Semantik und verschiedene operationale Aspekte zu beeinflussen. Als Nebenresultat unserer Arbeit haben wir einen Fehler in der Originalversion von BNL entdeckt und liefern dazu eine korrigierte Version. Wir schlagen ein neues Einsatzgebiet für den Elimination Filter (EF) vor und zwar: BNL+EF. Diese Kombination stellt eine erhebliche Verbesserung gegenüber BNL dar.<br />Es ist eine bekannte Tatsache, dass die Performance von Skyline Abfragen von einer Reihe von Parametern abhängt. Aus umfangreichen Experimenten mit unserer Implementierung haben wir mehrere bemerkenswert einfache und nützliche Regeln abgeleitet, die nur schwer theoretisch zu gewinnen sind. Unsere Resultate helfen Heuristiken für die Skyline-Abfrage-Optimierung zu entwickeln und liefern einen Beitrag zum tieferen Verständnis der Skyline- Abfrage-Charakteristik.<br />Alle Resultate, der Source-Code und ein Web-Interface zum Testen unserer Implementierung sind auf http://skyline.dbai.tuwien.ac.at/ verfügbar.

In the realm of multi-criteria optimization designing an appropriate objective function is a challenging task from a user's perspective. The skyline operator filters out the interesting tuples from a potentially large dataset. A tuple belongs to the skyline if it is not dominated by any other tuple, i.e. there is no tuple which is at least as good as in all and better in at least one criteria. No matter how we weight our preferences along the attributes, only those tuples which score best under a monotone scoring function are part of the skyline. In other words, the skyline does not contain tuples which are nobody's favorite. The notion of skyline is also called Pareto optimal set and its computation maximum vector problem.<br />In this thesis we aim at extending PostgreSQL, an open source relational database management system (RDBMS), with the skyline operator and the evaluation of skyline algorithms in the RDBMS context, with the ultimate goal of building a skyline query optimizer to automatically generate a good query plan w.r.t. I/O, time, and memory consumption. This effort lays the ground for future work in this area and moves the skyline operator from standalone implementations to the habitat it belongs to:<br />an RDBMS.<br />Our implementation provides several physical operators for computing the skyline, including: BNL, SFS, and a variant of LESS. In addition, we extend the standard syntax to influence the semantics and various operational aspects. As a byproduct of our work, we discovered flaw in the original version of BNL and give a corrected version. We propose a new use case for the elimination filter (EF), namely: BNL+EF. It turns out that BNL+EF is a substantial improvement to BNL.<br />It is well known that the performance of skyline queries is sensitive to a number of parameters. Extensive experiments on skyline implementations helped us to discover several remarkably simple and useful rules, which are hard to obtain from theoretical investigations. Our findings are beneficial for developing heuristics for the skyline query optimization, and in the meantime provide some insight for a deeper understanding of the skyline query characteristics.<br />All results, the source code, and a web-interface to test-drive the implementation are available at: http://skyline.dbai.tuwien.ac.at/