摘要：Selectivity estimation is crucial for query optimizers choosing an optimal spatial execution plan in a spatial database management system. This paper presents an Annular Bucket spatial histogram (AB histogram) that can estimate the selectivity in finer spatial selection and spatial join operations even when the spatial query has more operators or more joins. The AB histogram is represented as a set of bucket-range, bucket-count value pairs. The bucket-range often covers an annular region like a single-cell-sized photo frame. The bucket-count is the number of objects whose Minimum Bounding Rectangles (MBRs) fall between outer rectangle and inner rectangle of the bucket-range. Assuming that all MBRs in each a bucket distribute evenly, for every bucket, we can obtain serial probabilities that satisfy a certain spatial selection or join conditions from the operations’ semantics and the spatial relations between every bucket-range and query ranges. Thus, according to some probability theories, spatial selection or join selectivity can be estimated by the every bucket-count and its probabilities. This paper also shows a way to generate an updated AB histogram from an original AB histogram and those probabilities. Our tests show that the AB histogram not only supports the selectivity estimation of spatial selection or spatial join with “disjoint”, “intersect”, “within”, “contains”, and “overlap” operators but also provides an approach to generate a reliable updated histogram whose spatial distribution is close to the distribution of actual query result.
关键词：selectivity estimation; AB histogram; annular bucket; spatial selection; spatial join
