Sampling over joins is a fundamental task in large-scale data analytics. Instead of computing the full join results, which could be massive, a uniform sample of the join results would suffice for many purposes, such as answering analytical queries or training machine learning models. In this article, we study the problem of how to maintain a random sample over joins while the tuples are streaming in. Without the join, this problem can be solved by some simple and classical reservoir sampling algorithms. However, the join operator makes the problem significantly harder, as the join size can be polynomially larger than the input. We present a new algorithm for this problem that achieves a near-linear complexity. The key technical components are a generalized reservoir sampling algorithm that supports a predicate, and a dynamic index for sampling over joins. We also conduct extensive experiments on both graph and relational data over various join queries, and the experimental results demonstrate significant performance improvement over the state of the art.

Query processing under updates (a.k.a. incremental view maintenance) has received increasing attention in recent years, from both theoretical and practical angles. While existing algorithms work well in handling reporting queries, they may incur a high cost on aggregation queries, which are the more important type of analytical workload. In this paper, we show that by allowing a small approximation error, aggregation queries can be processed efficiently under updates. Specifically, we design a new approximate query processing (AQP) algorithm that can maintain the result of any free-connex aggregation query in logarithmic time amortized per update over an insertion-only update sequence. For update sequences with both insertions and deletions, the logarithmic time bound does not hold, due to known lower bounds. Practically, our algorithm performs well on both insertion-only and fully dynamic update sequences. Our experimental results show that, with a 10% error guarantee, the algorithm achieves average speedups of 1.5x, 4.8x, and 13.4x over three exact solutions. Our algorithm works in a general semiring framework, which incorporates a variety of aggregations, including count, sum, avg, max, and count distinct, possibly with a group by.

Acyclic conjunctive queries form the backbone of most analytical workloads, and have been extensively studied in the literature from both theoretical and practical angles. However, there is still a large divide between theory and practice. While the 40-year-old Yannakakis algorithm has strong theoretical running time guarantees, it has not been adopted in real systems due to its high hidden constant factor. In this paper, we strive to close this gap by proposing Yannakakis+, an improved version of the Yannakakis algorithm, which is more practically efficient while preserving its theoretical guarantees. Our experiments demonstrate that Yannakakis+ consistently outperforms the original Yannakakis algorithm by 2x to 5x across a wide range of queries and datasets. Another nice feature of our new algorithm is that it generates a traditional DAG query plan consisting of standard relational operators, allowing Yannakakis+ to be easily plugged into any standard SQL engine. Our system prototype currently supports four different SQL engines (DuckDB, PostgreSQL, SparkSQL, and AnalyticDB from Alibaba Cloud), and our experiments show that Yannakakis+ is able to deliver better performance than their native query plans on 160 out of the 162 queries tested, with an average speedup of 2.41x and a maximum speedup of 47,059x.

We will demonstrate Quorion, a query rewriter with theoretical guarantees and better practical performance. Quorion adopts some of the recently developed query planning methods that provide optimality guarantees, including Yannakakis + , an optimized version of the Yannakakis algorithm, generalized hypertree decompositions (GHD), GYO reduction, and cost-based optimization. Quorion also provides a platform for users to explore different query plans for a given query through a web-based interface and compare their performance with classical query plans. Quorion currently supports DuckDB, MySQL, and PostgreSQL, and can be connected to any user-provided database easily through a JDBC connector.

Sampling over joins is a fundamental task in large-scale data analytics. Instead of computing the full join results, which could be massive, a uniform sample of the join results would suffice for many purposes, such as answering analytical queries or training machine learning models. In this paper, we study the problem of how to maintain a random sample over joins while the tuples are streaming in. Without the join, this problem can be solved by some simple and classical reservoir sampling algorithms. However, the join operator makes the problem significantly harder, as the join size can be polynomially larger than the input. We present a new algorithm for this problem that achieves a near-linear complexity. The key technical components are a generalized reservoir sampling algorithm that supports a predicate, and a dynamic index for sampling over joins. We also conduct extensive experiments on both graph and relational data over various join queries, and the experimental results demonstrate significant performance improvement over the state of the art.

We revisit the classical change propagation framework for query evaluation under updates. The standard framework takes a query plan and materializes the intermediate views, which incurs high polynomial costs in both space and time, with the join operator being the culprit. In this paper, we propose a new change propagation framework without joins, thus naturally avoiding this polynomial blowup. Meanwhile, we show that the new framework still supports constant-delay enumeration of both the deltas and the full query results, the same as in the standard framework. Furthermore, we provide a quantitative analysis of its update cost, which not only recovers many recent theoretical results on the problem, but also yields an effective approach to optimizing the query plan. The new framework is also easy to be integrated into an existing streaming database system. Experimental results show that our system prototype, implemented using Flink DataStream API, significantly outperforms other systems in terms of space, time, and latency.