← Back to branch summary

~stewart/drizzle/embedded-innodb-create-select-transaction-arrgh

« back to all changes in this revision

Viewing changes to sql/key.cc

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

Show diffs side-by-side

added added

removed removed

Lines of Context:
sql/key.cc
 
1
/* Copyright (C) 2000-2006 MySQL AB
 
2
 
 
3
   This program is free software; you can redistribute it and/or modify
 
4
   it under the terms of the GNU General Public License as published by
 
5
   the Free Software Foundation; version 2 of the License.
 
6
 
 
7
   This program is distributed in the hope that it will be useful,
 
8
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
   GNU General Public License for more details.
 
11
 
 
12
   You should have received a copy of the GNU General Public License
 
13
   along with this program; if not, write to the Free Software
 
14
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
15
 
 
16
 
 
17
/* Functions to handle keys and fields in forms */
 
18
 
 
19
#include "mysql_priv.h"
 
20
 
 
21
/*
 
22
  Search after a key that starts with 'field'
 
23
 
 
24
  SYNOPSIS
 
25
    find_ref_key()
 
26
    key                 First key to check
 
27
    key_count           How many keys to check
 
28
    record              Start of record
 
29
    field               Field to search after
 
30
    key_length          On partial match, contains length of fields before
 
31
                        field
 
32
    keypart             key part # of a field
 
33
 
 
34
  NOTES
 
35
   Used when calculating key for NEXT_NUMBER
 
36
 
 
37
  IMPLEMENTATION
 
38
    If no key starts with field test if field is part of some key. If we find
 
39
    one, then return first key and set key_length to the number of bytes
 
40
    preceding 'field'.
 
41
 
 
42
  RETURN
 
43
   -1  field is not part of the key
 
44
   #   Key part for key matching key.
 
45
       key_length is set to length of key before (not including) field
 
46
*/
 
47
 
 
48
int find_ref_key(KEY *key, uint key_count, uchar *record, Field *field,
 
49
                 uint *key_length, uint *keypart)
 
50
{
 
51
  register int i;
 
52
  register KEY *key_info;
 
53
  uint fieldpos;
 
54
 
 
55
  fieldpos= field->offset(record);
 
56
 
 
57
  /* Test if some key starts as fieldpos */
 
58
  for (i= 0, key_info= key ;
 
59
       i < (int) key_count ;
 
60
       i++, key_info++)
 
61
  {
 
62
    if (key_info->key_part[0].offset == fieldpos)
 
63
    {                                           /* Found key. Calc keylength */
 
64
      *key_length= *keypart= 0;
 
65
      return i;                                 /* Use this key */
 
66
    }
 
67
  }
 
68
 
 
69
  /* Test if some key contains fieldpos */
 
70
  for (i= 0, key_info= key;
 
71
       i < (int) key_count ;
 
72
       i++, key_info++)
 
73
  {
 
74
    uint j;
 
75
    KEY_PART_INFO *key_part;
 
76
    *key_length=0;
 
77
    for (j=0, key_part=key_info->key_part ;
 
78
         j < key_info->key_parts ;
 
79
         j++, key_part++)
 
80
    {
 
81
      if (key_part->offset == fieldpos)
 
82
      {
 
83
        *keypart= j;
 
84
        return i;                               /* Use this key */
 
85
      }
 
86
      *key_length+= key_part->store_length;
 
87
    }
 
88
  }
 
89
  return(-1);                                   /* No key is ok */
 
90
}
 
91
 
 
92
 
 
93
/**
 
94
  Copy part of a record that forms a key or key prefix to a buffer.
 
95
 
 
96
    The function takes a complete table record (as e.g. retrieved by
 
97
    handler::index_read()), and a description of an index on the same table,
 
98
    and extracts the first key_length bytes of the record which are part of a
 
99
    key into to_key. If length == 0 then copy all bytes from the record that
 
100
    form a key.
 
101
 
 
102
  @param to_key      buffer that will be used as a key
 
103
  @param from_record full record to be copied from
 
104
  @param key_info    descriptor of the index
 
105
  @param key_length  specifies length of all keyparts that will be copied
 
106
*/
 
107
 
 
108
void key_copy(uchar *to_key, uchar *from_record, KEY *key_info,
 
109
              uint key_length)
 
