← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/quick_range_select.cc

  • Committer: Monty Taylor
  • Date: 2008-11-16 06:29:53 UTC
  • mto: (584.1.9 devel)
  • mto: This revision was merged to the branch mainline in revision 589.
  • Revision ID: monty@inaugust.com-20081116062953-ivdltjmfe009b5fr
Moved stuff into item/

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/optimizer/quick_range_select.cc
1
 
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2
 
 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3
 
 *
4
 
 *  Copyright (C) 2008-2009 Sun Microsystems
5
 
 *
6
 
 *  This program is free software; you can redistribute it and/or modify
7
 
 *  it under the terms of the GNU General Public License as published by
8
 
 *  the Free Software Foundation; version 2 of the License.
9
 
 *
10
 
 *  This program is distributed in the hope that it will be useful,
11
 
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12
 
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13
 
 *  GNU General Public License for more details.
14
 
 *
15
 
 *  You should have received a copy of the GNU General Public License
16
 
 *  along with this program; if not, write to the Free Software
17
 
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
18
 
 */
19
 
 
20
 
#include "config.h"
21
 
#include "drizzled/session.h"
22
 
#include "drizzled/optimizer/quick_range.h"
23
 
#include "drizzled/optimizer/quick_range_select.h"
24
 
#include "drizzled/sql_bitmap.h"
25
 
#include "drizzled/internal/m_string.h"
26
 
#include <fcntl.h>
27
 
 
28
 
using namespace std;
29
 
 
30
 
namespace drizzled
31
 
