Row pattern matching in terms of the MATCH_RECOGNIZE clause is a powerful and relatively recent feature in SQL that allows users to define regular patterns over ordered rows in a table. As of today, few database systems offer support for match recognize , making it unaccessible to a wide range of users. We demonstrate the implementation of a transpiler that translates match recognize into a plain SQL query executable by any database system that supports window functions and recursive common table expressions—no changes to the underlying database systems are required. We evaluate the performance of this approach on the running example to show that the transpiler generates code competitive with contemporary database systems that implement row pattern matching natively. The on-site demonstration is based on DuckDB.

SQL query engines can act as efficient runtime environments for the execution of imperative programs over database-resident tabular data. To make this point, we lay out the details of a compilation strategy that maps the basic blocks of arbitrarily branching and looping control flow graphs into plain---possibly recursive---SQL:1999 common table expressions. The compiler does not stumble when faced with imperative programs of several hundred lines and emits SQL code that can execute such programs over entire batches of input arguments. These batches create opportunities for parallel program evaluation which contemporary query decorrelation techniques exploit automatically. SQL engines that already support UDFs may find the present program execution approach to outperform their native implementation---SQL engines without such support may gain UDF capabilities without the need to build a dedicated interpreter.

"Move your computation close to the data" is decades-old advice that is hard to follow if your code exhibits complex control flow. The runtime of such applications suffers from a continual back and forth between database-external code execution and plan-based SQL evaluation. We demonstrate the ByePy compiler which translates entire Python functions with arbitrary control flow-including deeply nested iteration-into plain recursive SQL:1999 queries. The invocation of a ByePy-compiled function enters the database engine once to execute the plan of a single query. Computation does not get much closer to the data than this. The system rewards this translation effort from Python to SQL with runtime improvements of up to an order of magnitude.

PL/SQL integrates an imperative statement-by-statement style of programming with the plan-based evaluation of SQL queries. The disparity of both leads to friction at runtime, slowing PL/SQL execution down significantly. This work describes a compiler from PL/SQL UDFs to plain SQL queries. Post-compilation, evaluation entirely happens on the SQL side of the fence. With the friction gone, we observe execution times to improve by about a factor of 2, even for complex UDFs. The compiler builds on techniques long established by the programming language community. In particular, it uses trampolined style to compile arbitrarily nested iterative control flow in PL/SQL into SQL's recursive common table expressions.

We advocate to express complex in-database computation using a functional style in which SQL UDFs use plain self-invocation to recurse. The resulting UDFs are concise and readable, but their run time performance on contemporary RDBMSs is sobering. This paper describes how to compile such functional-style UDFs into SQL:1999 recursive common table expressions. We build on function call graphs to build the compiler's core and to realize a series of optimizations (reference counting, memoization, exploitation of linear and tail recursion). The compiled UDFs evaluate efficiently, challenging the performance of manually tweaked (but often convoluted) SQL code. SQL UDFs can indeed be functional and fast.

We demonstrate a source-to-source compilation technique that can translate user-defined PL/SQL functions into plain SQL queries. These PL/SQL functions may feature arbitrarily complex control flow-iteration, in particular. From this imperative-style input code we derive equivalent recursive common table expressions, ready for execution on any relational SQL:1999 back-end. Principally due to the absence of PL/SQL?SQL context switches, the output plain SQL code comes with substantial runtime savings. The demonstration embeds the compiler into an interactive setup that admits function editing while live re-compilation and visualization of intermediate code forms happens in the background.

We demonstrate how to use PostgreSQL's planner hook to open a side entrance through which we can pass plan trees for immediate execution. Since this reaches deep into PostgreSQL, we implement plan detail inference and decoration to ensure that externally crafted trees perfectly mimic regular plans. Plan trees may then (1) be generated by external code generators that want to use PostgreSQL as a reliable and efficient back-end for new (maybe even non-relational) languages, or (2) stem from experimental rewrites of SQL plans that PostgreSQL itself does not implement (yet). The demonstration provides a live account of what becomes possible once we let PostgreSQL hatch foreign plan eggs.

Ideas from programming languages play an important role in a range of advanced applications of databases, in database system implementation, distributed programming (MapReduce), streaming computation, and high-performance (GPU/multicore) computation. This creative research area is broadening into a subfield of data-centric computation. Although the interaction of databases and programming has a long history (the 16th biennial Database Programming Languages symposium was held in 2017), there has been a recent renewal of interest and broadening of programming language techniques for dealing with data from several quarters in the last few years, including workshops at Microsoft Research (RADICAL 2010), ICFP (XLDI 2012), POPL (DDFP 2013, DCM 2014) and a Dagstuhl Seminar on Programming Languages for Big Data (December 2014). This special issue recognises and encourages the publication of mature research contributions in this area.

SQL declaratively specifies what the desired output of a query is. This work shows that a non-standard interpretation of the SQL semantics can, instead, disclose where a piece of the output originated in the input and why that piece found its way into the result. We derive such data provenance for very rich SQL dialects---including recursion, windowed aggregates, and user-defined functions---at the fine-grained level of individual table cells. The approach is non-invasive and implemented as a compositional source-level SQL rewrite: an input SQL query is transformed into its own interpreter that wields data dependencies instead of regular values. We deliberately design this transformation to preserve the shape of both data and query, which allows provenance derivation to scale to complex queries without overwhelming the underlying database system.

We demonstrate how the compilation of SQL expressions into machine code leads to significant query runtime improvements in PostgreSQL 9. Our primary goal is to connect recent research in query code generation with one of the most widely deployed database engines. The approach calls on LLVM to translate arithmetic and filter expressions into native x86 instructions just before SQL query execution begins. We deliberately follow a non-invasive design that does not turn PostgreSQL on its head: interpreted and compiled expression evaluation coexist and both are used to execute the same query. We will bring an enhanced version of PostgreSQL that exhibits notable runtime savings and provides visual insight into exactly where and how execution plans can benefit from SQL expression compilation.

We demonstrate a new incarnation of Habitat, an observational debugger for SQL. In observational debugging, users highlight parts of a presumably faulty query to observe the evaluation of SQL subexpressions and learn about the query's actual runtime behavior. The present version of Habitat has been redesigned from scratch and employs a query instrumentation technique that exclusively relies on the SQL facilities of the underlying RDBMS. We particularly shed light on new features like (1) the debugging of recursive SQL queries and (2) the observation of row groups (before and after aggregation). Habitat can turn any reasonably modern SQL:1999 RDBMS into its own language-level SQL debugger.

We demonstrate the insides and outs of a query compiler based on the flattening transformation, a translation technique designed by the programming language community to derive efficient data-parallel implementations from iterative programs. Flattening admits the straightforward formulation of intricate query logic including deeply nested loops over (possibly ordered) data or the construction of rich data structures. To demonstrate the level of expressiveness that can be achieved, we will bring a compiler frontend that accepts queries embedded into the Haskell programming language. Compilation via flattening takes places in a series of simple steps all of which will be made tangible by the demonstration. The final output is a program of lifted primitive operations which existing query engines can efficiently implement. We provide backends based on PostgreSQL and VectorWise to make this point however, most set-oriented or data-parallel engines could benefit from a flattening-based query compiler.

With Thinking Functionally in Haskell Richard Bird steps up to continue a family of textbook classics.Bird and Wadler jointly started the series with two editions of Introduction to Functional Programming (in Haskell) in 1988 and 1998, respectively.Let me begin with the outright spoiler that I think that this third edition breathes new life into the series and indeed presents a worthy continuation.The 12 chapters of the 340-page volume contain more material than most layouts of a one-term introductory course on functional programming can accommodate.If the many exercises are considered in depth and a discussion of Haskell-specifics is added (more on both points below), we hold the syllabus of a two-term course in our hands.According to the blurb, the book addresses first-or second-year undergraduates.I agree, but gained the impression that true programming novices would probably struggle starting with the fifth chapter when concepts, scripts, and exercises become more complex.This is also where the exposition generally picks up speed.From the outset, Bird consistently adopts a style of programming in which complex functions are composed from simpler constituents that are useful on their own (". . .functions that seem to be basic in programming are often composed of even simpler functions.A bit like protons and quarks.")Already the earliest exercises in Chapter 1 adhere to this principle: an elaborate pipeline of function types has to be designed even before students can be expected to write the functions' bodies.Early on lazy evaluation is established as a principle that makes this rigorous compositional style viable.Here, and at many occasions later in the book, Bird relates the discussion to the research literature or blog posts. 1 This provides welcome entry points for deep dives into the subject.When Chapter 4 introduces lists it carefully distinguishes finite, infinite, and partial values, a discussion that has its dedicated Chapter 9 but permeates the entire book.Chapter 5 is entirely devoted to a Sudoku solver that readers of Bird's Pearls of Functional Algorithm Design (Cambridge University Press, 2010) will recognize.The present book significantly expands on the earlier treatment through an in-depth discussion of the many involved component functions.The derivation of an efficient solver from the "clearest specification" also marks the first larger showcase of equational reasoning.Bird consequently uses the "Wim Feijen style" e 1 = {justification} e 2 to simplify and optimize programs or to establish proofs of their properties.The rewriting of compositions of functions remains one of Bird's grand themes.Calculations pervade the entire book, from its preface(!) to the final Chapter 12 where a (semi-)automatic equational rewriter is developed.Lawful program construction encourages "wholemeal programming", 1 Regarding a discussion of strict vs. lazy evaluation, Bird points to a blog post by Robert Harper and the extensive thread of comments that followed (http://existentialtype.wordpress.

