← 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: Mark Atwood
  • Date: 2008-10-03 01:39:40 UTC
  • mto: This revision was merged to the branch mainline in revision 437.
  • Revision ID: mark@fallenpegasus.com-20081003013940-mvefjo725dltz41h
rename logging_noop to logging_query

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