Fast and Effective Distribution-Key Recommendation for Amazon Redshift

Summary: Proposes Distribution-Key Recommendation for Redshift, modeling workloads with a Join Multi-Graph to minimize inter-node network cost of joins. Shows NP-hardness; BaW hybridizes heuristics and exact search to yield near-optimal keys, with up to 32x network-cost reduction on real/synthetic workloads. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12126
Venue: VLDB
Year: 2020
Pagerank: 4.9710856e-05
Overall Rank: 6,659 | 53.68%
DOI: 10.14778/3407790.3407834

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,284	Amazon Redshift Re-invented	2022	SIGMOD	0.00012837822
4,152	openGauss: An Autonomous Database System	2021	VLDB	6.4060406e-05
5,407	Remus: Efficient Live Migration for Distributed Databases with Snapshot Isolation	2022	SIGMOD	5.5242392e-05
8,103	Grep: A Graph Learning Based Database Partitioning System	2023	SIGMOD	4.5852201e-05
8,225	Automated Multidimensional Data Layouts in Amazon Redshift	2024	SIGMOD	4.555289e-05
9,203	Intelligent Automated Workload Analysis for Database Replatforming	2022	SIGMOD	4.3740313e-05
10,111	Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1945683e-05
10,230	Breaking the Isolation-Freshness Trade-off: Joint Adaptive Storage Optimization for HTAP Systems	2026	VLDB	4.1945683e-05
10,496	Physical Visualization Design: Decoupling Interface and System Design	2025	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
209	Schism: a Workload-Driven Approach to Database Replication and Partitioning	2010	VLDB	0.00034468292
285	Automating Physical Database Design in a Parallel Database	2002	SIGMOD	0.0002899128
286	Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design	2004	SIGMOD	0.00028990057
426	Amazon Redshift and the Case for Simpler Data Warehouses	2015	SIGMOD	0.00023594359
659	The Making of TPC-DS	2006	VLDB	0.00018500853
679	Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems	2012	SIGMOD	0.00018215154
773	Multi-Dimensional Database Allocation for Parallel Data Warehouses	2000	VLDB	0.00016870159
932	Database Partitioning In A Cluster Of Processors	1983	VLDB	0.00015236447
2,413	Automated Partitioning Design in Parallel Database Systems	2011	SIGMOD	8.8672223e-05
2,983	Supporting Table Partitioning By Reference in Oracle	2008	SIGMOD	7.7796493e-05
3,821	Locality-aware Partitioning in Parallel Database Systems	2015	SIGMOD	6.7281515e-05
7,337	Unified Spatial Analytics from Heterogeneous Sources with Amazon Redshift	2020	SIGMOD	4.7584825e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,132	Advanced Join Strategies for Large-Scale Distributed Computation	2014	VLDB	6.4241067e-05
3,434	Efficient Bulk Insertion into a Distributed Ordered Table	2008	SIGMOD	7.0994919e-05
2,413	Automated Partitioning Design in Parallel Database Systems	2011	SIGMOD	8.8672223e-05
9,908	Keep Your Distributed Data Warehouse Consistent at a Minimal Cost	2023	SIGMOD	4.2576943e-05
11,890	Let's Rethink Join Optimization in Distributed Systems	2015	CIDR	4.1945683e-05
6,694	Optimal Splitters for Temporal and Multi-version Databases	2013	SIGMOD	4.9586454e-05
7,715	Query Centric Partitioning and Allocation for Partially Replicated Database Systems	2017	SIGMOD	4.6699261e-05
3,821	Locality-aware Partitioning in Parallel Database Systems	2015	SIGMOD	6.7281515e-05
7,153	Submodularity of Distributed Join Computation	2018	SIGMOD	4.8153963e-05
6,619	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	4.9910152e-05