Manual merge

include/my_base.h:
  Auto merged
include/my_bitmap.h:
  Auto merged
include/my_sys.h:
  Auto merged
innobase/include/row0mysql.h:
  Auto merged
innobase/row/row0sel.c:
  Auto merged
mysys/my_bitmap.c:
  Auto merged
sql/ha_berkeley.cc:
  Auto merged
sql/ha_berkeley.h:
  Auto merged
sql/ha_heap.h:
  Auto merged
sql/ha_innodb.cc:
  Auto merged
sql/ha_innodb.h:
  Auto merged
sql/handler.h:
  Auto merged
sql/opt_range.cc:
  Auto merged
sql/opt_range.h:
  Auto merged
sql/sql_select.h:
  Auto merged

1 files changed, 249 insertions, 21 deletions

diff --git a/sql/opt_range.h b/sql/opt_range.h
index 4763600963d..122d444af31 100644
--- a/sql/opt_range.h
+++ b/sql/opt_range.h
@@ -78,25 +78,59 @@ public:
   ha_rows records;  /* estimate of # of records to be retrieved */
   double  read_time; /* time to perform this retrieval          */
   TABLE   *head;
+  /*
+    Index this quick select uses, or MAX_KEY for quick selects 
+    that use several indexes
+  */
+  uint index;
 
   /*
-    the only index this quick select uses, or MAX_KEY for 
-    QUICK_INDEX_MERGE_SELECT
+    Total length of first used_key_parts parts of the key.
+    Applicable if index!= MAX_KEY.
   */
-  uint index; 
-  uint max_used_key_length, used_key_parts;
+  uint max_used_key_length;
+
+  /*
+    Max. number of (first) key parts this quick select uses for retrieval.
+    eg. for "(key1p1=c1 AND key1p2=c2) OR key1p1=c2" used_key_parts == 2.
+    Applicable if index!= MAX_KEY.
+  */
+  uint used_key_parts;
 
   QUICK_SELECT_I();
   virtual ~QUICK_SELECT_I(){};
-  /* 
-    Call init() immediately after creation of quick select. if init() call 
-    fails, reset() or get_next() must not be called.
+  
+  /*
+    Do post-constructor initialization.
+    SYNOPSIS
+      init()
+    
+    init() performs initializations that should have been in constructor if 
+    it was possible to return errors from constructors. The join optimizer may 
+    create and then delete quick selects without retrieving any rows so init()
+    must not contain any IO or CPU intensive code.
+
+    If init() call fails the only valid action is to delete this quick select, 
+    reset() and get_next() must not be called.
+    
+    RETURN
+      0      OK
+      other  Error code
   */
   virtual int  init() = 0;
   
   /* 
-    Call reset() before first get_next call. get_next must not be called if 
-    reset() call fails.
+    Initialize quick select for row retrieval.
+    SYNOPSIS
+      reset()
+    
+    reset() should be called when it is certain that row retrieval will be 
+    necessary. This call may do heavyweight initialization like buffering first
+    N records etc. If reset() call fails get_next() must not be called.
+    
+    RETURN
+      0      OK
+      other  Error code
   */
   virtual int  reset(void) = 0;
   virtual int  get_next() = 0;   /* get next record to retrieve */
@@ -107,27 +141,98 @@ public:
     QS_TYPE_RANGE = 0,
     QS_TYPE_INDEX_MERGE = 1,
     QS_TYPE_RANGE_DESC = 2,
-    QS_TYPE_FULLTEXT   = 3
+    QS_TYPE_FULLTEXT   = 3,
+    QS_TYPE_ROR_INTERSECT = 4,
+    QS_TYPE_ROR_UNION = 5,
   };
 
