Chen Ye, Haoyang Duan, Hua Zhang et al. · Mathematics · 2024
Over the last decades, various cost-based optimizers have been proposed to generate optimal plans for SQL queries. These optimizers are key to achieving good performance in database systems and can speed up query execution. Still, they may need enormous expert efforts and perform poorly on complicated queries. Learning-based optimizers have been shown to achieve high-quality plans by learning from past experiences. However, these solutions treat each query separately and neglect the semantic equivalence among different queries. Intuitively, a high-quality plan may be obtained for a complicated query by discovering a simple equivalent query. Motivated by this, in this paper, we present Celo, a novel constraint-enhanced learned optimizer to directly integrate the equivalent information of queries into the learning-based model. We apply denial constraints to identify equivalent queries by replacing equivalent predicates. Given a query, we augment the query plans generated by the learning-based model with the high-quality plans of its equivalent queries. Then, a more potentially well-performed plan will be predicted among the augmented query plans. Extensive experiments using real-world datasets demonstrated that Celo outperforms the previous state-of-the-art (SOTA) results even with few constraints.
Cited by 1Open access
Ashraf Aboulnaga, Surajit Chaudhuri · 1999
Query optimizers use approximate techniques such as histograms or sampling for result size and distinct value estimation, even though these techniques may incur high estimation errors, leading the optimizer to choose sub-optimal query execution plans. In this report, we propose a novel approach to query optimization that provides the query optimizer with exact values for the result size of operators and operator trees, which we call sub-plans, and for the number of distinct values in the output of these subplans. In our approach, the query optimizer optimizes the query and records all the sub-plans for which result size or distinct value estimates are required in a data structure that we call the sub-plan memo. After query optimization is completed, the sub-plans in the sub-plan memo are executed and their actual result sizes and the number of distinct values in their outputs are recorded in the memo. The optimizer then re-optimizes the query using the more accurate result size and distinct value information in the subplan memo, which results in potentially choosing a better query execution plan. The process is repeated if re-optimization encounters sub-plans that are not in the sub-plan memo. This technique can result in potentially increasing the optimization time sharply. However, it is very effective in choosing the optimal query execution plan. Therefore, this approach is primarily suitable for frequently executed queries embedded in application programs. We present an experimental evaluation of our proposed approach based on a prototype implementation in Microsoft SQL Server 2000.
Cited by 0
Menekşe, Günay · OpenMETU (Middle East Technical University) · 2019
Cited by 0
T. V. Vijay Kumar, Amit Kumar, Rahul Singh · International Journal of Swarm Intelligence Research · 2013
A large number of queries are posed on databases spread across the globe. In order to process these queries efficiently, optimal query processing strategies that generate efficient query processing plans are being devised. In distributed relational database systems, due to replication of relations at multiple sites, the relations required to answer a query may necessitate accessing of data from multiple sites. This leads to an exponential increase in the number of possible alternative query plans for processing a query. Though it is not computationally feasible to explore all possible query plans in such a large search space, the query plan that provides the most cost-effective option for query processing is considered necessary and should be generated for a given query. In this paper, an attempt has been made to generate such optimal query plans using Set based Comprehensive Learning Particle Swarm Optimization (S-CLPSO). Experimental comparisons of this algorithm with the GA based distributed query plan generation algorithm shows that for higher number of relations, the S-CLPSO based algorithm is able to generate comparatively better quality Top-K query plans.
Cited by 7
Menekse, G, Polat, Faruk, Cosar, A · OpenMETU (Middle East Technical University) · 1998
Alternative Plan Generation (APG) is an important phase of Multiple Query Optimization (MQO) in relational databases. It is necessary to generate a number of alternative plans in such a way that the sharing between queries is maximized and an optimal execution plan with minimal cost is obtained. For relational databases several methods have previously been proposed for generating alternative plans using commutativity and associativity properties of select, project and join operations. When all possible alternative plans are generated using these properties, the number of alternative plans to be used in MQO will be quite large leading to an unacceptable increase in the cost of APG which eliminates the benefits of MQO for query execution. The quality of the alternative plans determines the cost of the global execution plan for the queries. In this paper, we propose a new method for APG that uses information about the queries to best utilize the sharing between the queries. This method generates the alternative plans for queries having more common tasks by introducing the factors that provides a good estimation of shared tasks of queries using information such as common relations, common possible joins and common conditions. We also compare benefits obtained from MQO with the previously proposed APG methods and with our method, and show that it is possible to find a near optimal solution with this technique. For 14 queries and a database of 15 relations on the average, MQO performs 30 times faster by using the alternative plans generated by this new method while we are within 7% of the optimal solution.
Cited by 0Open access
Vibhuti S. Sengar, Jayant R. Haritsa · NOT FOUND REPOSITORY (Indian Institute of Science Bangalore) · 2003
INTRODUCTION Query optimization is a computationally intensive process, especially for the complex queries that are typical in current data warehousing and mining applications. The inherent overheads of query optimization are compounded by the fact that a new query is typically optimized afresh, providing no opportunity to amortize these overheads over prior optimizations. While current commercial query optimizers do provide facilities for reusing execution plans generated for earlier queries (e.g. "stored outlines" in Oracle 9i), the query matching is extremely restrictive -- only if the incoming query has a close textual resemblance with one of the stored queries is the associated plan re-used to execute the new query. Recently, in [1], we proposed a tool called PLASTIC (Plan Selection Through Incremental Clustering) to significantly increase the scope of plan reuse. The tool is based on the observation that even queries which differ in projection, selection and join predicates, as
Cited by 1Open access
T. V. Vijay Kumar, Rahul Singh, Amit Kumar · International Journal of Applied Metaheuristic Computing · 2015
Query processing is a critical performance evaluation parameter and has received a considerable amount of attention especially in the context of distributed database systems. The aim of distributed query processing is to effectively and efficiently process the query. This entails laying down an optimal distributed query processing strategy that generates efficient query plans Since in distributed database systems, the data is distributed and replicated at multiple sites, the number of query plans increases exponentially with increase in the number of relations accessed by the query along with increase in the number of sites containing these relations. Thus, from amongst these query plans, there is a need to generate optimal query plans involving lesser number of sites which, in turn, would entail lower site-to-site communication cost leading to faster query response times. In this paper, an attempt has been made to generate such query plans for a distributed query using Ant Colony Optimization (ACO). This ACO based distributed query plan generation (DQPG) algorithm, when compared with the GA based DQPG algorithm, is able to generate comparatively better quality Top-K query plans for a given distributed query.
Cited by 12
Haibo Xiu, Pankaj K. Agarwal, Jun Yang · arXiv (Cornell University) · 2024
The effectiveness of a query optimizer relies on the accuracy of selectivity estimates. The execution plan generated by the optimizer can be extremely poor in reality due to uncertainty in these estimates. This paper presents PARQO (Penalty-Aware Robust Plan Selection in Query Optimization), a novel system where users can define powerful robustness metrics that assess the expected penalty of a plan with respect to true optimal plans under uncertain selectivity estimates. PARQO uses workload-informed profiling to build error models, and employs principled sensitivity analysis techniques to identify human-interpretable selectivity dimensions with the largest impact on penalty. Experiments on three benchmarks demonstrate that PARQO finds robust, performant plans, and enables efficient and effective parametric optimization.
Cited by 0Open access
Lijie Zhang, Yaxuan Wang · 2010
Continuous queries are the more interesting class of data stream queries. The answer to a continuous query is continuously produced over time unless stopped artificially. During an executed continuous query, the run environment changes continuously, meanwhile some properties of data stream itself change too, such as input rate, selectivity of operators and execute time and so on. In order to adapt the continuity of queries and variability of system environment and date itself during continuous query, this paper presents a query plan optimization and migration strategy based on multi-factors and gives corresponding algorithm. Experiments have proved that this optimization and migration strategy ensures output results correctness and time sequence, meanwhile validly increases throughput and output rate and reduces output time latency.
Cited by 2
Haibo Xiu, Pankaj K. Agarwal, Jun Yang · Proceedings of the VLDB Endowment · 2024
The effectiveness of a query optimizer relies on the accuracy of selectivity estimates. The execution plan generated by the optimizer can be extremely poor in reality due to uncertainty in these estimates. This paper presents PARQO ( P enalty- A ware R obust Plan Selection in Q uery O ptimization), a novel system where users can define powerful robustness metrics that assess the expected penalty of a plan with respect to true optimal plans under uncertain selectivity estimates. PARQO uses workload-informed profiling to build error models, and employs principled sensitivity analysis techniques to identify human-interpretable selectivity dimensions with the largest impact on penalty. Experiments on three benchmarks demonstrate that PARQO finds robust, performant plans, and enables efficient and effective parametric optimization.
Cited by 6
Nikita Vasilenko, Alexander Demin, Vladimir Boorlakov · ArXiv.org · 2025
Large language model (LLM) embeddings offer a promising new avenue for database query optimization. In this paper, we explore how pre-trained execution plan embeddings can guide SQL query execution without the need for additional model training. We introduce LLM-PM (LLM-based Plan Mapping), a framework that embeds the default execution plan of a query, finds its k nearest neighbors among previously executed plans, and recommends database hintsets based on neighborhood voting. A lightweight consistency check validates the selected hint, while a fallback mechanism searches the full hint space when needed. Evaluated on the JOB-CEB benchmark using OpenGauss, LLM-PM achieves an average speed-up of 21% query latency reduction. This work highlights the potential of LLM-powered embeddings to deliver practical improvements in query performance and opens new directions for training-free, embedding-based optimizer guidance systems.
Cited by 0Open access
Nikita Vasilenko, Alexander Demin, V.V. Burlakov · 2025
Cost based SQL optimizers remain brittle under real world data and engine diversity; small errors in cardinality or cost estimates can cascade into poor plans. We propose a conceptual architecture for hint based query optimization and describe two modules in detail: a fast module which encodes physical plans as text, embeds with a pretrained language model, retrieves nearest neighbors, and produces a compact binary hint vector with a safety check against the default plan; and an agent guided module powered by a fine tuned Large Language Model, which refines hints through iterative search with database feedback under a strict evaluation budget. We specify interfaces, data flow, and decision policies for both modules, and outline integration through standard hint mechanisms without engine changes. Preliminary module level results on JOB CEB indicate roughly twenty percent average runtime reduction for the fast module and fewer trial executions than a greedy baseline for the agent guided module. The paper focuses on architecture and module behavior rather than a single end to end deployment, so system wide testing is intentionally out of scope.
Cited by 1
Faruk Polat, Ahmet Coşar, Reda Alhajj · Information Sciences · 2001
Cited by 8Open access
Chaofan Zhao, Jing Ren · Lecture notes in computer science · 2024
Cited by 0
SANA SHAFIQUE, ATIF AZIZ · Journal of Computer & Information Technology · 2017
In any database system query Optimization is an important component. Optimizer designing that takes less time for searching and provides the most optimal query execution plan has been a challenge for DBMS research community in the last decade. The cost of executing a plan depends heavily on selectivity which keeps changing frequently and thusstatic compilation provides an inconsistent performance. Adaptive query optimization is an excellent method of generating optimal plans quite consistently. This paper proposes new hybrid architecture for query optimization which combine features of adaptive query processing and also reduces the search space for re optimization using reduced plan diagrams and cost diagrams. This hybrid architecture is bound to give more efficient performance as compared to any other optimization technique along with increased robustness and a substantial increase in consistency the selection of the most optimal execution plan
Cited by 0Open access
Wenrui Zhou, Qiyu Liu, Jianfeng Peng et al. · ArXiv.org · 2025
Efficient data processing is increasingly vital, with query optimizers playing a fundamental role in translating SQL queries into optimal execution plans. Traditional cost-based optimizers, however, often generate suboptimal plans due to flawed heuristics and inaccurate cost models, leading to the emergence of Learned Query Optimizers (LQOs). To address challenges in existing LQOs, such as the inconsistency and suboptimality inherent in pairwise ranking methods, we introduce CARPO, a generic framework leveraging listwise learning-to-rank for context-aware query plan optimization. CARPO distinctively employs a Transformer-based model for holistic evaluation of candidate plan sets and integrates a robust hybrid decision mechanism, featuring Out-Of-Distribution (OOD) detection with a top-k fallback strategy to ensure reliability. Furthermore, CARPO can be seamlessly integrated with existing plan embedding techniques, demonstrating strong adaptability. Comprehensive experiments on TPC-H and STATS benchmarks demonstrate that CARPO significantly outperforms both native PostgreSQL and Lero, achieving a Top-1 Rate of 74.54% on the TPC-H benchmark compared to Lero's 3.63%, and reducing the total execution time to 3719.16 ms compared to PostgreSQL's 22577.87 ms.
Cited by 0Open access
Calisto Zuzarte, Víctor Muntés-Mulero, Josep Lluís Larriba Pey et al. · Dialnet (Universidad de la Rioja) · 2004
Cited by 1
Angela Yang · 2010
The DB2 optimization profile is often used as a work around to get a required query execution plan when the DB2 optimizer failed to produce a good plan. However users often find it challenging to use. Part of the reason is documentation has been focused on the command line processor (CLP). It lacks coverage with concrete examples on profile usage in applications, like Java and SQL procedure, which are more widely used.
Cited by 1
Feng Liang, Francis C. M. Lau, Heming Cui et al. · Information Sciences · 2023
Cited by 5
Abudula, Dilixiati · OpenMETU (Middle East Technical University) · 2019
In this thesis, alternative plan generation methods for multiple query optimization(MQO) are introduced and an implementation in the C++ programming.language has been developed. Multiple query optimization, aims to minimize the total cost of executing a set of relational database queries. In traditional single query optimization only the cost of execution of a single relational database query is minimized. In single query optimization a search is performed to investigate possible alternative methods of accessing relational database tables and alternative methods of performing join operations in the case of multi-relation queries where records from two or more relational tables have to be brought together using one of the join algortihms (e.g. nested loops, sort merge, hash join,etc). The choice of join method depends on the availability of indexes, amount of available main memory, the existence of ORDER BY clause for sorted output, the sizes of involved relations, many other factors. A simple way of performing multiple query optimization is to take the query execution plans generated for each of the queries as input to a MQO algorithm, and then try to identify common tasks in those plans using the MQO algorithm. However, this approach will reduce the achievable benefits since a more expensive execution plan (thus discarded by a single query optimizer) could have more common operations with other query execution plans, resulting in a lower total cost for MQO. .For this purpose we will introduce several methods for generating such potentially beneficial alternative query execution plans and experimentaly evaluate and compare their performances.
Cited by 0Open access