Generic cumulative annular bucket histogram for spatial selectivity estimation of spatial database management system

Abstract

Selectivity estimation is crucial to query optimizers in choosing an optimal execution plan in a given spatial query, and there has been a great deal of focus on how to achieve good selectivity estimation for finer spatial selection operators. Equally crucial to this is understanding how to produce an updated spatial histogram. With this in mind, we used a cumulative annular bucket histogram (AB histogram), which not only accurately estimates the selectivity of a spatial selection or a spatial join operation with finer operators but also provides an updated spatial histogram to estimate the selectivity of subsequent spatial operations in a multi-level spatial query plan. A basic unit of AB histogram stores the number of minimum bounding rectangles whose lower left points and upper right points are located in specific rectangular regions. According to the basic units of a cumulative AB histogram, we can find out the selectivity of a spatial selection with a number of different finer operators. When it comes to spatial join operations, a relationship between two cumulative AB histograms can be translated into a relationship between one histogram and numerous query windows from the other histogram. Furthermore, an updated cumulative AB histogram can be simultaneously built into the process of selectivity calculation, making it possible to achieve both selectivity and an updated histogram of spatial join; its implementation made in the optimizer facility (OPF) of INGRES9.2. To highlight the performance of a cumulative AB histogram, several experiments have been conducted, with results showing that the cumulative AB histogram not only supports the selectivity estimation of spatial selection and spatial join with ‘Disjoint’, ‘Intersect’, ‘Within’, ‘Contains’, ‘Crosses’ and ‘Overlap’ operators but also supports the generation of an updated histogram. This indicates that Ingres would do better to find a query plan with low-execution costs.

Keywords:

• selectivity estimation
• cumulative AB histogram
• annular bucket
• spatial selection
• spatial join

Acknowledgements

This research is supported by the project of NSFC under grant No. 41130747. Its support is gratefully acknowledged. Thanks to Yanlu Zhu and Xun Yan for their searching and translating work about some related literatures.