{
32
 
 
33
 
 
34
 
optimizer::QuickRangeSelect::QuickRangeSelect(Session *session,
35
 
                                              Table *table,
36
 
                                              uint32_t key_nr,
37
 
                                              bool no_alloc,
38
 
                                              memory::Root *parent_alloc,
39
 
                                              bool *create_error)
40
 
  :
41
 
    cursor(NULL),
42
 
    ranges(),
43
 
    in_ror_merged_scan(false),
44
 
    column_bitmap(),
45
 
    save_read_set(NULL),
46
 
    save_write_set(NULL),
47
 
    free_file(false),
48
 
    cur_range(NULL),
49
 
    last_range(NULL),
50
 
    qr_traversal_ctx(),
51
 
    mrr_buf_size(0),
52
 
    key_parts(NULL),
53
 
    dont_free(false),
54
 
    mrr_flags(0),
55
 
    alloc()
56
 
{
57
 
  my_bitmap_map *bitmap= NULL;
58
 
 
59
 
  sorted= 0;
60
 
  index= key_nr;
61
 
  head= table;
62
 
  key_part_info= head->key_info[index].key_part;
63
 
  my_init_dynamic_array(&ranges, sizeof(optimizer::QuickRange*), 16, 16);
64
 
 
65
 
  /* 'session' is not accessible in QuickRangeSelect::reset(). */
66
 
  mrr_buf_size= session->variables.read_rnd_buff_size;
67
 
 
68
 
  if (! no_alloc && ! parent_alloc)
69
 
  {
70
 
    // Allocates everything through the internal memroot
71
 
    memory::init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
72
 
    session->mem_root= &alloc;
73
 
  }
74
 
  else
75
 
  {
76
 
    memset(&alloc, 0, sizeof(alloc));
77
 
  }
78
 
 
79
 
  cursor= head->cursor;
80
 
  record= head->record[0];
81
 
  save_read_set= head->read_set;
82
 
  save_write_set= head->write_set;
83
 
 
84
 
  /* Allocate a bitmap for used columns. Using memory::sql_alloc instead of malloc
85
 
     simply as a "fix" to the MySQL 6.0 code that also free()s it at the
86
 
     same time we destroy the mem_root.
87
 
   */
88
 
 
89
 
  bitmap= reinterpret_cast<my_bitmap_map*>(memory::sql_alloc(head->getShare()->column_bitmap_size));
90
 
  if (! bitmap)
91
 
  {
92
 
    column_bitmap.setBitmap(NULL);
93
 
    *create_error= 1;
94
 
  }
95
 
  else
96
 
  {
97
 
    column_bitmap.init(bitmap, head->getShare()->sizeFields());
98
 
  }
99
 
}
100
 
 
101
 
 
102
 
int optimizer::QuickRangeSelect::init()
103
 
{
104
 
  if (cursor->inited != Cursor::NONE)
105
 
    cursor->ha_index_or_rnd_end();
106
 
  return (cursor->startIndexScan(index, 1));
107
 
}
108
 
 
109
 
 
110
 
void optimizer::QuickRangeSelect::range_end()
111
 
{
112
 
  if (cursor->inited != Cursor::NONE)
113
 
    cursor->ha_index_or_rnd_end();
114
 
}
115
 
 
116
 
 
117
 
optimizer::QuickRangeSelect::~QuickRangeSelect()
118
 
{
119
 
  if (! dont_free)
120
 
  {
121
 
    /* cursor is NULL for CPK scan on covering ROR-intersection */
122
 
    if (cursor)
123
 
    {
124
 
      range_end();
125
 
      if (head->key_read)
126
 
      {
127
 
        head->key_read= 0;
128
 
        cursor->extra(HA_EXTRA_NO_KEYREAD);
129
 
      }
130
 
      if (free_file)
131
 
      {
132
 
        cursor->ha_external_lock(current_session, F_UNLCK);
133
 
        cursor->close();
134
 
        delete cursor;
135
 
      }
136
 
    }
137
 
    delete_dynamic(&ranges); /* ranges are allocated in alloc */
138
 
    alloc.free_root(MYF(0));
139
 
  }
140
 
  head->column_bitmaps_set(save_read_set, save_write_set);
141
 
}
142
 
 
143
 
 
144
 
int optimizer::QuickRangeSelect::init_ror_merged_scan(bool reuse_handler)
145
 
{
146
 
  Cursor *save_file= cursor, *org_file;
147
 
  Session *session;
148
 
 
149
 
  in_ror_merged_scan= 1;
150
 
  if (reuse_handler)
151
 
  {
152
 
    if (init() || reset())
153
 
    {
154
 
      return 0;
155
 
    }
156
 
    head->column_bitmaps_set(&column_bitmap, &column_bitmap);
157
 
    goto end;
158
 
  }
159
 
 
160
 
  /* Create a separate Cursor object for this quick select */
161
 
  if (free_file)
162
 
  {
163
 
    /* already have own 'Cursor' object. */
164
 
    return 0;
165
 
  }
166
 
 
167
 
  session= head->in_use;
168
 
  if (! (cursor= head->cursor->clone(session->mem_root)))
169
 
  {
170
 
    /*
171
 
      Manually set the error flag. Note: there seems to be quite a few
172
 
      places where a failure could cause the server to "hang" the client by
173
 
      sending no response to a query. ATM those are not real errors because
174
 
      the storage engine calls in question happen to never fail with the
175
 
      existing storage engines.
176
 
    */
177
 
    my_error(ER_OUT_OF_RESOURCES, MYF(0));
178
 
    /* Caller will free the memory */
179
 
    goto failure;
180
 
  }
181
 
 
182
 
  head->column_bitmaps_set(&column_bitmap, &column_bitmap);
183
 
 
184
 
  if (cursor->ha_external_lock(session, F_RDLCK))
185
 
    goto failure;
186
 
 
187
 
  if (init() || reset())
188
 
  {
189
 
    cursor->ha_external_lock(session, F_UNLCK);
190
 
    cursor->close();
191
 
    goto failure;
192
 
  }
193
 
  free_file= true;
194
 
  last_rowid= cursor->ref;
195
 
 
196
 
end:
197
 
  /*
198
 
    We are only going to read key fields and call position() on 'cursor'
199
 
    The following sets head->tmp_set to only use this key and then updates
200
 
    head->read_set and head->write_set to use this bitmap.
201
 
    The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
202
 
  */
203
 
  org_file= head->cursor;
204
 
  head->cursor= cursor;
205
 
  /* We don't have to set 'head->keyread' here as the 'cursor' is unique */
206
 
  if (! head->no_keyread)
207
 
  {
208
 
    head->key_read= 1;
209
 
    head->mark_columns_used_by_index(index);
210
 
  }
211
 
  head->prepare_for_position();
212
 
  head->cursor= org_file;
213
 
  column_bitmap= *head->read_set;
214
 
  head->column_bitmaps_set(&column_bitmap, &column_bitmap);
215
 
 
216
 
  return 0;
217
 
 
218
 
failure:
219
 
  head->column_bitmaps_set(save_read_set, save_write_set);
220
 
  delete cursor;
221
 
  cursor= save_file;
222
 
  return 0;
223
 
}
224
 
 
225
 
 
226
 
void optimizer::QuickRangeSelect::save_last_pos()
227
 
{
228
 
  cursor->position(record);
229
 
}
230
 
 
231
 
 
232
 
bool optimizer::QuickRangeSelect::unique_key_range() const
233
 
{
234
 
  if (ranges.elements == 1)
235
 
  {
236
 
    optimizer::QuickRange *tmp= *((optimizer::QuickRange**)ranges.buffer);
237
 
    if ((tmp->flag & (EQ_RANGE | NULL_RANGE)) == EQ_RANGE)
238
 
    {
239
 
      KeyInfo *key=head->key_info+index;
240
 
      return ((key->flags & (HA_NOSAME)) == HA_NOSAME &&
241
 
              key->key_length == tmp->min_length);
242
 
    }
243
 
  }
244
 
  return false;
245
 
}
246
 
 
247
 
 
248
 
int optimizer::QuickRangeSelect::reset()
249
 
{
250
 
  int error= 0;
251
 
  last_range= NULL;
252
 
  cur_range= (optimizer::QuickRange**) ranges.buffer;
253
 
 
254
 
  if (cursor->inited == Cursor::NONE && (error= cursor->startIndexScan(index, 1)))
255
 
  {
256
 
    return error;
257
 
  }
258
 
 
259
 
  /*
260
 
    (in the past) Allocate buffer if we need one but haven't allocated it yet 
261
 
    There is a later assert in th code that hoped to catch random free() that might
262
 
    have done this.
263
 
  */
264
 
  assert(not (mrr_buf_size));
265
 
 
266
 
  if (sorted)
267
 
  {
268
 
     mrr_flags|= HA_MRR_SORTED;
269
 
  }
270
 
  RANGE_SEQ_IF seq_funcs= {
271
 
    optimizer::quick_range_seq_init,
272
 
    optimizer::quick_range_seq_next
273
 
  };
274
 
  error= cursor->multi_range_read_init(&seq_funcs,
275
 
                                       (void*) this,
276
 
                                       ranges.elements,
277
 
                                       mrr_flags);
278
 
  return error;
279
 
}
280
 
 
281
 
 
282
 
int optimizer::QuickRangeSelect::get_next()
283
 
{
284
 
  char *dummy= NULL;
285
 
  if (in_ror_merged_scan)
286
 
  {
287
 
    /*
288
 
      We don't need to signal the bitmap change as the bitmap is always the
289
 
      same for this head->cursor
290
 
    */
291
 
    head->column_bitmaps_set(&column_bitmap, &column_bitmap);
292
 
  }
293
 
 
294
 
  int result= cursor->multi_range_read_next(&dummy);
295
 
 
296
 
  if (in_ror_merged_scan)
297
 
  {
298
 
    /* Restore bitmaps set on entry */
299
 
    head->column_bitmaps_set(save_read_set, save_write_set);
300
 
  }
301
 
  return result;
302
 
}
303
 
 
304
 
 
305
 
int optimizer::QuickRangeSelect::get_next_prefix(uint32_t prefix_length,
306
 
                                                 key_part_map keypart_map,
307
 
                                                 unsigned char *cur_prefix)
308
 
{
309
 
  for (;;)
310
 
  {
311
 
    int result;
312
 
    key_range start_key, end_key;
313
 
    if (last_range)
314
 
    {
315
 
      /* Read the next record in the same range with prefix after cur_prefix. */
316
 
      assert(cur_prefix != 0);
317
 
      result= cursor->index_read_map(record,
318
 
                                     cur_prefix,
319
 
                                     keypart_map,
320
 
                                     HA_READ_AFTER_KEY);
321
 
      if (result || (cursor->compare_key(cursor->end_range) <= 0))
322
 
        return result;
323
 
    }
324
 
 
325
 
    uint32_t count= ranges.elements - (cur_range - (optimizer::QuickRange**) ranges.buffer);
326
 
    if (count == 0)
327
 
    {
328
 
      /* Ranges have already been used up before. None is left for read. */
329
 
      last_range= 0;
330
 
      return HA_ERR_END_OF_FILE;
331
 
    }
332
 
    last_range= *(cur_range++);
333
 
 
334
 
    start_key.key= (const unsigned char*) last_range->min_key;
335
 
    start_key.length= min(last_range->min_length, (uint16_t)prefix_length);
336
 
    start_key.keypart_map= last_range->min_keypart_map & keypart_map;
337
 
    start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
338
 
                                                                (last_range->flag & EQ_RANGE) ?
339
 
                                                                HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
340
 
    end_key.key= (const unsigned char*) last_range->max_key;
341
 
    end_key.length= min(last_range->max_length, (uint16_t)prefix_length);
342
 
    end_key.keypart_map= last_range->max_keypart_map & keypart_map;
343
 
    /*
344
 
      We use READ_AFTER_KEY here because if we are reading on a key
345
 
      prefix we want to find all keys with this prefix
346
 
    */
347
 
    end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
348
 
                                                             HA_READ_AFTER_KEY);
349
 
 
350
 
    result= cursor->read_range_first(last_range->min_keypart_map ? &start_key : 0,
351
 
                                                             last_range->max_keypart_map ? &end_key : 0,
352
 
                                     test(last_range->flag & EQ_RANGE),
353
 
                                                             sorted);
354
 
    if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
355
 
      last_range= 0; // Stop searching
356
 
 
357
 
    if (result != HA_ERR_END_OF_FILE)
358
 
      return result;
359
 
    last_range= 0; // No matching rows; go to next range
360
 
  }
361
 
}
362
 
 
363
 
 
364
 
