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
Eduardo Mella, M. Andrea Rodríguez, Loreto Bravo et al. · GeoInformatica · 2019
Cited by 7
Д.Е. Бакитько, Maksym Nesterov · Scientific news of Dahl university · 2019
..,
Cited by 0Open access
Tu, Yicheng, Eslami, Mehrad · Digital Commons - University of South Florida (University of South Florida) · 2025
Disclosed are various embodiments for batched query processing and optimization in database management systems. A single algebraic expression is generated based at least in part on applying equivalence rules to algebraic expressions for a plurality of database queries of a database comprising a set of relations. The equivalence rules involve relational operators comprising Psi (Ï) operators. The database can be queried using a single database query to create a result that is equivalent to the plurality of database queries.
Cited by 0
Hyuck Yoo · Deep Blue (University of Michigan) · 1990
Query optimization is a crucial part in relational database management systems because it can make a significant improvement in the overall performance of these systems. As the need for relational database management systems to handle larger amounts of data and more complex queries increases, it is of paramount importance that an optimal and efficient solution is found to answer a given query. Traditionally, dynamic programming or exhaustive search has been used to guarantee optimality, but these approaches are not effective for complex queries with large search spaces. In this dissertation, we investigate the problem of finding an optimal solution to the query optimization problem without having to search all the possibilities. The savings result from the idea of intelligently predicting future processing costs. Specifically, four query optimization problems are addressed: query optimization by semijoins, join query optimization, multiple query optimization, and query optimization for fragmented databases. For each problem, a new query optimization method is developed in light of the goal of enhancing the search efficiency while preserving optimality. Simulation experiments are carried out to show that substantial improvements can indeed be achieved. Another advantage of our approach is its modularity, in that different query processing strategies can be easily incorporated into the methods and general cost functions can be used for the optimization. Modularity is achieved because the methods developed consist of four well-defined and unrelated modules so that one module can be modified without affecting the others.
Cited by 0
Nagireddy Karri, Partha Sarathi Reddy Pedda Muntala · International Journal of Emerging Trends in Computer Science and Information Technology · 2023
Traditional database optimizers rely on hand-crafted heuristics and cost models that assume predicate independence, uniform distributions, and stable runtime conditions. These assumptions are generally flawed on contemporary, heterogeneous workloads deep join trees, correlated attributes, UDFs, and elastic cloud resources that give rise to cascading cardinality errors, ineffective plan decisions, and inflated tail latencies. Machine learning (ML) offers it as an alternative based on the data. Report on and synthesize ML methods that enhance three optimizer layers: (i) predictive (learned cardinality estimators, neural cost models, plan-time latency predictors), (ii) decision (reinforcement learning to join ordering, operator selection, and knob tuning), and (iii) control (bandits to online adaptation, uncertainty-sensitive pruning, and rollback guardrails) in this paper. Present feature representations of SQL/ASTs, logical/physical plan DAGS, and operator-level sketches; contrast offline training on past logs with online continual learning; and study robustness to distribution shift and drift. Analytical and mixed workloads Empirical data using both analytical and mixed workloads indicate steady double-digit decrees in end-to-end execution time and SLO violations with low overheads in optimization. Another set of engineering concerns find are cold start, query log privacy, and interaction with concurrency control, and integration patterns of reproducibility and outline covering advisory scoring to end-to-end learned optimizers. The paper is finalized with a research agenda that is dedicated to uncertainty-calibrated planning, cross-database transfer, explainability, and cross-tail and standardized benchmarks
Cited by 0Open access
Yannis Ioannidis, Eugene Wong · 1987
Query optimizers of future database management systems are likely to face large access plan spaces in their task. Exhaustively searching such access plan spaces is unacceptable. We propose a query optimization algorithm based on simulated annealing, which is a probabilistic hill climbing algorithm. We show the specific formulation of the algorithm for the case of optimizing complex non-recursive queries that arise in the study of linear recursion. The query answer is explicitly represented and manipulated within the closed semiring of linear relational operators. The optimization algorithm is applied to a state space that is constructed from the equivalent algebraic forms of the query answer. A prototype of the simulated annealing algorithm has been built and few experiments have been performed for a limited class of relational operators. Our initial experience is that, in general, the algorithm converges to processing strategies that are very close to the optimal. Moreover, the traditional processing strategies (e.g., the semi-naive evaluation) have been found to be, in general, suboptimal.
Cited by 184Open access
Francis C. Chu, Joseph Y. Halpern, Praveen Seshadri · 1999
We identify two unreasonable, though standard, assumptions made by database query optimizers that can adversely affect the quality of t,he chosen evaluation plans. One assumption is that it is adequate to optimize for the expected case-that is, the case where various parameters (like available memory) take on their expected value. The other assumption is that the parameters are constant throughout the execution of the query. We present an algorithm based on the 'System R"-s@ile query optimization algorithm that does not rely on these assumptions. The algorithm we propose chooses the plan of the least expected cost instead of the plan of least cost given expected values of the parameters. In execution environments that exhibit a high degree of variability, our techniques should result in better performance.
Cited by 61Open access
Shital Satpute, Ashwini Shinde, Sonali Tambe et al. · 2018
Cited by 0
Gautam Jain Student, Gautam Jain · 2007
Parallel query processing has received a lot of attention in the database community because customer applications on databases are growing in size and complexity with an ever increasing demand for performance. The main objective of parallel query processing is to achieve speedup, scaleup and high throughput. Parallel machines are necessary for achieving the speedup, however efficient resource utilization and workload scheduling is crucial for maximizing throughput of database systems. Query optimization is identified as the most important aspect in achieving this objective, and so will be the main topic of this study. Query Optimization basically deals with exploiting the inherent parallelism available in queries. We study the different forms of parallelism that have been addressed in literature and comment on the suitability of each. Query optimizers are used to generate query evaluation plans for parallel execution of queries by identifying the different forms of paralle...
Cited by 0
Yuqing Wu, H. V. Jagadish · Deep Blue (University of Michigan) · 2004
With the growing importance of XML as a format for data representation and data transport, being able to process XML queries efficiently becomes a topic of interest. Relational database techniques, even though mature, don't always apply in an XML context, due to the special features of XML data and XML queries. In this thesis, we study these features and investigate various aspects of query processing and query optimization in the framework of the Timber native XML database system. We evaluate XML queries by breaking them into pattern trees, which specify the nodes to match, and the desired relationships between the nodes. The structural relationships are evaluated via structural joins. We introduce two families of structural join algorithms (Tree-Marge and Stack-Based), which take advantage of the (DocId, StartPos : EndPos, LevelNum) representation of positions of XML components and perform structural join efficiently, with time, space and I/O complexity linear to the input and output lists. In this thesis, we focus on cost-based optimization for pattern tree matching. We propose five structural join order selection algorithms and show that fully-pipelined plans are possible for any given query pattern. Moreover, left-deep plans, which are chosen as the rule-of-thumb in a relational database, are not desirable. Relaxing the fully-indexed assumption brings issues related to data instantiation into the picture. The challenge is that in XML databases, the data associated with an element can vary. We define data instantiation as a first-class physical operator and take into consideration both the placement and granularity of data instantiation while optimizing pattern tree matching. Accurate cost-based optimization depends on accurate result size estimation. We propose a novel summary structure, <italic>position histogram</italic>, to capture the position relationship between nodes in an XML document. Experiments demonstrate that the <italic>Ph-Hist</italic> algorithm is capable of estimating the result size accurately, for both single twig patterns and patterns that are arbitrarily complex. Collectively, we are trying to address issues of storing and querying XML data efficiently, in the context of the Timber project. However, the theories behind the techniques proposed in this thesis apply irrespective to how the XML data is stored.
Cited by 0
Martinez Medina, Lourdes · theses.fr (ABES) · 2014
Les systèmes de gestion de données distribuées deviennent de plus en plus complexes. Ils interagissent avec des réseaux de dispositifs fixes et/ou mobiles, tels que des smartphones ou des tablettes, dispositifs hétérogènes, autonomes et possédant des limitations physiques. Ces dispositifs exécutent des applications permettant l'interaction des usagers (i.e. jeux virtuels, réseaux sociaux). Ces applications produisent et consomment des données à tout moment voire même en continu. Les caractéristiques de ces systèmes ajoutent des dimensions au problème de l'optimisation de requêtes, telles que la variabilité des objectifs d'optimisation, l'absence d'information sur les données (métadonnées) ou le manque d'une vision globale du système. Les techniques traditionnelles d'optimisation des requêtes n'abordent pas (ou très peu) les systèmes autonomes. Elles se basent sur les métadonnées et font des hypothèses très fortes sur le comportement du système. En plus, la majorité de ces techniques d'optimisation ciblent uniquement l'optimisation du temps d'exécution. La difficulté d'évaluation des requêtes dans les applications modernes incite à revisiter les techniques traditionnelles d'optimisation. Cette thèse fait face aux défis décris précédemment par l'adaptation du paradigme du Raisonnement à partir de cas (CBR pour Case-Based Reasoning) au problème de l'optimisation des requêtes. Cette adaptation, associée à une exploration pseudo-aléatoire de l'espace de solutions fournit un moyen pour optimiser des requêtes dans les contextes possédant très peu voire aucune information sur les données. Cette approche se concentre sur l'optimisation de requêtes en utilisant les cas générés précédemment dans l'évaluation de requêtes similaires. Un cas de requête et composé par : (i) la requête (le problème), (ii) le plan d'exécution (la solution) et (iii) les mesures de ressources utilisés par l'exécution du plan (l'évaluation de la solution). Cette thèse aborde également la façon que le processus CBR interagit avec le processus de génération de plan d'exécution de la requête qui doit permettre d'explorer l'espace des solutions. Ce processus utilise les heuristiques classiques et prennent des décisions de façon aléatoire lorsque les métadonnées viennent à manquer (e.g. pour l'ordre des jointures, la sélection des algorithmes, voire même le choix des protocoles d'acheminement de messages). Ce processus exploite également le CBR pour générer des plans pour des sous-requêtes, accélérant ainsi l'apprentissage de nouveaux cas. Les propositions de cette thèse ont été validées à l'aide du prototype CoBRA développé dans le contexte du projet UBIQUEST.
Cited by 0
Bryan Howard Genet · Research Commons (University of Waikato) · 2007
The term quote semantic query optimization quote (SQO) denotes a methodology whereby queries against databases are optimized using semantic information about the database objects being queried. The result of semantically optimizing a query is another query which is syntactically different to the original, but semantically equivalent and which may be answered more efficiently than the original. SQO is distinctly different from the work performed by the conventional SQL optimizer. The SQL optimizer generates a set of logically equivalent alternative execution paths based ultimately on the rules of relational algebra. However, only a small proportion of the readily available semantic information is utilised by current SQL optimizers. Researchers in SQO agree that SQO can be very effective. However, after some twenty years of research into SQO, there is still no commercial implementation. In this thesis we argue that we need to quantify the conditions for which SQO is worthwhile. We investigate what these conditions are and apply this knowledge to relational database management systems (RDBMS) with static schemas and infrequently updated data. Any semantic query optimizer requires the ability to reason using the semantic information available, in order to draw conclusions which ultimately facilitate the recasting of the original query into a form which can be answered more efficiently. This reasoning engine is currently not part of any commercial RDBMS implementation. We show how a practical semantic query optimizer may be built utilising readily available semantic information, much of it already captured by meta-data typically stored in commercial RDBMS. We develop cost models which predict an upper bound to the amount of optimization one can expect when queries are pre-processed by a semantic optimizer. We present a series of empirical results to confirm the effectiveness or otherwise of various types of SQO and demonstrate the circumstances under which SQO can be effective.
Cited by 0Open access
Liviana Tudor · Studies in Informatics and Control · 2016
Web services allow middleware access to a relational database and require data representation in XML format. The XML views obtained from relational databases can be accessed by using XPath queries. This article proposes an optimization model for XML data processing based on a heuristic algorithm to extract data from XPath views. To this end, the author uses various XPath query classes temporarily stored in cache, as XPath views. For each view selected from cache, a compensation query can be found and composed with in order to solve an XML data query. Experimental results reveal the effectiveness of the heuristic method used to solve queries on XML documents.
Cited by 1Open access
Nicolas Bruno, Surajit Chaudhuri, Ravi Ramamurthy · Proceedings - International Conference on Data Engineering · 2009
Commercial database systems expose query hints to address situations in which the optimizer chooses a poor plan for a given query. However, current query hints are not flexible enough to deal with a variety of non-trivial scenarios. In this paper, we introduce a hinting framework that enables the specification of rich constraints to influence the optimizer to pick better plans. We show that while our framework unifies previous approaches, it goes considerably beyond existing hinting mechanisms, and can be implemented efficiently with moderate changes to current optimizers.
Cited by 35
Çiğdem Kaptanoğlu · Istanbul Technical University Academic Open Archive (Istanbul Technical University) · 1992
Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 1992
Cited by 0
Francis Chu, Joseph Y. Halpern, Johannes Gehrke · 2002
A standard assumption in the database query optimization literature is that it suffices to optimize for the "typical" case---that is, the case in which various parameters (e.g., the amount of available memory, the selectivities of predicates, etc.) take on their "typical" values. It was claimed in [CHS99] that we could do better by choosing plans based on their expected cost. Here we investigate this issue more thoroughly. We show that in many circumstances of interest, a "typical" value of the parameter often does give acceptable answers, provided that it is chosen carefully and we are interested only in minimizing expected running time. However, by minimizing the expected running time, we are effectively assuming that if plan p1 runs three times as long as plan p2, then p1 is exactly three times as bad as p2. An assumption like this is not always appropriate. We show that focusing on least expected cost can lead to significant improvement for a number of cost functions of interest.
Cited by 0
Rada Chirkova, Fereidoon Sadri · 2006
We study optimization of relational queries using materialized views, where views may be regular or restructured. In a restructured view, some data from the base table(s) are represented as metadata - that is, schema information, such as table and attribute names - or vice versa.Using restructured views in query optimization opens up a new spectrum of views that were not previously available, and can result in significant additional savings in query-evaluation costs. These savings can be obtained due to a significantly larger set of views to choose from, and may involve reduced table sizes, elimination of self-joins, clustering produced by restructuring, and horizontal partitioning.In this paper we propose a general query-optimization framework that treats regular and restructured views in a uniform manner and is applicable to SQL select-project-join queries and views with or without aggregation. Within the framework we provide (1) algorithms to determine when a view (regular or restructured) is usable in answering a query, and (2) algorithms to rewrite a query using usable views.Semantic information, such as knowledge of the key of a view, can be used to further optimize a rewritten query. Within our general query-optimization framework, we develop techniques for determining the key of a (regular or restructured) view, and show how this information can be used to further optimize a rewritten query. It is straightforward to integrate all our algorithms and techniques into standard query-optimization algorithms.
Cited by 3
Florian Waas · UvA-DARE (University of Amsterdam) · 2000
Cited by 19Open access
Kumail Saifuddin Saif · Zenodo (CERN European Organization for Nuclear Research) · 2020
Query performance is a key aspect for any development done in SAP HANA and it is very common to have performance issues when the data size grows in the system. SAP HANA offers effective tools and techniques for developers to make sure the query is optimized as per the hardware of SAP HANA database. Understanding the details of Query processing by different HANA engines like Calculation engine, Join engine, OLAP engine to name a few, and the role of the SQL optimizer, SQL plan cache, PlanViz, OOM dumps helps developers to write and test the code to make sure performance is optimized.
Cited by 0Open access