MWL#68 Subquery optimization: Efficient NOT IN execution with NULLs

This patch implements correct NULL semantics for materialized subquery execution.
The implementation has the following properties and main limitations:
- It passes all query result tests, but fails a number of EXPLAIN tests because of
  changed plans.
- The EXPLAIN output for partial matching is not decided yet.
- It works only when all necessary indexes fit into main memory. Notice that these
  are not the general B-tree/Hash indexes, but instead much more compact ones,
  therefore this limitation may not be a problem in many practical cases.
- It doesn't contain specialized tests.
- In several places the implementation uses methods that are modified copies of
  other similar methods. These cases need to be refactored to avoid code duplication.
- Add a test if the predicate is top-level just before deciding on partial matching.
  If it is top-level, use a more efficient exec method (index lookup).
- Add sorting of indexes according to their selectivity. The code is almost there.
- Needs more comments, and to sync existing ones with the implementation.

sql/item_cmpfunc.h:
  Expose the Arg_comparator of a comparison predicate. This makes it possible to
  directly get the comparison result {-1,0,1}, which is not possible through the
  val_XXX() methods which "fold" such results into a boolean.
sql/item_subselect.cc:
  The core of the implementation of MWL#68.
sql/item_subselect.h:
  The core of the implementation of MWL#68.
sql/opt_subselect.cc:
  Removed the limitation for materialized subquery execution that it is applicable only
  for top-level predicates.
sql/sql_class.cc:
  New class select_materialize_with_stats that collects data statistics about
  the data being inserted into the target table.
sql/sql_class.h:
  New class select_materialize_with_stats that collects data statistics about
  the data being inserted into the target table.
sql/sql_select.cc:
  - more complete initialization of the TABLE object of a temp table.
  - call setup_subquery_materialization at one more exit point.

1 files changed, 4 insertions, 9 deletions

diff --git a/sql/opt_subselect.cc b/sql/opt_subselect.cc
index a1d0111d743..0c91f84cd0c 100644
--- a/sql/opt_subselect.cc
+++ b/sql/opt_subselect.cc
@@ -187,11 +187,7 @@ int check_and_do_in_subquery_rewrites(JOIN *join)
              does not call setup_subquery_materialization(). We could make 
              SELECT ... FROM DUAL call that function but that doesn't seem
              to be the case that is worth handling.
-        4. Subquery predicate is a top-level predicate
-           (this implies it is not negated)
-           TODO: this is a limitation that should be lifted once we
-           implement correct NULL semantics (WL#3830)
-        5. Subquery is non-correlated
+        4. Subquery is non-correlated
            TODO:
            This is an overly restrictive condition. It can be extended to:
            (Subquery is non-correlated ||
@@ -199,7 +195,7 @@ int check_and_do_in_subquery_rewrites(JOIN *join)
             (Subquery is correlated to the immediate outer query &&
              Subquery !contains {GROUP BY, ORDER BY [LIMIT],
              aggregate functions}) && subquery predicate is not under "NOT IN"))
-        6. No execution method was already chosen (by a prepared statement).
+        5. No execution method was already chosen (by a prepared statement).
 
         (*) The subquery must be part of a SELECT statement. The current
              condition also excludes multi-table update statements.
@@ -218,9 +214,8 @@ int check_and_do_in_subquery_rewrites(JOIN *join)
           subquery_types_allow_materialization(in_subs))
       {
         // psergey-todo: duplicated_subselect_card_check: where it's done?
-        if (in_subs->is_top_level_item() &&                             // 4
-            !in_subs->is_correlated &&                                  // 5
-            in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
+        if (!in_subs->is_correlated &&                                  // 4
+            in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 5
           in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
       }