Galley: Modern Query Optimization for Sparse Tensor Programs

Summary: Galley enables sparse-tensor programming, reducing manual optimization. First to cost-based lowering of sparse tensor algebra to the imperative language of sparse-tensor compilers, via a FAQ-based aggregation, compiling steps to engines and delivering speedups on ML-joins. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7289
Venue: SIGMOD
Year: 2025
Pagerank: 5.4119882e-05
Overall Rank: 8,513 | 41.60%
DOI: 10.1145/3725301

Incoming Non-self Citations Over Time

Authors

1. Kyle Deeds (University of Washington)
2. Willow Ahrens (Massachusetts Institute of Technology)
3. Magda Balazinska (University of Washington)
4. Dan Suciu (University of Washington)

BibTeX Citation

@inproceedings{deeds_sigmod25,
        title = {{Galley: Modern Query Optimization for Sparse Tensor Programs}},
        author = {Deeds, Kyle and Ahrens, Willow and Balazinska, Magda and Suciu, Dan},
        series = {{SIGMOD} '25},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3725301},
        url = {https://dl.acm.org/doi/10.1145/3725301},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,514	Automated Tensor-Relational Decomposition for Large-Scale Sparse Tensor Computation	2026	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 24 of 24 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0024089429
103	DuckDB: an Embeddable Analytical Database	2019	SIGMOD	0.00034161428
358	FAQ: Questions Asked Frequently	2016	PODS	0.00020243592
415	SystemML: Declarative Machine Learning on Spark	2016	VLDB	0.0001888524
422	Umbra: A Disk-Based System with In-Memory Performance	2020	CIDR	0.00018732744
536	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.0001693369
715	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00014655327
1,235	Towards Linear Algebra over Normalized Data	2017	VLDB	0.00011548457
1,237	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00011545768
1,499	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010564536
1,756	SystemDS: A Declarative Machine Learning System for the End-to-End Data Science Lifecycle	2020	CIDR	9.8172465e-05
2,823	Query Processing on Tensor Computation Runtimes	2022	VLDB	8.0893814e-05
2,865	End-to-end Optimization of Machine Learning Prediction Queries	2022	SIGMOD	8.0180243e-05
2,940	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	7.9381573e-05
3,070	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.7900444e-05
3,874	Tensors: An abstraction for general data processing	2021	VLDB	7.0561161e-05
3,959	Simplicity Done Right for Join Ordering	2021	CIDR	6.9879431e-05
4,253	Efficient and Portable Einstein Summation in SQL	2023	SIGMOD	6.8029311e-05
4,976	SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra	2020	VLDB	6.4168322e-05
5,195	Tensor Relational Algebra for Distributed Machine Learning System Design	2021	VLDB	6.3232105e-05
5,576	SafeBound: A Practical System for Generating Cardinality Bounds	2023	SIGMOD	6.1663946e-05
8,794	AWARE: Workload-aware, Redundancy-exploiting Linear Algebra	2023	SIGMOD	5.370464e-05
9,834	EinDecomp: Decomposition of Declaratively-Specified Machine Learning and Numerical Computations for Parallel Execution	2025	VLDB	5.2112879e-05
9,835	Share the Tensor Tea: How Databases can Leverage the Machine Learning Ecosystem	2022	VLDB	5.2112879e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	23	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB
2	11,453	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB
3	534	Building Efficient Query Engines in a High-Level Language	2014	VLDB
4	4,045	Logical and Physical Optimizations for SQL Query Execution over Large Language Models	2025	SIGMOD
5	10,409	TQEx: Tensor-based Query Engine Enhanced by Bridging the Gap	2026	SIGMOD
6	9,835	Share the Tensor Tea: How Databases can Leverage the Machine Learning Ecosystem	2022	VLDB
7	10,185	A Backend-Agnostic Compiler for Approximate Query Processing with Probabilistic Tensor Algebra	2026	SIGMOD
8	2,823	Query Processing on Tensor Computation Runtimes	2022	VLDB
9	6,938	Guided automated learning for query workload re-optimization	2019	VLDB
10	5,414	Optimizing Tensor Programs on Flexible Storage	2023	SIGMOD