← 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: Mats Kindahl
  • Date: 2008-08-26 07:32:59 UTC
  • mto: (489.1.2 codestyle)
  • mto: This revision was merged to the branch mainline in revision 491.
  • Revision ID: mats@mysql.com-20080826073259-9k4evtajgldgolli
Replaced use of thd_proc_info() macro with calls to
set_proc_info() and get_proc_info() internally.  Introduced
functions set_thd_proc_info() and get_thd_proc_info() for
external users, i.e., plug-ins.

The set_thd_proc_info() accepted callers info that can be used to
print debug output, but the information was not used. The return
value was changed to void and the old value is not fetched any
more. To be able to get the value of proc_info for external
users, the function get_thd_proc_info() was introduced.

The thd_proc_info() macro called set_thd_proc_info() but almost
never used the return value of set_thd_proc_info() so the macro
was replaced with a call of THD::set_proc_info().

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/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 */