The fixes for #643424 was part of the fix for #652727, that's why both
fixes are pushed together.

- The cause for #643424 was the improper use of get_partial_join_cost(),
  which assumed that the 'n_tables' parameter was the upper bound for
  query plan node indexes.
  Fixed by generalizing get_partial_join_cost() as a method that computes
  the cost of any partial join.

- The cause of #652727 was that JOIN::choose_subquery_plan() incorrectly
  deleted the contents of the old keyuse array in the cases when an injected
  plan would not provide more key accesses, and reoptimization was not actually
  performed.

Added missing logic to handle the case when subquery tables are optimized
away early during optimization.

- Added more tests to the MWL#89 specific test, and made the test more modular.
- Updated test files.
- Fixed a memory leak.
- More comments.

mysql-test/r/subselect_mat.result:
  - Updated the test file to reflect the new optimizer switches related to
    materialized subquery execution.
  - Added one extra test to test all cases that expose BUG#40037 (this is an old bug from 5.x).
  - Updated the test result with correct results that expose BUG#40037.
mysql-test/t/subselect_mat.test:
  - Updated the test file to reflect the new optimizer switches related to
    materialized subquery execution.
  - Added one extra test to test all cases that expose BUG#40037 (this is an old bug from 5.x).
  - Updated the test result with correct results that expose BUG#40037.
sql/sql_select.cc:
  Fixed a memory leak reported by Valgrind.

- Changed the default optimizer switches to provide 5.1/5.2 compatible behavior
- Added a regression test file to test consistently all cases covered by MWL#89
- Added/corrected/improved comments.

Added/corrected/improved comments.

Improved handling of EXPLAIN statements for subqueries.
This patch specifically solves the problem when EXPLAIN reports:
  "const row not found"
instead of
  "no matching row in const table".

  Phase 3: Implementation of re-optimization of subqueries with injected predicates
           and cost comparison between Materialization and IN->EXISTS strategies.

The commit contains the following known problems:
- The implementation of EXPLAIN has not been re-engineered to reflect the
  changes in subquery optimization. EXPLAIN for subqueries is called during
  the execute phase, which results in different code paths during JOIN::optimize
  and thus in differing EXPLAIN messages for constant/system tables.
- There are some valgrind warnings that need investigation
- Several EXPLAINs with minor differences need to be reconsidered after fixing
  the EXPLAIN problem above.

This patch also adds one extra optimizer_switch: 'in_to_exists' for complete
manual control of the subquery execution strategies.

* Fixed a "crack" between semijoin analysis and materialization analysis
  where semijoin didn't set the correct strategy for the IN predicate.

* Cosmetic changes in the code/comments.

  
Reset correctly the LIMIT and the uncacheable flag of a subquery when executing
it via materialization.

- Corrected a wrong result that was recorded by the MySQL fix for BUG#39069.

- Removed Item_func_isnull::cached_value and all the logic around this custom-made
  caching of the NULL result because MWL#89 optimizes subqueries before the outer
  query is being executed, and this cache cannot be made easily to work for all
  kinds of Items (specifically Item_sum_sum, but others too).

Fixed a crash in Item_equal::fix_length_and_dec that was a result of the
architecture of the MWL#89 subquery optimization.

The injection of IN->EXISTS predicates for subqueries happened inside
make_join_statistics, after constant substitution, but before multiple
equality substitution done by substitute_for_best_equal_field. As a
result, when we called fix_fields for the WHERE clause after the injection
of IN->EXISTS predicates, Item_equal was not fixed, and it was in a state
not anticipated by Item_equal::fix_length_and_dec - the Item_equal
containted only a constant, and no fields at all.

The fix takes into account this new possible state when calling fix_fields.

Fixes for multiple problems/bugs/test failures that resulted from moving
subquery optimization from the execution phase to the optimization phase.

  
Step2 in the separation of the creation of IN->EXISTS equi-join conditions from
their injection. The goal of this separation is to make it possible that the
IN->EXISTS conditions can be used for cost estimation without actually modifying
the subquery.
  
