Optimization Techniques for Query Processing in Relational Databases
DOI:
https://doi.org/10.15662/IJARCST.2018.0101001Keywords:
Query optimization, Cost-based optimization, Rule-based optimization, Query rewriting, Materialized views, Indexing strategies, Join algorithms, LEO learning optimizer, Sargable queries, Filter-and-RefineAbstract
Optimization of query processing in relational databases is a cornerstone of efficient data retrieval. This study examines key techniques developed prior to 2017, addressing how relational database management systems (RDBMSs) enhance performance by optimizing query execution. Essential strategies include cost-based and rule-based query optimization, query rewriting, materialized views, indexing methods, join algorithm selection, and heuristic approaches such as System R and LEO. The cost-based optimizer evaluates multiple possible plans and selects the least expensive one based on cardinality estimates and cost models—groundbreaking work first introduced by the System R project in 1979. Query rewriting exploits relational algebra equivalences to transform original queries into semantically identical forms that execute more efficiently. Materialized views and indexing accelerate frequent query patterns by pre-computing or structuring search paths for rapid data access.
Join execution strategies—nested loop, indexed nested loops, sort-merge, and hash join—play critical roles in optimizing multi-table queries by minimizing disk I/O and computation. Advanced solutions include LEO (Learning Optimizer) from DB2, leveraging workload adaptation patterns, and heuristic enhancements for multi-way join ordering. Additional optimization techniques, such as Filter-and-Refine (FRP) for spatial queries, sargable predicates for efficient index usage, and denormalization through materialized or indexed views, further underscore the depth of research in optimizing query pathways.
Collectively, these strategies reflect decades of rigorous research and practical engineering, enabling relational databases to deliver robust query performance. This review synthesizes these pre-2017 advancements, setting the foundation for deeper analysis in subsequent sections.
References
1. Selinger, P. G., Astrahan, M. M., Chamberlin, D. D., Lorie, R. A., & Price, T. G. (1979). Access Path Selection in a Relational Database Management System. Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, 23–34.
2. Graefe, G. (1993). Query evaluation techniques for large databases. ACM Computing Surveys (CSUR), 25(2), 73– 169.
3. Chaudhuri, S. (1998). An Overview of Query Optimization in Relational Systems. Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS '98), 34–43.
4. Gupta, H., & Mumick, I. S. (1995). Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Engineering Bulletin, 18(2), 3–18.
5. Ioannidis, Y. E., & Kang, K. (1990). Randomized Algorithms for Optimizing Large Join Queries. Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, 312–321.
6. Ioannidis, Y. E. (1996). Query optimization. ACM Computing Surveys, 28(1), 121–123.
7. Stillger, M., Lohman, G. M., Markl, V., & Kandil, M. (2001). LEO – DB2’s Learning Optimizer. VLDB Journal,
10(2–3), 177–198.
8. Swami, A., Deshpande, P., & Ioannidis, Y. (1988). Time and Space Tradeoffs in Query Optimization. Proceedings
of the 14th International Conference on Very Large Data Bases (VLDB '88), 171–180.
9. Chaudhuri, S., Motwani, R., & Narasayya, V. (1998). On Random Sampling over Joins. Proceedings of the 17th
ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 263–274.
10.Ramakrishnan, R., & Gehrke, J. (2003). Database Management Systems (3rd Edition). McGraw-Hill.