bool optimizer::QuickRangeSelect::row_in_ranges()
365
 
{
366
 
  optimizer::QuickRange *res= NULL;
367
 
  uint32_t min= 0;
368
 
  uint32_t max= ranges.elements - 1;
369
 
  uint32_t mid= (max + min) / 2;
370
 
 
371
 
  while (min != max)
372
 
  {
373
 
    if (cmp_next(*(optimizer::QuickRange**)dynamic_array_ptr(&ranges, mid)))
374
 
    {
375
 
      /* current row value > mid->max */
376
 
      min= mid + 1;
377
 
    }
378
 
    else
379
 
      max= mid;
380
 
    mid= (min + max) / 2;
381
 
  }
382
 
  res= *(optimizer::QuickRange**)dynamic_array_ptr(&ranges, mid);
383
 
  return (! cmp_next(res) && ! cmp_prev(res));
384
 
}
385
 
 
386
 
 
387
 
int optimizer::QuickRangeSelect::cmp_next(optimizer::QuickRange *range_arg)
388
 
{
389
 
  if (range_arg->flag & NO_MAX_RANGE)
390
 
    return 0;                                   /* key can't be to large */
391
 
 
392
 
  KEY_PART *key_part= key_parts;
393
 
  uint32_t store_length;
394
 
 
395
 
  for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
396
 
       key < end;
397
 
       key+= store_length, key_part++)
