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: 8556
Venue: VLDB
Year: 1996
Pagerank: 7.04191e-05
Overall Rank: 3,893 | 73.30%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Viswanath Poosala (University of Wisconsin)
2. Yannis E. Ioannidis (University of Wisconsin)

BibTeX Citation

@article{poosala_vldb96,
        title = {{Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing}},
        author = {Poosala, Viswanath and Ioannidis, Yannis E.},
        journal = {PVLDB},
        series = {{VLDB} '96},
        pages = {448--459},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
213	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024723025
235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023783792
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
1,319	SkewTune: Mitigating Skew in MapReduce Applications	2012	SIGMOD	0.00011175005
3,046	Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources	1997	VLDB	7.8159925e-05
5,184	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	6.3283918e-05
6,596	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.828647e-05
7,111	Submodularity of Distributed Join Computation	2018	SIGMOD	5.69924e-05
9,642	Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects	2010	SIGMOD	5.2434488e-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
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00048351457
52	GAMMA - A High Performance Dataflow Database Machine	1986	VLDB	0.00041107291
89	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00035031529
118	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00031922279
242	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023604323
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
481	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017780716
786	Universality of Serial Histograms	1993	VLDB	0.00014053885
811	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00013859761
1,188	Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC)	1990	VLDB	0.00011756444
1,236	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00011548179
3,863	Using Shared Virtual Memory for Parallel Join Processing	1993	SIGMOD	7.0649349e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,111	Submodularity of Distributed Join Computation	2018	SIGMOD
2	2,846	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB
3	844	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB
4	1,729	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB
5	2,230	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB
6	786	Universality of Serial Histograms	1993	VLDB
7	4,241	Dynamic Multi-Resource Load Balancing in Parallel Database Systems	1995	VLDB
8	4,668	Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor	1991	VLDB
9	481	Practical Skew Handling in Parallel Joins	1992	VLDB
10	274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD