Compilation of Cursor Loops by Realizing Aggify: Milestone Report

Aggify series: Home · Proposal · Milestone (this page) · Final report

Group Information

Haoyu Zhang: haoyuzha

Yuchen Liu: yuchenl6

URL for Project

https://www.haoyu.dev/blog/aggify-home

Major Changes

We changed our roadmap: the first step became benchmarking Aggify on the TPC-H workloads. We hand-wrote the best code we could for every Aggify workload and profiled it. Benchmarking before automatic code generation made sense for two reasons. Writing the code by hand taught us the algorithm well enough to reproduce it programmatically, and the control flow graph (CFG) was not yet ready for dataflow analysis anyway. It turned out to be the right call: walking through each step of the paper by hand surfaced two roadblocks, DuckDB’s limited support for custom aggregates and a fundamental design flaw in Aggify itself. Because we hit both early, we have dealt with them and are on track to finish on time.

Current Progress

Two pieces of work made implementing Aggify in DuckDB possible.

Custom Aggregates in DuckDB without Combine()

A custom aggregate’s Combine() method defines how to merge the results of aggregating two groups into one. With it, the execution engine can split a large group into partitions, aggregate each in parallel, and combine the results. Inferring Combine() from a cursor loop is out of scope for the Aggify paper, and we suspect it is impossible in general. DuckDB, however, requires every custom aggregate to provide one. To implement Aggify in DuckDB we modified query execution to run custom aggregates single-threaded, which removes the need for Combine().

Fixing a design flaw in Aggify

While trying to reproduce Aggify’s experimental results, we found a major design flaw. Take one of the paper’s own test cases, Figure 1(a); Figure 1(b) shows the result of applying Aggify to it. custom_count behaves like the native count except that it has no Combine() method, so it cannot run in parallel. Aggify produces the correct result for this test case as written. Change the initial value of val to a non-zero number, though, and the transformation breaks. If the cursor (pink) query returns nothing, running the loop normally leaves val untouched and the UDF returns 100 (Figure 1(c)), but the custom aggregate overwrites val with 0 (Figure 1(d)), which disagrees with the original UDF.

The fix is simple. The problem only appears when the cursor query returns nothing, so we guard the custom aggregate with a precondition that the query is non-empty. The correct transformation of (c) is shown below. It introduces a second query that repeats work; next we will test whether the optimizer’s common subexpression elimination can absorb that overhead.

val := 100;
if exists SELECT O_ORDERKEY 
			    FROM orders
			    WHERE O_CUSTKEY = custkey
	val := SELECT custom_count(okey, val) FROM (
				 SELECT O_ORDERKEY 
			   FROM orders
			   WHERE O_CUSTKEY = custkey
			   ) AS tmp;

Benchmark Result

With those problems fixed, we compared Aggify against built-in aggregates, which represent the best possible performance. The experiment uses the TPC-H dataset at scale factor 10 on a MacBook with an Apple M1 Pro and 32 GB of RAM.

As expected, custom aggregates generally do not perform as well as built-in ones, up to 0.18 times slower on the DiscountRevenue workload. The gap comes from the lack of parallelism: Aggify’s custom aggregates have no Combine() and so run sequentially, while built-in aggregates use every available thread. To check this, we ran both workloads again with DuckDB limited to one thread, and Aggify performed about the same as the built-in aggregate. Using more sophisticated program analysis to infer Combine() for cursor loops would be an interesting research direction.

Revised Schedule

At the time of this report we were at week 4 of the project.

Resources Needed

Hard work.

References

[1] S. Gupta, S. Purandare, and K. Ramachandra, “Aggify: Lifting the Curse of Cursor Loops using Custom Aggregates,” in Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, Portland OR USA: ACM, Jun. 2020, pp. 559–573. doi: 10.1145/3318464.3389736.