Optimizing large join queries using a graph-based approach

Chiang Lee, Chi Sheng Shih, Yaw Huei Chen

Research output: Contribution to journalArticle

23 Citations (Scopus)

Abstract

Although many query tree optimization strategies have been proposed in the literature, there still is a lack of a formal and complete representation of all possible permutations of query operations (i.e., execution plans) in a uniform manner. A graph-theoretic approach presented in this paper provides a sound mathematical basis for representing a query and searching for an execution plan. In this graph model, a node represents an operation and a directed edge between two nodes indicates the order of executing these two operations in an execution plan. Each node is associated with a weight and so is an edge. The weight is an expression containing optimization required parameters, such as relation size, join selectivity factors. All possible execution plans are representable in this graph and each spanning tree of the graph becomes an execution plan. It is a general model which can be used in the optimizer of a DBMS for interal representation. On the basis of this model, we devise an algorithm that finds a near optimal execution plan using only polynomial time. The algorithm is compared with a few other popular optimization methods. Experiments show that the proposed algorithm is superior to the others under most circumstances.

Original languageEnglish
Pages (from-to)298-315
Number of pages18
JournalIEEE Transactions on Knowledge and Data Engineering
Volume13
Issue number2
DOIs
Publication statusPublished - 2001 Mar 1

Fingerprint

Polynomials
Acoustic waves
Experiments

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this

Lee, Chiang ; Shih, Chi Sheng ; Chen, Yaw Huei. / Optimizing large join queries using a graph-based approach. In: IEEE Transactions on Knowledge and Data Engineering. 2001 ; Vol. 13, No. 2. pp. 298-315.
@article{892b7505a59344aaaf7d3198b794b82f,
title = "Optimizing large join queries using a graph-based approach",
abstract = "Although many query tree optimization strategies have been proposed in the literature, there still is a lack of a formal and complete representation of all possible permutations of query operations (i.e., execution plans) in a uniform manner. A graph-theoretic approach presented in this paper provides a sound mathematical basis for representing a query and searching for an execution plan. In this graph model, a node represents an operation and a directed edge between two nodes indicates the order of executing these two operations in an execution plan. Each node is associated with a weight and so is an edge. The weight is an expression containing optimization required parameters, such as relation size, join selectivity factors. All possible execution plans are representable in this graph and each spanning tree of the graph becomes an execution plan. It is a general model which can be used in the optimizer of a DBMS for interal representation. On the basis of this model, we devise an algorithm that finds a near optimal execution plan using only polynomial time. The algorithm is compared with a few other popular optimization methods. Experiments show that the proposed algorithm is superior to the others under most circumstances.",
author = "Chiang Lee and Shih, {Chi Sheng} and Chen, {Yaw Huei}",
year = "2001",
month = "3",
day = "1",
doi = "10.1109/69.917567",
language = "English",
volume = "13",
pages = "298--315",
journal = "IEEE Transactions on Knowledge and Data Engineering",
issn = "1041-4347",
publisher = "IEEE Computer Society",
number = "2",

}

Optimizing large join queries using a graph-based approach. / Lee, Chiang; Shih, Chi Sheng; Chen, Yaw Huei.

In: IEEE Transactions on Knowledge and Data Engineering, Vol. 13, No. 2, 01.03.2001, p. 298-315.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Optimizing large join queries using a graph-based approach

AU - Lee, Chiang

AU - Shih, Chi Sheng

AU - Chen, Yaw Huei

PY - 2001/3/1

Y1 - 2001/3/1

N2 - Although many query tree optimization strategies have been proposed in the literature, there still is a lack of a formal and complete representation of all possible permutations of query operations (i.e., execution plans) in a uniform manner. A graph-theoretic approach presented in this paper provides a sound mathematical basis for representing a query and searching for an execution plan. In this graph model, a node represents an operation and a directed edge between two nodes indicates the order of executing these two operations in an execution plan. Each node is associated with a weight and so is an edge. The weight is an expression containing optimization required parameters, such as relation size, join selectivity factors. All possible execution plans are representable in this graph and each spanning tree of the graph becomes an execution plan. It is a general model which can be used in the optimizer of a DBMS for interal representation. On the basis of this model, we devise an algorithm that finds a near optimal execution plan using only polynomial time. The algorithm is compared with a few other popular optimization methods. Experiments show that the proposed algorithm is superior to the others under most circumstances.

AB - Although many query tree optimization strategies have been proposed in the literature, there still is a lack of a formal and complete representation of all possible permutations of query operations (i.e., execution plans) in a uniform manner. A graph-theoretic approach presented in this paper provides a sound mathematical basis for representing a query and searching for an execution plan. In this graph model, a node represents an operation and a directed edge between two nodes indicates the order of executing these two operations in an execution plan. Each node is associated with a weight and so is an edge. The weight is an expression containing optimization required parameters, such as relation size, join selectivity factors. All possible execution plans are representable in this graph and each spanning tree of the graph becomes an execution plan. It is a general model which can be used in the optimizer of a DBMS for interal representation. On the basis of this model, we devise an algorithm that finds a near optimal execution plan using only polynomial time. The algorithm is compared with a few other popular optimization methods. Experiments show that the proposed algorithm is superior to the others under most circumstances.

UR - http://www.scopus.com/inward/record.url?scp=0035272723&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035272723&partnerID=8YFLogxK

U2 - 10.1109/69.917567

DO - 10.1109/69.917567

M3 - Article

VL - 13

SP - 298

EP - 315

JO - IEEE Transactions on Knowledge and Data Engineering

JF - IEEE Transactions on Knowledge and Data Engineering

SN - 1041-4347

IS - 2

ER -