Bug #15

Product of Sum form has very poor performance.

Added by Andrae Muys - over 12 years ago. Updated almost 11 years ago.

Status:In Progress Start date:
Priority:Normal Due date:
Assignee:Andrae Muys - % Done:


Target version:-


 1 [[OrderedAppend]] currently assumes that all it's operands share a common ordering.  This is currently guarenteed by [[TuplesOperations]].append(), but the use of calls to project() on all operands not matching the first's variable list.  This has signifigant performance ramifications as the desired ordering is unknown until any parent-join is optimised.
 2 <br/>
 4 <br/>
 5 Without the projections currently done by [[TuplesOperations]].append(), we need new logic in [[OrderedAppend]] to handle mapping variables to operands columns.  This is not a problem unless there the disjunction is subject to a join containing a left-bound prefix including mismatched variables.
 6 <br/>
 8 <br/>
 9 Consider the following tuple expressions:
10 <br/>
12 <br/>
13 A[$z] ^ B( C[$z $y] v D[$y  $z] )
14 <br/>
16 <br/>
17 Note: 
18 <br/>
19 &nbsp;&nbsp;A[] will provide $z prefix to B[].  
20 <br/>
21 &nbsp;&nbsp;B[] currently passes this on blindly to C[] and D[].
22 <br/>
23 &nbsp;&nbsp;This will bind $z for $y in D[], leading to an incorrect result.
24 <br/>
25 &nbsp;&nbsp;Currently the non-union compatible
26 <br/>
27 &nbsp;&nbsp;Fixing this will require either reordering D[], or filtering it; deciding between them is a performance optimisation issue.
28 <br/>
30 <br/>
31 A[$y $z] ^ B(C[$y] v D[$z])
32 <br/>
34 <br/>
35 Note:
36 <br/>
37 &nbsp;&nbsp;Here there is a full prefix provided by A[] to B[].
38 <br/>
39 &nbsp;&nbsp;The prefix needs to be decomposed for C[] and D[]
40 <br/>
41 &nbsp;&nbsp;This is a case of non-union compatible disjunction, and will probably result in UNBOUND's.
42 <br/>
44 <br/>
45 Cases where this is probably a problem:
46 <br/>
48 <br/>
49 non-symmetric sum-of-products  (ie. {$a &lt;foo&gt; $b ^ $b &lt;bar&gt; $c in &lt;m1&gt;} v {$b &lt;bar&gt; $c ^ $a &lt;foo&gt; $b in &lt;m2&gt;} )
50 <br/>
51 &nbsp;&nbsp;Note: this is one of the key areas of concern.  Differences between models can cause join-optimisation to generate a different ordering; This interferes with attempts to improve SOP performance which is required to support efficient views.
52 <br/>
54 <br/>
55 symmetric disjunctions: (ie. $s &lt;foo&gt; $o v $o &lt;bar&gt; $s). - uncommon.
56 <br/>
58 <br/>
59 non-union compatible disjunction (ie. $s &lt;name&gt; $name v $s &lt;email&gt; $email)
60 <br/>
61 &nbsp;&nbsp;Note: this query is better phrased as a subquery anyway.


Updated by Andrae Muys - almost 12 years ago

1 With the NUC-disj fixes the workaround for this bug has been implemented - the performance considerations remain.  With the workaround merged to trunk this bug is downgraded from major to minor.

Updated by Andrae Muys - almost 11 years ago

  • Status changed from New to In Progress

Original Topic: OrderedAppend needs to check variable orderings for arguments before passing prefix. TuplesOperations.append() needs to defer variable mapping to OrderedAppend.

Also available in: Atom PDF