Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing

Summary: Optimal histograms for join-result size also estimate the result’s data distribution. Applied to load balancing in parallel Hybrid hash joins with a skew-aware cost model; Gamma simulations show superior, low-overhead performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8366
Venue: VLDB
Year: 1996
Pagerank: 6.6526869e-05
Overall Rank: 3,896 | 72.93%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Viswanath Poosala
2. Yannis E. Ioannidis

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
270	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029648047
275	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00029381206
325	The History of Histograms (abridged)	2003	VLDB	0.00027398081
1,339	SkewTune: Mitigating Skew in MapReduce Applications	2012	SIGMOD	0.00012492978
3,129	Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources	1997	VLDB	7.5132501e-05
5,636	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	5.3985928e-05
6,618	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	4.9864636e-05
7,154	Submodularity of Distributed Join Computation	2018	SIGMOD	4.8107765e-05
9,508	Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects	2010	SIGMOD	4.3300131e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
21	GAMMA - A High Performance Dataflow Database Machine	1986	VLDB	0.00086104592
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080571183
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
100	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050033475
114	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046317654
230	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00032145125
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
548	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00020369531
801	Universality of Serial Histograms	1993	VLDB	0.00016440976
852	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00015896035
1,219	Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC)	1990	VLDB	0.00013215689
1,355	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00012417228
3,901	Using Shared Virtual Memory for Parallel Join Processing	1993	SIGMOD	6.6481179e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,154	Submodularity of Distributed Join Computation	2018	SIGMOD	4.8107765e-05
2,416	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB	8.8520203e-05
549	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB	0.00020348047
1,691	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	0.00010890775
2,328	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB	9.024235e-05
801	Universality of Serial Histograms	1993	VLDB	0.00016440976
4,213	Dynamic Multi-Resource Load Balancing in Parallel Database Systems	1995	VLDB	6.3482542e-05
4,398	Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor	1991	VLDB	6.2137073e-05
548	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00020369531
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497