Previous topic  Top  Next topic  Print this Topic
 

Optimizing the Sequence of Body Literals in Rules

 

Uses sophisticated heuristics for optimizing the sequence of join operations, but sometimes the best heuristic is not able to find out the optimal join sequence for a specific query with specific rules. An example should illustrate this. Consider the following sequence of body literals in the rule:

QUERY q1: ?- ?P["inTournament"->?WM].

RULE r1: "P"["inTournament"->"WM"].

<-

 P:Player.                // 1000 tuples

 WM:Tournament        AND        // 25 tuples

 WM[match -> M] AND        // 30 tuples

 M[team -> T] AND        // 2 tuples

 T[lineup -> P] AND        // 11 tuples

However, this sequence is not the optimal join sequence as many tuples that are created e.g. by the "P:Player" literal are later discarded in join operations. So the following sequence strongly reduces this effect:

QUERY q1: ?- ?P["inTournament"->?WM].

RULE r1: "P"["inTournament"->"WM"].

<-

 WM:Tournament        AND        // 25 tuples

 WM[match -> M] AND        // 30 tuples

 M[team -> T] AND        // 2 tuples

 T[lineup -> P] AND        // 11 tuples

 P:Player.                // 1000 tuples

This is exactly the case where features like the cost model or the genetic optimizer come into play. Both features use different strategies to optimize the join sequence, but both are able to improve performance significantly.