Justification of the quasi-optimum distribution of elementary queries in multiprocessor database

Аuthors

Brekhov O. M.^1*, Than H. M.^2**

1. Moscow Aviation Institute (National Research University), 4, Volokolamskoe shosse, Moscow, А-80, GSP-3, 125993, Russia
2. Defence services academy, Pyin OO Lwin, Republic of the Union of Myanmar

*e-mail: obrekhov@mail.ru
**e-mail: hlaing82@gmail.com

Abstract

Criterion for the distribution of elementary queries to processors naturally defined as receiving a minimum processing time of queries when all the processors would have completed its work at the same time , while , of course, necessary to keep the order of processing of elementary queries on each processor in accordance with the terms of [1,2].
We can apply the natural distribution of elementary queries to processors in accordance with the rule, when the i-th (i = 1 , ..., r) processor receives elementary queries with numbers i, r + i, 2r + i, 3r + i, 4r + i, 5r + i, 6r + i, ...
In [3] we proposed quasi-optimal distribution method , when the i-th (i = 1 , ..., r) processor receives elementary queries with numbers i, 2r +1 — i, 2r + i, 4r +1 — i, 4r + i, 6r +1 — i, 6r + i, ...
This article provides an evaluation of the effectiveness of quasi-optimal distribution method in a multiprocessor database.
We have received query execution time in a multiprocessor database for natural and quasi-optimal order of their distribution; minimum and maximum limits of time for performing queries in separate processors for natural and quasi-optimal order of distribution of elementary queries; proof of the effectiveness of the quasi-optimal distribution based on the absolute and relative decrease queries execution borders using the quasi-optimal instead of a natural distribution.
We have received a number of numerical results for execution time of the query consisting of a conjunction of elementary queries. These results confirmed the effectiveness of the quasi- optimal distribution.

Keywords:

database, multiprocessor computer, queries, distribution of elementary queries, optimization

References

1. Amol Deshpande, Zacchary Ives, Vijayshankar Raman Adaptive Query Processing. Foundations and Trends in Databases, 2007, vol. 1, no. 1, pp.1-140.
2. Brekhov O.M. Uspekhi sovremennoi radioelektroniki, 2012, vol. 12, no. 7, pp. 37-45.
3. Brekhov O.M., Myo Thant Vestnik Moskovskogo aviatsionnogo instituta, 2012, vol. 19, no. 5, pp. 138-146.

Download