110
{
 
111
  uint length;
 
112
  KEY_PART_INFO *key_part;
 
113
 
 
114
  if (key_length == 0)
 
115
    key_length= key_info->key_length;
 
116
  for (key_part= key_info->key_part; (int) key_length > 0; key_part++)
 
117
  {
 
118
    if (key_part->null_bit)
 
119
    {
 
120
      *to_key++= test(from_record[key_part->null_offset] &
 
121
                   key_part->null_bit);
 
122
      key_length--;
 
123
    }
 
124
    if (key_part->key_part_flag & HA_BLOB_PART ||
 
125
        key_part->key_part_flag & HA_VAR_LENGTH_PART)
 
126
    {
 
127
      key_length-= HA_KEY_BLOB_LENGTH;
 
128
      length= min(key_length, key_part->length);
 
129
      key_part->field->get_key_image(to_key, length, Field::itRAW);
 
130
      to_key+= HA_KEY_BLOB_LENGTH;
 
131
    }
 
132
    else
 
133
    {
 
134
      length= min(key_length, key_part->length);
 
135
      Field *field= key_part->field;
 
136
      CHARSET_INFO *cs= field->charset();
 
137
      uint bytes= field->get_key_image(to_key, length, Field::itRAW);
 
138
      if (bytes < length)
 
139
        cs->cset->fill(cs, (char*) to_key + bytes, length - bytes, ' ');
 
140
    }
 
141
    to_key+= length;
 
142
    key_length-= length;
 
143
  }
 
144
}
 
145
 
 
146
 
 
147
/**
 
148
  Zero the null components of key tuple.
 
149
*/
 
150
 
 
151
void key_zero_nulls(uchar *tuple, KEY *key_info)
 
152
{
 
153
  KEY_PART_INFO *key_part= key_info->key_part;
 
154
  KEY_PART_INFO *key_part_end= key_part + key_info->key_parts;
 
155
  for (; key_part != key_part_end; key_part++)
 
156
  {
 
157
    if (key_part->null_bit && *tuple)
 
158
      bzero(tuple+1, key_part->store_length-1);
 
159
    tuple+= key_part->store_length;
 
160
  }
 
161
}
 
162
 
 
163
 
 
164
/*
 
165
  Restore a key from some buffer to record.
 
166
 
 
167
    This function converts a key into record format. It can be used in cases
 
168
    when we want to return a key as a result row.
 
169
 
 
170
  @param to_record   record buffer where the key will be restored to
 
171
  @param from_key    buffer that contains a key
 
172
  @param key_info    descriptor of the index
 
173
  @param key_length  specifies length of all keyparts that will be restored
 
174
*/
 
175
 
 
176
void key_restore(uchar *to_record, uchar *from_key, KEY *key_info,
 
177
                 uint key_length)
 
178
{
 
179
  uint length;
 
180
  KEY_PART_INFO *key_part;
 
181
 
 
182
  if (key_length == 0)
 
183
  {
 
184
    key_length= key_info->key_length;
 
185
  }
 
186
  for (key_part= key_info->key_part ; (int) key_length > 0 ; key_part++)
 
187
  {
 
188
    uchar used_uneven_bits= 0;
 
189
    if (key_part->null_bit)
 
190
    {
 
191
      if (*from_key++)
 
192
        to_record[key_part->null_offset]|= key_part->null_bit;
 
193
      else
 
194
        to_record[key_part->null_offset]&= ~key_part->null_bit;
 
195
      key_length--;
 
196
    }
 
197
    if (key_part->type == HA_KEYTYPE_BIT)
 
198
    {
 
199
      Field_bit *field= (Field_bit *) (key_part->field);
 
200
      if (field->bit_len)
 
201
      {
 
202
        uchar bits= *(from_key + key_part->length -
 
203
                      field->pack_length_in_rec() - 1);
 
204
        set_rec_bits(bits, to_record + key_part->null_offset +
 
205
                     (key_part->null_bit == 128),
 
206
                     field->bit_ofs, field->bit_len);
 
207
        /* we have now used the byte with 'uneven' bits */
 
208
        used_uneven_bits= 1;
 
209
      }
 
210
    }
 
211
    if (key_part->key_part_flag & HA_BLOB_PART)
 
212
    {
 
213
      /*
 
214
        This in fact never happens, as we have only partial BLOB
 
215
        keys yet anyway, so it's difficult to find any sence to
 
216
        restore the part of a record.
 
217
        Maybe this branch is to be removed, but now we
 
218
        have to ignore GCov compaining.
 
219
      */
 
220
      uint blob_length= uint2korr(from_key);
 
221
      Field_blob *field= (Field_blob*) key_part->field;
 
222
      from_key+= HA_KEY_BLOB_LENGTH;
 
223
      key_length-= HA_KEY_BLOB_LENGTH;
 
224
      field->set_ptr_offset(to_record - field->table->record[0],
 
225
                            (ulong) blob_length, from_key);
 
226
      length= key_part->length;
 
227
    }
 
228
    else if (key_part->key_part_flag & HA_VAR_LENGTH_PART)
 
229
    {
 
230
      Field *field= key_part->field;
 
231
      my_bitmap_map *old_map;
 
232
      my_ptrdiff_t ptrdiff= to_record - field->table->record[0];
 
233
      field->move_field_offset(ptrdiff);
 
234
      key_length-= HA_KEY_BLOB_LENGTH;
 
235
      length= min(key_length, key_part->length);
 
236
      old_map= dbug_tmp_use_all_columns(field->table, field->table->write_set);
 
237
      field->set_key_image(from_key, length);
 
238
      dbug_tmp_restore_column_map(field->table->write_set, old_map);
 
239
      from_key+= HA_KEY_BLOB_LENGTH;
 
240
      field->move_field_offset(-ptrdiff);
 
241
    }
 
242
    else
 
243
    {
 
244
      length= min(key_length, key_part->length);
 
245
      /* skip the byte with 'uneven' bits, if used */
 
246
      memcpy(to_record + key_part->offset, from_key + used_uneven_bits
 
247
             , (size_t) length - used_uneven_bits);
 
248
    }
 
249
    from_key+= length;
 
250
    key_length-= length;
 
251
  }
 
252
}
 