398
 
  {
399
 
    int cmp;
400
 
    store_length= key_part->store_length;
401
 
    if (key_part->null_bit)
402
 
    {
403
 
      if (*key)
404
 
      {
405
 
        if (! key_part->field->is_null())
406
 
          return 1;
407
 
        continue;
408
 
      }
409
 
      else if (key_part->field->is_null())
410
 
        return 0;
411
 
      key++;                                    // Skip null byte
412
 
      store_length--;
413
 
    }
414
 
    if ((cmp= key_part->field->key_cmp(key, key_part->length)) < 0)
415
 
      return 0;
416
 
    if (cmp > 0)
417
 
      return 1;
418
 
  }
419
 
  return (range_arg->flag & NEAR_MAX) ? 1 : 0;          // Exact match
420
 
}
421
 
 
422
 
 
423
 
int optimizer::QuickRangeSelect::cmp_prev(optimizer::QuickRange *range_arg)
424
 
{
425
 
  if (range_arg->flag & NO_MIN_RANGE)
426
 
    return 0; /* key can't be to small */
427
 
 
428
 
  int cmp= key_cmp(key_part_info,
429
 
                   range_arg->min_key,
430
 
                   range_arg->min_length);
431
 
  if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
432
 
    return 0;
433
 
  return 1; // outside of range
434
 
}
435
 
 
436
 
 
437
 
