My Project
opt_range.h
00001 /* Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.
00002 
00003    This program is free software; you can redistribute it and/or modify
00004    it under the terms of the GNU General Public License as published by
00005    the Free Software Foundation; version 2 of the License.
00006 
00007    This program is distributed in the hope that it will be useful,
00008    but WITHOUT ANY WARRANTY; without even the implied warranty of
00009    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00010    GNU General Public License for more details.
00011 
00012    You should have received a copy of the GNU General Public License
00013    along with this program; if not, write to the Free Software Foundation,
00014    51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA */
00015 
00016 
00017 /* classes to use when handling where clause */
00018 
00019 #ifndef _opt_range_h
00020 #define _opt_range_h
00021 
00022 #include "thr_malloc.h"                         /* sql_memdup */
00023 #include "records.h"                            /* READ_RECORD */
00024 #include "queues.h"                             /* QUEUE */
00025 /*
00026   It is necessary to include set_var.h instead of item.h because there
00027   are dependencies on include order for set_var.h and item.h. This
00028   will be resolved later.
00029 */
00030 #include "sql_class.h"                          // set_var.h: THD
00031 #include "set_var.h"                            /* Item */
00032 
00033 #include <algorithm>
00034 
00035 class JOIN;
00036 class Item_sum;
00037 
00038 typedef struct st_key_part {
00039   uint16           key,part;
00040   /* See KEY_PART_INFO for meaning of the next two: */
00041   uint16           store_length, length;
00042   uint8            null_bit;
00043   /*
00044     Keypart flags (0 when this structure is used by partition pruning code
00045     for fake partitioning index description)
00046   */
00047   uint8 flag;
00048   Field            *field;
00049   Field::imagetype image_type;
00050 } KEY_PART;
00051 
00052 
00053 class QUICK_RANGE :public Sql_alloc {
00054  public:
00055   uchar *min_key,*max_key;
00056   uint16 min_length,max_length,flag;
00057   key_part_map min_keypart_map, // bitmap of used keyparts in min_key
00058                max_keypart_map; // bitmap of used keyparts in max_key
00059 
00060   QUICK_RANGE();                                /* Full range */
00061   QUICK_RANGE(const uchar *min_key_arg, uint min_length_arg,
00062               key_part_map min_keypart_map_arg,
00063               const uchar *max_key_arg, uint max_length_arg,
00064               key_part_map max_keypart_map_arg,
00065               uint flag_arg);
00066 
00081   void make_min_endpoint(key_range *kr, uint prefix_length, 
00082                          key_part_map keypart_map) {
00083     using std::min;
00084     make_min_endpoint(kr);
00085     kr->length= min(kr->length, prefix_length);
00086     kr->keypart_map&= keypart_map;
00087   }
00088   
00098   void make_min_endpoint(key_range *kr) {
00099     kr->key= (const uchar*)min_key;
00100     kr->length= min_length;
00101     kr->keypart_map= min_keypart_map;
00102     kr->flag= ((flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
00103                (flag & EQ_RANGE) ? HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
00104   }
00105 
00120   void make_max_endpoint(key_range *kr, uint prefix_length, 
00121                          key_part_map keypart_map) {
00122     using std::min;
00123     make_max_endpoint(kr);
00124     kr->length= min(kr->length, prefix_length);
00125     kr->keypart_map&= keypart_map;
00126   }
00127 
00137   void make_max_endpoint(key_range *kr) {
00138     kr->key= (const uchar*)max_key;
00139     kr->length= max_length;
00140     kr->keypart_map= max_keypart_map;
00141     /*
00142       We use READ_AFTER_KEY here because if we are reading on a key
00143       prefix we want to find all keys with this prefix
00144     */
00145     kr->flag= (flag & NEAR_MAX ? HA_READ_BEFORE_KEY : HA_READ_AFTER_KEY);
00146   }
00147 };
00148 
00149 
00150 /*
00151   Quick select interface.
00152   This class is a parent for all QUICK_*_SELECT and FT_SELECT classes.
00153 
00154   The usage scenario is as follows:
00155   1. Create quick select
00156     quick= new QUICK_XXX_SELECT(...);
00157 
00158   2. Perform lightweight initialization. This can be done in 2 ways:
00159   2.a: Regular initialization
00160     if (quick->init())
00161     {
00162       //the only valid action after failed init() call is delete
00163       delete quick;
00164     }
00165   2.b: Special initialization for quick selects merged by QUICK_ROR_*_SELECT
00166     if (quick->init_ror_merged_scan())
00167       delete quick;
00168 
00169   3. Perform zero, one, or more scans.
00170     while (...)
00171     {
00172       // initialize quick select for scan. This may allocate
00173       // buffers and/or prefetch rows.
00174       if (quick->reset())
00175       {
00176         //the only valid action after failed reset() call is delete
00177         delete quick;
00178         //abort query
00179       }
00180 
00181       // perform the scan
00182       do
00183       {
00184         res= quick->get_next();
00185       } while (res && ...)
00186     }
00187 
00188   4. Delete the select:
00189     delete quick;
00190   
00191   NOTE 
00192     quick select doesn't use Sql_alloc/MEM_ROOT allocation because "range
00193     checked for each record" functionality may create/destroy
00194     O(#records_in_some_table) quick selects during query execution.
00195 */
00196 
00197 class QUICK_SELECT_I
00198 {
00199 public:
00200   ha_rows records;  /* estimate of # of records to be retrieved */
00201   double  read_time; /* time to perform this retrieval          */
00202   TABLE   *head;
00203   /*
00204     Index this quick select uses, or MAX_KEY for quick selects
00205     that use several indexes
00206   */
00207   uint index;
00208 
00209   /*
00210     Total length of first used_key_parts parts of the key.
00211     Applicable if index!= MAX_KEY.
00212   */
00213   uint max_used_key_length;
00214 
00215   /*
00216     Max. number of (first) key parts this quick select uses for retrieval.
00217     eg. for "(key1p1=c1 AND key1p2=c2) OR key1p1=c2" used_key_parts == 2.
00218     Applicable if index!= MAX_KEY.
00219 
00220     For QUICK_GROUP_MIN_MAX_SELECT it includes MIN/MAX argument keyparts.
00221   */
00222   uint used_key_parts;
00223 
00224   QUICK_SELECT_I();
00225   virtual ~QUICK_SELECT_I(){};
00226 
00227   /*
00228     Do post-constructor initialization.
00229     SYNOPSIS
00230       init()
00231 
00232     init() performs initializations that should have been in constructor if
00233     it was possible to return errors from constructors. The join optimizer may
00234     create and then delete quick selects without retrieving any rows so init()
00235     must not contain any IO or CPU intensive code.
00236 
00237     If init() call fails the only valid action is to delete this quick select,
00238     reset() and get_next() must not be called.
00239 
00240     RETURN
00241       0      OK
00242       other  Error code
00243   */
00244   virtual int  init() = 0;
00245 
00246   /*
00247     Initialize quick select for row retrieval.
00248     SYNOPSIS
00249       reset()
00250 
00251     reset() should be called when it is certain that row retrieval will be
00252     necessary. This call may do heavyweight initialization like buffering first
00253     N records etc. If reset() call fails get_next() must not be called.
00254     Note that reset() may be called several times if 
00255      * the quick select is executed in a subselect
00256      * a JOIN buffer is used
00257     
00258     RETURN
00259       0      OK
00260       other  Error code
00261   */
00262   virtual int  reset(void) = 0;
00263 
00264   virtual int  get_next() = 0;   /* get next record to retrieve */
00265 
00266   /* Range end should be called when we have looped over the whole index */
00267   virtual void range_end() {}
00268 
00272   virtual bool reverse_sorted() const = 0;
00277   virtual bool reverse_sort_possible() const = 0;
00278   virtual bool unique_key_range() { return false; }
00279   virtual bool clustered_pk_range() { return false; }
00280   
00281   /*
00282     Request that this quick select produces sorted output.
00283     Not all quick selects can provide sorted output, the caller is responsible 
00284     for calling this function only for those quick selects that can.
00285     The implementation is also allowed to provide sorted output even if it
00286     was not requested if benificial, or required by implementation 
00287     internals.
00288   */
00289   virtual void need_sorted_output() = 0;
00290   enum {
00291     QS_TYPE_RANGE = 0,
00292     QS_TYPE_INDEX_MERGE = 1,
00293     QS_TYPE_RANGE_DESC = 2,
00294     QS_TYPE_FULLTEXT   = 3,
00295     QS_TYPE_ROR_INTERSECT = 4,
00296     QS_TYPE_ROR_UNION = 5,
00297     QS_TYPE_GROUP_MIN_MAX = 6
00298   };
00299 
00300   /* Get type of this quick select - one of the QS_TYPE_* values */
00301   virtual int get_type() = 0;
00302 
00303   /*
00304     Initialize this quick select as a merged scan inside a ROR-union or a ROR-
00305     intersection scan. The caller must not additionally call init() if this
00306     function is called.
00307     SYNOPSIS
00308       init_ror_merged_scan()
00309         reuse_handler  If true, the quick select may use table->handler,
00310                        otherwise it must create and use a separate handler
00311                        object.
00312     RETURN
00313       0     Ok
00314       other Error
00315   */
00316   virtual int init_ror_merged_scan(bool reuse_handler)
00317   { DBUG_ASSERT(0); return 1; }
00318 
00319   /*
00320     Save ROWID of last retrieved row in file->ref. This used in ROR-merging.
00321   */
00322   virtual void save_last_pos(){};
00323 
00324   /*
00325     Append comma-separated list of keys this quick select uses to key_names;
00326     append comma-separated list of corresponding used lengths to used_lengths.
00327     This is used by select_describe.
00328   */
00329   virtual void add_keys_and_lengths(String *key_names,
00330                                     String *used_lengths)=0;
00331 
00332   /*
00333     Append text representation of quick select structure (what and how is
00334     merged) to str. The result is added to "Extra" field in EXPLAIN output.
00335     This function is implemented only by quick selects that merge other quick
00336     selects output and/or can produce output suitable for merging.
00337   */
00338   virtual void add_info_string(String *str) {};
00339   /*
00340     Return 1 if any index used by this quick select
00341     uses field which is marked in passed bitmap.
00342   */
00343   virtual bool is_keys_used(const MY_BITMAP *fields);
00344 
00350   virtual bool is_valid() { return index != MAX_KEY; };
00351 
00352   /*
00353     rowid of last row retrieved by this quick select. This is used only when
00354     doing ROR-index_merge selects
00355   */
00356   uchar    *last_rowid;
00357 
00358   /*
00359     Table record buffer used by this quick select.
00360   */
00361   uchar    *record;
00362 #ifndef DBUG_OFF
00363   /*
00364     Print quick select information to DBUG_FILE. Caller is responsible
00365     for locking DBUG_FILE before this call and unlocking it afterwards.
00366   */
00367   virtual void dbug_dump(int indent, bool verbose)= 0;
00368 #endif
00369 
00370   /*
00371     Returns a QUICK_SELECT with reverse order of to the index.
00372   */
00373   virtual QUICK_SELECT_I *make_reverse(uint used_key_parts_arg) { return NULL; }
00374   virtual void set_handler(handler *file_arg) {}
00375 };
00376 
00377 
00378 struct st_qsel_param;
00379 class PARAM;
00380 class SEL_ARG;
00381 
00382 
00383 /*
00384   MRR range sequence, array<QUICK_RANGE> implementation: sequence traversal
00385   context.
00386 */
00387 typedef struct st_quick_range_seq_ctx
00388 {
00389   QUICK_RANGE **first;
00390   QUICK_RANGE **cur;
00391   QUICK_RANGE **last;
00392 } QUICK_RANGE_SEQ_CTX;
00393 
00394 range_seq_t quick_range_seq_init(void *init_param, uint n_ranges, uint flags);
00395 uint quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
00396 
00397 
00398 /*
00399   Quick select that does a range scan on a single key. The records are
00400   returned in key order if ::need_sorted_output() has been called.
00401 */
00402 class QUICK_RANGE_SELECT : public QUICK_SELECT_I
00403 {
00404 protected:
00405   handler *file;
00406   /* Members to deal with case when this quick select is a ROR-merged scan */
00407   bool in_ror_merged_scan;
00408   MY_BITMAP column_bitmap;
00409 
00410   friend class TRP_ROR_INTERSECT;
00411   friend
00412   QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table,
00413                                                struct st_table_ref *ref,
00414                                                ha_rows records);
00415   friend bool get_quick_keys(PARAM *param,
00416                              QUICK_RANGE_SELECT *quick,KEY_PART *key,
00417                              SEL_ARG *key_tree,
00418                              uchar *min_key, uint min_key_flag,
00419                              uchar *max_key, uint max_key_flag);
00420   friend QUICK_RANGE_SELECT *get_quick_select(PARAM*,uint idx,
00421                                               SEL_ARG *key_tree,
00422                                               uint mrr_flags,
00423                                               uint mrr_buf_size,
00424                                               MEM_ROOT *alloc);
00425   friend uint quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
00426   friend range_seq_t quick_range_seq_init(void *init_param,
00427                                           uint n_ranges, uint flags);
00428   friend class QUICK_SELECT_DESC;
00429   friend class QUICK_INDEX_MERGE_SELECT;
00430   friend class QUICK_ROR_INTERSECT_SELECT;
00431   friend class QUICK_GROUP_MIN_MAX_SELECT;
00432 
00433   DYNAMIC_ARRAY ranges;     /* ordered array of range ptrs */
00434   bool free_file;   /* TRUE <=> this->file is "owned" by this quick select */
00435 
00436   /* Range pointers to be used when not using MRR interface */
00437   QUICK_RANGE **cur_range;  /* current element in ranges  */
00438   QUICK_RANGE *last_range;
00439   
00440   /* Members needed to use the MRR interface */
00441   QUICK_RANGE_SEQ_CTX qr_traversal_ctx;
00442 public:
00443   uint mrr_flags; /* Flags to be used with MRR interface */
00444 protected:
00445   uint mrr_buf_size; /* copy from thd->variables.read_rnd_buff_size */  
00446   HANDLER_BUFFER *mrr_buf_desc; /* the handler buffer */
00447 
00448   /* Info about index we're scanning */
00449   KEY_PART *key_parts;
00450   KEY_PART_INFO *key_part_info;
00451   
00452   bool dont_free; /* Used by QUICK_SELECT_DESC */
00453 
00454   int cmp_next(QUICK_RANGE *range);
00455   int cmp_prev(QUICK_RANGE *range);
00456   bool row_in_ranges();
00457 public:
00458   MEM_ROOT alloc;
00459 
00460   QUICK_RANGE_SELECT(THD *thd, TABLE *table,uint index_arg,bool no_alloc,
00461                      MEM_ROOT *parent_alloc, bool *create_error);
00462   ~QUICK_RANGE_SELECT();
00463   
00464   void need_sorted_output();
00465   int init();
00466   int reset(void);
00467   int get_next();
00468   void range_end();
00469   int get_next_prefix(uint prefix_length, uint group_key_parts, 
00470                       uchar *cur_prefix);
00471   bool reverse_sorted() const { return false; }
00472   bool reverse_sort_possible() const { return true; }
00473   bool unique_key_range();
00474   int init_ror_merged_scan(bool reuse_handler);
00475   void save_last_pos()
00476   { file->position(record); }
00477   int get_type() { return QS_TYPE_RANGE; }
00478   void add_keys_and_lengths(String *key_names, String *used_lengths);
00479   void add_info_string(String *str);
00480 #ifndef DBUG_OFF
00481   void dbug_dump(int indent, bool verbose);
00482 #endif
00483   QUICK_SELECT_I *make_reverse(uint used_key_parts_arg);
00484   void set_handler(handler *file_arg) { file= file_arg; }
00485 private:
00486   /* Default copy ctor used by QUICK_SELECT_DESC */
00487 };
00488 
00489 
00490 class QUICK_RANGE_SELECT_GEOM: public QUICK_RANGE_SELECT
00491 {
00492 public:
00493   QUICK_RANGE_SELECT_GEOM(THD *thd, TABLE *table, uint index_arg,
00494                           bool no_alloc, MEM_ROOT *parent_alloc,
00495                           bool *create_error)
00496     :QUICK_RANGE_SELECT(thd, table, index_arg, no_alloc, parent_alloc,
00497                         create_error)
00498     {};
00499   virtual int get_next();
00500 };
00501 
00502 
00503 /*
00504   QUICK_INDEX_MERGE_SELECT - index_merge access method quick select.
00505 
00506     QUICK_INDEX_MERGE_SELECT uses
00507      * QUICK_RANGE_SELECTs to get rows
00508      * Unique class to remove duplicate rows
00509 
00510   INDEX MERGE OPTIMIZER
00511     Current implementation doesn't detect all cases where index_merge could
00512     be used, in particular:
00513      * index_merge will never be used if range scan is possible (even if
00514        range scan is more expensive)
00515 
00516      * index_merge+'using index' is not supported (this the consequence of
00517        the above restriction)
00518 
00519      * If WHERE part contains complex nested AND and OR conditions, some ways
00520        to retrieve rows using index_merge will not be considered. The choice
00521        of read plan may depend on the order of conjuncts/disjuncts in WHERE
00522        part of the query, see comments near imerge_list_or_list and
00523        SEL_IMERGE::or_sel_tree_with_checks functions for details.
00524 
00525      * There is no "index_merge_ref" method (but index_merge on non-first
00526        table in join is possible with 'range checked for each record').
00527 
00528     See comments around SEL_IMERGE class and test_quick_select for more
00529     details.
00530 
00531   ROW RETRIEVAL ALGORITHM
00532 
00533     index_merge uses Unique class for duplicates removal.  index_merge takes
00534     advantage of Clustered Primary Key (CPK) if the table has one.
00535     The index_merge algorithm consists of two phases:
00536 
00537     Phase 1 (implemented in QUICK_INDEX_MERGE_SELECT::prepare_unique):
00538     prepare()
00539     {
00540       activate 'index only';
00541       while(retrieve next row for non-CPK scan)
00542       {
00543         if (there is a CPK scan and row will be retrieved by it)
00544           skip this row;
00545         else
00546           put its rowid into Unique;
00547       }
00548       deactivate 'index only';
00549     }
00550 
00551     Phase 2 (implemented as sequence of QUICK_INDEX_MERGE_SELECT::get_next
00552     calls):
00553 
00554     fetch()
00555     {
00556       retrieve all rows from row pointers stored in Unique;
00557       free Unique;
00558       retrieve all rows for CPK scan;
00559     }
00560 */
00561 
00562 class QUICK_INDEX_MERGE_SELECT : public QUICK_SELECT_I
00563 {
00564   Unique *unique;
00565 public:
00566   QUICK_INDEX_MERGE_SELECT(THD *thd, TABLE *table);
00567   ~QUICK_INDEX_MERGE_SELECT();
00568 
00569   int  init();
00570   void need_sorted_output() { DBUG_ASSERT(false); /* Can't do it */ }
00571   int  reset(void);
00572   int  get_next();
00573   bool reverse_sorted() const { return false; }
00574   bool reverse_sort_possible() const { return false; }
00575   bool unique_key_range() { return false; }
00576   int get_type() { return QS_TYPE_INDEX_MERGE; }
00577   void add_keys_and_lengths(String *key_names, String *used_lengths);
00578   void add_info_string(String *str);
00579   bool is_keys_used(const MY_BITMAP *fields);
00580 #ifndef DBUG_OFF
00581   void dbug_dump(int indent, bool verbose);
00582 #endif
00583 
00584   bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
00585 
00586   /* range quick selects this index_merge read consists of */
00587   List<QUICK_RANGE_SELECT> quick_selects;
00588 
00589   /* quick select that uses clustered primary key (NULL if none) */
00590   QUICK_RANGE_SELECT* pk_quick_select;
00591 
00592   /* true if this select is currently doing a clustered PK scan */
00593   bool  doing_pk_scan;
00594 
00595   MEM_ROOT alloc;
00596   THD *thd;
00597   int read_keys_and_merge();
00598 
00599   bool clustered_pk_range() { return MY_TEST(pk_quick_select); }
00600 
00601   virtual bool is_valid()
00602   {
00603     List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
00604     QUICK_RANGE_SELECT *quick;
00605     bool valid= true;
00606     while ((quick= it++))
00607     {
00608       if (!quick->is_valid())
00609       {
00610         valid= false;
00611         break;
00612       }
00613     }
00614     return valid;
00615   }
00616 
00617   /* used to get rows collected in Unique */
00618   READ_RECORD read_record;
00619 };
00620 
00621 
00622 /*
00623   Rowid-Ordered Retrieval (ROR) index intersection quick select.
00624   This quick select produces intersection of row sequences returned
00625   by several QUICK_RANGE_SELECTs it "merges".
00626 
00627   All merged QUICK_RANGE_SELECTs must return rowids in rowid order.
00628   QUICK_ROR_INTERSECT_SELECT will return rows in rowid order, too.
00629 
00630   All merged quick selects retrieve {rowid, covered_fields} tuples (not full
00631   table records).
00632   QUICK_ROR_INTERSECT_SELECT retrieves full records if it is not being used
00633   by QUICK_ROR_INTERSECT_SELECT and all merged quick selects together don't
00634   cover needed all fields.
00635 
00636   If one of the merged quick selects is a Clustered PK range scan, it is
00637   used only to filter rowid sequence produced by other merged quick selects.
00638 */
00639 
00640 class QUICK_ROR_INTERSECT_SELECT : public QUICK_SELECT_I
00641 {
00642 public:
00643   QUICK_ROR_INTERSECT_SELECT(THD *thd, TABLE *table,
00644                              bool retrieve_full_rows,
00645                              MEM_ROOT *parent_alloc);
00646   ~QUICK_ROR_INTERSECT_SELECT();
00647 
00648   int  init();
00649   void need_sorted_output() { DBUG_ASSERT(false); /* Can't do it */ }
00650   int  reset(void);
00651   int  get_next();
00652   bool reverse_sorted() const { return false; }
00653   bool reverse_sort_possible() const { return false; }
00654   bool unique_key_range() { return false; }
00655   int get_type() { return QS_TYPE_ROR_INTERSECT; }
00656   void add_keys_and_lengths(String *key_names, String *used_lengths);
00657   void add_info_string(String *str);
00658   bool is_keys_used(const MY_BITMAP *fields);
00659 #ifndef DBUG_OFF
00660   void dbug_dump(int indent, bool verbose);
00661 #endif
00662   int init_ror_merged_scan(bool reuse_handler);
00663   bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
00664 
00665   /*
00666     Range quick selects this intersection consists of, not including
00667     cpk_quick.
00668   */
00669   List<QUICK_RANGE_SELECT> quick_selects;
00670 
00671   virtual bool is_valid()
00672   {
00673     List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
00674     QUICK_RANGE_SELECT *quick;
00675     bool valid= true;
00676     while ((quick= it++))
00677     {
00678       if (!quick->is_valid())
00679       {
00680         valid= false;
00681         break;
00682       }
00683     }
00684     return valid;
00685   }
00686 
00687   /*
00688     Merged quick select that uses Clustered PK, if there is one. This quick
00689     select is not used for row retrieval, it is used for row retrieval.
00690   */
00691   QUICK_RANGE_SELECT *cpk_quick;
00692 
00693   MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */
00694   THD *thd;       /* current thread */
00695   bool need_to_fetch_row; /* if true, do retrieve full table records. */
00696   /* in top-level quick select, true if merged scans where initialized */
00697   bool scans_inited; 
00698 };
00699 
00700 
00701 /*
00702   Rowid-Ordered Retrieval index union select.
00703   This quick select produces union of row sequences returned by several
00704   quick select it "merges".
00705 
00706   All merged quick selects must return rowids in rowid order.
00707   QUICK_ROR_UNION_SELECT will return rows in rowid order, too.
00708 
00709   All merged quick selects are set not to retrieve full table records.
00710   ROR-union quick select always retrieves full records.
00711 
00712 */
00713 
00714 class QUICK_ROR_UNION_SELECT : public QUICK_SELECT_I
00715 {
00716 public:
00717   QUICK_ROR_UNION_SELECT(THD *thd, TABLE *table);
00718   ~QUICK_ROR_UNION_SELECT();
00719 
00720   int  init();
00721   void need_sorted_output() { DBUG_ASSERT(false); /* Can't do it */ }
00722   int  reset(void);
00723   int  get_next();
00724   bool reverse_sorted() const { return false; }
00725   bool reverse_sort_possible() const { return false; }
00726   bool unique_key_range() { return false; }
00727   int get_type() { return QS_TYPE_ROR_UNION; }
00728   void add_keys_and_lengths(String *key_names, String *used_lengths);
00729   void add_info_string(String *str);
00730   bool is_keys_used(const MY_BITMAP *fields);
00731 #ifndef DBUG_OFF
00732   void dbug_dump(int indent, bool verbose);
00733 #endif
00734 
00735   bool push_quick_back(QUICK_SELECT_I *quick_sel_range);
00736 
00737   List<QUICK_SELECT_I> quick_selects; /* Merged quick selects */
00738 
00739   virtual bool is_valid()
00740   {
00741     List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
00742     QUICK_SELECT_I *quick;
00743     bool valid= true;
00744     while ((quick= it++))
00745     {
00746       if (!quick->is_valid())
00747       {
00748         valid= false;
00749         break;
00750       }
00751     }
00752     return valid;
00753   }
00754 
00755   QUEUE queue;    /* Priority queue for merge operation */
00756   MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */
00757 
00758   THD *thd;             /* current thread */
00759   uchar *cur_rowid;      /* buffer used in get_next() */
00760   uchar *prev_rowid;     /* rowid of last row returned by get_next() */
00761   bool have_prev_rowid; /* true if prev_rowid has valid data */
00762   uint rowid_length;    /* table rowid length */
00763 private:
00764   bool scans_inited; 
00765 };
00766 
00767 
00768 /*
00769   Index scan for GROUP-BY queries with MIN/MAX aggregate functions.
00770 
00771   This class provides a specialized index access method for GROUP-BY queries
00772   of the forms:
00773 
00774        SELECT A_1,...,A_k, [B_1,...,B_m], [MIN(C)], [MAX(C)]
00775          FROM T
00776         WHERE [RNG(A_1,...,A_p ; where p <= k)]
00777          [AND EQ(B_1,...,B_m)]
00778          [AND PC(C)]
00779          [AND PA(A_i1,...,A_iq)]
00780        GROUP BY A_1,...,A_k;
00781 
00782     or
00783 
00784        SELECT DISTINCT A_i1,...,A_ik
00785          FROM T
00786         WHERE [RNG(A_1,...,A_p ; where p <= k)]
00787          [AND PA(A_i1,...,A_iq)];
00788 
00789   where all selected fields are parts of the same index.
00790   The class of queries that can be processed by this quick select is fully
00791   specified in the description of get_best_trp_group_min_max() in opt_range.cc.
00792 
00793   The get_next() method directly produces result tuples, thus obviating the
00794   need to call end_send_group() because all grouping is already done inside
00795   get_next().
00796 
00797   Since one of the requirements is that all select fields are part of the same
00798   index, this class produces only index keys, and not complete records.
00799 */
00800 
00801 class QUICK_GROUP_MIN_MAX_SELECT : public QUICK_SELECT_I
00802 {
00803 private:
00804   JOIN *join;            /* Descriptor of the current query */
00805   KEY  *index_info;      /* The index chosen for data access */
00806   uchar *record;          /* Buffer where the next record is returned. */
00807   uchar *tmp_record;      /* Temporary storage for next_min(), next_max(). */
00808   uchar *group_prefix;    /* Key prefix consisting of the GROUP fields. */
00809   const uint group_prefix_len; /* Length of the group prefix. */
00810   uint group_key_parts;  /* A number of keyparts in the group prefix */
00811   uchar *last_prefix;     /* Prefix of the last group for detecting EOF. */
00812   bool have_min;         /* Specify whether we are computing */
00813   bool have_max;         /*   a MIN, a MAX, or both.         */
00814   bool have_agg_distinct;/*   aggregate_function(DISTINCT ...).  */
00815   bool seen_first_key;   /* Denotes whether the first key was retrieved.*/
00816   KEY_PART_INFO *min_max_arg_part; /* The keypart of the only argument field */
00817                                    /* of all MIN/MAX functions.              */
00818   uint min_max_arg_len;  /* The length of the MIN/MAX argument field */
00819   uchar *key_infix;       /* Infix of constants from equality predicates. */
00820   uint key_infix_len;
00821   DYNAMIC_ARRAY min_max_ranges; /* Array of range ptrs for the MIN/MAX field. */
00822   uint real_prefix_len; /* Length of key prefix extended with key_infix. */
00823   uint real_key_parts;  /* A number of keyparts in the above value.      */
00824   List<Item_sum> *min_functions;
00825   List<Item_sum> *max_functions;
00826   List_iterator<Item_sum> *min_functions_it;
00827   List_iterator<Item_sum> *max_functions_it;
00828   /* 
00829     Use index scan to get the next different key instead of jumping into it 
00830     through index read 
00831   */
00832   bool is_index_scan; 
00833 public:
00834   /*
00835     The following two members are public to allow easy access from
00836     TRP_GROUP_MIN_MAX::make_quick()
00837   */
00838   MEM_ROOT alloc; /* Memory pool for this and quick_prefix_select data. */
00839   QUICK_RANGE_SELECT *quick_prefix_select;/* For retrieval of group prefixes. */
00840 private:
00841   int  next_prefix();
00842   int  next_min_in_range();
00843   int  next_max_in_range();
00844   int  next_min();
00845   int  next_max();
00846   void update_min_result();
00847   void update_max_result();
00848 public:
00849   QUICK_GROUP_MIN_MAX_SELECT(TABLE *table, JOIN *join, bool have_min,
00850                              bool have_max, bool have_agg_distinct,
00851                              KEY_PART_INFO *min_max_arg_part,
00852                              uint group_prefix_len, uint group_key_parts,
00853                              uint used_key_parts, KEY *index_info, uint
00854                              use_index, double read_cost, ha_rows records, uint
00855                              key_infix_len, uchar *key_infix, MEM_ROOT
00856                              *parent_alloc, bool is_index_scan);
00857   ~QUICK_GROUP_MIN_MAX_SELECT();
00858   bool add_range(SEL_ARG *sel_range);
00859   void update_key_stat();
00860   void adjust_prefix_ranges();
00861   bool alloc_buffers();
00862   int init();
00863   void need_sorted_output() { /* always do it */ }
00864   int reset();
00865   int get_next();
00866   bool reverse_sorted() const { return false; }
00867   bool reverse_sort_possible() const { return false; }
00868   bool unique_key_range() { return false; }
00869   int get_type() { return QS_TYPE_GROUP_MIN_MAX; }
00870   void add_keys_and_lengths(String *key_names, String *used_lengths);
00871 #ifndef DBUG_OFF
00872   void dbug_dump(int indent, bool verbose);
00873 #endif
00874   bool is_agg_distinct() { return have_agg_distinct; }
00875   virtual void append_loose_scan_type(String *str) 
00876   {
00877     if (is_index_scan)
00878       str->append(STRING_WITH_LEN("scanning"));
00879   }
00880 };
00881 
00882 
00883 class QUICK_SELECT_DESC: public QUICK_RANGE_SELECT
00884 {
00885 public:
00886   QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint used_key_parts, 
00887                     bool *create_err);
00888   int get_next();
00889   bool reverse_sorted() const { return true; }
00890   bool reverse_sort_possible() const { return true; }
00891   int get_type() { return QS_TYPE_RANGE_DESC; }
00892   QUICK_SELECT_I *make_reverse(uint used_key_parts_arg)
00893   {
00894     return this; // is already reverse sorted
00895   }
00896 private:
00897   bool range_reads_after_key(QUICK_RANGE *range);
00898   int reset(void) { rev_it.rewind(); return QUICK_RANGE_SELECT::reset(); }
00899   List<QUICK_RANGE> rev_ranges;
00900   List_iterator<QUICK_RANGE> rev_it;
00901   uint used_key_parts;
00902 };
00903 
00904 
00905 class SQL_SELECT :public Sql_alloc {
00906  public:
00907   QUICK_SELECT_I *quick;        // If quick-select used
00908   Item          *cond;          // where condition
00909   Item          *icp_cond;      // conditions pushed to index
00910   TABLE *head;
00911   IO_CACHE file;                // Positions to used records
00912   ha_rows records;              // Records in use if read from file
00913   double read_time;             // Time to read rows
00914   key_map quick_keys;           // Possible quick keys
00915   key_map needed_reg;           // Possible quick keys after prev tables.
00916   table_map const_tables,read_tables;
00917   bool  free_cond;
00918 
00928   bool traced_before;
00929 
00930   SQL_SELECT();
00931   ~SQL_SELECT();
00932   void cleanup();
00933   void set_quick(QUICK_SELECT_I *new_quick) { delete quick; quick= new_quick; }
00934   bool check_quick(THD *thd, bool force_quick_range, ha_rows limit)
00935   {
00936     key_map tmp(key_map::ALL_BITS);
00937     return test_quick_select(thd, tmp, 0, limit, force_quick_range,
00938                              ORDER::ORDER_NOT_RELEVANT) < 0;
00939   }
00940   inline bool skip_record(THD *thd, bool *skip_record)
00941   {
00942     *skip_record= cond ? cond->val_int() == FALSE : FALSE;
00943     return thd->is_error();
00944   }
00945   int test_quick_select(THD *thd, key_map keys, table_map prev_tables,
00946                         ha_rows limit, bool force_quick_range,
00947                         const ORDER::enum_order interesting_order);
00948 };
00949 
00950 
00951 class FT_SELECT: public QUICK_RANGE_SELECT 
00952 {
00953 public:
00954   FT_SELECT(THD *thd, TABLE *table, uint key, bool *error) :
00955       QUICK_RANGE_SELECT (thd, table, key, 1, NULL, error) { (void) init(); }
00956   ~FT_SELECT() { file->ft_end(); }
00957   int init() { return file->ft_init(); }
00958   int reset() { return 0; }
00959   int get_next() { return file->ft_read(record); }
00960   int get_type() { return QS_TYPE_FULLTEXT; }
00961 };
00962 
00963 FT_SELECT *get_ft_select(THD *thd, TABLE *table, uint key);
00964 QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table,
00965                                              struct st_table_ref *ref,
00966                                              ha_rows records);
00967 SQL_SELECT *make_select(TABLE *head, table_map const_tables,
00968                         table_map read_tables, Item *conds,
00969                         bool allow_null_cond,  int *error);
00970 
00971 #ifdef WITH_PARTITION_STORAGE_ENGINE
00972 bool prune_partitions(THD *thd, TABLE *table, Item *pprune_cond);
00973 void store_key_image_to_rec(Field *field, uchar *ptr, uint len);
00974 #endif
00975 
00976 extern String null_string;
00977 
00978 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines