SQL allows for very flexible nesting of queries, including subqueries that access attributes by the outer part of the query. These correlated subqueries simplify query formulation, but their execution is very inefficient, leading to O(n^2) runtime complexity. Which can become prohibitively expensive for large databases.

Query optimizers therefore try to unnest, i.e., decorrelate the dependent queries. Existing decorrelation techniques, however are either limited in scope or lead to suboptimal execution plans when correlated queries are stacked repeatedly inside each other. In this work we present a generalized unnesting approach that can handle deep nestings of correlated subqueries and that generalizes

to complex query constructs, including recursive SQL. This generalized unnesting improves the asymptotic complexity, and thus can lead to dramatic performance improvements in the affected queries.

A query model for sequence data was introduced in Kleest-Meißner et al. (2022)

in the form of subsequence-queries with wildcards and gap-size constraints

(swg-queries, for short). These queries consist of a pattern over an alphabet of

variables and values, as well as a global window size and a number of local

gap-size constraints.

Based on previous extensions of swg-queries, namely multi-dimensional

swg-queries and disjunctive swg-queries, we converge to common languages in

the field of Complex Event Processing by introducing multi-dimensional disjunctive subsequence-queries with intervals.

This pushes the expressive power of the query language to certain kinds of

inequalities as well.

We discuss a suitable characterisation of containment, a classical property

considered in database theory, and adapt results concerning the discovery of

(multi-dimensional or disjunctive) swg-queries to multi-dimensional disjunctive

subsequence-queries with intervals.

Data warehouses need materialized views and their indexes because fetching a pre-computed query result is faster than computing it. Incremental maintenance is a solved problem for “group by” views and their indexes (for most aggregation functions), with updates made efficient by log-structured merge-forests. Views that join two or more tables have proven much more difficult—if supported at all, they are often left to fall out-of-date with occasional and expensive re-computation from base tables.

Instead of either indexes on base tables or materialized and indexed join results, an intermediate index or “image” format—the merged index—promises fast maintenance in small transactions (insertions, updates, and deletions), as well as efficient queries in point queries and in complete or bulk joins at full scan bandwidth. It supports bulk loads into one or both join inputs, is agnostic to join type (e.g., outer join), and requires only a moderate software development effort. We present the storage structure, argue for its simplicity and generality, and compare its performance with existing strategies.

Optimizing for memory consumption during query processing can be facilitated by enumerating pipeline execution orders in query processors to minimize the lifetime of intermediates. The number of possible enumerations is potentially factorial. Recent literature has explored algorithms to enumerate pipeline execution orders for a given query execution plan. However, no methods of calculating the number of pipeline execution orders for any given query execution plan were provided. Due to the factorial complexity a pre-calculation of the expected enumeration count is necessary.

This work will provide the combinatorial framework to calculate the structural complexity, i.e. the expected enumeration count, of any given query execution plan without traversing. Through this, we provide the means to identify expensive query execution plans. The precise calculation then enables optimizers to employ heuristics for memory optimization if the given query execution plan exposes too many possible pipeline execution orders.

With increasingly faster networks, storage disaggregation in databases enhances resource utilization by independently scaling compute and storage nodes. Storage technologies like NVMe SSDs provide high throughput and low latency, but maintaining these characteristics in a disaggregated architecture poses significant challenges. NVMe-oF is a recent remote storage protocol that leverages fast network technologies such as RDMA to allow for efficient storage disaggregation with low access overheads. In this paper, we present a first evaluation of the performance properties of NVMe-oF for database workloads to guide the development of databases. Our evaluation shows that NVMe-oF can offer high I/O performance when choosing configurations that are optimal for for various database workloads. However, we also show that some optimizations, such as target-offload, which minimize CPU involvement on the storage side are not (yet) working as expected.