Optimizing large join queries using a graph-based approach

Chiang Lee, Chi Sheng Shih, Yaw Huei Chen

Research output: Contribution to journalArticlepeer-review

25 Citations (Scopus)


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
Issue number2
Publication statusPublished - 2001 Mar

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'Optimizing large join queries using a graph-based approach'. Together they form a unique fingerprint.

Cite this