Type: New Feature
Affects Version/s: None
Fix Version/s: None
Component/s: Query Engine
There is some excellent work by the MonetDB people on Runtime Optimization for XQuery (ROX) [1,2]. Query optimization is basically dynamic programming. ROX is basically incremental dynamic programming, which has been well studied in other areas. The advantage of ROX is that it is robust under a very wide variety of queries and does not requiring maintenance of additional information, such as chain histograms. Instead, good query plans are discovered by sampling permutations of the remaining joins based on the initial joins. The initial joins are chosen based on ground truth estimates of the cardinality of the access paths demanded by the various joins (that is, by index range count operations).
Unlike MonetDB, bigdata using a pipelined join algorithm and is a parallel (aka distributed) database doing shard-wise processing. Therefore the implementation strategy would necessarily be somewhat different from ROX. However, since ROX appears to be relatively robust to front-bias in sampling, it should be simple enough to perform runtime query optimization once the initial intermediate solutions arrive at the first join with a dependency on upstream variable bindings. At that point, one or more node(s) with a partial result set for the query can sample various permutations of the remaining joins. This process proceeds incrementally, making a decision on the (n+1)th join once the samples clearly predict a minimum cost over the possible next join. Those estimates need to be based on the cost to a full solution (which could have some bias as indices warm up). Once the (n+1)th join is decided, it can be executed and the process repeats once initial solutions arrive at the downstream node(s). If more than one node does runtime optimization, then those nodes must coordinate in order to arrive at a decision on the minimum cost for the next join step. Because runtime optimization is integrated with the pipeline join and occurs while the previous join is still being executed, the latency should disappear entirely for all but the simplest of queries.
Related tickets include:
- http://sourceforge.net/apps/trac/bigdata/ticket/258 (Integrate RTO into SAIL)
- http://sourceforge.net/apps/trac/bigdata/ticket/257 (Support BOP fragments in the RTO)
- http://sourceforge.net/apps/trac/bigdata/ticket/259 (Dynamically increase RTO sampling limit)
- http://sourceforge.net/apps/trac/bigdata/ticket/256 (Amortize RTO cost)