Cost-Controlled OFL Rewriting Rules for Multiple Collection Traversals.
Didier Chrétien, Fernando Machuca, Puthirak Om, Zhaohui Tang · 1996
The integration of path expression evaluations in an object-oriented cost-driven query optimizer is the subject of this paper. We present rewriting rules that transform path expressions into different object target programs (i.e., query execution plans). An analytical cost model is presented and used to compare the quality of various programs. We have used the OFL (Object Functional Language) traversal formalism to describe the rules. OFL is a target object language for OQL-like query compilers. By using the OFL formalism, the most efficient program corresponds to the best collection traversal. Experimental results when traversing multiple collections highlight the outperformance in some cases of ternary hash joins compared to classical binary hash join traversals. Binary and ternary joins are more responsive to the join selectivity than to the memory size. The results show that traversing path indexes are usually the most efficient traversals. Pipelined (i.e., one object at a time or ...