This patch separates row_value_in_to_exists_transformer() into two methods:
- create_row_value_in_to_exists_cond(), and
- inject_row_value_in_to_exists_cond()
The patch performs minimal refactoring of the code so that it is easier to solve
problems resulting from the separation. There is a lot to be simplified in this
code, but this will be done separately.

Step1 in the separation of the creation of IN->EXISTS equi-join conditions from
their injection. The goal of this separation is to make it possible that the
IN->EXISTS conditions can be used for cost estimation without actually modifying
the subquery.

This patch separates single_value_in_to_exists_transformer() into two methods:
- create_single_value_in_to_exists_cond(), and
- inject_single_value_in_to_exists_cond()
The patch performs minimal refactoring of the code so that it is easier to solve
problems resulting from the separation. There is a lot to be simplified in this
code, but this will be done separately.

was not cleaned up between PS re-executions. The reason was two-fold:
- a merge with mysql-6.0 missed select_union::cleanup() that should
  have cleaned up the temp table, and
- the subclass of select_union used by materialization didn't call
  the base class cleanup() method.

1. Changed the lazy optimization for subqueries that can be
   materialized into bottom-up optimization during the optimization of
   the main query.

   The main change is implemented by the method
   Item_in_subselect::setup_engine.
  
   All other changes were required to correct problems resulting from
   changing the order of optimization. Most of these problems followed
   the same pattern - there are some shared structures between a
   subquery and its parent query. Depending on which one is optimized
   first (parent or child query), these shared strucutres may get
   different values, thus resulting in an inconsistent query plan.

2. Changed the code-generation for subquery materialization to be
   performed in runtime memory for each (re)execution, instead of in
   statement memory (once per prepared statement).
   - Item_in_subselect::setup_engine() no longer creates materialization
     related objects in statement memory.
   - Merged subselect_hash_sj_engine::init_permanent and
     subselect_hash_sj_engine::init_runtime into
     subselect_hash_sj_engine::init, which is called for each
     (re)execution.
   - Fixed deletion of the temp table accordingly.


mysql-test/r/subselect_mat.result:
  Adjusted changed EXPLAIN because of earlier optimization of subqueries.

- Let "mysqld  --help --verbose" list all optimizer options
- Make it possible to add new @@optimizer_switch flags w/o causing .result 
  changes all over the testsuite:
  = Remove "select @@optimizer_switch" from tests that do not need all switches
  = Move @@optimizer_switch-specific tests to t/optimizer_switch.test

Updated configure.in to have version 5.3

configure.in:
  Updated to version 5.3.0

Improved speed of thr_alarm from O(N) to O(1). thr_alarm is used to handle timeouts and kill of connections.
Fixed compiler warnings.
queues.h and queues.c are now based on the UNIREG code and thus made BSD.
Fix code to use new queue() interface. This mostly affects how you access elements in the queue.
If USE_NET_CLEAR is not set, don't clear connection from unexpected characters. This should give a speed up when doing a lot of fast queries.
Fixed some code in ma_ft_boolean_search.c that had not made it from myisam/ft_boolean_search.c


include/queues.h:
  Use UNIREG code base (BSD)
  Changed init_queue() to take all initialization arguments.
  New interface to access elements in queue
include/thr_alarm.h:
  Changed to use time_t instead of ulong (portability)
  Added index_in_queue, to be able to remove random element from queue in O(1)
mysys/queues.c:
  Use UNIREG code base (BSD)
  init_queue() and reinit_queue() now takes more initialization arguments. (No need for init_queue_ex() anymore)
  Now one can tell queue_insert() to store in the element a pointer to where element is in queue. This allows one to remove elements from queue in O(1) instead of O(N)
mysys/thr_alarm.c:
  Use new option in queue() to allow fast removal of elements.
  Do less inside LOCK_alarm mutex.
  This should give a major speed up of thr_alarm usage when there is many threads
sql/create_options.cc:
  Fixed wrong printf
