Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Bachelor's Thesis |
| Scope | Discipline-based scholarship |
| Title | A General-purpose Range Join Algorithm for PostgreSQL |
| Organization Unit | |
| Authors |
|
| Supervisors |
|
| Language |
|
| Institution | University of Zurich |
| Faculty | Faculty of Business, Economics and Informatics |
| Date | 2020 |
| Abstract Text | In this thesis we provide a range join algorithm based on the sort-merge paradigm and its implementation into the open-source RDBS PostgreSQL. The traditional sort-merge join is an efficient join algorithm for equality constraints, while a range join additionally considers a predicate describing that a value from one relation is in the range between two values of the other relation. PostgreSQL implements the sort-merge join or Merge Join (MJ) as a state machine adhering to the demand-pull pipeline paradigm. Our range join or Range Merge Join (RMJ) builds on the existing implementation and expands it with additional conditions to efficiently handle range joins. We describe in detail, how we modified the PostgreSQL optimizer and executor to achieve this goal. We provide the implementation of the RMJ algorithm as well as the identification of possible range join predicates and the correct sorting of the input relations. We show the benefits of our implementation in several experiments using real-world and synthetic workloads and datasets. The experiments show a major reduction in execution time in most real-world and all of our synthetic workloads, while only incurring a minor overhead in planning time in a few cases. |
| Zusammenfassung | In dieser Thesis zeigen wir einen Range-Join-Algorithmus, der auf dem Sort-Merge-Paradigma basiert und dessen Implementierung im Open-Source-RDBS PostgreSQL. Der Sort-Merge-Join ist ein effizienter Join-Algorithmus für Gleichheitsbedingungen. Ein Range-Join berücksichtigt ein zusätzliches Prädikat, das beschreibt, dass ein Wert aus einer Relation im Bereich zwischen zwei Werten der anderen Relation liegt. PostgreSQL implementiert den Sort-Merge-Join oder Merge-Join (MJ) als eine ``state machine'', welche nach dem Demand-Pull-Pipelining-Prinzip funktioniert. Unser Range-Join oder Range-Merge-Join (RMJ) baut auf der bestehenden Implementierung auf und erweitert sie um zusätzliche Bedingungen, um Range-Joins effizient zu handhaben. Wir beschreiben im Detail, wie wir den Optimizer und Executor von PostgreSQL modifiziert haben. Wir zeigen nicht nur die Implementierung des RMJ-Algorithmus, sondern auch die Identifizierung möglicher Range-Join-Prädikate und die korrekte Sortierung der Input-Relationen. Wir zeigen die Vorteile unserer Implementierung in mehreren Experimenten unter Verwendung von realen und synthetischen Arbeitslasten und Datensätzen. Die Experimente zeigen eine erhebliche Reduzierung der Ausführungszeit in einigen realen und all unseren synthetischen Arbeitslasten mit nur einem geringf\"ugig h\"oheren Planungsaufwand in bestimmten Fällen. |
| PDF File |
Download
|
| Export |
BibTeX
|