Труб И.И. Аналитическое вероятностное моделирование bitmap-индексов

Аннотация: Объектом исследования являются двоичные (bitmap)-индексы как средство повышения эффективности обработки поисковых запросов и построения отчетов в современных СУБД. Предметом исследования является математическая модель зависимости количества индексов, необходимых для построения выборки, удовлетворяющей запросу, от интенсивности добавления записей в базу данных и заданного диапазона значений запроса. Данная характеристика является наиболее значимой для оценки производительности обработки запроса, так как определяет количество операций дизъюнкции над битовыми строками, которое необходимо выполнить для получения результирующей выборки. Данная задача возникла целиком из практических потребностей ввиду критического влияния быстродействия построения отчетов на потребительскую ценность коммерческих продуктов - приложений СУБД. Методологией исследования является вероятностное аналитическое моделирование на основе представления исходных данных в виде пуассоновских процессов, а также использование аппарата математического анализа (интегральное исчисление и суммирование рядов) для получения конечных результатов. Новизна исследования заключается в разработке математической модели, предложенной для данного объекта исследования, которая позволяет ставить широкий спектр задач анализа и оптимизации. Поставленная задача решена - получены формулы для распределения количества индексов и среднего количества индексов в одном запросе. Для каждого результата проведена оценка его достоверности на основе альтернативного подхода или правдоподобных рассуждений. Поставлены задачи построения вероятностной модели для распределений произвольного вида и оптимизации обработки запросов с помощью иерархических bitmap-индексов. Следует отметить, что сформулированная в работе задача и полученные результаты имеют и самостоятельное теоретическое значение в рамках теории массового обслуживания безотносительно к прикладной области.

Ключевые слова:

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: