Drizzled Public API Documentation

quick_range_select.cc
00001 /* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
00002  *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
00003  *
00004  *  Copyright (C) 2008-2009 Sun Microsystems, Inc.
00005  *
00006  *  This program is free software; you can redistribute it and/or modify
00007  *  it under the terms of the GNU General Public License as published by
00008  *  the Free Software Foundation; version 2 of the License.
00009  *
00010  *  This program is distributed in the hope that it will be useful,
00011  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00012  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013  *  GNU General Public License for more details.
00014  *
00015  *  You should have received a copy of the GNU General Public License
00016  *  along with this program; if not, write to the Free Software
00017  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00018  */
00019 
00020 #include <config.h>
00021 
00022 #include <drizzled/session.h>
00023 #include <drizzled/optimizer/quick_range.h>
00024 #include <drizzled/optimizer/quick_range_select.h>
00025 #include <drizzled/internal/m_string.h>
00026 #include <drizzled/current_session.h>
00027 #include <drizzled/key.h>
00028 #include <drizzled/table.h>
00029 
00030 #include <fcntl.h>
00031 
00032 using namespace std;
00033 
00034 namespace drizzled
00035 {
00036 
00037 
00038 optimizer::QuickRangeSelect::QuickRangeSelect(Session *session,
00039                                               Table *table,
00040                                               uint32_t key_nr,
00041                                               bool no_alloc,
00042                                               memory::Root *parent_alloc)
00043   :
00044     cursor(NULL),
00045     ranges(),
00046     in_ror_merged_scan(false),
00047     column_bitmap(NULL),
00048     save_read_set(NULL),
00049     save_write_set(NULL),
00050     free_file(false),
00051     cur_range(NULL),
00052     last_range(NULL),
00053     qr_traversal_ctx(),
00054     mrr_buf_size(0),
00055     key_parts(NULL),
00056     dont_free(false),
00057     mrr_flags(0),
00058     alloc()
00059 {
00060   sorted= 0;
00061   index= key_nr;
00062   head= table;
00063   key_part_info= head->key_info[index].key_part;
00064   my_init_dynamic_array(&ranges, sizeof(optimizer::QuickRange*), 16, 16);
00065 
00066   /* 'session' is not accessible in QuickRangeSelect::reset(). */
00067   mrr_buf_size= session->variables.read_rnd_buff_size;
00068 
00069   if (! no_alloc && ! parent_alloc)
00070   {
00071     // Allocates everything through the internal memroot
00072     memory::init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
00073     session->mem_root= &alloc;
00074   }
00075   else
00076   {
00077     memset(&alloc, 0, sizeof(alloc));
00078   }
00079 
00080   cursor= head->cursor;
00081   record= head->record[0];
00082   save_read_set= head->read_set;
00083   save_write_set= head->write_set;
00084   column_bitmap= new boost::dynamic_bitset<>(table->getShare()->sizeFields());
00085 }
00086 
00087 
00088 int optimizer::QuickRangeSelect::init()
00089 {
00090   if (cursor->inited != Cursor::NONE)
00091     cursor->ha_index_or_rnd_end();
00092   return (cursor->startIndexScan(index, 1));
00093 }
00094 
00095 
00096 void optimizer::QuickRangeSelect::range_end()
00097 {
00098   if (cursor->inited != Cursor::NONE)
00099     cursor->ha_index_or_rnd_end();
00100 }
00101 
00102 
00103 optimizer::QuickRangeSelect::~QuickRangeSelect()
00104 {
00105   if (! dont_free)
00106   {
00107     /* cursor is NULL for CPK scan on covering ROR-intersection */
00108     if (cursor)
00109     {
00110       range_end();
00111       if (head->key_read)
00112       {
00113         head->key_read= 0;
00114         cursor->extra(HA_EXTRA_NO_KEYREAD);
00115       }
00116       if (free_file)
00117       {
00118         cursor->ha_external_lock(current_session, F_UNLCK);
00119         cursor->close();
00120         delete cursor;
00121       }
00122     }
00123     delete_dynamic(&ranges); /* ranges are allocated in alloc */
00124     delete column_bitmap;
00125     alloc.free_root(MYF(0));
00126   }
00127   head->column_bitmaps_set(*save_read_set, *save_write_set);
00128 }
00129 
00130 
00131 int optimizer::QuickRangeSelect::init_ror_merged_scan(bool reuse_handler)
00132 {
00133   Cursor *save_file= cursor, *org_file;
00134   Session *session;
00135 
00136   in_ror_merged_scan= 1;
00137   if (reuse_handler)
00138   {
00139     if (init() || reset())
00140     {
00141       return 0;
00142     }
00143     head->column_bitmaps_set(*column_bitmap, *column_bitmap);
00144     goto end;
00145   }
00146 
00147   /* Create a separate Cursor object for this quick select */
00148   if (free_file)
00149   {
00150     /* already have own 'Cursor' object. */
00151     return 0;
00152   }
00153 
00154   session= head->in_use;
00155   if (! (cursor= head->cursor->clone(session->mem_root)))
00156   {
00157     /*
00158       Manually set the error flag. Note: there seems to be quite a few
00159       places where a failure could cause the server to "hang" the client by
00160       sending no response to a query. ATM those are not real errors because
00161       the storage engine calls in question happen to never fail with the
00162       existing storage engines.
00163     */
00164     my_error(ER_OUT_OF_RESOURCES, MYF(0));
00165     /* Caller will free the memory */
00166     goto failure;
00167   }
00168 
00169   head->column_bitmaps_set(*column_bitmap, *column_bitmap);
00170 
00171   if (cursor->ha_external_lock(session, F_RDLCK))
00172     goto failure;
00173 
00174   if (init() || reset())
00175   {
00176     cursor->ha_external_lock(session, F_UNLCK);
00177     cursor->close();
00178     goto failure;
00179   }
00180   free_file= true;
00181   last_rowid= cursor->ref;
00182 
00183 end:
00184   /*
00185     We are only going to read key fields and call position() on 'cursor'
00186     The following sets head->tmp_set to only use this key and then updates
00187     head->read_set and head->write_set to use this bitmap.
00188     The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
00189   */
00190   org_file= head->cursor;
00191   head->cursor= cursor;
00192   /* We don't have to set 'head->keyread' here as the 'cursor' is unique */
00193   if (! head->no_keyread)
00194   {
00195     head->key_read= 1;
00196     head->mark_columns_used_by_index(index);
00197   }
00198   head->prepare_for_position();
00199   head->cursor= org_file;
00200   *column_bitmap|= *head->read_set;
00201   head->column_bitmaps_set(*column_bitmap, *column_bitmap);
00202 
00203   return 0;
00204 
00205 failure:
00206   head->column_bitmaps_set(*save_read_set, *save_write_set);
00207   delete cursor;
00208   cursor= save_file;
00209   return 0;
00210 }
00211 
00212 
00213 void optimizer::QuickRangeSelect::save_last_pos()
00214 {
00215   cursor->position(record);
00216 }
00217 
00218 
00219 bool optimizer::QuickRangeSelect::unique_key_range() const
00220 {
00221   if (ranges.size() == 1)
00222   {
00223     optimizer::QuickRange *tmp= *((optimizer::QuickRange**)ranges.buffer);
00224     if ((tmp->flag & (EQ_RANGE | NULL_RANGE)) == EQ_RANGE)
00225     {
00226       KeyInfo *key=head->key_info+index;
00227       return ((key->flags & (HA_NOSAME)) == HA_NOSAME &&
00228         key->key_length == tmp->min_length);
00229     }
00230   }
00231   return false;
00232 }
00233 
00234 
00235 int optimizer::QuickRangeSelect::reset()
00236 {
00237   int error= 0;
00238   last_range= NULL;
00239   cur_range= (optimizer::QuickRange**) ranges.buffer;
00240 
00241   if (cursor->inited == Cursor::NONE && (error= cursor->startIndexScan(index, 1)))
00242   {
00243     return error;
00244   }
00245 
00246   /*
00247     (in the past) Allocate buffer if we need one but haven't allocated it yet 
00248     There is a later assert in th code that hoped to catch random free() that might
00249     have done this.
00250   */
00251   assert(not (mrr_buf_size));
00252 
00253   if (sorted)
00254   {
00255      mrr_flags|= HA_MRR_SORTED;
00256   }
00257   RANGE_SEQ_IF seq_funcs= {
00258     optimizer::quick_range_seq_init,
00259     optimizer::quick_range_seq_next
00260   };
00261   error= cursor->multi_range_read_init(&seq_funcs,
00262                                        (void*) this,
00263                                        ranges.size(),
00264                                        mrr_flags);
00265   return error;
00266 }
00267 
00268 
00269 int optimizer::QuickRangeSelect::get_next()
00270 {
00271   char *dummy= NULL;
00272   if (in_ror_merged_scan)
00273   {
00274     /*
00275       We don't need to signal the bitmap change as the bitmap is always the
00276       same for this head->cursor
00277     */
00278     head->column_bitmaps_set(*column_bitmap, *column_bitmap);
00279   }
00280 
00281   int result= cursor->multi_range_read_next(&dummy);
00282 
00283   if (in_ror_merged_scan)
00284   {
00285     /* Restore bitmaps set on entry */
00286     head->column_bitmaps_set(*save_read_set, *save_write_set);
00287   }
00288   return result;
00289 }
00290 
00291 
00292 int optimizer::QuickRangeSelect::get_next_prefix(uint32_t prefix_length,
00293                                                  key_part_map keypart_map,
00294                                                  unsigned char *cur_prefix)
00295 {
00296   for (;;)
00297   {
00298     int result;
00299     key_range start_key, end_key;
00300     if (last_range)
00301     {
00302       /* Read the next record in the same range with prefix after cur_prefix. */
00303       assert(cur_prefix != 0);
00304       result= cursor->index_read_map(record,
00305                                      cur_prefix,
00306                                      keypart_map,
00307                                      HA_READ_AFTER_KEY);
00308       if (result || (cursor->compare_key(cursor->end_range) <= 0))
00309         return result;
00310     }
00311 
00312     uint32_t count= ranges.size() - (cur_range - (optimizer::QuickRange**) ranges.buffer);
00313     if (count == 0)
00314     {
00315       /* Ranges have already been used up before. None is left for read. */
00316       last_range= 0;
00317       return HA_ERR_END_OF_FILE;
00318     }
00319     last_range= *(cur_range++);
00320 
00321     start_key.key= (const unsigned char*) last_range->min_key;
00322     start_key.length= min(last_range->min_length, (uint16_t)prefix_length);
00323     start_key.keypart_map= last_range->min_keypart_map & keypart_map;
00324     start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
00325                                                     (last_range->flag & EQ_RANGE) ?
00326                                                     HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
00327     end_key.key= (const unsigned char*) last_range->max_key;
00328     end_key.length= min(last_range->max_length, (uint16_t)prefix_length);
00329     end_key.keypart_map= last_range->max_keypart_map & keypart_map;
00330     /*
00331       We use READ_AFTER_KEY here because if we are reading on a key
00332       prefix we want to find all keys with this prefix
00333     */
00334     end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
00335                                                  HA_READ_AFTER_KEY);
00336 
00337     result= cursor->read_range_first(last_range->min_keypart_map ? &start_key : 0,
00338                                      last_range->max_keypart_map ? &end_key : 0,
00339                                      test(last_range->flag & EQ_RANGE),
00340                                      sorted);
00341     if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
00342       last_range= 0; // Stop searching
00343 
00344     if (result != HA_ERR_END_OF_FILE)
00345       return result;
00346     last_range= 0; // No matching rows; go to next range
00347   }
00348 }
00349 
00350 
00351 bool optimizer::QuickRangeSelect::row_in_ranges()
00352 {
00353   optimizer::QuickRange *res= NULL;
00354   uint32_t min= 0;
00355   uint32_t max= ranges.size() - 1;
00356   uint32_t mid= (max + min) / 2;
00357 
00358   while (min != max)
00359   {
00360     if (cmp_next(reinterpret_cast<optimizer::QuickRange**>(ranges.buffer)[mid]))
00361     {
00362       /* current row value > mid->max */
00363       min= mid + 1;
00364     }
00365     else
00366       max= mid;
00367     mid= (min + max) / 2;
00368   }
00369   res= reinterpret_cast<optimizer::QuickRange**>(ranges.buffer)[mid];
00370   return not cmp_next(res) && not cmp_prev(res);
00371 }
00372 
00373 
00374 int optimizer::QuickRangeSelect::cmp_next(optimizer::QuickRange *range_arg)
00375 {
00376   if (range_arg->flag & NO_MAX_RANGE)
00377     return 0;                                   /* key can't be to large */
00378 
00379   KEY_PART *key_part= key_parts;
00380   uint32_t store_length;
00381 
00382   for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
00383        key < end;
00384        key+= store_length, key_part++)
00385   {
00386     int cmp;
00387     store_length= key_part->store_length;
00388     if (key_part->null_bit)
00389     {
00390       if (*key)
00391       {
00392         if (! key_part->field->is_null())
00393           return 1;
00394         continue;
00395       }
00396       else if (key_part->field->is_null())
00397         return 0;
00398       key++;          // Skip null byte
00399       store_length--;
00400     }
00401     if ((cmp= key_part->field->key_cmp(key, key_part->length)) < 0)
00402       return 0;
00403     if (cmp > 0)
00404       return 1;
00405   }
00406   return (range_arg->flag & NEAR_MAX) ? 1 : 0;          // Exact match
00407 }
00408 
00409 
00410 int optimizer::QuickRangeSelect::cmp_prev(optimizer::QuickRange *range_arg)
00411 {
00412   if (range_arg->flag & NO_MIN_RANGE)
00413     return 0; /* key can't be to small */
00414 
00415   int cmp= key_cmp(key_part_info,
00416                    range_arg->min_key,
00417                    range_arg->min_length);
00418   if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
00419     return 0;
00420   return 1; // outside of range
00421 }
00422 
00423 
00424 void optimizer::QuickRangeSelect::add_info_string(string *str)
00425 {
00426   KeyInfo *key_info= head->key_info + index;
00427   str->append(key_info->name);
00428 }
00429 
00430 
00431 void optimizer::QuickRangeSelect::add_keys_and_lengths(string *key_names,
00432                                                        string *used_lengths)
00433 {
00434   char buf[64];
00435   uint32_t length;
00436   KeyInfo *key_info= head->key_info + index;
00437   key_names->append(key_info->name);
00438   length= internal::int64_t2str(max_used_key_length, buf, 10) - buf;
00439   used_lengths->append(buf, length);
00440 }
00441 
00442 
00443 /*
00444   This is a hack: we inherit from QUICK_SELECT so that we can use the
00445   get_next() interface, but we have to hold a pointer to the original
00446   QUICK_SELECT because its data are used all over the place.  What
00447   should be done is to factor out the data that is needed into a base
00448   class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
00449   which handle the ranges and implement the get_next() function.  But
00450   for now, this seems to work right at least.
00451  */
00452 optimizer::QuickSelectDescending::QuickSelectDescending(optimizer::QuickRangeSelect *q, uint32_t, bool *)
00453   :
00454     optimizer::QuickRangeSelect(*q)
00455 {
00456   optimizer::QuickRange **pr= (optimizer::QuickRange**) ranges.buffer;
00457   optimizer::QuickRange **end_range= pr + ranges.size();
00458   for (; pr != end_range; pr++)
00459   {
00460     rev_ranges.push_back(*pr);
00461   }
00462   rev_it= rev_ranges.begin();
00463 
00464   /* Remove EQ_RANGE flag for keys that are not using the full key */
00465   for (vector<optimizer::QuickRange *>::iterator it= rev_ranges.begin();
00466        it != rev_ranges.end();
00467        ++it)
00468   {
00469     optimizer::QuickRange *r= *it;
00470     if ((r->flag & EQ_RANGE) &&
00471         head->key_info[index].key_length != r->max_length)
00472     {
00473       r->flag&= ~EQ_RANGE;
00474     }
00475   }
00476   q->dont_free= 1; // Don't free shared mem
00477   delete q;
00478 }
00479 
00480 
00481 int optimizer::QuickSelectDescending::get_next()
00482 {
00483   /* The max key is handled as follows:
00484    *   - if there is NO_MAX_RANGE, start at the end and move backwards
00485    *   - if it is an EQ_RANGE, which means that max key covers the entire
00486    *     key, go directly to the key and read through it (sorting backwards is
00487    *     same as sorting forwards)
00488    *   - if it is NEAR_MAX, go to the key or next, step back once, and
00489    *     move backwards
00490    *   - otherwise (not NEAR_MAX == include the key), go after the key,
00491    *     step back once, and move backwards
00492    */
00493   for (;;)
00494   {
00495     int result;
00496     if (last_range)
00497     {           // Already read through key
00498       result= ((last_range->flag & EQ_RANGE) ?
00499                cursor->index_next_same(record, last_range->min_key,
00500                                        last_range->min_length) :
00501                cursor->index_prev(record));
00502       if (! result)
00503       {
00504           if (cmp_prev(*(rev_it - 1)) == 0)
00505             return 0;
00506       }
00507       else if (result != HA_ERR_END_OF_FILE)
00508         return result;
00509     }
00510 
00511     if (rev_it == rev_ranges.end())
00512     {
00513       return HA_ERR_END_OF_FILE; // All ranges used
00514     }
00515     last_range= *rev_it;
00516     ++rev_it;
00517 
00518     if (last_range->flag & NO_MAX_RANGE)        // Read last record
00519     {
00520       int local_error;
00521       if ((local_error= cursor->index_last(record)))
00522         return local_error; // Empty table
00523       if (cmp_prev(last_range) == 0)
00524         return 0;
00525       last_range= 0; // No match; go to next range
00526       continue;
00527     }
00528 
00529     if (last_range->flag & EQ_RANGE)
00530     {
00531       result = cursor->index_read_map(record,
00532                                       last_range->max_key,
00533                                       last_range->max_keypart_map,
00534                                       HA_READ_KEY_EXACT);
00535     }
00536     else
00537     {
00538       assert(last_range->flag & NEAR_MAX ||
00539              range_reads_after_key(last_range));
00540       result= cursor->index_read_map(record,
00541                                      last_range->max_key,
00542                                      last_range->max_keypart_map,
00543                                      ((last_range->flag & NEAR_MAX) ?
00544                                       HA_READ_BEFORE_KEY :
00545                                       HA_READ_PREFIX_LAST_OR_PREV));
00546     }
00547     if (result)
00548     {
00549       if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
00550         return result;
00551       last_range= 0;                            // Not found, to next range
00552       continue;
00553     }
00554     if (cmp_prev(last_range) == 0)
00555     {
00556       if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
00557         last_range= 0;        // Stop searching
00558       return 0;       // Found key is in range
00559     }
00560     last_range= 0;                              // To next range
00561   }
00562 }
00563 
00564 
00565 /*
00566  * true if this range will require using HA_READ_AFTER_KEY
00567    See comment in get_next() about this
00568  */
00569 bool optimizer::QuickSelectDescending::range_reads_after_key(optimizer::QuickRange *range_arg)
00570 {
00571   return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
00572           ! (range_arg->flag & EQ_RANGE) ||
00573           head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
00574 }
00575 
00576 
00577 } /* namespace drizzled */