STHoles: A Multidimensional Workload-Aware Histogram Nicolas Bruno* Columbia University Luis Gravano* Columbia University Surajit Chaudhuri Microsoft Research.

  • Published on

  • View

  • Download


Slide 1STHoles: A Multidimensional Workload-Aware Histogram Nicolas Bruno* Columbia University Luis Gravano* Columbia University Surajit Chaudhuri Microsoft Research SIGMOD 2001 * Work done in part while the authors were visiting Microsoft Research. Slide 2 2 Histograms as Succinct Data Set Summaries n Used for selectivity estimation and approximate query processing. n Data set partitioned into buckets, each approximated by aggregate statistics. Slide 3 3 Histograms n Each bucket consists of a bounding box and a tuple frequency value. n Uniformity is assumed inside buckets. Histograms should partition data set in buckets with uniform tuple density. n Multi-dimensional data makes partitioning even more challenging. Slide 4 4 Outline n Overview of existing multidimensional histogram techniques. n Introduction to STHoles histograms. n System architecture and STHoles construction algorithm. n Experimental evaluation. Slide 5 5 Gaussian Data Set Histograms Techniques: EquiDepth EquiDepth Histogram [Muralikrishna and DeWitt 1988] n Correctly identifies core of densest clusters. n Partitioning uses equi-count instead of equi- density Slide 6 6 Gaussian Data SetMHist Histogram [Poosala and Ioannidis 1997] Histogram Techniques: MHist n Works well for highly skewed data distributions. n Devotes too many buckets to the densest clusters. n Bad initial choices are amplified in later steps. Slide 7 7 Gaussian Data Set GenHist Histogram [Gunopulos et al. 2000] Histogram Techniques: GenHist n More robust than previous techniques (based on multidimensional information). n Difficult to choose right values of various parameters. n Requires at least 5-10 passes over the data. Slide 8 8 Gaussian Data SetSTGrid Histogram [Aboulnaga and Chaudhuri 1999] Histogram Techniques: STGrid n Incorporates feedback from query execution. n Grid partitioning strategy is sometimes too rigid. n Focuses on efficiency rather than accuracy. Slide 9 9 Our New Histogram Technique: STHoles n Flexible bucket partitioning. n Exploits workload information to allocate buckets. n Query feedback captures uniformly dense regions. n Does not examine actual data set. Slide 10 10 STHoles Histograms n Tree structure among buckets. n Buckets with holes: relaxes rectangular regions while using rectangular bucket structures. Non rectangular region Slide 11 11 System Architecture for STHoles Range Query Slide 12 12 STHoles Construction Algorithm n Initialize histogram H as an empty histogram. n For each query q in workload: 1- Gather simple statistics from query results. 2- Identify candidate holes and drill (add) them as new buckets in H. 3- Merge superfluous buckets in H. Slide 13 13 ? Drilling New Candidate Buckets Count how many tuples in result stream lie inside q b. n Drill q b as a new bucket (child of b). q For each query q in workload and bucket b in histogram: Slide 14 14 Shrinking Candidate Buckets n Partition constraint: Bounding boxes must be rectangular. n Apply greedy technique to shrink a candidate hole to a rectangle. Slide 15 15 Merging Buckets n To avoid exceeding available space. n Merge most similar buckets in terms of tuple density. Slide 16 16 Parent-Child Merges Eliminate buckets too similar to their parents. Example: The interesting region in bc is covered by its child b1. Slide 17 17 Sibling-Sibling Merges n Consolidate buckets with similar densities that cover close regions. n Extrapolate frequency distributions to yet unseen regions. Slide 18 18 Gaussian Data SetSTHoles Histogram An Example STHoles Histogram Slide 19 19 Experimental Setting n Data Sets: Real: (UCI Repository) Sample of Census data set (200K tuples) Cover data set (500K tuples) Synthetic: Variations of Gaussian and Zipfian(Array) distributions. 200K to 500K tuples, 2 to 4 dimensions. n Histograms: 1024 available bytes per histogram. EquiDept, MHist, GenHist, STGrid, STHoles. Slide 20 20 Experimental Setting (cont.) n Workloads [Pagel et al. 1993]: 1,000 queries. Query centers follow different distributions: Uniform, Biased, Gaussian. Query boundaries follow different constraints: area covered, tuples covered. Census data setBiased (tuples) workloadGaussian (area) workload n Accuracy Metric: Absolute Error. (with some normalization; details in paper) Slide 21 21 Comparison with Other Approaches: Biased Workload Biased workload, query boundaries cover around 1% of the data domain Slide 22 22 Comparison with Other Approaches: Uniform Workload Uniform workload, query boundaries cover around 1% of the data set tuples. Slide 23 23 Convergence with Workload Biased workload Slide 24 24 Handling Data Set Updates From Gaussian to Zipfian data distributions. Slide 25 25 Other Experiments n Varying: data skew. data dimensionality. histogram size. workload generation parameters. number of attributes in queries. n Overhead for intercepting query results in Microsoft SQL Server 2000 is less than 8%. n STHoles lead to robust selectivity estimates across data distributions and workloads. n See full paper for details! Slide 26 26 Summary: STHoles, a Multidimensional Workload-Aware Histogram n Exploits query feedback. n Built without examining data set. n Allows bucket nesting to capture complex shapes using only rectangular bucket structures. n Results in robust and accurate selectivity estimations. n In many cases, outperforms the best techniques that access full data sets. Slide 27 27 Related Work (Histograms) n Unidimensional: EquiDepth [Piatetsky-Shapiro and Connell 1984] MaxDiff [Poosala et al. 1996] V-Optimal [Jagadish et al. 1998] Many more! n Multidimensional: EquiDepth [Muralikrishna and DeWitt 1988] MHist [Poosala and Ioannidis 1997] GenHist [Gunopulos et al. 2000] STGrid [Aboulnaga and Chaudhuri 1999] Slide 28 28 Related Work (Other Techniques) n Sampling [Olken and Rotem 1990] n Wavelets [Matias et al. 1997] n Discrete transformations [Lee et al. 1999] n Parametric Curve Fitting [Chen and Roussopoulos 1994] Slide 29 29 Evaluation Metric n Absolute Error: n Normalized Absolute Error: Slide 30 30 Overhead Evaluation over Microsoft SQL Server 2000 Slide 31 31 Varying Histogram Size Gaussian Data Set Zipfian Data Set Census Data Set Slide 32 32 Varying Spatial Selectivity Gaussian Data Set Zipfian Data Set Census Data Set


View more >