Optimizing large join queries using a graph-based approach

doi:10.1109/69.917567

Optimizing large join queries using a graph-based approach

2001-01-01

31

PRE

AI

C

Chi‐Sheng Shih

DOI：10.1109/69.917567

Original

Original request for help

Save

Abstract

En 中文

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, tuple 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 query 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.

Keywords:

large join query

graph theory

join cost

query tree

query optimization

Optimizing large join queries using a graph-based approach

Abstract

AI Summary

Journal

Organization