Feature #21

HybridTuples should defer sort and support prefix-define/reresolve

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

Status:New Start date:
Priority:High Due date:
Assignee:Andrae Muys - % Done:

0%

Category:Mulgara
Target version:-
Resolution:

Description

 1 Currently [[HybridTuples]] performs it's sort when it is constructed.  This forces the evaluation of its argument before join-optimisation has an opportunity to specify a desired prefix or reresolve.  [[HybridTuples]] should defer it's sort until at least the first call to beforeFirst.
 2 <br/>
 3 
 4 <br/>
 5 Considerations:
 6 <br/>
 7 
 8 <br/>
 9 Reresolve - If [[HybridTuples]] argument is Reresolvable [[HybridTuples]] should support passing this argument through.
10 <br/>
11 
12 <br/>
13 [[DefinablePrefix]] - If our argument is unordered then a projection is free, so we should expose this to the join optimisation.  However note that if we are only sorting once, then we cannot pass this call through to the argument.  Rather we should project the argument to maximise the prefix length available.  
14 <br/>
15 
16 <br/>
17 Single vs. Multiple sorts - A sort is O(nlogn), and a n from m prefix is O((0 from m)^((n - m) / m)).  If we can increase the prefix length sufficiently to pay for the cost of the extra sorts we should resort on each call to beforeFirst().  Note that if the argument is itself prefix-definable then the cost of a sort is in terms of the estimated reduced length.

Also available in: Atom PDF