We demonstrate the derivation of fine-grained where - and why -provenance for a rich dialect of SQL that includes recursion, (correlated) subqueries, windows, grouping/aggregation, and the RDBMS's library of built-in functions. The approach relies on ideas that originate in the programming language community---program slicing and abstract interpretation, in particular. A two-stage process first records a query's control flow decisions and locations of data access before it derives provenance without consultation of the actual data values (rendering the method largely "value-less"). We will bring an interactive demonstrator that uses this provenance information to make input/output dependencies in real-world SQL queries tangible.

We demonstrate a full-fledged implementation of first-class functions for the widely used PL/SQL database programming language. Functions are treated as regular data items that may be (1) constructed at query runtime, (2) stored in and retrieved from tables, (3) assigned to variables, and (4) passed to and from other (higher-order) functions. The resulting PL/SQL dialect concisely and elegantly expresses a wide range of new query idioms which would be cumbersome to formulate if functions remained second-class citizens. We include a diverse set of application scenarios that make these advantages tangible. First-class PL/SQL functions require featherweight syntactic extensions only and come with a non-invasive implementation-- the defunctionalization transformation--that can entirely be built on top of existing relational DBMS infrastructure. An interactive demonstrator helps users to experiment with the "function as data" paradigm and to earn a solid intuition of its inner workings.

We describe H abitat , a declarative observational debugger for SQL. H abitat facilitates true language-level (not: plan-level) debugging of, probably flawed, SQL queries that yield unexpected results. Users mark SQL subexpressions of arbitrary size and then observe whether these evaluate as expected. H abitat understands query nesting and free row variables in correlated subqueries, and generally aims to not constrain users while suspect subexpressions are marked for observation. From the marked SQL text, H abitat 's algebraic compiler derives a new query whose result represents the values of the desired observations. These observations are generated by the target SQL database host itself and are derived from the original data: H abitat does not require prior data extraction or extra debugging middleware. Experiments with TPC-H database instances indicate that observations impose a runtime overhead sufficiently low to allow for interactive debugging sessions.

We demonstrate SWITCH, a deep embedding of relational queries into Ruby and Ruby on Rails. With SWITCH, there is no syntactic or stylistic difference between Ruby programs that operate over in-memory array objects or database-resident tables, even if these programs rely on array order or nesting. SWITCH's built-in compiler and SQL code generator guarantee to emit few queries, addressing long-standing performance problems that trace back to Rails' Active Record database binding. "Looks likes Ruby, but performs like handcrafted SQL, " is the ideal that drives the research and development effort behind SWITCH.

We demonstrate Habitat, a declarative observational debugger for SQL. Habitat facilitates true language-level (not: plan-level) debugging of, probably flawed, SQL queries that yield unexpected results. Users may mark arbitrary SQL subexpressions---ranging from literals, over fragments of predicates, to entire subquery blocks---to observe whether these evaluate as expected.

This paper is about a Glasgow Haskell Compiler (GHC) extension that generalises Haskell's list comprehension notation to monads. The monad comprehension notation implemented by the extension supports generator and filter clauses, as was the case in the Haskell 1.4 standard. In addition, the extension generalises the recently proposed parallel and SQL-like list comprehension notations to monads. The aforementioned generalisations are formally defined in this paper. The extension will be available in GHC 7.2.

A purely relational account of the true XQuery semantics can turn any relational database system into an XQuery processor. Compiling nested expressions of the fully compositional XQuery language, however, yields odd algebraic plan shapes featuring scattered distributions of join operators that currently overwhelm commercial SQL query optimizers.