253
 
 
254
 
 
255
/**
 
256
  Compare if a key has changed.
 
257
 
 
258
  @param table          TABLE
 
259
  @param key            key to compare to row
 
260
  @param idx            Index used
 
261
  @param key_length     Length of key
 
262
 
 
263
  @note
 
264
    In theory we could just call field->cmp() for all field types,
 
265
    but as we are only interested if a key has changed (not if the key is
 
266
    larger or smaller than the previous value) we can do things a bit
 
267
    faster by using memcmp() instead.
 
268
 
 
269
  @retval
 
270
    0   If key is equal
 
271
  @retval
 
272
    1   Key has changed
 
273
*/
 
274
 
 
275
bool key_cmp_if_same(TABLE *table,const uchar *key,uint idx,uint key_length)
 
276
{
 
277
  uint store_length;
 
278
  KEY_PART_INFO *key_part;
 
279
  const uchar *key_end= key + key_length;;
 
280
 
 
281
  for (key_part=table->key_info[idx].key_part;
 
282
       key < key_end ; 
 
283
       key_part++, key+= store_length)
 
284
  {
 
285
    uint length;
 
286
    store_length= key_part->store_length;
 
287
 
 
288
    if (key_part->null_bit)
 
289
    {
 
290
      if (*key != test(table->record[0][key_part->null_offset] & 
 
291
                       key_part->null_bit))
 
292
        return 1;
 
293
      if (*key)
 
294
        continue;
 
295
      key++;
 
296
      store_length--;
 
297
    }
 
298
    if (key_part->key_part_flag & (HA_BLOB_PART | HA_VAR_LENGTH_PART |
 
299
                                   HA_BIT_PART))
 
300
    {
 
301
      if (key_part->field->key_cmp(key, key_part->length))
 
302
        return 1;
 
303
      continue;
 
304
    }
 
305
    length= min((uint) (key_end-key), store_length);
 
306
    if (!(key_part->key_type & (FIELDFLAG_NUMBER+FIELDFLAG_BINARY+
 
307
                                FIELDFLAG_PACK)))
 
308
    {
 
309
      CHARSET_INFO *cs= key_part->field->charset();
 
310
      uint char_length= key_part->length / cs->mbmaxlen;
 
311
      const uchar *pos= table->record[0] + key_part->offset;
 
312
      if (length > char_length)
 
313
      {
 
314
        char_length= my_charpos(cs, pos, pos + length, char_length);
 
315
        set_if_smaller(char_length, length);
 
316
      }
 
317
      if (cs->coll->strnncollsp(cs,
 
318
                                (const uchar*) key, length,
 
319
                                (const uchar*) pos, char_length, 0))
 
320
        return 1;
 
321
      continue;
 
322
    }
 
323
    if (memcmp(key,table->record[0]+key_part->offset,length))
 
324
      return 1;
 
325
  }
 
326
  return 0;
 
327
}
 
328
 
 
329
/*
 
330
  unpack key-fields from record to some buffer.
 
331
 
 
332
  This is used mainly to get a good error message.  We temporary 
 
333
  change the column bitmap so that all columns are readable.
 
334
 
 
335
  @param
 
336
     to         Store value here in an easy to read form
 
337
  @param
 
338
     table      Table to use
 
339
  @param
 
340
     idx        Key number
 
341
*/
 
