Minimization of data base query's conditions: evoluation of efficiency
Abstract
This paper describes enhanced algorisms of query lexical optimization. These algorisms detect and remove redundant conditions from query restriction to simplify it. The paper also presents results of implementation of these optimization techniques and those effects on query processing speed.
About the Authors
N. A. Mendkovich
OOO «FREEnet Group»
Russian Federation
Russian Federation
S. D. Kuznetsov
ISP RAS, Moscow
Russian Federation
Russian Federation
References
1. Jarke M., Koch J. Query Optimization in Database Systems. ACM Computing Surveys (CSUR), 1984. March, Volume 16, Issue 2. Pp. 111-152.
2. Mannino M. V., Chu P., Sager T. Statistical profile estimation in database systems. ACM Computing Surveys, Volume 20, Issue 3. September 1988.
3. Ionnidis Y. E. Query Optimization. The Computer Science and Engineering Handbook. Boca Raton, CRC Press, 1996.
4. Chaudhari S. An Overview of Query Optimization in Relational Systems. Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, 1998.
5. Kuznetsov S. D. Metody optimizacii vypolnenija zaprosov v reljacionnyh SUBD [Query optimization techniques for relational DBMSs]. [http://www.citforum.ru/database/articles/art_26.shtml] (in Russian).
6. Chaudhuri S., Shim K. Including Group-By in Query Optimization. Proceedings of the 20th International Conference on Very Large Data Bases, Morgan Kaufmann, San Mateo, USA, 1994. San Francisco: Morgan Kaufmann Publishers Inc., 1994. Pp. 354-366.
7. Khaitan P., Satish K. M., Korra S. B., Jena S. K. Improved query plans for unnesting nested SQL queries. Proceedings of 2nd International Conference on Computer Science and its Applications, December 10-12, South Korea, 2009. Jeju Island: IEEE, 2009. Pp. 147-152.
8. Muralikrishna M. Improved unnesting algorithms for join aggregate SQL queries. Proceedings of the 18th International Conference on Very Large Data Bases, August 23-27, Vancouver, Canada, 1992. San Francisco: Morgan Kaufmann Publishers Inc., 1992. Pp. 91-102.
9. Sippu S., Soisalon-Soininen E. An Analysis of Magic Sets and Related Optimization Strategies for Logic Queries. Journal of the ACM, Volume 43, № 6, November 1996.
10. Mendkovich N. A., Kuznetsov S. D. Obzor razvitija metodov leksicheskoj optimizacii zaprosov [An Overwiew of Evolution of Lexical Query Optimization Techniques]. Trudy Instituta sistemnogo programmirovanija, t. 23, M., ISP RAN, 2012. Ss. 204-207 (in Russian).
11. 2.1.2 How MySQL Optimizes WHERE Clauses [http://dev.mysql.com/doc/refman/5.5/en/where-optimizations.html.
12. MySQL 5.5 Reference Manual. Chapter 7. Optimization. http://dev.mysql.com/doc/refman/5.5/en/optimization.html.
13. Paket PostgreSQL 8.3.3. Adres fajla postgresql-8.3.3\src\backend\optimizer\util\predtest.c.
14. Query Optimization in Oracle Database 10g Release 2. An Oracle White Paper, June 2005. Redwood Shores, Oracle Corporation, 2005.
15. Mendkovich N., Kuznetcov S. New Algorithms for Lexical Query Optimization. Proceedings of the 31st International Conference on Information Technology Interfaces. Cavtat/Dubrovnik, Croatia, June 22-25, 2009. Zagreb: University of Zagreb, 2009. Pp. 187-192.
16. Kuznetsov S. D., Mendkovich N. A. Novye algoritmy leksicheskoj optimizacii zaprosov New [Algorithms for Lexical Query Optimization]. Modeli i analiz informacionnyh sistem, 2009. T. 16, № 4. S. 22-33 (in Russian).
17. Mendkovich N. A., Kuznetsov S. D. Optimizacija kon#junktov uslovij v sostave zaprosov [Optimization of query condition’ conjucts]. Modeli i analiz informacionnyh sistem, 2011. T. 18, № 3. S. 144-154 (in Russian).
18. Hall P. A. V. Optimization of single expressions in a relational data base system. IBM Journal of Research and Development, 1976. Volume 20, Number 3.
19. Bellamkonda S., Ahmed R., Witkowski A., Amor A., Zait M., Lin Ch.-Ch. Enhanced Subquery Optimizations in Oracle /. Proceedings of the 35th international conference on Very large data base, August 2009. Volume 2 Issue 2. P. 1368.
20. Veitch E. W. A Chart Method for Simplifying Truth Functions. ACM Annual Conference/Annual Meeting: Proceedings of the 1952 ACM Annual Meeting, Pittsburg: ACM, NY, 1952.
21. Karnaugh M. The Map Method for Synthesis of Combinational Logic Circuits. Transactions of the American Institute of Electrical Engineers. Part I, № 72 (9), November 1953.
22. Quin W. V. O cores and prime implicants of truth functions. American Mathematics Monthly. 1959. V. 66. №9.
23. McCluskey E. J. Minimization of Boolean Functions. The Bell System Technical Journal. November 1956. V. 35, Issue 5.
24. Wu M. C. Query Optimization for Selecting Using Bitmaps. ACM SIGMOD Record Volume 28 Issue 2, June 1999. P. 234.
25. Tarasenko P. F., Buharova M. F. Tehnologija «The Reporter» dlja postroenija otchetov po bazam dannyh. Vestnik Tomskogo Gosudarstvennogo Universiteta, № 275, aprel' 2002 (in Russian).
26. Sarma A., Theobald M., Widom J. Exploiting Lineage for Confidence Computation in Uncertain and Probabilistic Databases. Technical Report. Stanford, 2007. [http://ilpubs.stanford.edu:8090/800/] [Обращение 20 ноября 2012].
27. Saad Y., van der Vorst H. A. Iterative solution of linear systems in the 20th Century. Journal of Computational and Applied Mathmatics, Issue 123, 2000.
28. Benzi M. The Early History of Matrix Iterations: With a Focus on the Italian Contribution. SIAM Conference on Applied Linear Algebra, Monterey Bay, Seaside, California, 26 October 2009.
29. Bronshtejn I. N., Semedjaev K. A. Spravochnik po matematike dlja inzhenerov i uchashhihsja vtuzov [Directory by mathematics for engineers and students of technical schools]. 13-e izd. ispravlennoe. M.: Nauka, 1986 (in Russian).
30. Ozsu M. N., Valduriez P. Principles of Distributed Database Systems. Second Edition. New Jersey, 1999. P. 233.
31. Graefe G. Query Evaluation Techniques for Large Databases. ACM Computing Surveys, 1993. Volume 25, Issue 2.
32. Hromkovi J. Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. Berlin: Springer, 2004.
33. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms. Third Edition. Cambridge-London: Massachusetts Institute of Technology Press, 2009.
Review
For citations:
Mendkovich N.A., Kuznetsov S.D. Minimization of data base query's conditions: evoluation of efficiency. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2013;25:113-130. (In Russ.)
Email this article 