Aggify series: Home · Proposal (this page) · Milestone · Final report
Use Aggify to rewrite a query loop written in JDBC
Group Information
Haoyu Zhang: haoyuzha
Yuchen Liu: yuchenl6
Project Description
We want to implement the techniques from the paper Aggify: Lifting the Curse of Cursor Loops using Custom Aggregates in DuckDB. Aggify is an optimization pass that rewrites the cursor loops in procedural user-defined functions as custom aggregate functions, after which techniques like UDF inlining [2, 3] or UDF compilation [4] can be applied. We target PL/pgSQL UDFs and DuckDB. PL/pgSQL is static and syntactically conservative, which makes compilation easier; DuckDB is a system we already know well, and its open-source community has been very helpful.
The technique requires building a CFG for the whole procedure, running dataflow analyses (reaching definitions, live variables), generating the custom aggregate in C++, and rewriting the original UDF to call it.
75% Goal
Pass all six TPCH test cases.
Construct CFG of PL/pgSQL.
Do correct Data Flow Analysis.
Code generation.
Using the vectorized API (need to check if there is a scalar version)
Rewrite original UDF.
100% Goal
Perform optimizations related to loops, such as DCE, LICM.
125% Goal
Perform “query motion”. In Query 2, for example, the loop body starts with a filter condition; we can hoist it out of the loop into the WHERE clause of the cursor's SELECT, which cuts the iteration count and materializes less data.
declare c1 cursor for (select PS_SUPPLYCOST, S_NAME
from dbo.partsupp, dbo.supplier where ...);
...
fetch next from c1 into @fetchedCost, @fetchedName;
if(@fetchedCost<@minCost) //<-- filter on top of loop body
begin
...
Logistics
Getting Started
This project is a component of an ongoing one, so the CFG and compilation framework already exist and we can reuse most of them. Neither the CFG nor the CFG-to-C++ backend is fully functional yet, and the schedule below accounts for finishing those prerequisites.
Implementing Aggify on the framework should also make the framework more general. The paper reports that Aggify speeds up UDFs with cursor loops by up to 1000x in SQL Server [1].
Schedule
From the week of Oct 30 to Dec 7.
| Week No. | Task |
|---|---|
| 1 | Haoyu: Fully read the existing codebase. Yuchen: Generate the CFG for PL/pgSQL. |
| 2 | Haoyu: Do Data Flow Analysis on the CFG. Yuchen: Generate code from CFG to C++. |
| 3 | Haoyu: Correctly manipulate the CFG based on Aggify. Yuchen: Generate correct code using vectorized custom aggregation API. |
| 4 | Haoyu & Yuchen: Benchmark on TPC-H workloads. |
| 5 | Haoyu: Work on DCE, LICM. Yuchen: Work on Query Motion. |
| 6 | Haoyu & Yuchen: Prepare presentation, poster and report. |
Milestone
The Nov 20 milestone covers everything through week 3: the whole pipeline should work under manual checking, without necessarily passing all the TPC-H test cases.
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.
[2] K. Ramachandra, K. Park, K. V. Emani, A. Halverson, C. Galindo-Legaria, and C. Cunningham, “Froid: optimization of imperative programs in a relational database,” Proc. VLDB Endow., vol. 11, no. 4, pp. 432–444, Dec. 2017, doi: 10.1145/3186728.3164140.
[3] D. Hirn and T. Grust, “One WITH RECURSIVE is Worth Many GOTOs,” in Proceedings of the 2021 International Conference on Management of Data, Virtual Event China: ACM, Jun. 2021, pp. 723–735. doi: 10.1145/3448016.3457272.
[4] M. Sichert and T. Neumann, “User-defined operators: efficiently integrating custom algorithms into modern databases,” Proc. VLDB Endow., vol. 15, no. 5, pp. 1119–1131, Jan. 2022, doi: 10.14778/3510397.3510408.