2005 · 46 citations · 17 references
ComputingComputer ScienceAlgorithmsData StructuresDatabasesNearest Neighbor SearchQuery OptimizationQuery ProcessingSearching AlgorithmsBitmap IndexingCost-based Query OptimizationIndex DesignIndex OptimizationIndex-aware Query ProcessingIndex-based Query ProcessingQuery EvaluationQuery Performance Optimization
In this paper, we propose a new strategy for optimizing the placement of bin boundaries to minimize the cost of query evaluation using bitmap indices with binning. For attributes with a large number of distinct values, often the most efficient index scheme is a bitmap index with binning. However, this type of index may not be able to fully resolve some user queries. To fully resolve these queries, one has to access parts of the original data to check whether certain candidate records actually satisfy the specified conditions. We call this procedure the candidate check, which usually dominates the total query processing time. Given a set of user queries, we seek to minimize the total time required to an-swer the queries by optimally placing the bin boundaries. We show that our dynamic programming based algorithm can efficiently determine the bin boundaries. We verify our analysis with some real user queries from the Sloan Digital Sky Survey. For queries that require significant amount of time to perform candidate check, using our optimal bin boundaries reduces the candidate check time by a factor of 2 and the total query processing time by 40%.
17
Improved query performance with variant indexes
Patrick E. O׳Neil, Dallan Quass · 1997 · 484 citations
Nuclear Instruments and Methods in Physics Research A
L. Castillo García · 2012 · 257 citations
Engineering, Electrical Engineering, Nuclear Engineering +15
Designing and mining multi-terabyte astronomy archives
Alexander S. Szalay, Peter Kunszt, Ani Thakar et al. · ACM SIGMOD Record · 2000 · 188 citations
Byte-aligned bitmap compression
Gennady Antoshenkov · 2002 · 173 citations