void optimizer::QuickRangeSelect::add_info_string(String *str)
438
 
{
439
 
  KeyInfo *key_info= head->key_info + index;
440
 
  str->append(key_info->name);
441
 
}
442
 
 
443
 
 
444
 
void optimizer::QuickRangeSelect::add_keys_and_lengths(String *key_names,
445
 
                                                       String *used_lengths)
446
 
{
447
 
  char buf[64];
448
 
  uint32_t length;
449
 
  KeyInfo *key_info= head->key_info + index;
450
 
  key_names->append(key_info->name);
451
 
  length= internal::int64_t2str(max_used_key_length, buf, 10) - buf;
452
 
  used_lengths->append(buf, length);
453
 
}
454
 
 
455
 
 
456
 
/*
457
 
  This is a hack: we inherit from QUICK_SELECT so that we can use the
458
 
  get_next() interface, but we have to hold a pointer to the original
459
 
  QUICK_SELECT because its data are used all over the place.  What
460
 
  should be done is to factor out the data that is needed into a base
461
 
  class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
462
 
  which handle the ranges and implement the get_next() function.  But
463
 
  for now, this seems to work right at least.
464
 
 */
465
 
optimizer::QuickSelectDescending::QuickSelectDescending(optimizer::QuickRangeSelect *q, uint32_t, bool *)
466
 
  :
467
 
    optimizer::QuickRangeSelect(*q)
468
 
{
469
 
  optimizer::QuickRange **pr= (optimizer::QuickRange**) ranges.buffer;
470
 
  optimizer::QuickRange **end_range= pr + ranges.elements;
471
 
  for (; pr != end_range; pr++)
472
 
  {
473
 
    rev_ranges.push_back(*pr);
474
 
  }
475
 
  rev_it= rev_ranges.begin();
476
 
 
477
 
  /* Remove EQ_RANGE flag for keys that are not using the full key */
478
 
  for (vector<optimizer::QuickRange *>::iterator it= rev_ranges.begin();
479
 
       it != rev_ranges.end();
480
 
       ++it)
481
 
  {
482
 
    optimizer::QuickRange *r= *it;
483
 
    if ((r->flag & EQ_RANGE) &&
484
 
        head->key_info[index].key_length != r->max_length)
485
 
    {
486
 
      r->flag&= ~EQ_RANGE;
487
 
    }
488
 
  }
489
 
  q->dont_free= 1; // Don't free shared mem
490
 
  delete q;
491
 
}
492
 
 
493
 
 
494
 
