Measuring the complexity of join enumeration in query optimization
Published 1 September 1990
Kiyoshi Ono, Guy M. Lohman
Citations158
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper describes and measures the performance of the Starburst join enumerator, which can parameterically adjust for each query the space of join sequences that arc evaluated by the optimizer to allow or disallow composite tables as the inner operand of a join.
Abstract
Since relational database management systems typically support only diadic join operators as primitive opera-tions, a query optimizer must choose the “best ” sc-quence of two-way joins to achieve the N-way join of
Keywords
Computer Science
Access path selection in a relational database management system
2,153 Citations1979Patricia G. Selinger, M. M. Astrahan +3 more
This paper describes how System R chooses access paths for both simple (single relation) and complex queries (such as joins) given a user specification of desired data as a boolean expression of predicates.
ACM Transactions on Database SystemsDecomposition—a strategy for query processing
387 Citations1976Eugene Wong, Karel Youssefi
Strategy for processing multivariable queries in the database management system INGRES is considered, and algorithms for reduction and for choosing the variable to be substituted are given.
IEEE Transactions on Knowledge and Data EngineeringStarburst mid-flight: as the dust clears (database project)
247 Citations1990Laura M. Haas, Wan Chang +8 more
The purpose of the Starburst project is to improve the design of relational database management systems and enhance their performance, while building an extensible system to better support nontraditional applications and to serve as a testbed for future improvements in database technology.
Optimization of Nonrecursive Queries
210 Citations1986Ravi Krishnamurthy, Haran Boral +1 more
A formal model and a precise statement of the optimization problem that delineates the assumptions and limitations of the previous approaches are presented, and a quadratic-tinie algorithm determines the optimum join order for acyclic queries is proposed.
The optimization of queries in relational databases
173 Citations1980Robert Philip Kooi
A fully implemented system for optimizing and executing queries for relational databases is described, which optimizes n-table, equi-join queries written in QUEL, the query language supported by the INGRES relational database management system (DBMS).
ACM SIGMOD RecordGrammar-like functional rules for representing query optimization alternatives
162 Citations1988Guy M. Lohman
Very Large Data BasesImplementing an Interpreter for Functional Rules in a Query Optimizer
44 Citations1988Mavis K. Lee, Johann Christoph Freytag +1 more
This paper presents a design for implementing a query optimizer that interprets a new kind of compositional rules for specifying alternative execution strategies that are input to the optimizer as data.
Minds at UW (University of Wisconsin)Rule-based query optimization in extensible database systems
37 Citations1987Goetz Graefe
The design and an initial evaluation of the query optimizer generator developed for the EXODUS extensible database system and an optimizer currently under development for a new query evaluation method show the power and flexibility of the approach.
Very Large Data BasesOptimization of nested queries in a distributed relational database
32 Citations1986Guy M. Lohman, Dean Daniels +3 more
This paper describes how nested queries in the SQL language are processed by R*, an experimental adaptation to the distributed environment of the well-known centralized relational DBMS, System R.
An architecture for query optimization
31 Citations1982Arnon Rosenthal, David Reiner
An optimizer for relational queries to databases stored as flat files and Codasyl networks, which derives a sequence of internal data structures at successively more detailed levels and prunes the physical graph to produce a final access strategy tree.
Do semantically equivalent SQL queries perform differently?
2 Citations1986Guy M. Lohman
The relational database query language SQL (originally, "SEQUEL") was first developed as a non-procedural language: the user should specify only what data is desired, leaving it to the the system's query optimizer to determine how the data is accessed.