Ticket #21 (new enhancement)

Opened 2 years ago

Last modified 2 years ago

HybridTuples should defer sort and support prefix-define/reresolve

Reported by: andrae Assigned to: andrae
Priority: major Milestone:
Component: Mulgara Version:
Keywords: Cc:

Description

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.

Considerations:

Reresolve - If HybridTuples argument is Reresolvable HybridTuples should support passing this argument through.

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.

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.