342
 
 
343
void key_unpack(String *to,TABLE *table,uint idx)
 
344
{
 
345
  KEY_PART_INFO *key_part,*key_part_end;
 
346
  Field *field;
 
347
  String tmp;
 
348
  my_bitmap_map *old_map= dbug_tmp_use_all_columns(table, table->read_set);
 
349
  DBUG_ENTER("key_unpack");
 
350
 
 
351
  to->length(0);
 
352
  for (key_part=table->key_info[idx].key_part,key_part_end=key_part+
 
353
         table->key_info[idx].key_parts ;
 
354
       key_part < key_part_end;
 
355
       key_part++)
 
356
  {
 
357
    if (to->length())
 
358
      to->append('-');
 
359
    if (key_part->null_bit)
 
360
    {
 
361
      if (table->record[0][key_part->null_offset] & key_part->null_bit)
 
362
      {
 
363
        to->append(STRING_WITH_LEN("NULL"));
 
364
        continue;
 
365
      }
 
366
    }
 
367
    if ((field=key_part->field))
 
368
    {
 
369
      CHARSET_INFO *cs= field->charset();
 
370
      field->val_str(&tmp);
 
371
      if (cs->mbmaxlen > 1 &&
 
372
          table->field[key_part->fieldnr - 1]->field_length !=
 
373
          key_part->length)
 
374
      {
 
375
        /*
 
376
          Prefix key, multi-byte charset.
 
377
          For the columns of type CHAR(N), the above val_str()
 
378
          call will return exactly "key_part->length" bytes,
 
379
          which can break a multi-byte characters in the middle.
 
380
          Align, returning not more than "char_length" characters.
 
381
        */
 
382
        uint charpos, char_length= key_part->length / cs->mbmaxlen;
 
383
        if ((charpos= my_charpos(cs, tmp.ptr(),
 
384
                                 tmp.ptr() + tmp.length(),
 
385
                                 char_length)) < key_part->length)
 
386
          tmp.length(charpos);
 
387
      }
 
388
      
 
389
      if (key_part->length < field->pack_length())
 
390
        tmp.length(min(tmp.length(),key_part->length));
 
391
      to->append(tmp);
 
392
    }
 
393
    else
 
394
      to->append(STRING_WITH_LEN("???"));
 
395
  }
 
396
  dbug_tmp_restore_column_map(table->read_set, old_map);
 
397
  DBUG_VOID_RETURN;
 
398
}
 
399
 
 
400
 
 
401
/*
 
402
  Check if key uses field that is marked in passed field bitmap.
 
403
 
 
404
  SYNOPSIS
 
405
    is_key_used()
 
406
      table   TABLE object with which keys and fields are associated.
 
407
      idx     Key to be checked.
 
408
      fields  Bitmap of fields to be checked.
 
409
 
 
410
  NOTE
 
411
    This function uses TABLE::tmp_set bitmap so the caller should care
 
412
    about saving/restoring its state if it also uses this bitmap.
 
413
 
 
414
  RETURN VALUE
 
415
    TRUE   Key uses field from bitmap
 
416
    FALSE  Otherwise
 
417
*/
 
418
 
 
419
bool is_key_used(TABLE *table, uint idx, const MY_BITMAP *fields)
 
420
{
 
421
  bitmap_clear_all(&table->tmp_set);
 
422
  table->mark_columns_used_by_index_no_reset(idx, &table->tmp_set);
 
423
  if (bitmap_is_overlapping(&table->tmp_set, fields))
 
424
    return 1;
 
425
 
 
426
  /*
 
427
    If table handler has primary key as part of the index, check that primary
 
428
    key is not updated
 
429
  */
 
430
  if (idx != table->s->primary_key && table->s->primary_key < MAX_KEY &&
 
431
      (table->file->ha_table_flags() & HA_PRIMARY_KEY_IN_READ_INDEX))
 
432
    return is_key_used(table, table->s->primary_key, fields);
 
433
  return 0;
 
434
}
 
435
 
 
436
 
 
437
/**
 
438
  Compare key in row to a given key.
 
439
 
 
440
  @param key_part               Key part handler
 
441
  @param key                    Key to compare to value in table->record[0]
 
442
  @param key_length             length of 'key'
 
443
 
 
444
  @return
 
445
    The return value is SIGN(key_in_row - range_key):
 
446
    -   0               Key is equal to range or 'range' == 0 (no range)
 
447
    -  -1               Key is less than range
 
448
    -   1               Key is larger than range
 
449
*/
 
450
 
 
451
int key_cmp(KEY_PART_INFO *key_part, const uchar *key, uint key_length)
 
