This patch adds cost estimation for the queries with ORDER BY / GROUP BY
and LIMIT. 
If there was a ref/range access to the table whose rows were required
to be ordered in the result set the optimizer always employed this access
though a scan by a different index that was compatible with the required 
order could be cheaper to produce the first L rows of the result set.
Now for such queries the optimizer makes a choice between the cheapest
ref/range accesses not compatible with the given order and index scans
compatible with it.

IN/BETWEEN predicates in sorting expressions.
Wrong results may occur when the select list contains an expression
with IN/BETWEEN predicate that differs from a sorting expression by
an additional NOT only.
 
Added the method Item_func_opt_neg::eq to compare correctly expressions
containing [NOT] IN/BETWEEN.
The eq method inherited from the Item_func returns TRUE when comparing
'a IN (1,2)' with 'a NOT IN (1,2)' that is not, of course, correct.  

 DATE/DATETIME values are out of the currently supported
 4 basic value types (INT,STRING,REAL and DECIMAL).
 So expressions (not fields) of compile type DATE/DATETIME are 
 generally considered as STRING values. This is not so
 when they are compared : then they are compared as 
 INTEGER values.
 But the rule for comparison as INTEGERS must be checked
 explicitly each time when a comparison is to be performed.
 filesort is one such place. However there the check was 
 not done and hence the expressions (not fields) of type 
 DATE/DATETIME were sorted by their string representation.
 Fixed to compare them as INTEGER values for filesort.

Functions over sum functions wasn't set up correctly for the ORDER BY clause
which leads to a wrong order of the result set.

The split_sum_func() function is called now for each ORDER BY item that
contains a sum function to set it up correctly.

"update existingtable set anycolumn=nonexisting order by nonexisting" would crash
the server.

Though we would find the reference to a field, that doesn't mean we can then use
it to set some values.  It could be a reference to another field.  If it is NULL, 
don't try to use it to set values in the Item_field and instead return an error.

Over the previous patch, this signals an error at the location of the error, rather
than letting the subsequent deref signal it.

 st_table::const_key_parts member is used in determining if
 certain key has a prefix that is compared to constant(s) in
 the query predicates.
 If there's such prefix the index can be used to get the data
 from the remaining suffix columns in sorted order.
 However if a field is compared to another field from a "const"
 table the const_key_parts is not amended.
 This makes the optimizer unable to detect that the key can be 
 used for sorting and adds an extra filesort.
 Fixed by updating const_key_parts after reading in the "const"
 table.

In the method Item_field::fix_fields we try to resolve the name of
the field against the names of the aliases that occur in the select
list. This is done by a call of the function find_item_in_list.
When this function finds several occurrences of the field name
it sends an error message to the error queue and returns 0.
Yet the code did not take into account that find_item_in_list
could return 0 and tried to dereference the returned value.

 The parser is allocating Item_field for references by name in ORDER BY
 expressions. Such expressions however may point not only to Item_field 
 in the select list (or to a table column) but also to an arbitrary Item. 
 This causes Item_field::fix_fields to throw an error about missing 
 column.
 The fix substitutes Item_field for the reference with an Item_ref when 
 not pointing to Item_field.

 - undeterminstic tests fixed

            on a second table in a join
- undeterministic output of the test case removed.

             table in a join
 The optimizer removes redundant columns in ORDER BY. It is considering 
redundant every reference to const table column, e.g b in :
create table t1 (a int, b int, primary key(a)); 
select 1 from t1 order by b where a = 1

But it must not remove references to const table columns if the 
const table is an outer table because there still can be 2 values :
the const value and NULL. e.g.:
create table t1 (a int, b int, primary key(a));
select t2.b c from t1 left join t1 t2 on (t1.a = t2.a and t2.a = 5) 
  order by c;

The bug caused wrong result sets for union constructs of the form
(SELECT ... ORDER BY order_list1 [LIMIT n]) ORDER BY order_list2.
For such queries order lists were concatenated and limit clause was
completely neglected. 

* Provide backwards compatibility extension to name resolution of
  coalesced columns. The patch allows such columns to be qualified
  with a table (and db) name, as it is in 4.1.
  Based on a patch from Monty.

* Adjusted tests accordingly to test both backwards compatible name
  resolution of qualified columns, and ANSI-style resolution of
  non-qualified columns.
  For this, each affected test has two versions - one with qualified
  columns, and one without. 

"Process NATURAL and USING joins according to SQL:2003".

* Some of the main problems fixed by the patch:
  - in "select *" queries the * expanded correctly according to
    ANSI for arbitrary natural/using joins
  - natural/using joins are correctly transformed into JOIN ... ON
    for any number/nesting of the joins.
  - column references are correctly resolved against natural joins
    of any nesting and combined with arbitrary other joins.

* This patch also contains a fix for name resolution of items
  inside the ON condition of JOIN ... ON - in this case items must
  be resolved only against the JOIN operands. To support such
  'local' name resolution, the patch introduces a stack of
  name resolution contexts used at parse time.

NOTICE:
- This patch is not complete in the sense that
  - there are 2 test cases that still do not pass -
    one in join.test, one in select.test. Both are marked
    with a comment "TODO: WL#2486".
  - it does not include a new test specific for the task

  Added test case for bug #7672 that existed only in 4.0.

  Added a test case for bug #7672.
sql_yacc.yy:
  Fixed bug #7672.
  Made queries of the form (SELECT ...) ORDER BY ... to
  be equivalent to SELECT ... ORDER BY ...

are not specified in an insert. Most of these changes are actually to
clean up the test suite to either specify defaults to avoid warnings,
or add the warnings to the results. Related to bug #5986.

The problem was that when a QUICK_SELECT access method is chosen,
test_if_skip_sort_order() discovered that the index being used
by the quick select will not deliver tuples in sorted order.
In this case test_if_skip_sort_order() tried to change the index
used by the quick select, but it didn't properly set the other
members of the quick select, and especially the range flags of
the ranges in QUICK_SELECT::ranges.

The fix re-invokes the function SQL_SELECT::test_quick_select
to correctly create a valid QUICK_SELECT object.

identical to another in result"
According to SQL standard queries like 
"select t1.a as col from t1, t2 order by a" should return an error if
both tables contain field a.

When in find_item_in_list() we are looking for item we should take into account unaliased 
names of the fields but only if item with such aliased name is not found.
Also we should ignore aliases when looking for fully specified field.

Fixes after last merge

  result of the test case for FORCE INDEX on ORDER BY
order_by.test:
  test case for FORCE INDEX on ORDER BY
sql_select.cc:
  Changing behaviour that MySQL server takes FORCE INDEX clause into account when optimising ORDER BY clause

Added test case for the bug #3155: strange results with index (x, y) ... WHERE x=val_1 AND y>=val_2 ORDER BY pk;
(thankee Monty)

null_ref_key moved to TABLE_REF.
new null range created if necessary.

Fixed bug in ORDER BY on a small column (Bug #2147)
Fixed error from pthread_mutex_destroy() when one had wrong errmsg file

Deprecate the use of TYPE=... Preferred syntax is ENGINE=

was used with NULL value on NOT NULL column. (Bug #479)

Added initialization of all important global variables

   Fixed bug 263
order_by.test:
  Fixed bug 263