5.3 merge

1 files changed, 279 insertions, 86 deletions

diff --git a/sql/sql_select.h b/sql/sql_select.h
index 4b5e2903c1d..644828fa08c 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -2,7 +2,7 @@
 #define SQL_SELECT_INCLUDED
 
 /* Copyright (c) 2000, 2011, Oracle and/or its affiliates.
-   Copyright (c) 2010, 2011, Monty Program Ab
+   Copyright (c) 2008-2011 Monty Program Ab
 
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
@@ -84,6 +84,8 @@ typedef struct keyuse_t {
   bool is_for_hash_join() { return is_hash_join_key_no(key); }
 } KEYUSE;
 
+#define NO_KEYPART ((uint)(-1))
+
 class store_key;
 
 const int NO_REF_PART= uint(-1);
@@ -165,6 +167,17 @@ enum enum_nested_loop_state
 };
 
 
+/* Possible sj_strategy values */
+enum sj_strategy_enum
+{
+  SJ_OPT_NONE=0,
+  SJ_OPT_DUPS_WEEDOUT=1,
+  SJ_OPT_LOOSE_SCAN  =2,
+  SJ_OPT_FIRST_MATCH =3,
+  SJ_OPT_MATERIALIZE =4,
+  SJ_OPT_MATERIALIZE_SCAN=5
+};
+
 /* Values for JOIN_TAB::packed_info */
 #define TAB_INFO_HAVE_VALUE 1
 #define TAB_INFO_USING_INDEX 2
