key.cc 15.2 KB
Newer Older
unknown's avatar
unknown committed
1
/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
unknown's avatar
unknown committed
2

unknown's avatar
unknown committed
3 4 5 6
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
unknown's avatar
unknown committed
7

unknown's avatar
unknown committed
8 9 10 11
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
unknown's avatar
unknown committed
12

unknown's avatar
unknown committed
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */


/* Functions to handle keys and fields in forms */

#include "mysql_priv.h"

	/*
	** Search after with key field is. If no key starts with field test
	** if field is part of some key.
	**
	** returns number of key. keylength is set to length of key before
	** (not including) field
	** Used when calculating key for NEXT_NUMBER
	*/

unknown's avatar
unknown committed
31
int find_ref_key(KEY *key, uint key_count, Field *field, uint *key_length)
unknown's avatar
unknown committed
32 33 34 35 36 37 38 39 40
{
  reg2 int i;
  reg3 KEY *key_info;
  uint fieldpos;

  fieldpos=    field->offset();

	/* Test if some key starts as fieldpos */

unknown's avatar
unknown committed
41 42
  for (i= 0, key_info= key ;
       i < (int) key_count ;
43
       i++, key_info++)
unknown's avatar
unknown committed
44 45 46 47 48 49 50 51 52
  {
    if (key_info->key_part[0].offset == fieldpos)
    {						/* Found key. Calc keylength */
      *key_length=0;
      return(i);			/* Use this key */
    }
  }
	/* Test if some key contains fieldpos */

unknown's avatar
unknown committed
53 54
  for (i= 0, key_info= key;
       i < (int) key_count ;
55
       i++, key_info++)
unknown's avatar
unknown committed
56 57 58 59 60 61 62 63 64 65
  {
    uint j;
    KEY_PART_INFO *key_part;
    *key_length=0;
    for (j=0, key_part=key_info->key_part ;
	 j < key_info->key_parts ;
	 j++, key_part++)
    {
      if (key_part->offset == fieldpos)
	return(i);			/* Use this key */
unknown's avatar
unknown committed
66
      *key_length+=key_part->store_length;
unknown's avatar
unknown committed
67 68 69 70 71 72
    }
  }
  return(-1);					/* No key is ok */
}


73 74
/*
  Copy part of a record that forms a key or key prefix to a buffer.
unknown's avatar
unknown committed
75

76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
  SYNOPSIS
    key_copy()
    to_key      buffer that will be used as a key
    from_record full record to be copied from
    key_info    descriptor of the index
    key_length  specifies length of all keyparts that will be copied

  DESCRIPTION
    The function takes a complete table record (as e.g. retrieved by
    handler::index_read()), and a description of an index on the same table,
    and extracts the first key_length bytes of the record which are part of a
    key into to_key. If length == 0 then copy all bytes from the record that
    form a key.

  RETURN
    None
*/
unknown's avatar
unknown committed
93

