Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems

Summary: Skew-aware automatic partitioning for shared-nothing OLTP; addresses data and access skew, stored-procedure routing, and replicated secondary indexes. Analytical cost model plus large-neighborhood search minimize distributed transactions and scale with schema and data, yielding up to 16x throughput. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h2c8dd21a77923a2c
Venue: SIGMOD
Year: 2012
Pagerank: 0.00017684278
Overall Rank: 473 | 96.83%
DOI: 10.1145/2213836.2213844

Incoming Non-self Citations Over Time

Authors

1. Andrew Pavlo (Brown University)
2. Carlo Curino (Yahoo)
3. Stan Zdonik (Brown University)

BibTeX Citation

@inproceedings{pavlo_sigmod12,
        title = {{Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems}},
        author = {Pavlo, Andrew and Curino, Carlo and Zdonik, Stan},
        series = {{SIGMOD} '12},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2213836.2213844},
        url = {https://dl.acm.org/doi/10.1145/2213836.2213844},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 71 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
444	Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores	2015	VLDB	0.0001817002
729	Anti-Caching: A New Approach to Database Management System Architecture	2013	VLDB	0.00014417679
779	To Join or Not to Join? Thinking Twice about Joins before Feature Selection	2016	SIGMOD	0.00014048128
864	Let’s Talk About Storage & Recovery Methods for Non-Volatile Memory Database Systems	2015	SIGMOD	0.00013388481
891	E-Store: Fine-Grained Elastic Partitioning for Distributed Transaction Processing Systems	2015	VLDB	0.00013241227
945	The End of Slow Networks: It's Time for a Redesign	2016	VLDB	0.00012933247
1,128	Qd-tree: Learning Data Layouts for Big Data Analytics	2020	SIGMOD	0.00011901941
1,289	An Inquiry into Machine Learning-based Automatic Configuration Tuning Services on Real-World Database Management Systems	2021	VLDB	0.00011159167
1,339	The End of a Myth: Distributed Transactions Can Scale	2017	VLDB	0.0001097043
1,939	S-Store: Streaming Meets Transaction Processing	2015	VLDB	9.3299482e-05
1,945	An Evaluation of Distributed Concurrency Control	2017	VLDB	9.3239199e-05
1,948	Scalable Atomic Visibility with RAMP Transactions	2014	SIGMOD	9.3202419e-05
2,279	Design Principles for Scaling Multi-core OLTP Under High Contention	2016	SIGMOD	8.7047643e-05
2,290	Clay: Fine-Grained Adaptive Partitioning for General Database Schemas	2017	VLDB	8.6873304e-05
2,337	Towards a Non-2PC Transaction Management in Distributed Database Systems	2016	SIGMOD	8.6180776e-05
2,425	Squall: Fine-Grained Live Reconfiguration for Partitioned Main Memory Databases	2015	SIGMOD	8.4820179e-05
2,476	Learning a Partitioning Advisor for Cloud Databases	2020	SIGMOD	8.407183e-05
2,765	Instance-Optimized Data Layouts for Cloud Analytics Workloads	2021	SIGMOD	8.0401855e-05
2,880	Optimal Column Layout for Hybrid Workloads	2019	VLDB	7.9118308e-05
3,048	Handling Highly Contended OLTP Workloads Using Fast Dynamic Partitioning	2020	SIGMOD	7.7087933e-05
3,061	Accordion: Elastic Scalability for Database Systems Supporting Distributed Transactions	2014	VLDB	7.6928177e-05
3,128	How to Win a Hot Dog Eating Contest: Distributed Incremental View Maintenance with Batch Updates	2016	SIGMOD	7.611678e-05
3,160	S-Store: A Streaming NewSQL System for Big Velocity Applications	2014	VLDB	7.5773134e-05
3,216	SharPer: Sharding Permissioned Blockchains Over Network Clusters	2021	SIGMOD	7.5232261e-05
3,241	Locality-aware Partitioning in Parallel Database Systems	2015	SIGMOD	7.4972383e-05
3,588	Make Your Database System Dream of Electric Sheep: Towards Self-Driving Operation	2021	VLDB	7.1841858e-05
3,724	Sundial: Harmonizing Concurrency Control and Caching in a Distributed OLTP Database Management System	2018	VLDB	7.0679706e-05
3,751	MaaT: Effective and scalable coordination of distributed transactions in the cloud	2014	VLDB	7.0495774e-05
3,898	Analyzing the Impact of System Architecture on the Scalability of OLTP Engines for High-Contention Workloads	2018	VLDB	6.9331677e-05
4,067	Transaction Healing: Scaling Optimistic Concurrency Control on Multicores	2016	SIGMOD	6.8196985e-05
4,146	Parallel Analytics as a Service	2013	SIGMOD	6.7774377e-05
4,198	Proteus: A Self-Designing Range Filter	2022	SIGMOD	6.7385809e-05
4,534	AdaptDB: Adaptive Partitioning for Distributed Joins	2017	VLDB	6.5535468e-05
4,822	Epoch-based Commit and Replication in Distributed OLTP Databases	2021	VLDB	6.3931726e-05
4,896	TrillionG: A Trillion-scale Synthetic Graph Generator using a Recursive Vector Model	2017	SIGMOD	6.3640267e-05
5,186	PolarDB-MP: A Multi-Primary Cloud-Native Database via Disaggregated Shared Memory	2024	SIGMOD	6.2357787e-05
5,213	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.222614e-05
5,320	Chiller: Contention-centric Transaction Execution and Data Partitioning for Modern Networks	2020	SIGMOD	6.1813707e-05
5,368	Taurus MM: bringing multi-master to the cloud	2023	VLDB	6.1578957e-05
5,529	AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data	2015	VLDB	6.0908508e-05
5,547	JECB: a Join-Extension, Code-Based Approach to OLTP Data Partitioning	2014	SIGMOD	6.0857802e-05
6,274	Is Scalable OLTP in the Cloud a Solved Problem? Analyzing Data Access for Distributed OLTP Architectures	2023	CIDR	5.8256214e-05
6,280	Fast and Effective Distribution-Key Recommendation for Amazon Redshift	2020	VLDB	5.8239136e-05
6,748	Don’t Look Back, Look into the Future: Prescient Data Partitioning and Migration for Deterministic Database Systems	2021	SIGMOD	5.6882313e-05
6,967	Incremental Elasticity For Array Databases	2014	SIGMOD	5.6301184e-05
6,971	Jigsaw: A Data Storage and Query Processing Engine for Irregular Table Partitioning	2021	SIGMOD	5.628441e-05
7,005	Towards Optimal Transaction Scheduling	2024	VLDB	5.6218081e-05
7,157	Adaptive Hybrid Indexes	2022	SIGMOD	5.595284e-05
7,182	MgCrab: Transaction Crabbing for Live Migration in Deterministic Database Systems	2019	VLDB	5.5903567e-05
7,283	Transaction Scheduling: From Conflicts to Runtime Conflicts	2023	SIGMOD	5.5645493e-05

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
70	The End of an Architectural Era (It’s Time for a Complete Rewrite)	2007	VLDB	0.00037851432
80	H-Store: A High-Performance, Distributed Main Memory Transaction Processing System	2008	VLDB	0.00036354352
88	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00035340164
123	Schism: a Workload-Driven Approach to Database Replication and Partitioning	2010	VLDB	0.00030749898
151	An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server	1997	VLDB	0.00028664776
157	OLTP Through the Looking Glass, and What We Found There	2008	SIGMOD	0.00028316479
187	DB2 Design Advisor: Integrated Automatic Physical Database Design	2004	VLDB	0.00025914764
192	Data Placement In Bubba	1988	SIGMOD	0.00025689465
195	Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design	2004	SIGMOD	0.00025619089
243	Automating Physical Database Design in a Parallel Database	2002	SIGMOD	0.00023349603
322	Tuning Database Configuration Parameters with iTuned	2009	VLDB	0.00021034201
378	AutoAdmin "What-if" Index Analysis Utility	1998	SIGMOD	0.00019541534
797	Low Overhead Concurrency Control for Partitioned Main Memory Databases	2010	SIGMOD	0.00013916653
833	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00013577649
1,041	Generic Database Cost Models for Hierarchical Memory Systems	2002	VLDB	0.00012354465
1,244	Compressing SQL Workloads	2002	SIGMOD	0.00011369155
1,332	Fast Updates on Read-Optimized Databases Using Multi-Core CPUs	2012	VLDB	0.00010993664
1,842	On Predictive Modeling for Optimizing Transaction Execution in Parallel OLTP Systems	2012	VLDB	9.5247433e-05
1,884	Automated Partitioning Design in Parallel Database Systems	2011	SIGMOD	9.4349703e-05
2,651	A Performance Analysis of Alternative Multi-Attribute Declustering Strategies	1992	SIGMOD	8.1699714e-05
7,947	A Non-Uniform Data Fragmentation Strategy for Parallel Main-Memory Database Systems	1995	VLDB	5.4190982e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,971	Resource Bricolage for Parallel Database Systems	2015	VLDB
2	6,559	Optimal Splitters for Temporal and Multi-version Databases	2013	SIGMOD
3	797	Low Overhead Concurrency Control for Partitioned Main Memory Databases	2010	SIGMOD
4	1,671	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD
5	1,256	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB
6	3,241	Locality-aware Partitioning in Parallel Database Systems	2015	SIGMOD
7	1,583	On the Design and Scalability of Distributed Shared-Data Databases	2015	SIGMOD
8	243	Automating Physical Database Design in a Parallel Database	2002	SIGMOD
9	1,884	Automated Partitioning Design in Parallel Database Systems	2011	SIGMOD
10	7,712	Query Centric Partitioning and Allocation for Partially Replicated Database Systems	2017	SIGMOD