We report on a query compilation technique that enables the construction of alternative efficient query providers for Microsoft's Language Integrated Query (LINQ) framework. LINQ programs are mapped into an intermediate algebraic form, suitable for execution on any SQL:1999-capable relational database system. This compilation technique leads to query providers that (1) faithfully preserve list order and nesting, both being core features of the LINQ data model, (2) support the complete family of LINQ's Standard Query Operators, (3) bring database support to LINQ to XML where the original provider performs in-memory query evaluation, and, most importantly, (4) emit SQL statement sequences whose size is only determined by the input query's result type (and thus independent of the database size). A sample query scenario uses this LINQ provider to marry database-resident TPC-H and XMark data---resulting in a unique query experience that exhibits quite promising performance characteristics, especially for large data instances.

We demonstrate an efficient LINQ to SQL provider and its significant impact on the runtime performance of LINQ programs that process large data volumes. This alternative provider is based on Ferry, compilation technology that lets relational database systems participate in the evaluation of first-order functional programs over nested, ordered data structures. The Ferry-based provider seamlessly hooks into the .NET LINQ framework and generates SQL code that strictly adheres to the semantics of the LINQ data model. Ferry comes with strong code size guarantees and complete support for the LINQ Standard Query Operator family, enabling a truly interactive and compelling LINQ demonstration. A variety of inspection holes may be opened to learn about the internals of the Ferry-based LINQ to SQL provider.

We introduce a controlled form of recursion in XQuery, an inflationary fixed point operator, familiar from the context of relational databases. This operator imposes restrictions on the expressible types of recursion, but it is sufficiently versatile to capture a wide range of interesting use cases, including Regular XPath and its core transitive closure operator.

A purely relational account of the true XQuery semantics can turn any relational database system into an XQuery processor. Compiling nested expressions of the fully compositional XQuery language, however, yields odd algebraic plan shapes featuring scattered distributions of join operators that currently overwhelm commercial SQL query optimizers. This work rewrites such plans before submission to the relational database back-end. Once cast into the shape of join graphs, we have found off-the-shelf relational query optimizers - the B-tree indexing subsystem and join tree planner, in particular - to cope and even be autonomously capable of "reinventing" advanced processing strategies that have originally been devised specifically for the XQuery domain, e.g., XPath step reordering, axis reversal, and path stitching. Performance assessments provide evidence that relational query engines are among the most versatile and efficient XQuery processors readily available today.

We demonstrate the language Ferry and its editing, compilation, and execution environment FerryDeck. Ferry's type system and operations match those of scripting or programming languages; its compiler has been designed to emit (bundles of) compliant and efficient SQL:1999 statements. Ferry acts as glue that permits a programming style in which developers access database tables using their programming language's own syntax and idioms -- the Ferry-expressible fragments of such programs may be executed by a relational database back-end, i.e., close to the data. The demonstrator FerryDeck implements compile-and-execute-as-you-type interactivity for Ferry and offers a variety of (graphical) hooks to explore and inspect this approach to database-supported program execution.

We introduce a controlled form of recursion in XQuery, an inflationary fixed point operator, familiar from the context of relational databases. This operator imposes restrictions on the expressible types of recursion, but we show that it is sufficiently versatile to capture a wide range of interesting use cases, including Regular XPath and its core transitive closure operator. While the optimization of general user-defined recursive functions in XQuery appears elusive, we describe how inflationary fixed points can be efficiently evaluated, provided that the recursive XQuery expressions are distributive. We test distributivity syntactically and algebraically, and provide experimental evidence that XQuery processors can benefit substantially from this mode of evaluation.

In the implementation of hosted business services, multiple tenants are often consolidated into the same database to reduce total cost of ownership. Common practice is to map multiple single-tenant logical schemas in the application to one multi-tenant physical schema in the database. Such mappings are challenging to create because enterprise applications allow tenants to extend the base schema, e.g., for vertical industries or geographic regions. Assuming the workload stays within bounds, the fundamental limitation on scalability for this approach is the number of tables the database can handle. To get good consolidation, certain tables must be shared among tenants and certain tables must be mapped into fixed generic structures such as Universal and Pivot Tables, which can degrade performance.

Though inevitable for effective cost-based query rewriting, the derivation of meaningful cardinality estimates has remained a notoriously hard problem in the context of XQuery. By basing the estimation on a relational representation of the XQuery syntax, we show how existing cardinality estimation techniques for XPath and proven relational estimation machinery can play together to yield dependable forecasts for arbitrary XQuery (sub)expressions. Our approach benefits from a light-weight form of data flow analysis. Abstract domain identifiers guide our query analyzer through the estimation process and allow for informed decisions even in case of deeply nested XQuery expressions. A variant of projection paths [15] provides a versatile interface into which existing techniques for XPath cardinality estimation can be plugged in seamlessly. We demonstrate an implementation of this interface based on data guides. Experiments show how our approach can equally cope with both, structure-and value-based queries. It is robust with respect to intermediate estimation errors, from which we typically found our implementation to recover gracefully.