94
void key_copy(byte *to_key, byte *from_record, KEY *key_info, uint key_length)
unknown's avatar
unknown committed
95 96 97 98 99
{
  uint length;
  KEY_PART_INFO *key_part;

  if (key_length == 0)
100 101
    key_length= key_info->key_length;
  for (key_part= key_info->key_part; (int) key_length > 0; key_part++)
unknown's avatar
unknown committed
102 103 104
  {
    if (key_part->null_bit)
    {
105
      *to_key++= test(from_record[key_part->null_offset] &
unknown's avatar
unknown committed
106 107 108
		   key_part->null_bit);
      key_length--;
    }
unknown's avatar
unknown committed
109 110 111 112 113 114 115 116 117 118 119 120 121
    if (key_part->type == HA_KEYTYPE_BIT)
    {
      Field_bit *field= (Field_bit *) (key_part->field);
      if (field->bit_len)
      {
        uchar bits= get_rec_bits((uchar*) from_record +
                                 key_part->null_offset +
                                 (key_part->null_bit == 128),
                                 field->bit_ofs, field->bit_len);
        *to_key++= bits;
        key_length--;
      }
    }
unknown's avatar
unknown committed
122 123 124
    if (key_part->key_part_flag & HA_BLOB_PART)
    {
      char *pos;
125
      ulong blob_length= ((Field_blob*) key_part->field)->get_length();
126
      key_length-= HA_KEY_BLOB_LENGTH;
unknown's avatar
unknown committed
127
      ((Field_blob*) key_part->field)->get_ptr(&pos);
128 129 130
      length=min(key_length, key_part->length);
      set_if_smaller(blob_length, length);
      int2store(to_key, (uint) blob_length);
131
      to_key+= HA_KEY_BLOB_LENGTH;			// Skip length info
132
      memcpy(to_key, pos, blob_length);
unknown's avatar
unknown committed
133
    }
134 135 136 137
    else if (key_part->key_part_flag & HA_VAR_LENGTH_PART)
    {
      key_length-= HA_KEY_BLOB_LENGTH;
      length= min(key_length, key_part->length);
unknown's avatar
unknown committed
138
      key_part->field->get_key_image((char *) to_key, length, Field::itRAW);
139 140
      to_key+= HA_KEY_BLOB_LENGTH;
    }
unknown's avatar
unknown committed
141 142
    else
    {
143 144
      length= min(key_length, key_part->length);
      memcpy(to_key, from_record + key_part->offset, (size_t) length);
unknown's avatar
unknown committed
145
    }
146 147
    to_key+= length;
    key_length-= length;
unknown's avatar
unknown committed
148
  }
149
}
unknown's avatar
unknown committed
150 151


152 153
/*
  Restore a key from some buffer to record.
unknown's avatar
unknown committed
154

155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171
  SYNOPSIS
    key_restore()
    to_record   record buffer where the key will be restored to
    from_key    buffer that contains a key
    key_info    descriptor of the index
    key_length  specifies length of all keyparts that will be restored

  DESCRIPTION
    This function converts a key into record format. It can be used in cases
    when we want to return a key as a result row.

  RETURN
    None
*/

void key_restore(byte *to_record, byte *from_key, KEY *key_info,
                 uint key_length)
unknown's avatar
unknown committed
172 173 174 175 176 177
{
  uint length;
  KEY_PART_INFO *key_part;

  if (key_length == 0)
  {
178
    key_length= key_info->key_length;
unknown's avatar
unknown committed
179
  }
180
  for (key_part= key_info->key_part ; (int) key_length > 0 ; key_part++)
unknown's avatar
unknown committed
181 182 183
  {
    if (key_part->null_bit)
    {
184 185
      if (*from_key++)
	to_record[key_part->null_offset]|= key_part->null_bit;
unknown's avatar
unknown committed
186
      else
187
	to_record[key_part->null_offset]&= ~key_part->null_bit;
unknown's avatar
unknown committed
188 189
      key_length--;
    }
unknown's avatar
unknown committed
190 191 192 193 194
    if (key_part->type == HA_KEYTYPE_BIT)
    {
      Field_bit *field= (Field_bit *) (key_part->field);
      if (field->bit_len)
      {
unknown's avatar
unknown committed
195 196
        uchar bits= *(from_key + key_part->length -
                      field->pack_length_in_rec() - 1);
unknown's avatar
unknown committed
197 198 199 200 201
        set_rec_bits(bits, to_record + key_part->null_offset +
                     (key_part->null_bit == 128),
                     field->bit_ofs, field->bit_len);
      }
    }
unknown's avatar
unknown committed
202 203
    if (key_part->key_part_flag & HA_BLOB_PART)
    {
204
      uint blob_length= uint2korr(from_key);
205 206
      from_key+= HA_KEY_BLOB_LENGTH;
      key_length-= HA_KEY_BLOB_LENGTH;
unknown's avatar
unknown committed
207
      ((Field_blob*) key_part->field)->set_ptr((ulong) blob_length,
208 209
					       (char*) from_key);
      length= key_part->length;
unknown's avatar
unknown committed
210
    }
211 212
    else if (key_part->key_part_flag & HA_VAR_LENGTH_PART)
    {
213
      my_bitmap_map *old_map;
214 215
      key_length-= HA_KEY_BLOB_LENGTH;
      length= min(key_length, key_part->length);
216 217
      old_map= dbug_tmp_use_all_columns(key_part->field->table,
                                        key_part->field->table->write_set);
unknown's avatar
unknown committed
218
      key_part->field->set_key_image((char *) from_key, length);
219
      dbug_tmp_restore_column_map(key_part->field->table->write_set, old_map);
220 221
      from_key+= HA_KEY_BLOB_LENGTH;
    }
unknown's avatar
unknown committed
222 223
    else
    {
224 225
      length= min(key_length, key_part->length);
      memcpy(to_record + key_part->offset, from_key, (size_t) length);
unknown's avatar
unknown committed
226
    }
227 228
    from_key+= length;
    key_length-= length;
unknown's avatar
unknown committed
229
  }
230
}
unknown's avatar
unknown committed
231 232