@@ -278,7 +291,16 @@ typedef struct st_join_table {
   double        partial_join_cardinality;
 
   table_map	dependent,key_dependent;
-  uint		use_quick,index;
+  /*
+     1 - use quick select
+     2 - use "Range checked for each record"
+  */
+  uint		use_quick;
+  /*
+    Index to use. Note: this is valid only for 'index' access, but not range or
+    ref access.
+  */
+  uint          index;
   uint		status;				///< Save status for cache
   uint		used_fields;
   ulong         used_fieldlength;
@@ -326,6 +348,8 @@ typedef struct st_join_table {
   /* Variables for semi-join duplicate elimination */
   SJ_TMP_TABLE  *flush_weedout_table;
   SJ_TMP_TABLE  *check_weed_out_table;
+  /* for EXPLAIN only: */
+  SJ_TMP_TABLE  *first_weedout_table;
   
   /*
     If set, means we should stop join enumeration after we've got the first
@@ -370,7 +394,7 @@ typedef struct st_join_table {
     POSITION::sj_strategy field. This field is set up by the
     fix_semijoin_strategies_for_picked_join_order.
   */
-  uint sj_strategy;
+  enum sj_strategy_enum sj_strategy;
 
   uint n_sj_tables;
 
@@ -502,12 +526,221 @@ end_write_group(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
 		bool end_of_records);
 
 
+struct st_position;
+
+class Semi_join_strategy_picker
+{
+public:
+  /* Called when starting to build a new join prefix */
+  virtual void set_empty() = 0;
+
+  /* 
+    Update internal state after another table has been added to the join
+    prefix
+  */
+  virtual void set_from_prev(struct st_position *prev) = 0;
+  
+  virtual bool check_qep(JOIN *join,
+                         uint idx,
+                         table_map remaining_tables, 
+                         const JOIN_TAB *new_join_tab,
+                         double *record_count,
+                         double *read_time,
+                         table_map *handled_fanout,
+                         sj_strategy_enum *strategy,
+                         struct st_position *loose_scan_pos) = 0;
+
+  virtual void mark_used() = 0;
+
+  virtual ~Semi_join_strategy_picker() {} 
+};
+
+
+/*
+  Duplicate Weedout strategy optimization state
+*/
+
+class Duplicate_weedout_picker : public Semi_join_strategy_picker
+{
+  /* The first table that the strategy will need to handle */
+  uint  first_dupsweedout_table;
+
+  /*
+    Tables that we will need to have in the prefix to do the weedout step
+    (all inner and all outer that the involved semi-joins are correlated with)
+  */
+  table_map dupsweedout_tables;
+  
+  bool is_used;
+public:
+  void set_empty()
+  {
+    dupsweedout_tables= 0;
+    first_dupsweedout_table= MAX_TABLES;
+    is_used= FALSE;
+  }
+  void set_from_prev(struct st_position *prev);
+  
+  bool check_qep(JOIN *join,
+                 uint idx,
+                 table_map remaining_tables, 
+                 const JOIN_TAB *new_join_tab,
+                 double *record_count,
+                 double *read_time,
+                 table_map *handled_fanout,
+                 sj_strategy_enum *stratey,
+                 struct st_position *loose_scan_pos);
+
+  void mark_used() { is_used= TRUE; }
+  friend void fix_semijoin_strategies_for_picked_join_order(JOIN *join);
+};
+
+
+class Firstmatch_picker : public Semi_join_strategy_picker
+{
+  /*
+    Index of the first inner table that we intend to handle with this
+    strategy
+  */
+  uint first_firstmatch_table;
+  /*
+    Tables that were not in the join prefix when we've started considering 
+    FirstMatch strategy.
+  */
+  table_map first_firstmatch_rtbl;
+  /* 
+    Tables that need to be in the prefix before we can calculate the cost
+    of using FirstMatch strategy.
+   */
+  table_map firstmatch_need_tables;
+
+  bool is_used;
+
+  bool in_firstmatch_prefix() { return (first_firstmatch_table != MAX_TABLES); }
+  void invalidate_firstmatch_prefix() { first_firstmatch_table= MAX_TABLES; }
+public:
+  void set_empty()
+  {
+    invalidate_firstmatch_prefix();
+    is_used= FALSE;
+  }
+
+  void set_from_prev(struct st_position *prev);
+  bool check_qep(JOIN *join,
+                 uint idx,
+                 table_map remaining_tables, 
+                 const JOIN_TAB *new_join_tab,
+                 double *record_count,
+                 double *read_time,
+                 table_map *handled_fanout,
+                 sj_strategy_enum *strategy,
+                 struct st_position *loose_scan_pos);
+
+  void mark_used() { is_used= TRUE; }
+  friend void fix_semijoin_strategies_for_picked_join_order(JOIN *join);
+};
+
+
+class LooseScan_picker : public Semi_join_strategy_picker
+{
+  /* The first (i.e. driving) table we're doing loose scan for */
+  uint        first_loosescan_table;
+  /* 
+     Tables that need to be in the prefix before we can calculate the cost
+     of using LooseScan strategy.
+  */
+  table_map   loosescan_need_tables;
+
+  /*
+    keyno  -  Planning to do LooseScan on this key. If keyuse is NULL then 
+              this is a full index scan, otherwise this is a ref+loosescan
+              scan (and keyno matches the KEUSE's)
+    MAX_KEY - Not doing a LooseScan
+  */
+  uint loosescan_key;  // final (one for strategy instance )
+  uint loosescan_parts; /* Number of keyparts to be kept distinct */
+  
+  bool is_used;
+public:
+  void set_empty()
+  {
+    first_loosescan_table= MAX_TABLES; 
+    is_used= FALSE;
+  }
+
+  void set_from_prev(struct st_position *prev);
+  bool check_qep(JOIN *join,
+                 uint idx,
+                 table_map remaining_tables, 
+                 const JOIN_TAB *new_join_tab,
+                 double *record_count,
+                 double *read_time,
+                 table_map *handled_fanout,
+                 sj_strategy_enum *strategy,
+                 struct st_position *loose_scan_pos);
+  void mark_used() { is_used= TRUE; }
+
+  friend class Loose_scan_opt;
+  friend void best_access_path(JOIN      *join,
+                               JOIN_TAB  *s,
+                               table_map remaining_tables,
+                               uint      idx,
+                               bool      disable_jbuf,
+                               double    record_count,
+                               struct st_position *pos,
+                               struct st_position *loose_scan_pos);
+  friend bool get_best_combination(JOIN *join);
+  friend int setup_semijoin_dups_elimination(JOIN *join, ulonglong options,
+                                             uint no_jbuf_after);
+  friend void fix_semijoin_strategies_for_picked_join_order(JOIN *join);
+};
+
+
+class Sj_materialization_picker : public Semi_join_strategy_picker
+{
+  bool is_used;
+
+  /* The last inner table (valid once we're after it) */
+  uint      sjm_scan_last_inner;
+  /*
+    Tables that we need to have in the prefix to calculate the correct cost.
+    Basically, we need all inner tables and outer tables mentioned in the
+    semi-join's ON expression so we can correctly account for fanout.
+  */
+  table_map sjm_scan_need_tables;
+
+public:
+  void set_empty()
+  {
+    sjm_scan_need_tables= 0;
+    LINT_INIT(sjm_scan_last_inner);
+    is_used= FALSE;
+  }
+  void set_from_prev(struct st_position *prev);
+  bool check_qep(JOIN *join,
+                 uint idx,
+                 table_map remaining_tables, 
+                 const JOIN_TAB *new_join_tab,
+                 double *record_count,
+                 double *read_time,
+                 table_map *handled_fanout,
+                 sj_strategy_enum *strategy,
+                 struct st_position *loose_scan_pos);
+  void mark_used() { is_used= TRUE; }
+
+  friend void fix_semijoin_strategies_for_picked_join_order(JOIN *join);
+};
+
+
 /**
   Information about a position of table within a join order. Used in join
   optimization.
 */
 typedef struct st_position
 {
+  /* The table that's put into join order */
+  JOIN_TAB *table;
+
   /*
     The "fanout": number of output rows that will be produced (after
     pushed down selection condition is applied) per each row combination of
@@ -521,7 +754,10 @@ typedef struct st_position
     number the access method will be invoked.
   */
   double read_time;
-  JOIN_TAB *table;
+
+  /* Cumulative cost and record count for the join prefix */
+  COST_VECT prefix_cost;
+  double    prefix_record_count;
 
   /*
     NULL  -  'index' or 'range' or 'index_merge' or 'ALL' access is used.
@@ -531,14 +767,13 @@ typedef struct st_position
 
   /* If ref-based access is used: bitmap of tables this table depends on  */
   table_map ref_depend_map;
-
-  bool use_join_buffer; 
-  
-  
-  /* These form a stack of partial join order costs and output sizes */
-  COST_VECT prefix_cost;
-  double    prefix_record_count;
-
+ 
+  /*
+    TRUE <=> join buffering will be used. At the moment this is based on 
+    *very* imprecise guesses made in best_access_path(). 
+  */
+  bool use_join_buffer;
+ 
   /*
     Current optimization state: Semi-join strategy to be used for this
     and preceding join tables.
@@ -551,7 +786,8 @@ typedef struct st_position
     this applies to. The values of covered_preceding_positions->sj_strategy
     must be ignored.
   */
-  uint sj_strategy;
+  enum sj_strategy_enum sj_strategy;
+  
   /*
     Valid only after fix_semijoin_strategies_for_picked_join_order() call:
     if sj_strategy!=SJ_OPT_NONE, this is the number of subsequent tables that
@@ -559,67 +795,15 @@ typedef struct st_position
   */
   uint n_sj_tables;
 
-/* LooseScan strategy members */
-
-  /* The first (i.e. driving) table we're doing loose scan for */
-  uint        first_loosescan_table;
-  /* 
-     Tables that need to be in the prefix before we can calculate the cost
-     of using LooseScan strategy.
-  */
-  table_map   loosescan_need_tables;
-
-  /*
-    keyno  -  Planning to do LooseScan on this key. If keyuse is NULL then 
-              this is a full index scan, otherwise this is a ref+loosescan
-              scan (and keyno matches the KEUSE's)
-    MAX_KEY - Not doing a LooseScan
-  */
-  uint loosescan_key;  // final (one for strategy instance )
-  uint loosescan_parts; /* Number of keyparts to be kept distinct */
-  
-/* FirstMatch strategy */
-  /*
-    Index of the first inner table that we intend to handle with this
-    strategy
-  */
-  uint first_firstmatch_table;
-  /*
-    Tables that were not in the join prefix when we've started considering 
-    FirstMatch strategy.
-  */
-  table_map first_firstmatch_rtbl;
-  /* 
-    Tables that need to be in the prefix before we can calculate the cost
-    of using FirstMatch strategy.
-   */
-  table_map firstmatch_need_tables;
-
-  bool in_firstmatch_prefix() { return (first_firstmatch_table != MAX_TABLES); }
-  void invalidate_firstmatch_prefix() { first_firstmatch_table= MAX_TABLES; }
-
-/* Duplicate Weedout strategy */
-  /* The first table that the strategy will need to handle */
-  uint  first_dupsweedout_table;
-  /*
-    Tables that we will need to have in the prefix to do the weedout step
-    (all inner and all outer that the involved semi-joins are correlated with)
-  */
-  table_map dupsweedout_tables;
-
-/* SJ-Materialization-Scan strategy */
-  /* The last inner table (valid once we're after it) */
-  uint      sjm_scan_last_inner;
-  /*
-    Tables that we need to have in the prefix to calculate the correct cost.
-    Basically, we need all inner tables and outer tables mentioned in the
-    semi-join's ON expression so we can correctly account for fanout.
-  */
-  table_map sjm_scan_need_tables;
-
   table_map prefix_dups_producing_tables;
-} POSITION;
 
+  table_map inner_tables_handled_with_other_sjs;
+   
+  Duplicate_weedout_picker  dups_weedout_picker;
+  Firstmatch_picker         firstmatch_picker;
+  LooseScan_picker          loosescan_picker;
+  Sj_materialization_picker sjmat_picker;
+} POSITION;
 
 typedef struct st_rollup
 {
@@ -631,18 +815,6 @@ typedef struct st_rollup
 } ROLLUP;
 
 
-#define SJ_OPT_NONE 0
-#define SJ_OPT_DUPS_WEEDOUT 1
-#define SJ_OPT_LOOSE_SCAN   2
-#define SJ_OPT_FIRST_MATCH  3
-#define SJ_OPT_MATERIALIZE  4
-#define SJ_OPT_MATERIALIZE_SCAN  5
-
-inline bool sj_is_materialize_strategy(uint strategy)
-{
-  return strategy >= SJ_OPT_MATERIALIZE;
-}
-
 class JOIN_TAB_RANGE: public Sql_alloc
 {
 public:
@@ -750,6 +922,7 @@ public:
   */
   bool     sort_and_group; 
   bool     first_record,full_join, no_field_update;
+  bool     hash_join;
   bool	   do_send_rows;
   table_map const_table_map;
   /*
@@ -810,7 +983,7 @@ public:
     they produce.
   */
   table_map cur_dups_producing_tables;
-
+  
   /* We also maintain a stack of join optimization states in * join->positions[] */
 /******* Join optimization state members end *******/
   /*
@@ -935,6 +1108,7 @@ public:
   COND *conds;                            // ---"---
   Item *conds_history;                    // store WHERE for explain
   COND *outer_ref_cond;       ///<part of conds containing only outer references
+  COND *pseudo_bits_cond;     // part of conds containing special bita
   TABLE_LIST *tables_list;           ///<hold 'tables' parameter of mysql_select
   List<TABLE_LIST> *join_list;       ///< list of joined tables in reverse order
   COND_EQUAL *cond_equal;
@@ -1061,7 +1235,7 @@ public:
     rollup.state= ROLLUP::STATE_NONE;
 
     no_const_tables= FALSE;
-    outer_ref_cond= 0;
+    outer_ref_cond= pseudo_bits_cond= NULL;
     in_to_exists_where= NULL;
     in_to_exists_having= NULL;
   }
@@ -1151,6 +1325,25 @@ public:
     return test(allowed_join_cache_types & JOIN_CACHE_HASHED_BIT) &&
            max_allowed_join_cache_level > JOIN_CACHE_HASHED_BIT;
   }
+  /*
+    Check if we need to create a temporary table.
+    This has to be done if all tables are not already read (const tables)
+    and one of the following conditions holds:
+    - We are using DISTINCT (simple distinct's are already optimized away)
+    - We are using an ORDER BY or GROUP BY on fields not in the first table
+    - We are using different ORDER BY and GROUP BY orders
+    - The user wants us to buffer the result.
+    When the WITH ROLLUP modifier is present, we cannot skip temporary table
+    creation for the DISTINCT clause just because there are only const tables.
+  */
+  bool test_if_need_tmp_table()
+  {
+    return ((const_tables != table_count &&
+	    ((select_distinct || !simple_order || !simple_group) ||
+	     (group_list && order) ||
+	     test(select_options & OPTION_BUFFER_RESULT))) ||
+            (rollup.state != ROLLUP::STATE_NONE && select_distinct));
+  }
   bool choose_subquery_plan(table_map join_tables);
   void get_partial_cost_and_fanout(int end_tab_idx,
                                    table_map filter_map,