sql/event_queue.cc:
  Use new queue interface()
sql/filesort.cc:
  Use new queue interface()
sql/ha_partition.cc:
  Use new queue interface()
sql/ha_partition.h:
  Fixed compiler warning
sql/item_cmpfunc.cc:
  Fixed compiler warning
sql/item_subselect.cc:
  Use new queue interface()
  Removed not used variable
sql/net_serv.cc:
  If USE_NET_CLEAR is not set, don't clear connection from unexpected characters.
  This should give a speed up when doing a lot of fast queries at the disadvantage that if there is a bug in the client protocol the connection will be dropped instead of being unnoticed.
sql/opt_range.cc:
  Use new queue interface()
  Fixed compiler warnings
sql/uniques.cc:
  Use new queue interface()
storage/maria/ma_ft_boolean_search.c:
  Copy code from myisam/ft_boolean_search.c
  Use new queue interface()
storage/maria/ma_ft_nlq_search.c:
  Use new queue interface()
storage/maria/ma_sort.c:
  Use new queue interface()
storage/maria/maria_pack.c:
  Use new queue interface()
  Use queue_fix() instead of own loop to fix queue.
storage/myisam/ft_boolean_search.c:
  Use new queue interface()
storage/myisam/ft_nlq_search.c:
  Use new queue interface()
storage/myisam/mi_test_all.sh:
  Remove temporary file from last run
storage/myisam/myisampack.c:
  Use new queue interface()
  Use queue_fix() instead of own loop to fix queue.
storage/myisam/sort.c:
  Use new queue interface()
storage/myisammrg/myrg_queue.c:
  Use new queue interface()
storage/myisammrg/myrg_rnext.c:
  Use new queue interface()
storage/myisammrg/myrg_rnext_same.c:
  Use new queue interface()
storage/myisammrg/myrg_rprev.c:
  Use new queue interface()

range plans with identical costs.

subquery execution, where the the REF buffer format was mistaken to
be in record format instead of key format. The error was that the null
byte for all fields of the record was in the front of the buffer,
and not before each field data.

libmysqld/Makefile.am:
  The new file added.
mysql-test/r/index_merge_myisam.result:
  subquery_cache optimization option added.
mysql-test/r/myisam_mrr.result:
  subquery_cache optimization option added.
mysql-test/r/subquery_cache.result:
  The subquery cache tests added.
mysql-test/r/subselect3.result:
  Subquery cache switched off to avoid changing read statistics.
mysql-test/r/subselect3_jcl6.result:
  Subquery cache switched off to avoid changing read statistics.
mysql-test/r/subselect_no_mat.result:
  subquery_cache optimization option added.
mysql-test/r/subselect_no_opts.result:
  subquery_cache optimization option added.
mysql-test/r/subselect_no_semijoin.result:
  subquery_cache optimization option added.
mysql-test/r/subselect_sj.result:
  subquery_cache optimization option added.
mysql-test/r/subselect_sj_jcl6.result:
  subquery_cache optimization option added.
mysql-test/t/subquery_cache.test:
  The subquery cache tests added.
mysql-test/t/subselect3.test:
  Subquery cache switched off to avoid changing read statistics.
sql/CMakeLists.txt:
  The new file added.
sql/Makefile.am:
  The new files added.
sql/item.cc:
  Expression cache item (Item_cache_wrapper) added.
  Item_ref and Item_field fixed for correct usage of result field and fast resolwing in SP.
sql/item.h:
  Expression cache item (Item_cache_wrapper) added.
  Item_ref and Item_field fixed for correct usage of result field and fast resolwing in SP.
sql/item_cmpfunc.cc:
  Subquery cache added.
sql/item_cmpfunc.h:
  Subquery cache added.
sql/item_subselect.cc:
  Subquery cache added.
sql/item_subselect.h:
  Subquery cache added.
sql/item_sum.cc:
  Registration of subquery parameters added.
sql/mysql_priv.h:
  subquery_cache optimization option added.
sql/mysqld.cc:
  subquery_cache optimization option added.