unknown's avatar
unknown committed
233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252
/*
  Compare if a key has changed

  SYNOPSIS
    key_cmp_if_same()
    table		TABLE
    key			key to compare to row
    idx			Index used
    key_length		Length of key

  NOTES
    In theory we could just call field->cmp() for all field types,
    but as we are only interested if a key has changed (not if the key is
    larger or smaller than the previous value) we can do things a bit
    faster by using memcmp() instead.

  RETURN
    0	If key is equal
    1	Key has changed
*/
unknown's avatar
unknown committed
253

unknown's avatar
unknown committed
254
bool key_cmp_if_same(TABLE *table,const byte *key,uint idx,uint key_length)
unknown's avatar
unknown committed
255
{
unknown's avatar
unknown committed
256
  uint store_length;
unknown's avatar
unknown committed
257
  KEY_PART_INFO *key_part;
unknown's avatar
unknown committed
258
  const byte *key_end= key + key_length;;
unknown's avatar
unknown committed
259 260

  for (key_part=table->key_info[idx].key_part;
unknown's avatar
unknown committed
261 262
       key < key_end ; 
       key_part++, key+= store_length)
unknown's avatar
unknown committed
263
  {
unknown's avatar
unknown committed
264 265 266
    uint length;
    store_length= key_part->store_length;

unknown's avatar
unknown committed
267 268 269
    if (key_part->null_bit)
    {
      if (*key != test(table->record[0][key_part->null_offset] & 
270
		       key_part->null_bit))
unknown's avatar
unknown committed
271 272 273 274
	return 1;
      if (*key)
	continue;
      key++;
unknown's avatar
unknown committed
275
      store_length--;
unknown's avatar
unknown committed
276
    }
unknown's avatar
unknown committed
277 278
    if (key_part->key_part_flag & (HA_BLOB_PART | HA_VAR_LENGTH_PART |
                                   HA_BIT_PART))
unknown's avatar
unknown committed
279
    {
280
      if (key_part->field->key_cmp(key, key_part->length))
unknown's avatar
unknown committed
281
	return 1;
unknown's avatar
unknown committed
282
      continue;
unknown's avatar
unknown committed
283
    }
unknown's avatar
unknown committed
284 285 286
    length= min((uint) (key_end-key), store_length);
    if (!(key_part->key_type & (FIELDFLAG_NUMBER+FIELDFLAG_BINARY+
                                FIELDFLAG_PACK)))
unknown's avatar
unknown committed
287
    {
unknown's avatar
unknown committed
288 289 290 291
      CHARSET_INFO *cs= key_part->field->charset();
      uint char_length= key_part->length / cs->mbmaxlen;
      const byte *pos= table->record[0] + key_part->offset;
      if (length > char_length)
unknown's avatar
unknown committed
292
      {
unknown's avatar
unknown committed
293 294
        char_length= my_charpos(cs, pos, pos + length, char_length);
        set_if_smaller(char_length, length);
unknown's avatar
unknown committed
295
      }
unknown's avatar
unknown committed
296 297 298 299 300
      if (cs->coll->strnncollsp(cs,
                                (const uchar*) key, length,
                                (const uchar*) pos, char_length, 0))
        return 1;
      continue;
unknown's avatar
unknown committed
301
    }
unknown's avatar
unknown committed
302 303
    if (memcmp(key,table->record[0]+key_part->offset,length))
      return 1;
unknown's avatar
unknown committed
304 305 306 307
  }
  return 0;
}