-  /* Get type of this quick select - one of the QS_* values */
-  virtual int get_type() = 0; 
+  /* Get type of this quick select - one of the QS_TYPE_* values */
+  virtual int get_type() = 0;
+
+  /*
+    Initialize this quick select as a merged scan inside a ROR-union or a ROR-
+    intersection scan. The caller must not additionally call init() if this 
+    function is called.
+    SYNOPSIS
+      init_ror_merged_scan()
+        reuse_handler If true, the quick select may use table->handler, otherwise
+                      it must create and use a separate handler object.
+    RETURN
+      0     Ok
+      other Error 
+  */
+  virtual int init_ror_merged_scan(bool reuse_handler)
+  { DBUG_ASSERT(0); return 1; }
+  
+  /*
+    Save ROWID of last retrieved row in file->ref. This used in ROR-merging.
+  */
+  virtual void save_last_pos(){};
+
+  /* 
+    Append comma-separated list of keys this quick select uses to key_names;
+    append comma-separated list of corresponding used lengths to used_lengths.
+    This is used by select_describe.
+  */
+  virtual void add_keys_and_lengths(String *key_names, 
+                                    String *used_lengths)=0;
+ 
+  /* 
+    Append text representation of quick select structure (what and how is 
+    merged) to str. The result is added to "Extra" field in EXPLAIN output.
+    This function is implemented only by quick selects that merge other quick
+    selects output and/or can produce output suitable for merging.
+  */
+  virtual void add_info_string(String *str) {};
+  /*
+    Return 1 if any index used by this quick select 
+     a) uses field that is listed in passed field list or 
+     b) is automatically updated (like a timestamp)
+  */
+  virtual bool check_if_keys_used(List<Item> *fields);
+
+  /*
+    rowid of last row retrieved by this quick select. This is used only when 
+    doing ROR-index_merge selects 
+  */
+  byte    *last_rowid;
+
+  /*
+    Table record buffer used by this quick select. 
+  */
+  byte    *record;
+#ifndef DBUG_OFF
+  /*
+    Print quick select information to DBUG_FILE. Caller is responsible 
+    for locking DBUG_FILE before this call and unlocking it afterwards.
+  */
+  virtual void dbug_dump(int indent, bool verbose)= 0;
+#endif 
 };
 
+
 struct st_qsel_param;
 class SEL_ARG;
 
-class QUICK_RANGE_SELECT : public QUICK_SELECT_I 
+/*
+  Quick select that does a range scan on a single key. The records are 
+  returned in key order.
+*/
+class QUICK_RANGE_SELECT : public QUICK_SELECT_I
 {
 protected:
   bool next,dont_free;
 public:
   int error;
+protected:
   handler *file;
-  byte    *record;
+  /*
+    If true, this quick select has its "own" handler object which should be
+    closed no later then this quick select is deleted.
+  */
+  bool free_file;
+
 protected:
-  friend void print_quick_sel_range(QUICK_RANGE_SELECT *quick,
-                                    const key_map* needed_reg);
   friend
   QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table, 
                                                struct st_table_ref *ref);
@@ -141,18 +246,20 @@ protected:
                                               MEM_ROOT *alloc);
   friend class QUICK_SELECT_DESC;
   friend class QUICK_INDEX_MERGE_SELECT;
+  friend class QUICK_ROR_INTERSECT_SELECT;
 
   DYNAMIC_ARRAY ranges;     /* ordered array of range ptrs */
   QUICK_RANGE **cur_range;  /* current element in ranges  */
 
   QUICK_RANGE *range;
-  MEM_ROOT alloc;
   KEY_PART *key_parts;  
   KEY_PART_INFO *key_part_info;
   int cmp_next(QUICK_RANGE *range);
   int cmp_prev(QUICK_RANGE *range);
   bool row_in_ranges();
 public:
+  MEM_ROOT alloc;
+
   QUICK_RANGE_SELECT(THD *thd, TABLE *table,uint index_arg,bool no_alloc=0,
                      MEM_ROOT *parent_alloc=NULL);
   ~QUICK_RANGE_SELECT();
@@ -168,7 +275,17 @@ public:
   int get_next();
   bool reverse_sorted() { return 0; }
   bool unique_key_range();
+  int init_ror_merged_scan(bool reuse_handler);
+  void save_last_pos()
+  {
+    file->position(record);
+  };
   int get_type() { return QS_TYPE_RANGE; }
+  void add_keys_and_lengths(String *key_names, String *used_lengths);
+  void add_info_string(String *str);
+#ifndef DBUG_OFF
+  void dbug_dump(int indent, bool verbose);
+#endif
 };
 
 
@@ -254,6 +371,12 @@ public:
   bool reverse_sorted() { return false; }
   bool unique_key_range() { return false; }
   int get_type() { return QS_TYPE_INDEX_MERGE; }
+  void add_keys_and_lengths(String *key_names, String *used_lengths);
+  void add_info_string(String *str);
+  bool check_if_keys_used(List<Item> *fields);
+#ifndef DBUG_OFF
+  void dbug_dump(int indent, bool verbose);
+#endif
 
   bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
 
@@ -264,9 +387,6 @@ public:
   List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it;
   QUICK_RANGE_SELECT* cur_quick_select;
   
-  /* last element in quick_selects list */
-  QUICK_RANGE_SELECT* last_quick_select;
-
   /* quick select that uses clustered primary key (NULL if none) */
   QUICK_RANGE_SELECT* pk_quick_select;
   
@@ -278,12 +398,120 @@ public:
 
   THD *thd;
   int prepare_unique();
-  bool reset_called;
   
   /* used to get rows collected in Unique */
   READ_RECORD read_record;
 };
 
+
+/*
+  Rowid-Ordered Retrieval (ROR) index intersection quick select.
+  This quick select produces intersection of row sequences returned 
+  by several QUICK_RANGE_SELECTs it "merges".
+  
+  All merged QUICK_RANGE_SELECTs must return rowids in rowid order. 
+  QUICK_ROR_INTERSECT_SELECT will return rows in rowid order, too.
+
+  All merged quick selects retrieve {rowid, covered_fields} tuples (not full 
+  table records).
+  QUICK_ROR_INTERSECT_SELECT retrieves full records if it is not being used 
+  by QUICK_ROR_INTERSECT_SELECT and all merged quick selects together don't 
+  cover needed all fields.
+  
+  If one of the merged quick selects is a Clustered PK range scan, it is
+  used only to filter rowid sequence produced by other merged quick selects.
+*/
+
+class QUICK_ROR_INTERSECT_SELECT : public QUICK_SELECT_I 
+{
+public:
+  QUICK_ROR_INTERSECT_SELECT(THD *thd, TABLE *table, 
+                             bool retrieve_full_rows,
+                             MEM_ROOT *parent_alloc);
+  ~QUICK_ROR_INTERSECT_SELECT();
+
+  int  init();
+  int  reset(void);
+  int  get_next();
+  bool reverse_sorted() { return false; }
+  bool unique_key_range() { return false; }
+  int get_type() { return QS_TYPE_ROR_INTERSECT; }
+  void add_keys_and_lengths(String *key_names, String *used_lengths);
+  void add_info_string(String *str);
+  bool check_if_keys_used(List<Item> *fields);
+#ifndef DBUG_OFF
+  void dbug_dump(int indent, bool verbose);
+#endif
+  int init_ror_merged_scan(bool reuse_handler);
+  bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
+
+  /* 
+    Range quick selects this intersection consists of, not including
+    cpk_quick.
+  */
+  List<QUICK_RANGE_SELECT> quick_selects;
+  
+  /* 
+    Merged quick select that uses Clustered PK, if there is one. This quick 
+    select is not used for row retrieval, it is used for row retrieval.
+  */
+  QUICK_RANGE_SELECT *cpk_quick;
+
+  MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */
+  THD *thd;       /* current thread */
+  bool need_to_fetch_row; /* if true, do retrieve full table records. */
+};
+
+
+/*
+  Rowid-Ordered Retrieval index union select.
+  This quick select produces union of row sequences returned by several
+  quick select it "merges".
+
+  All merged quick selects must return rowids in rowid order. 
+  QUICK_ROR_UNION_SELECT will return rows in rowid order, too.
+
+  All merged quick selects are set not to retrieve full table records.
+  ROR-union quick select always retrieves full records.
+ 
+*/
+
+class QUICK_ROR_UNION_SELECT : public QUICK_SELECT_I 
+{
+public:
+  QUICK_ROR_UNION_SELECT(THD *thd, TABLE *table);
+  ~QUICK_ROR_UNION_SELECT();
+
+  int  init();
+  int  reset(void);
+  int  get_next();
+  bool reverse_sorted() { return false; }
+  bool unique_key_range() { return false; }
+  int get_type() { return QS_TYPE_ROR_UNION; }
+  void add_keys_and_lengths(String *key_names, String *used_lengths);
+  void add_info_string(String *str);
+  bool check_if_keys_used(List<Item> *fields);
+#ifndef DBUG_OFF
+  void dbug_dump(int indent, bool verbose);
+#endif
+
+  bool push_quick_back(QUICK_SELECT_I *quick_sel_range);
+
+  List<QUICK_SELECT_I> quick_selects; /* Merged quick selects */
+  
+  QUEUE queue;    /* Priority queue for merge operation */
+  MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */
+
+  THD *thd;             /* current thread */
+  byte *cur_rowid;      /* buffer used in get_next() */
+  byte *prev_rowid;     /* rowid of last row returned by get_next() */
+  bool have_prev_rowid; /* true if prev_rowid has valid data */
+  uint rowid_length;    /* table rowid length */ 
+private:
+  static int queue_cmp(void *arg, byte *val1, byte *val2);
+};
+
+
 class QUICK_SELECT_DESC: public QUICK_RANGE_SELECT
 {
 public: