Ticket #15 (assigned defect)

Opened 2 years ago

Last modified 6 months ago

Product of Sum form has very poor performance.

Reported by: andrae Assigned to: andrae (accepted)
Priority: minor Milestone:
Component: Mulgara Version: 1.0.1
Keywords: Cc:

Description (Last modified by andrae)

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.

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.

Consider the following tuple expressions:

A[$z] ^ B( C[$z $y] v D[$y $z] )

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

A[$y $z] ^ B(C[$y] v D[$z])

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

Cases where this is probably a problem:

non-symmetric sum-of-products (ie. {$a <foo> $b ^ $b <bar> $c in <m1>} v {$b <bar> $c ^ $a <foo> $b in <m2>} )
  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.

symmetric disjunctions: (ie. $s <foo> $o v $o <bar> $s). - uncommon.

non-union compatible disjunction (ie. $s <name> $name v $s <email> $email)
  Note: this query is better phrased as a subquery anyway.

Change History

05/14/07 21:47:10 changed by andrae

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.

05/19/08 01:24:24 changed by andrae

  • status changed from new to assigned.
  • description changed.
  • summary changed from OrderedAppend needs to check variable orderings for arguments before passing prefix. TuplesOperations.append() needs to defer variable mapping to OrderedAppend. to Product of Sum form has very poor performance..

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