Scaling Package Queries to a Billion Tuples via Hierarchical Partitioning and Customized Optimization
Summary: Progressive Shading scales package-query ILP optimization to billions of tuples via hierarchical refinement, avoiding SketchRefine’s premature pruning under tight constraints. Dynamic Low Variance partitioning and custom Dual Reducer/Parallel Dual Simplex solvers deliver adaptive, orders-of-magnitude faster processing. (summarized by gpt-5.6-luna on Jul 24 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Anh L. Mai (New York University)
- 2. Pengyu Wang (New York University)
- 3. Azza Abouzied (New York University)
- 4. Matteo Brucato (Microsoft)
- 5. Peter J. Haas (University of Massachusetts Amherst)
- 6. Alexandra Meliou (University of Massachusetts Amherst)
BibTeX Citation
@article{mai_vldb24,
title = {{Scaling Package Queries to a Billion Tuples via Hierarchical Partitioning and Customized Optimization}},
author = {Mai, Anh L. and Wang, Pengyu and Abouzied, Azza and Brucato, Matteo and Haas, Peter J. and Meliou, Alexandra},
journal = {PVLDB},
series = {{VLDB} '24},
volume = {17},
number = {5},
pages = {1146--1158},
doi = {10.14778/3641204.3641222},
url = {https://doi.org/10.14778/3641204.3641222},
year = {2024}
}Incoming Citations (Sorted by Pagerank)
Showing 6 of 6 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,520 | Query Refinement for Diverse Top-k Selection | 2024 | SIGMOD | 5.7573717e-05 |
| 8,761 | Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation | 2025 | VLDB | 5.283642e-05 |
| 10,822 | Decisionhouse: Prescriptive Analytics in the Data Stack | 2026 | VLDB | 4.9793485e-05 |
| 11,302 | Stochastic SketchRefine: Scaling In-Database Decision-Making under Uncertainty to Millions of Tuples | 2025 | VLDB | 4.9793485e-05 |
| 11,515 | Counterfactual Explanation at Will, with Zero Privacy Leakage | 2024 | SIGMOD | 4.9793485e-05 |
| 13,592 | Dominance-Based Data Reduction for Package Queries | 2026 | VLDB | - |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,460 | Query Processing on Tensor Computation Runtimes | 2022 | VLDB | 8.4348335e-05 |
| 3,201 | Interactive Data Exploration Using Semantic Windows | 2014 | SIGMOD | 7.5428462e-05 |
| 3,279 | Searchlight: Enabling Integrated Search and Exploration over Large Multidimensional Data | 2015 | VLDB | 7.4620555e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 996 | Analyzing Plan Diagrams of Database Query Optimizers | 2005 | VLDB |
| 2 | 9,050 | Stochastic Package Queries in Probabilistic Databases | 2020 | SIGMOD |
| 3 | 1,186 | Adaptive Optimization of Very Large Join Queries | 2018 | SIGMOD |
| 4 | 1,036 | Fine-grained Partitioning for Aggressive Data Skipping | 2014 | SIGMOD |
| 5 | 4,069 | Dynamically Optimizing Queries over Large Scale Data Platforms | 2014 | SIGMOD |
| 6 | 8,651 | Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation | 2026 | VLDB |
| 7 | 13,592 | Dominance-Based Data Reduction for Package Queries | 2026 | VLDB |
| 8 | 9,621 | Parallelizing Query Optimization on Shared-Nothing Architectures | 2016 | VLDB |
| 9 | 11,302 | Stochastic SketchRefine: Scaling In-Database Decision-Making under Uncertainty to Millions of Tuples | 2025 | VLDB |
| 10 | 6,960 | Scalable Package Queries in Relational Database Systems | 2016 | VLDB |