There are more spots than immediately obvious in XQuery expressions where order is immaterial for evaluation - this affects most notably, but not exclusively, expressions in the scope of unordered {} and the argument of fn:unordered(). Clearly, performance gains are lurking behind such expression contexts but the prevalent impact of order on the XQuery semantics reaches deep into any compliant XQuery processor, making it non-trivial to set this potential free. Here, we describe how the relational XQuery compiler Pathfinder uniformly exploits such order indifference in a purely algebraic fashion: Pathfinder-emitted plans faithfully implement the required XQuery order semantics but (locally) ignore order wherever this is admitted.

The Pathfinder XQuery compiler has been enhanced by a new code generator that can target any SQL:1999-compliant relational database system(RDBMS). This code generator marks an important next step towards truly relational XQuery processing, a branch of database technology that aims to turn RDBMSs into highly efficient XML and XQuery processors without the need to invade the relational database kernel. Pathfinder, a retargetable front-end compiler, translates input XQuery expressions into DAG-shaped relational algebra plans. The code generator then turns these plans into sequences of either SQL:1999 statements or view definitions which jointly implement the (sometimes intricate) XQuery semantics. In a sense, this demonstration thus lets relational algebra and SQL swap their traditional roles in database query processing. The result is a code generator that (1) supports an almost complete dialect of XQuery, (2) can target any RDBMS with a SQL:1999 language interface, and (3) exhibits quite promising performance characteristics when run against high-volume XML data as well as complex XQuery expressions.

To compensate for the inherent impedance mismatch between the relational data model (tables of tuples) and XML (ordered, unranked trees), tree join algorithms have become the prevalent means to process XML data in relational databases, most notably the TwigStack[6], structural join[1], and staircase join[13] algorithms. However, the addition of these algorithms to existing systems depends on a significant invasion of the underlying database kernel, an option intolerable for most database vendors.

Relational XQuery systems try to re-use mature relational data management infrastructures to create fast and scalable XML database technology. This paper describes the main features, key contributions, and lessons learned while implementing such a system. Its architecture consists of (i) a range-based encoding of XML documents into relational tables, (ii) a compilation technique that translates XQuery into a basic relational algebra, (iii) a restricted (order) property-aware peephole relational query optimization strategy, and (iv) a mapping from XML update statements into relational updates. Thus, this system implements all essential XML database functionalities (rather than a single feature) such that we can learn from the full consequences of our architectural decisions. While implementing this system, we had to extend the state-of-the-art with a number of new technical contributions, such as loop-lifted staircase join and efficient relational query evaluation strategies for XQuery theta-joins with existential semantics. These contributions as well as the architectural lessons learned are also deemed valuable for other relational back-end engines. The performance and scalability of the resulting system is evaluated on the XMark benchmark up to data sizes of 11GB. The performance section also provides an extensive benchmark comparison of all major XMark results published previously, which confirm that the goal of purely relational XQuery processing, namely speed and scalability, was met.

This article is a proposal for a database index structure, the XPath accelerator , that has been specifically designed to support the evaluation of XPath path expressions. As such, the index is capable to support all XPath axes (including ancestor, following, preceding-sibling, descendant-or-self, etc.). This feature lets the index stand out among related work on XML indexing structures which had a focus on the child and descendant axes only. The index has been designed with a close eye on the XPath semantics as well as the desire to engineer its internals so that it can be supported well by existing relational database query processing technology: the index (a) permits set-oriented (or, rather, sequence-oriented) path evaluation, and (b) can be implemented and queried using well-established relational index structures, notably B-trees and R-trees.We discuss the implementation of the XPath accelerator on top of different database backends and show that the index performs well on all levels of the memory hierarchy, including disk-based and main-memory based database systems.

This work is a proposal for a database index structure that has been specifically designed to support the evaluation of XPath queries. As such, the index is capable to support all XPath axes (including ancestor, following, preceding-sibling, descendant-or-self, etc.). This feature lets the index stand out among related work on XML indexing structures which had a focus on regular path expressions (which correspond to the XPath axes children and descendant-or-self plus name tests). Its ability to start traversals from arbitrary context nodes in an XML document additionally enables the index to support the evaluation of path traversals embedded in XQuery expressions. Despite its flexibility, the new index can be implemented and queried using purely relational techniques, but it performs especially well if the underlying database host provides support for R-trees. A performance assessment which shows quite promising results completes this proposal.