← 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: Brian Aker
  • Date: 2009-02-21 00:18:15 UTC
  • Revision ID: brian@tangent.org-20090221001815-x20e8h71e984lvs1
Completion (?) of uint conversion.

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