WL#1074: Add Descending indexes support

Goal of this WL is to provide support for indexes in descending order. I.e
during forward index scan, values in such index are going in the descending
order, unlike ascending order which is supported by server now. There're two
reasons for this. First is often descending order is needed, but backward index
scan (which could be employed to execute queries in question) is noticeably
slower than forward index scan. Second reason is to be able to use indexes
instead of filesort for ORDER BY clause with mixed ASC/DESC sort key parts.

This WL will only support btree indexes. User would get an error when try to
create descending FTS / GIS index.

This WL should include:
*) Support in parser to allow to create indexes with DESC key parts. Parser
already allows DESC option, but simply ignores it
*) Enable SHOW commands to correctly report DESC key parts
*) Enable optimizer to detect when desc index could be used for ORDER BY
*) Enable optimizer to use indexes with mixed ASC/DESC keyparts when they
match ORDER BY clause
*) Indicate backward/forward index scans
*) Support for desc indexes in InnoDB (patch would be provided by InnoDB)
*) Support for range/loose index scans over indexes with DESC key parts

Limitations
-----------
*) An expected drawback that won't be covered by this WL is that when user has
two indexes, one ASC and another DESC over the same column, optimizer won't
necessary will be able to pick the right index. This is limitation of current
server architecture and planned to be addressed by WL#6179.
*) This WL won't add support for ROR scans over indexes with DESC key parts.
*) Backward range scans over indexes with mixed ASC/DESC key parts won't be
fully supported as they might require tricky reordering of ranges in order to
return record in proper order.
*) To limit the scope of the worklog, MIN/MAX optimization for queries without
GROUP BY is not performed for DESC keyparts.

Examples:
CREATE TABLE t1(
  a INT, b INT,
  KEY a_desc_b_asc (a DESC, b));

-- Should use (forward) index scan
SELECT * FROM t1 ORDER BY a DESC;

-- Should use backward index scan
SELECT * FROM t1 ORDER BY a ASC;

-- Should use (forward) index scan
SELECT * FROM t1 ORDER BY a DESC, b ASC;

-- Should use backward index scan
SELECT * FROM t1 ORDER BY a ASC, b DESC;

-- Should use filesort, not index
SELECT * FROM t1 ORDER BY a ASC, b ASC;

-- Should use filesort, not index
SELECT * FROM t1 ORDER BY a DESC, b DESC;


References
----------
Feature request: BUG#13375 Index with Desc sort feature

User Documentation
==================

* http://dev.mysql.com/doc/relnotes/mysql/8.0/en/news-8-0-1.html
* http://dev.mysql.com/doc/refman/8.0/en/descending-indexes.html

Functional requirements
-----------------------
f1) Server should allow to create indexes with desc key parts
f2) It should be allowed to create indexes with mixed asc/desc key parts,
e.g. an_index(a asc, b desc, c asc).
f3) Server should be able to use index with desc key parts in forward scan mode
when it matches ORDER BY clause, and in backward scan mode when it matches
opposite to ORDER BY clause, e.g:

-- should use forward scan on an_index defined above
  SELECT ... ORDER BY a ASC, b DESC

-- should use backward scan on an_index defined above
  SELECT ... ORDER BY a DESC, b ASC
f4) Only InnoDB should be fully supported, MyISAM would have limited support and
might have bugs that won't be fixed.
f5) SHOW commands that print index info (e.g SHOW CREATE TABLE) should print
DESC for key parts that were defined as DESC
f6) Both variants of EXPLAIN should print nothing for forward index scans and
"Backward index scan" for backward scans.
f7) DESC indexes should be supported for all data types, for which ASC indexes
are available.
f8) DESC indexes should be supported for both ordinary and both types of
generated columns.
f9) Attempt to add fulltext or spatial index with a desc keypart via
CREATE/ALTER should cause an error.
f10) GROUP BY no longer does implicit ordering. Order is taken into account
only for those columns, for which ASC/DESC is explicitly specified.
f11) DISTINCT could use any index containing matching columns.
f12) MIX/MAX optimization for queries with aggregates and no GROUP BY won't
use indexes with DESC key parts, to limit the scope of WL.

Non-functional requirements
---------------------------
nf1) An error should be thrown when creating a non-btree index with explicitly
specified ASC/DESC key parts (e.g GIS/FTS/HASH index), as those indexes are
naturally
unordered.

After this WL user should be able to do following
CREATE TABLE t1 (a INT, b INT, KEY a_idx(a DESC, b ASC));
INSERT INTO t1 VALUES(1,1),(2,2),(3,3);
SELECT * FROM t1 ORDER BY a DESC, b;
3 3
2 2 
1 1
and EXPLAIN will no longer print "Using filesort"
This means that an index with descending key part was created over the "t1"
table and server uses it in forward scan mode to retrieve values in
required order. Prior to this WL filesort is used.

