Jarek Gryz, Dongming Liang, Jarek Gryz et al. · 2002
Abstract. A join of two relations in real databases is usually much smaller than their Cartesian product. This means that most of the com-binations of tuples in the crossproduct of the respective relations do not appear together in the join result. We characterize these missing combi-nations as ranges of attributes that do not appear together and present experimental results on their discovery from real data sets. We then ex-plore potential applications of this knowledge to query optimization. By modeling empty joins as materialized views, we show how knowledge of these regions can be used to improve query performance. 1
Cited by 0
Dr. A. N. Wilschut, E Referent, Dr. H. M. Blanken et al. · 2008
ter verkrijging van de graad van doctor aan de Universiteit Twente, op gezag van de rector magnificus, prof.dr. Th. J. A. Popma, volgens besluit van het College voor Promoties in het openbaar te verdedigen
Cited by 0
Manish Kumar Sinha, Swati V. Chande · Research Journal of Information Technology · 2010
Cited by 14
Kete Wang, Qi Feng, Shaoyong Guo et al. · Lecture notes in electrical engineering · 2021
Cited by 1
Sutanay Choudhury, Lawrence B. Holder, George Chin et al. · arXiv (Cornell University) · 2014
Given a query graph that represents a pattern of interest, the emerging pattern detection problem can be viewed as a continuous query problem on a dynamic graph. We present an incremental algorithm for continuous query processing on dynamic graphs. The algorithm is based on the concept of query decomposition; we decompose a query graph into smaller subgraphs and assemble the result of sub-queries to find complete matches with the specified query. The novelty of our work lies in using the subgraph distributional statistics collected from the dynamic graph to generate the decomposition. We introduce a "Lazy Search" algorithm where the search strategy is decided on a vertex-to-vertex basis depending on the likelihood of a match in the vertex neighborhood. We also propose a metric named "Relative Selectivity" that is used to select between different query decomposition strategies. Our experiments performed on real online news, network traffic stream and a synthetic social network benchmark demonstrate 10-100x speedups over competing approaches.
Cited by 2Open access
Bo Du · 2005
Query operation is the most extensive operation in various database operations.So,query optimization is very important in the vast database.In making suitable indexes,setting appropriate conditions in the whereclause,creating temporary table for the optimizer of DBMS,the efficiency of the SQL queries can be improved.At the same time,many examples of query optimization in Informix are given.
Cited by 0
Encyclopedia of Database Systems · 2009
Cited by 0
G. N. Paulley, Per-Åke Larson · 2010
Consider an SQL query that specifies duplicate elimination via a DISTINCT clause. Because duplicate elimination often requires an expensive sort of the query result, it is often worthwhile to identify situations where the DISTINCT clause is unnecessary, to avoid the sort altogether. We prove a necessary and sufficient condition for deciding if a query requires duplicate elimination. The condition exploits knowledge about keys, table constraints, and query predicates. Because the condition cannot always be tested efficiently, we offer a practical algorithm that tests a simpler, sufficient condition. We consider applications of this condition for various types of queries, and show that we can exploit this condition in both relational and nonrelational database systems.
Cited by 9
SpringerReference · 2011
Cited by 0
Jonathan J. King · Defense Technical Information Center (DTIC) · 1981
The problem of database query optimization is to select an efficient way to process a query expressed in logical terms from among the alternative ways it can be carried out in the physical database. This thesis presents a new approach to this problem, called semantic query optimization. The goal of semantic query optimization is to produce a semantically equivalent query that is less expensive to process than the original query. Semantic query optimization actually transforms the original query into a new one by means of a process of inference. The transformations are limited to those that yield a semantically equivalent query, one that is guaranteed to produce the same answer as the original query in any permitted state of the database. This guarantee is achieved because the knowledge used to transform a query is the same knowledge used to insure the semantic integrity of the data stored in the database. Thus, semantic query optimization brings together the apparently separate research areas of query processing and database integrity. The thesis formally defines transformations that preserve semantic equivalence for queries in the relational calculus. In addition, it identifies several classes of cost-reducing query transformations for relational database queries, and provides quantitative estimates of the improvements they can produce, based upon widely accepted models of query processing. The thesis also discusses the design and implementation of a system that carries out semantic query optimization for an important class of relational database queries.
Cited by 111
Giedrius Slivinskas, Christian S. Jensen, Richard T. Snodgrass · ACM SIGMOD Record · 2002
A variety of developments combine to highlight the need for respecting order when manipulating relations. For example, new functionality is being added to SQL to support OLAP-style querying in which order is frequently an important aspect. The set- or multiset-based frameworks for query optimization that are currently being taught to database students are increasingly inadequate.This paper presents a foundation for query optimization that extends existing frameworks to also capture ordering. A list-based relational algebra is provided along with three progressively stronger types of algebraic equivalences, concrete query transformation rules that obey the different equivalences, and a procedure for determining which types of transformation rules are applicable for optimizing a query. The exposition follows the style chosen by many textbooks, making it relatively easy to teach this material in continuation of the material covered in the textbooks, and to integrate this material into the textbooks.
Cited by 18
Yannis Ioannidis, Eugene Wong · ACM SIGMOD Record · 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 29
Peter Bodorik, J. S. Riordon · 2003
The authors examine objectives, or measures of cost, which can be used in optimizing queries in a distributed database (DDB). They include the delay and dollar cost due to the network data transfer, CPU processing or a combination of both, and cost measures in terms of the size of partial results. These measures are used in distributed query processing modeling on a testbed of queries to examine the effect of choosing one measure of cost in optimizing strategies on their cost expressed in other measures and the cost of strategies generated by a two-phased approach. Results indicate that best strategies are generated when optimization considers cost measured in terms of both CPU processing and a network data transfer. They also confirm that the two-phased optimization yields close to optimal strategies.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 17
Francis C. 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 54
Stanley B. Zdonik · Lecture notes in computer science · 1988
Cited by 8
Mengmeng Liu, Zachary G. Ives, Boon Thau Loo · 2016
As declarative query processing techniques expand to the Web, data streams, network routers, and cloud platforms, there is an increasing need to re-plan execution in the presence of unanticipated performance changes. New runtime information may affect which query plan we prefer to run. Adaptive techniques require innovation both in terms of the <i>algorithms used to estimate costs</i>, and in terms of the <i>search algorithm</i> that finds the best plan. We investigate how to build a cost-based optimizer that recomputes the optimal plan <i>incrementally</i> given new cost information, much as a stream engine constantly updates its outputs given new data. Our implementation especially shows benefits for stream processing workloads. It lays the foundations upon which a variety of novel adaptive optimization algorithms can be built. We start by leveraging the recently proposed approach of formulating query plan enumeration as a set of <i>recursive datalog queries</i>; we develop a variety of novel optimization approaches to ensure effective pruning in both static and incremental cases. We further show that the lessons learned in the declarative implementation can be equally applied to more traditional optimizer implementations.
Cited by 11Open access
Hendrika Janna Steenhagen · University of Twente Research Information · 1995
Transformation of nested SQL queries into join queries is advantageous because a nested SQL query can be looked upon as a nested-loop join, which is just one of the several join implementations that may be available in a relational DBMS.In join queries, dangling (unmatched) operand tuples are lost, which causes a problem in transforming nested queries having the aggregate function COUNT between query blocks-a problem that has become well-known as the COUNT bug.In the relational context, the outerjoin has been employed to solve the COUNT bug.In complex object models supporting an SQLlike query language, transformation of nested queries into join queries is an important optimization issue as well.The COUNT bug turns out to be a special case of a general problem being revealed in a complex object model.To solve the more general problem, we introduce the nestjoin operator, which is a generalization of the outerjoin for complex objects.
Cited by 27Open access
n.n. · 2012
As declarative query processing techniques expand in scope — to the Web, data streams, network routers, and cloud platforms — there is an increasing need for adaptive query processing techniques that can re-plan in the presence of failures or unanticipated performance changes. A status update on the data distributions or the compute nodes may have significant repercussions on the choice of which query plan should be running. Ideally, new system architectures would be able to make cost-based decisions about reallocating work, migrating data, etc., and react quickly as real-time status information becomes available. Existing cost-based query optimizers are not incremental in nature, and must be run “from scratch ” upon each status or cost update. Hence, they generally result in adaptive schemes that can only react slowly to updates. An open question has been whether it is possible to build a costbased re-optimization architecture for adaptive query processing in a streaming or repeated query execution environment, e.g., by incrementally updating optimizer state given new cost information. We show that this can be achieved beneficially, especially for stream processing workloads. Our techniques build upon the recently proposed approach of formulating query plan enumeration as a set of recursive datalog queries; we develop a variety of novel optimization approaches to ensure effective pruning in both static and incremental cases. We implement our solution within an existing research query processing system, and show that it effectively supports cost-based initial optimization as well as frequent adaptivity.
Cited by 0
Christos H. Papadimitriou, Mihalis Yannakakis · 2007
Cited by 0
Yang, Zongheng · eScholarship (California Digital Library) · 2022
Data has been growing at an unprecedented rate in the past two decades. As a result, systems that store, process, and analyze data have become mission-critical. Crucial to the performance of data systems is the query optimizer, which translates high-level declarative queries (e.g., SQL) into efficient execution plans. However, query optimization is highly complex, leading to two key challenges. First, optimizers use a myriad of hand-designed heuristics to tame the complexity, but heuristics leave performance on the table. Second, optimizers are highly costly to develop, where human experts may spend months writing a first version and years refining it.This dissertation applies and enhances machine learning advances to tame the complexity in query optimization. First, we remove for the first time decades-old and accuracy-impacting heuristics in cardinality estimation—the Achilles’ heel of optimizers where heuristics particularly abound—thereby significantly improving estimation accuracy. We present Naru and NeuroCard, two cardinality estimators based on self-supervised learning advances that learn the joint data distribution of tables without any heuristic assumptions. Our estimators improve the accuracy of cardinality estimation by orders of magnitude compared to the prior state of the art. Second, we show that automatically learning to optimize SQL queries, without learning from an expert-designed optimizer, is both possible and efficient, thereby potentially alleviating the high development cost. We introduce Balsa, a deep reinforcement learning agent that automatically learns to optimize SQL queries by trial-and-error. Balsa can learn to outperform the optimizers of PostgreSQL—one of the most popular database systems—and a commercial database engine with a few hours of learning.Overall, by enhancing machine learning advances with new, carefully designed systems and ML techniques, this line of work improves existing query optimizers, while opening the possibility of alleviating the complex optimization in future environments and engines.
Cited by 1