308 309 310 311 312 313 314 315 316 317 318 319 320
/*
  unpack key-fields from record to some buffer

  SYNOPSIS
     key_unpack()
     to		Store value here in an easy to read form
     table	Table to use
     idx	Key number

  NOTES
    This is used mainly to get a good error message
    We temporary change the column bitmap so that all columns are readable.
*/
unknown's avatar
unknown committed
321 322 323 324 325 326

void key_unpack(String *to,TABLE *table,uint idx)
{
  KEY_PART_INFO *key_part,*key_part_end;
  Field *field;
  String tmp;
327
  my_bitmap_map *old_map= dbug_tmp_use_all_columns(table, table->read_set);
unknown's avatar
unknown committed
328 329 330 331 332 333 334 335 336 337 338 339 340 341
  DBUG_ENTER("key_unpack");

  to->length(0);
  for (key_part=table->key_info[idx].key_part,key_part_end=key_part+
	 table->key_info[idx].key_parts ;
       key_part < key_part_end;
       key_part++)
  {
    if (to->length())
      to->append('-');
    if (key_part->null_bit)
    {
      if (table->record[0][key_part->null_offset] & key_part->null_bit)
      {
342
	to->append(STRING_WITH_LEN("NULL"));
unknown's avatar
unknown committed
343 344 345 346 347
	continue;
      }
    }
    if ((field=key_part->field))
    {
348
      field->val_str(&tmp);
unknown's avatar
unknown committed
349 350 351 352 353
      if (key_part->length < field->pack_length())
	tmp.length(min(tmp.length(),key_part->length));
      to->append(tmp);
    }
    else
354
      to->append(STRING_WITH_LEN("???"));
unknown's avatar
unknown committed
355
  }
356
  dbug_tmp_restore_column_map(table->read_set, old_map);
unknown's avatar
unknown committed
357 358 359 360
  DBUG_VOID_RETURN;
}


361
/*
362 363 364 365 366 367 368 369 370 371 372 373 374 375 376
  Check if key uses field that is marked in passed field bitmap.

  SYNOPSIS
    is_key_used()
      table   TABLE object with which keys and fields are associated.
      idx     Key to be checked.
      fields  Bitmap of fields to be checked.

  NOTE
    This function uses TABLE::tmp_set bitmap so the caller should care
    about saving/restoring its state if it also uses this bitmap.

  RETURN VALUE
    TRUE   Key uses field from bitmap
    FALSE  Otherwise
377
*/
unknown's avatar
unknown committed
378

379
bool is_key_used(TABLE *table, uint idx, const MY_BITMAP *fields)
unknown's avatar
unknown committed
380
{
381 382 383 384
  bitmap_clear_all(&table->tmp_set);
  table->mark_columns_used_by_index_no_reset(idx, &table->tmp_set);
  if (bitmap_is_overlapping(&table->tmp_set, fields))
    return 1;
385 386 387 388 389

  /*
    If table handler has primary key as part of the index, check that primary
    key is not updated
  */
390
  if (idx != table->s->primary_key && table->s->primary_key < MAX_KEY &&
391
      (table->file->ha_table_flags() & HA_PRIMARY_KEY_IN_READ_INDEX))
392
    return is_key_used(table, table->s->primary_key, fields);
unknown's avatar
unknown committed
393 394
  return 0;
}
unknown's avatar
unknown committed
395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447