DESC indexes may also be used for joins, GROUP BY and DISTINCT. In
these cases the optimizer will always use forward scan, independently
of index order and ASC/DESC flags specified in GROUP BY. It's acceptable, as
we deprecated any particular sort order after GROUP BY in 5.6 and such
approach would allow us to better use available indexes. Effectively this means
that order of rows may be different, compared to when an ASC index is used,
and this will affect some tests cases results.

Server already contains almost all necessary code to handle both ASC and DESC
indexes. In scope of this WL only small adjustments are made to take index
order into account. MyISAM also already supports desc indexes, no changes are 
needed there.

Biggest changes are:
*) Parser now saves DESC flag, instead of ignoring it
*) The order of key parts are stored in data dictionary
*) SHOW CREATE TABLE/SHOW INDEX code prints DESC for key parts having
descending order. For SHOW INDEX key part's order is indicated in the
Collation field, by "D" or "A" for DESC or ASC, respectively. Same is shown in
the information_schema.statistics table.
*)  Traditional EXPLAIN shows "Backward index scan" in the Extra field, when
backward index scan in used. Structured EXPLAIN shows "backward_index_scan: true"
to indicate that.
If forward scan is used, no additional information is printed.
*) Optimizer, at various places, takes sort order into account, e.g. when
comparing key values in key_rec_cmp().
*) Range optimizer to allow range scans over indexes with mixed ASC/DESC
keyparts
*) Since FTS/HASH/SPATIAL indexes are naturally unordered, usage of explicit
ASC/DESC on key parts of such indexes will result in error. This is a change in
behavior from 5.7 and potentially could break replication.

Changes to parser
=================
Key_part_spec now has is_ascending flag that indicates order of the key part.
Parser now sets it with Key_part_spec::set_ascending(), instead of ignoring
the given DESC flag. Key_part_spec::operator== also takes is_ascending into
account.

Changes in data dictionary
==========================
New DD already has methods to save/read DESC flag.
fill_dd_index_elements_from_key_parts() and fill_index_element_from_dd() are
taking care about saving/restoring the flag to/from DD.

Changes in range optimizer
==========================
Overall range optimizer algorithm is remained as is:
1) generate SEL_ARG tree
2) generate keys for range estimates, in sel_arg_range_seq_next()
3) collect estimates via handler API
4) generate keys for quick selects, in get_quick_keys()
5) do the range scan

This WL alters steps 2 and 4. In both steps 2 and 4 approach to DESC key parts
is the same: generally speaking, range optimizer uses max value from SEL_ARG
tree to generate min key for a desc key part and vice versa. Min/max flags are
also need to be "inverted" appropriately. Such "inversion" consists of changing
NO_MIN_RANGE/NEAR_MIN to NO_MAX_RANGE/NEAR_MAX appropriately, and vice versa.

This approach is implemented in several places:
1) SEL_ARG class: now it has is_ascending flag that indicates order direction
of the key part. Two new helper functions, get_min_flag()/get_max_flag(), are
returning min/max_flags according to value of is_ascending. E.g for ASC key
parts, get_min_flag() returns min_flag, for DESC key parts "inverted" max_flag
is returned. Same (but opposite) is done my get_max_flag(). The inversion
itself is done by two new helper functions, invert_min_flag() and
invert_max_flag(). 

SEL_ARG::store_min()/store_max() are renamed to SEL_ARG::store_min_value() and 
store_max_value() for easier reading.

SEL_ARG::store_min_key()/store_max_key() also take is_ascending into account
when recursing for a next key part.

Changes to SEL_ARG::stack_push_range(), sel_arg_range_seq_next() and 
get_quick_keys() are very similar - depending on is_ascending flag, for
storing start key they call either store_min/store_min_key (for ASC key part)
or store_max/store_max_key (for DESC key part). Same (but opposite) for end
key.

quick_range_seq_init() depending of whether the first key part is ASC or DESC,
this function will initialize traversal of ranges in forward, or backward
direction, to preserve order or records when multiple ranges are retrieved.
quick_range_seq_next() is adjusted appropriately.

Changes to loose index scan
===========================
LIS optimization for MIN()/MAX() aggregates supports indexes with DESC key
parts. Changes are made to QUICK_GROUP_MIN_MAX_SELECT::get_next() function.
Instead of updating MIN() on the first key and MAX() on the last, it
resets and updates both on the first key, and only updates both on the last.
The point is that it's unknown whether the first key will be min or max, so
both are updated and functions will pick appropriate value on their own.

Other changes
=============
As before, the order flag HA_REVERSE_SORT is stored in the
KEY_PART_INFO::key_part_flag and taken care of (in addition) at many places:
has_index_def_changed() - check key definitions to match
key_rec_cmp() - compare key values
find_key_for_maxmin() - block MIX/MAX optimization for DESC key parts
test_if_cheaper_ordering() - prefer forward scans over backward
check_duplicate_key() - compare keys definitions
mysql_prepare_create_table() - prepare info for table creation
mysql_prepare_alter_table() - prepare info for table alteration
store_create_info() - print info for SHOW CREATE TABLE
Explain_join::explain_extra() - reports backward scan for EXPLAIN