Optimizing large join queries using a graph-based approach

Chiang Lee, Chi Sheng Shih, Yaw Huei Chen

研究成果: Article同行評審

18 引文 斯高帕斯(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.

頁(從 - 到)298-315
期刊IEEE Transactions on Knowledge and Data Engineering
出版狀態Published - 2001 3月

All Science Journal Classification (ASJC) codes

  • 資訊系統
  • 電腦科學應用
  • 計算機理論與數學


深入研究「Optimizing large join queries using a graph-based approach」主題。共同形成了獨特的指紋。