Lehrstuhl für Datenbanksysteme (Database Systems Chair)

Join graphs in databases

SQL query optimizers strive to produce query plans whose primary components are join graphs—bundles of relations interconnected by join predicates—while a secondary, peripheral plan tail performs further filtering, grouping, and sorting. Plans of this particular type are subject to effective optimization strategies that, taking into account the available indexes and applicable join methods, derive equivalent join trees, ideally with a left-deep profile to enable pipelining. For more than 30 years now, relational query processing infrastructure has been tuned to excel at the evaluation of plans of this shape.

The approach

Based on the loop lifting compilation scheme, we compile XQuery queries into logical algebra plans. Both the compositional language and compilation scheme lead to stacked plans whose shapes differ considerably from the ideal join graph + plan tail. Instead, join operators occur in sections distributed all over the plan. A similar distribution can be observed for the blocking operators δ and ρ (duplicate elimination and row ranking). This is quite unlike the algebraic plans produced by SQL SELECT-FROM-WHERE block compilation.

The omnipresence of blocking operators obstructs join operator movement and planning and leads industrial-strength optimizers, e.g., IBM DB2 UDB V9, to execute the plan in stages that read and then again materialize temporary tables.

Here, we propose a plan rewriting procedure that derives join graphs from the initial plans. The resulting plan may be expressed as a single SELECT-DISTINCT-FROM-WHERE-ORDERBY block to be submitted for execution by an off-the-shelf RDBMS. The database system then evaluates this query over a schema-oblivious tabular encoding of XML documents to compute the encoding of the resulting XML node sequence (which may then be serialized to yield the expected XML text). Alternatively the isolated join graph plans represent the input for ROX: Run-time Optimization of XQueries.

This page is no longer maintained. For up to date information on Nautilus, please visit http://nautilus-system.org.

News

• 11/07/25: Paper got accepted at the QDB Workshop colocated with VLDB 2011.
• 11/04/04: Tim Belhomme has joined the Nautilus team as a research assistant.
• 11/03/01: Hanno Eichelberger has joined the Nautilus team as a student member.
• 10/12/13: Project receives funding from the Baden-Württemberg Stiftung.
• 10/06/14: Paper got accepted at the VLDB 2010 conference.

"The deepest parts of [data transformation] are totally unknown to us. No soundings have been able to reach them. What goes on in those distant depths? What [data and transformations] inhabit, or could inhabit, those regions [...]? What is the constitution of these [...]? It's almost beyond conjecture.” A slightly altered version of an excerpt of Jules Verne's 20,000 Leagues under the Sea, Chapter II.

Overview

Database developers may formulate a thought similar to the one above when designing or modifying database applications that derive data by applying queries or, in general, transformations to source data. Indeed, using declarative languages such as SQL to specify queries, developers often face the problem that they cannot properly inspect or debug their query or transformation code. All they see is the tip of the iceberg once the result data is computed. If it does not comply with the developers’ expectation, they usually perform one or more tedious and mostly manual analyze-fix-test cycles until the expected result occurs. The goal of Nautilus is to support developers in this process by providing a suite of algorithms and tools to accompany the process.

News

• 2012-03-02: The slide set of the Bringing Back Monad Comprehensions and Extending Database Supported Haskell talk given at Functional Programming Laboratory Seminar in Nottingham is available.
• 2012-01-09: The video of the Bringing Back Monad Comprehensions talk given at Haskell Symposium 2011 in Tokyo is now available.
• 2011-09-23: Ferry enters the Scala world: Scala Days 2011 will feature a "Scala Integrated Query" talk (talk video).
• 2011-06-01: Haskell Symposium 2011 paper: Bringing Back Monad Comprehensions got accepted for publication.
• 2011-04-18: Our work on Ferry wins the Peter Landin Prize 2011 for the best paper at IFL 2010. Thank you, folks.
• 2011-02-03: DSH is available for download on Hackage!
• 2010-12-23: IFL 2010 paper: Haskell Boards the Ferry got accepted for publication.
• 2010-07-28: Paper about a Ferry-based Database Coprocessor for Haskell is accepted for presentation at IFL 2010.
• 2010-06-28: The Video of the RADICAL 2010 Ferry talk is available now.
• 2010-06-14: Two Ferry papers got accepted at the VLDB 2010 conference.
• 2010-03-29: RADICAL 2010 will feature a Ferry talk (May 10-11 2010, Microsoft Research, Cambridge).
• 2010-01-01: The Links team at U Edinburgh is collaborating with us to build a Ferry-powered Links query facility.
• 2010-01-01: The DFG is supporting our research on Ferry.

Ferry — Database-Supported Program Execution

With project Ferry we try to establish a connection between two somewhat distant shores: programming languages and database technology. Ferry explores how far we can push the idea of relational database engines that directly and seamlessly participate in program evaluation to support the super-fast execution of data-intensive programs written in a variety of (general purpose) programming languages. Ferry builds on technology developed in the context of our project Pathfinder.