Project

General

Profile

Bug #15

Product of Sum form has very poor performance.

Added by Andrae Muys - almost 14 years ago. Updated about 12 years ago.

Status:
In Progress
Priority:
Normal
Assignee:
Category:
Mulgara
Target version:
-
Start date:
Due date:
% Done:

0%

Estimated time:
Resolution:

Description

[[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.
<br/>

<br/>
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.
<br/>

<br/>
Consider the following tuple expressions:
<br/>

<br/>
A[$z] ^ B( C[$z $y] v D[$y  $z] )
<br/>

<br/>
Note: 
<br/>
&nbsp;&nbsp;A[] will provide $z prefix to B[].  
<br/>
&nbsp;&nbsp;B[] currently passes this on blindly to C[] and D[].
<br/>
&nbsp;&nbsp;This will bind $z for $y in D[], leading to an incorrect result.
<br/>
&nbsp;&nbsp;Currently the non-union compatible
<br/>
&nbsp;&nbsp;Fixing this will require either reordering D[], or filtering it; deciding between them is a performance optimisation issue.
<br/>

<br/>
A[$y $z] ^ B(C[$y] v D[$z])
<br/>

<br/>
Note:
<br/>
&nbsp;&nbsp;Here there is a full prefix provided by A[] to B[].
<br/>
&nbsp;&nbsp;The prefix needs to be decomposed for C[] and D[]
<br/>
&nbsp;&nbsp;This is a case of non-union compatible disjunction, and will probably result in UNBOUND's.
<br/>

<br/>
Cases where this is probably a problem:
<br/>

<br/>
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;} )
<br/>
&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.
<br/>

<br/>
symmetric disjunctions: (ie. $s &lt;foo&gt; $o v $o &lt;bar&gt; $s). - uncommon.
<br/>

<br/>
non-union compatible disjunction (ie. $s &lt;name&gt; $name v $s &lt;email&gt; $email)
<br/>
&nbsp;&nbsp;Note: this query is better phrased as a subquery anyway.
#1

Updated by Andrae Muys - about 13 years ago

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.
#2

Updated by Andrae Muys - about 12 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