Declarative Query Tuning and Optimization using Answer Set Programming
Yuliya Lierler and Philip Cannata · 2010
In [2, Chapter 14], Lewis describes the basics behind the procedure used by the oracle query optimizer for computing the optimal join order for a sample query. Given a set T of n pairs table:cost, a join order is a full binary tree such that (i) T is the set of its leaves, (ii) the right child of an inner node is a leaf, and (iii) each inner node is a pair join tag:cost where join tag is either nestedloop (nl), sort-merge (sm), or hash (ha), and cost is defined recursively using its children’s costs and its join tag. Requirement (ii) ensures that a join order is a left-deep tree [5]. The join order cost is the sum of the costs of its inner nodes. The optimal join order is an order with the minimal cost. Figure 1 (a) illustrates a sample join order for a set {c:2517, p:631, gp:127, ggp:64} of pairs, which expresses that the tables gp and p are joined first, then the resulting table is joined with c, and at last the table ggp is joined. An nl join is used for each of the three joins. The join order cost is 360 = 347 + 12 + 1.