Trub I.I. Analytical probabilistic modeling of bitmap-indexes

Abstract: The study is devoted to bitmap-indexes as a tool of improving efficiency of processing search queries and reporting in the current database. The subject of research is mathematical model of dependence of the number of indexes, required to build a sample that meets the request, on the intensity of adding records to the database and query the specified range of values. This characteristic is most significant for evaluating query processing performance because it determines the number of disjunction operations on bit strings, required to get a result set. This problem arose entirely from the practical needs due to the critical impact of the speed of building of reports on customer value commercial products - database applications. The methodology of this study is probabilistic analytical modeling based on representations of the original data in the form of Poisson process and the use of the apparatus of mathematical analysis (integral calculus and summation rows) to get the final results. The novelty of the research is to develop a suggested mathematical model, which allows to put a wide range of problems of the analysis and optimization. The problem is solved – the author presents the formula for the distribution of the number of indexes, and the average number of indexes in a single query. For each result author evaluated reliability on the basis of an alternative approach or plausible reasoning. The paper sets the tasks of constructing a probabilistic model for the distribution of any type of query processing and optimization using hierarchical bitmap-indexes. It should be noted, that formulated problem and the results obtained have an independent theoretical value within the queuing theory without regard to the application area.

Keywords: