WL#5558: Resolve ORDER BY execution method at the optimization stage.

Affects: Server-Prototype Only   —   Status: Complete

Currently the decision whether to sort the result dataset, or to use an index 
scan to get a sorted result is made during execution stage. 

Because of this info on ORDER BY shown by EXPLAIN is incorrect in many cases.

The goal of this WL is to move the decision on how to handle ORDER BY to the 
optimization stage. This is supposed to be a pure refactoring WL i.e it should
not change the current filesort cost model, nor wire the decision more deeply 
into the optimizer.

This should also fix BUG#1560.
The current usage of test_if_skip_sort_order() in context of JOIN::execute() and
'explain' should be moved into JOIN::optimize() instead. The decision taken in
JOIN::optimize() whether a GROUP/ORDER BY could 'skip' the filesort by using an
ordered index should be remembered as part of the 'struct JOIN' info.

Instead of calling test_if_skip.... inside JOIN::execute() and explain, we
should use the above 'skippable' info calculated during ::optimize() to decide
whether we will be 'Using filesort'. This code in both 'execute' and 'explain'
should use the same code pattern in order to ensure that we explain the same as
we are actually executing - which is a known problem with the current

We do not intent to change the cost model wrt. sort in this WL, hence there
should be no changed query plans as a result of this WL. However, there are 
known bugs where we do not correctly explain the query plan - These test results
will change as a result of this WL. Such changes should be expected for queries

As JOIN::execute() will now not 'change its mind' wrt. using an ordered index or
not, there are code in this method which now is obsolete. This is related to how
the 'pre_idx_push_cond' (used by ICP) had to be updated in case
test_if_skip_sort_order() changed the execution plan. However, we will not
remove that code as part of this WL. Instead, this has been marked with 
a 'TODO' such that it may be considered for removal later.
Prior to commiting the implementation of this WL, several defects related to
test_if_skip_sort_order() and its family of utility functions was identified.
These defects caused the explained query plan to be affected, and 
also the result set in some cases.

In order to isolate the effect of this WL itself, these bugs were fixed prior
to implementing WL5558, and as such this WL depends on these fixes:

 - bug 13514959: query plan fails to 'using index' where it should.
 - bug 13528826: test_if_cheaper_ordering(): calculates incorrect
 - bug 13529048: test_if_skip_sort_order() don't have to filesort
                 a single row.
 - bug 13531865: test_if_skip_sort_order() incorrectly skip 
                 filesort if 'type' is ref_or_null.

It would therefore be a good idea to review these fixes before starting to
review this WL as they are highly related