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: 8365
Venue: VLDB
Year: 1996
Pagerank: 6.6584217e-05
Overall Rank: 3,893 | 72.92%
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
269	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029656549
273	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00029390945
325	The History of Histograms (abridged)	2003	VLDB	0.00027378328
1,334	SkewTune: Mitigating Skew in MapReduce Applications	2012	SIGMOD	0.0001250413
3,124	Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources	1997	VLDB	7.5201555e-05
5,627	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	5.403782e-05
6,619	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	4.9910152e-05
7,153	Submodularity of Distributed Join Computation	2018	SIGMOD	4.8153963e-05
9,507	Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects	2010	SIGMOD	4.3341665e-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
20	GAMMA - A High Performance Dataflow Database Machine	1986	VLDB	0.00086459551
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080435857
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
99	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050022914
116	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046148737
232	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00032122485
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
588	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00019604754
808	Universality of Serial Histograms	1993	VLDB	0.00016432772
861	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00015848554
1,232	Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC)	1990	VLDB	0.00013147188
1,365	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00012368421
3,899	Using Shared Virtual Memory for Parallel Join Processing	1993	SIGMOD	6.6538884e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,153	Submodularity of Distributed Join Computation	2018	SIGMOD	4.8153963e-05
2,417	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB	8.8604775e-05
550	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB	0.00020359891
1,695	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	0.00010882793
2,326	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB	9.0282969e-05
808	Universality of Serial Histograms	1993	VLDB	0.00016432772
4,214	Dynamic Multi-Resource Load Balancing in Parallel Database Systems	1995	VLDB	6.3541e-05
4,460	Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor	1991	VLDB	6.1635864e-05
588	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00019604754
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479