sql/opt_range.cc:
  Fix due to subquery cache.
sql/opt_subselect.cc:
  Parameters of the function cahnged.
sql/procedure.h:
  .h file guard added.
sql/sql_base.cc:
  Registration of subquery parameters added.
sql/sql_class.cc:
  Option to allow add indeces to temporary table.
sql/sql_class.h:
  Item iterators added.
  Option to allow add indeces to temporary table.
sql/sql_expression_cache.cc:
  Expression cache for caching subqueries added.
sql/sql_expression_cache.h:
  Expression cache for caching subqueries added.
sql/sql_lex.cc:
  Registration of subquery parameters added.
sql/sql_lex.h:
  Registration of subqueries and subquery parameters added.
sql/sql_select.cc:
  Subquery cache added.
sql/sql_select.h:
  Subquery cache added.
sql/sql_union.cc:
  A new parameter to the function added.
sql/sql_update.cc:
  A new parameter to the function added.
sql/table.cc:
  Procedures to manage temporarty tables index added.
sql/table.h:
  Procedures to manage temporarty tables index added.
storage/maria/ha_maria.cc:
  Fix of handler to allow destoy a table in case of error during the table creation.
storage/maria/ha_maria.h:
  .h file guard added.
storage/myisam/ha_myisam.cc:
  Fix of handler to allow destoy a table in case of error during the table creation.

- Item_in_subselect::init_left_expr_cache() should not try to 
  guess whether the left expression is accessed "over the grouping operation"
  (i.e. the subselect is evaluated after the grouping while the left_expr is
   an Item_ref that wraps an expression from before the grouping). Instead, 
  let new_Cached_item not to try accessing item->real_item() when creating 
  left expr cache.

join cache module.
Without these calls SELECTs over tables with virtual columns
that used join cache could return wrong results. This could
be seen with the test case added into vcol_misc.test 

  field->pack_length() bytes.

5.3 had 

 handler::index_only_read_time(uint keynr, double records)

while 5.2 got:

 handler::keyread_read_time(uint index, uint ranges, ha_rows rows)

which causes floor()'ing of rows parameter, which makes all further costs different.

- fix a bug in LooseScan strategy execution code (exposed by changing costs/QEP)
- Do set join_tab->sorted=TRUE for JOIN_TABs that use LooseScan (partitioning 
   handler cares about "sorted" parameter of h->index_init() call)

create st_maria_plugin declarations of new xtradb I_S tables

* remove handler::index_read_last()
* create handler::keyread_read_time() (was get_index_only_read_time() in opt_range.cc)
* ha_show_status() allows engine's show_status() to fail
* remove HTON_FLUSH_AFTER_RENAME
* fix key_cmp_if_same() to work for floats and doubles
* set table->status in the server, don't force engines to do it
* increment status vars in the server, don't force engines to do it

mysql-test/r/status_user.result:
  correct test results - innodb was wrongly counting internal
  index searches as handler_read_* calls.
sql/ha_partition.cc:
  compensate for handler incrementing status counters -
  we want to count only calls to underlying engines
sql/handler.h:
  inline methods moved to sql_class.h
sql/key.cc:
  simplify the check
sql/opt_range.cc:
  move get_index_only_read_time to the handler class
sql/sp.cc:
  don't use a key that's stored in the record buffer -
  the engine can overwrite the buffer with anything, destroying the key
sql/sql_class.h:
  inline handler methods that need to see THD and TABLE definitions
sql/sql_select.cc:
  no ha_index_read_last_map anymore
sql/sql_table.cc:
  remove HTON_FLUSH_AFTER_RENAME
sql/table.cc:
  set HA_CAN_MEMCMP as appropriate
sql/tztime.cc:
  don't use a key that's stored in the record buffer -
  the engine can overwrite the buffer with anything, destroying the key
storage/myisam/ha_myisam.cc:
  engines don't need to update table->status or use ha_statistic_increment anymore
storage/myisam/ha_myisam.h:
  index_read_last_map is no more