/*
  Compare key in row to a given key

  SYNOPSIS
    key_cmp()
    key_part		Key part handler
    key			Key to compare to value in table->record[0]
    key_length		length of 'key'

  RETURN
    The return value is SIGN(key_in_row - range_key):

    0			Key is equal to range or 'range' == 0 (no range)
   -1			Key is less than range
    1			Key is larger than range
*/

int key_cmp(KEY_PART_INFO *key_part, const byte *key, uint key_length)
{
  uint store_length;

  for (const byte *end=key + key_length;
       key < end;
       key+= store_length, key_part++)
  {
    int cmp;
    store_length= key_part->store_length;
    if (key_part->null_bit)
    {
      /* This key part allows null values; NULL is lower than everything */
      register bool field_is_null= key_part->field->is_null();
      if (*key)                                 // If range key is null
      {
	/* the range is expecting a null value */
	if (!field_is_null)
	  return 1;                             // Found key is > range
        /* null -- exact match, go to next key part */
	continue;
      }
      else if (field_is_null)
	return -1;                              // NULL is less than any value
      key++;					// Skip null byte
      store_length--;
    }
    if ((cmp=key_part->field->key_cmp((byte*) key, key_part->length)) < 0)
      return -1;
    if (cmp > 0)
      return 1;
  }
  return 0;                                     // Keys are equal
}
448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479


/*
  Compare two records in index order
  SYNOPSIS
    key_rec_cmp()
    key                         Index information
    rec0                        Pointer to table->record[0]
    first_rec                   Pointer to record compare with
    second_rec                  Pointer to record compare against first_rec
  DESCRIPTION
    This method is set-up such that it can be called directly from the
    priority queue and it is attempted to be optimised as much as possible
    since this will be called O(N * log N) times while performing a merge
    sort in various places in the code.

    We retrieve the pointer to table->record[0] using the fact that key_parts
    have an offset making it possible to calculate the start of the record.
    We need to get the diff to the compared record since none of the records
    being compared are stored in table->record[0].

    We first check for NULL values, if there are no NULL values we use
    a compare method that gets two field pointers and a max length
    and return the result of the comparison.
*/

int key_rec_cmp(void *key, byte *first_rec, byte *second_rec)
{
  KEY *key_info= (KEY*)key;
  uint key_parts= key_info->key_parts, i= 0;
  KEY_PART_INFO *key_part= key_info->key_part;
  char *rec0= key_part->field->ptr - key_part->offset;
480
  my_ptrdiff_t first_diff= first_rec - (byte*)rec0, sec_diff= second_rec - (byte*)rec0;
481 482 483 484 485 486 487 488 489 490
  int result= 0;
  DBUG_ENTER("key_rec_cmp");

  do
  {
    Field *field= key_part->field;

    if (key_part->null_bit)
    {
      /* The key_part can contain NULL values */
unknown's avatar
unknown committed
491 492
      bool first_is_null= field->is_null_in_record_with_offset(first_diff);
      bool sec_is_null= field->is_null_in_record_with_offset(sec_diff);
493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529
      /*
        NULL is smaller then everything so if first is NULL and the other
        not then we know that we should return -1 and for the opposite
        we should return +1. If both are NULL then we call it equality
        although it is a strange form of equality, we have equally little
        information of the real value.
      */
      if (!first_is_null)
      {
        if (!sec_is_null)
          ; /* Fall through, no NULL fields */
        else
        {
          DBUG_RETURN(+1);
        }
      }
      else if (!sec_is_null)
      {
        DBUG_RETURN(-1);
      }
      else
        goto next_loop; /* Both were NULL */
    }
    /*
      No null values in the fields
      We use the virtual method cmp_max with a max length parameter.
      For most field types this translates into a cmp without
      max length. The exceptions are the BLOB and VARCHAR field types
      that take the max length into account.
    */
    result= field->cmp_max(field->ptr+first_diff, field->ptr+sec_diff,
                           key_part->length);
next_loop:
    key_part++;
  } while (!result && ++i < key_parts);
  DBUG_RETURN(result);
}