452
{
 
453
  uint store_length;
 
454
 
 
455
  for (const uchar *end=key + key_length;
 
456
       key < end;
 
457
       key+= store_length, key_part++)
 
458
  {
 
459
    int cmp;
 
460
    store_length= key_part->store_length;
 
461
    if (key_part->null_bit)
 
462
    {
 
463
      /* This key part allows null values; NULL is lower than everything */
 
464
      register bool field_is_null= key_part->field->is_null();
 
465
      if (*key)                                 // If range key is null
 
466
      {
 
467
        /* the range is expecting a null value */
 
468
        if (!field_is_null)
 
469
          return 1;                             // Found key is > range
 
470
        /* null -- exact match, go to next key part */
 
471
        continue;
 
472
      }
 
473
      else if (field_is_null)
 
474
        return -1;                              // NULL is less than any value
 
475
      key++;                                    // Skip null byte
 
476
      store_length--;
 
477
    }
 
478
    if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0)
 
479
      return -1;
 
480
    if (cmp > 0)
 
481
      return 1;
 
482
  }
 
483
  return 0;                                     // Keys are equal
 
484
}
 
485
 
 
486
 
 
487
/*
 
488
  Compare two records in index order
 
489
  SYNOPSIS
 
490
    key_rec_cmp()
 
491
    key                         Index information
 
492
    rec0                        Pointer to table->record[0]
 
493
    first_rec                   Pointer to record compare with
 
494
    second_rec                  Pointer to record compare against first_rec
 
495
 
 
496
  DESCRIPTION
 
497
    This method is set-up such that it can be called directly from the
 
498
    priority queue and it is attempted to be optimised as much as possible
 
499
    since this will be called O(N * log N) times while performing a merge
 
500
    sort in various places in the code.
 
501
 
 
502
    We retrieve the pointer to table->record[0] using the fact that key_parts
 
503
    have an offset making it possible to calculate the start of the record.
 
504
    We need to get the diff to the compared record since none of the records
 
505
    being compared are stored in table->record[0].
 
506
 
 
507
    We first check for NULL values, if there are no NULL values we use
 
508
    a compare method that gets two field pointers and a max length
 
509
    and return the result of the comparison.
 
510
*/
 
511
 
 
512
int key_rec_cmp(void *key, uchar *first_rec, uchar *second_rec)
 
513
{
 
514
  KEY *key_info= (KEY*)key;
 
515
  uint key_parts= key_info->key_parts, i= 0;
 
516
  KEY_PART_INFO *key_part= key_info->key_part;
 
517
  uchar *rec0= key_part->field->ptr - key_part->offset;
 
518
  my_ptrdiff_t first_diff= first_rec - rec0, sec_diff= second_rec - rec0;
 
519
  int result= 0;
 
520
  DBUG_ENTER("key_rec_cmp");
 
521
 
 
522
  do
 
523
  {
 
524
    Field *field= key_part->field;
 
525
 
 
526
    if (key_part->null_bit)
 
527
    {
 
528
      /* The key_part can contain NULL values */
 
529
      bool first_is_null= field->is_null_in_record_with_offset(first_diff);
 
530
      bool sec_is_null= field->is_null_in_record_with_offset(sec_diff);
 
531
      /*
 
532
        NULL is smaller then everything so if first is NULL and the other
 
533
        not then we know that we should return -1 and for the opposite
 
534
        we should return +1. If both are NULL then we call it equality
 
535
        although it is a strange form of equality, we have equally little
 
536
        information of the real value.
 
537
      */
 
538
      if (!first_is_null)
 
539
      {
 
540
        if (!sec_is_null)
 
541
          ; /* Fall through, no NULL fields */
 
542
        else
 
543
        {
 
544
          DBUG_RETURN(+1);
 
545
        }
 
546
      }
 
547
      else if (!sec_is_null)
 
548
      {
 
549
        DBUG_RETURN(-1);
 
550
      }
 
551
      else
 
552
        goto next_loop; /* Both were NULL */
 
553
    }
 
554
    /*
 
555
      No null values in the fields
 
556
      We use the virtual method cmp_max with a max length parameter.
 
557
      For most field types this translates into a cmp without
 
558
      max length. The exceptions are the BLOB and VARCHAR field types
 
559
      that take the max length into account.
 
560
    */
 
561
    result= field->cmp_max(field->ptr+first_diff, field->ptr+sec_diff,
 
562
                           key_part->length);
 
563
next_loop:
 
564
    key_part++;
 
565
  } while (!result && ++i < key_parts);
 
566
  DBUG_RETURN(result);
 
567
}