Query optimization techniques in data warehouses: Study and Comparison

Abstract

The query optimizer is a critical component of database systems, where the adoption of cost-based optimizers is prevalent. A cost-based optimizer employs a plan enumeration algorithm to find the most efficient plan by evaluating its cost. In the cost model, cardinality, the number of tuples through an operator, plays a vital role. Inaccurate cardinality estimation, errors in the cost model, and the vast plan space can hinder the optimizer’s ability to find the optimal execution plan for complex queries within a reasonable time frame. Several causes behind these limitations push studies to propose techniques to enhance the quality of cardinality estimation, the major key component of the query optimizer and emphasize the need for continued research to address the challenges associated with cardinality estimation and to develop robust techniques that can adapt to different environment and conditions. The objective of this work is to examine different approaches, including synopsis-based methods, sampling-based methods, and learning-based methods. Specifically, both supervised and unsupervised learning methods are investigated. A comparative analysis reveals that while progress has been made in improving cardinality estimation, consistent enhancements are not always achieved.***

L’optimisateur de requête est une composante critique des systèmes de bases de données où l’adoption d’optimiseurs basés sur le coût est prédominante. Un optimisateur basé sur les coûts utilise un algorithme de numérotation de plan pour trouver le plan le plus efficace en évaluant son coût. Dans le modèle de coût, la cardinalité, le nombre de tuples à travers un opérateur, joue un rôle vital. Des estimations de cardinalité inexactes, des erreurs dans le modèle de coût et l’espace de planification étendu peuvent entraver la capacité de l’optimisateur à trouver le plan d’exécution optimal pour les requêtes complexes dans un délai raisonnable. Plusieurs causes derrière ces limites poussent les études à proposer des techniques visant à améliorer la qualité de l’estimation de la cardinalité, la principale composante clé du optimisateur de requête, et soulignent la nécessité de poursuivre des recherches afin de relever les défis associés à l’évaluation des cardinalités et de développer des techniques robustes qui peuvent s’adapter à différents environnements et conditions. L’objectif de ce travail est d’examiner différentes approches, y compris les méthodes basées sur le résumé, les méthodes basées sur l’échantillonnage et les méthodes basées sur l’apprentissage. Une analyse comparative révèle que si des progrès ont été réalisés dans l’amélioration de l’estimation de la cardinalité, des améliorations cohérentes ne sont pas toujours réalisées.