int optimizer::QuickSelectDescending::get_next()
495
 
{
496
 
  /* The max key is handled as follows:
497
 
   *   - if there is NO_MAX_RANGE, start at the end and move backwards
498
 
   *   - if it is an EQ_RANGE, which means that max key covers the entire
499
 
   *     key, go directly to the key and read through it (sorting backwards is
500
 
   *     same as sorting forwards)
501
 
   *   - if it is NEAR_MAX, go to the key or next, step back once, and
502
 
   *     move backwards
503
 
   *   - otherwise (not NEAR_MAX == include the key), go after the key,
504
 
   *     step back once, and move backwards
505
 
   */
506
 
  for (;;)
507
 
  {
508
 
    int result;
509
 
    if (last_range)
510
 
    {                                           // Already read through key
511
 
      result= ((last_range->flag & EQ_RANGE) ?
512
 
                           cursor->index_next_same(record, last_range->min_key,
513
 
                                                                     last_range->min_length) :
514
 
                           cursor->index_prev(record));
515
 
      if (! result)
516
 
      {
517
 
          if (cmp_prev(*(rev_it - 1)) == 0)
518
 
            return 0;
519
 
      }
520
 
      else if (result != HA_ERR_END_OF_FILE)
521
 
        return result;
522
 
    }
523
 
 
524
 
    if (rev_it == rev_ranges.end())
525
 
    {
526
 
      return HA_ERR_END_OF_FILE; // All ranges used
527
 
    }
528
 
    last_range= *rev_it;
529
 
    ++rev_it;
530
 
 
531
 
    if (last_range->flag & NO_MAX_RANGE)        // Read last record
532
 
    {
533
 
      int local_error;
534
 
      if ((local_error= cursor->index_last(record)))
535
 
        return local_error;     // Empty table
536
 
      if (cmp_prev(last_range) == 0)
537
 
        return 0;
538
 
      last_range= 0; // No match; go to next range
539
 
      continue;
540
 
    }
541
 
 
542
 
    if (last_range->flag & EQ_RANGE)
543
 
    {
544
 
      result = cursor->index_read_map(record,
545
 
                                      last_range->max_key,
546
 
                                      last_range->max_keypart_map,
547
 
                                      HA_READ_KEY_EXACT);
548
 
    }
549
 
    else
550
 
    {
551
 
      assert(last_range->flag & NEAR_MAX ||
552
 
             range_reads_after_key(last_range));
553
 
      result= cursor->index_read_map(record,
554
 
                                     last_range->max_key,
555
 
                                     last_range->max_keypart_map,
556
 
                                     ((last_range->flag & NEAR_MAX) ?
557
 
                                      HA_READ_BEFORE_KEY :
558
 
                                      HA_READ_PREFIX_LAST_OR_PREV));
559
 
    }
560
 
    if (result)
561
 
    {
562
 
      if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
563
 
        return result;
564
 
      last_range= 0;                            // Not found, to next range
565
 
      continue;
566
 
    }
567
 
    if (cmp_prev(last_range) == 0)
568
 
    {
569
 
      if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
570
 
        last_range= 0;                          // Stop searching
571
 
      return 0;                         // Found key is in range
572
 
    }
573
 
    last_range= 0;                              // To next range
574
 
  }
575
 
}
576
 
 
577
 
 
578
 
/*
579
 
 * true if this range will require using HA_READ_AFTER_KEY
580
 
   See comment in get_next() about this
581
 
 */
582
 
bool optimizer::QuickSelectDescending::range_reads_after_key(optimizer::QuickRange *range_arg)
583
 
{
584
 
  return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
585
 
                ! (range_arg->flag & EQ_RANGE) ||
586
 
                head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
587
 
}
588
 
 
589
 
 
590
 
} /* namespace drizzled */