opt_range.cc 79.5 KB
Newer Older
unknown's avatar
unknown committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB

   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.

   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.

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

unknown's avatar
unknown committed
17 18 19 20 21
/*
  TODO:
  Fix that MAYBE_KEY are stored in the tree so that we can detect use
  of full hash keys for queries like:

unknown's avatar
unknown committed
22 23
  select s.id, kws.keyword_id from sites as s,kws where s.id=kws.site_id and kws.keyword_id in (204,205);

unknown's avatar
unknown committed
24 25
*/

unknown's avatar
unknown committed
26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
#ifdef __GNUC__
#pragma implementation				// gcc: Class implementation
#endif

#include "mysql_priv.h"
#include <m_ctype.h>
#include <nisam.h>
#include "sql_select.h"

#ifndef EXTRA_DEBUG
#define test_rb_tree(A,B) {}
#define test_use_count(A) {}
#endif


static int sel_cmp(Field *f,char *a,char *b,uint8 a_flag,uint8 b_flag);

static char is_null_string[2]= {1,0};

class SEL_ARG :public Sql_alloc
{
public:
  uint8 min_flag,max_flag,maybe_flag;
  uint8 part;					// Which key part
  uint8 maybe_null;
  uint16 elements;				// Elements in tree
  ulong use_count;				// use of this sub_tree
  Field *field;
  char *min_value,*max_value;			// Pointer to range

  SEL_ARG *left,*right,*next,*prev,*parent,*next_key_part;
  enum leaf_color { BLACK,RED } color;
  enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;

  SEL_ARG() {}
  SEL_ARG(SEL_ARG &);
  SEL_ARG(Field *,const char *,const char *);
  SEL_ARG(Field *field, uint8 part, char *min_value, char *max_value,
	  uint8 min_flag, uint8 max_flag, uint8 maybe_flag);
  SEL_ARG(enum Type type_arg)
unknown's avatar
unknown committed
66 67 68
    :elements(1),use_count(1),left(0),next_key_part(0),color(BLACK),
     type(type_arg)
  {}
unknown's avatar
unknown committed
69 70
  inline bool is_same(SEL_ARG *arg)
  {
71
    if (type != arg->type || part != arg->part)
unknown's avatar
unknown committed
72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172
      return 0;
    if (type != KEY_RANGE)
      return 1;
    return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0;
  }
  inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
  inline void maybe_smaller() { maybe_flag=1; }
  inline int cmp_min_to_min(SEL_ARG* arg)
  {
    return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
  }
  inline int cmp_min_to_max(SEL_ARG* arg)
  {
    return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);
  }
  inline int cmp_max_to_max(SEL_ARG* arg)
  {
    return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);
  }
  inline int cmp_max_to_min(SEL_ARG* arg)
  {
    return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);
  }
  SEL_ARG *clone_and(SEL_ARG* arg)
  {						// Get overlapping range
    char *new_min,*new_max;
    uint8 flag_min,flag_max;
    if (cmp_min_to_min(arg) >= 0)
    {
      new_min=min_value; flag_min=min_flag;
    }
    else
    {
      new_min=arg->min_value; flag_min=arg->min_flag; /* purecov: deadcode */
    }
    if (cmp_max_to_max(arg) <= 0)
    {
      new_max=max_value; flag_max=max_flag;
    }
    else
    {
      new_max=arg->max_value; flag_max=arg->max_flag;
    }
    return new SEL_ARG(field, part, new_min, new_max, flag_min, flag_max,
		       test(maybe_flag && arg->maybe_flag));
  }
  SEL_ARG *clone_first(SEL_ARG *arg)
  {						// min <= X < arg->min
    return new SEL_ARG(field,part, min_value, arg->min_value,
		       min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
		       maybe_flag | arg->maybe_flag);
  }
  SEL_ARG *clone_last(SEL_ARG *arg)
  {						// min <= X <= key_max
    return new SEL_ARG(field, part, min_value, arg->max_value,
		       min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
  }
  SEL_ARG *clone(SEL_ARG *new_parent,SEL_ARG **next);

  bool copy_min(SEL_ARG* arg)
  {						// Get overlapping range
    if (cmp_min_to_min(arg) > 0)
    {
      min_value=arg->min_value; min_flag=arg->min_flag;
      if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
	  (NO_MAX_RANGE | NO_MIN_RANGE))
	return 1;				// Full range
    }
    maybe_flag|=arg->maybe_flag;
    return 0;
  }
  bool copy_max(SEL_ARG* arg)
  {						// Get overlapping range
    if (cmp_max_to_max(arg) <= 0)
    {
      max_value=arg->max_value; max_flag=arg->max_flag;
      if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
	  (NO_MAX_RANGE | NO_MIN_RANGE))
	return 1;				// Full range
    }
    maybe_flag|=arg->maybe_flag;
    return 0;
  }

  void copy_min_to_min(SEL_ARG *arg)
  {
    min_value=arg->min_value; min_flag=arg->min_flag;
  }
  void copy_min_to_max(SEL_ARG *arg)
  {
    max_value=arg->min_value;
    max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
  }
  void copy_max_to_min(SEL_ARG *arg)
  {
    min_value=arg->max_value;
    min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
  }
  void store(uint length,char **min_key,uint min_key_flag,
	     char **max_key, uint max_key_flag)
  {
unknown's avatar
unknown committed
173 174 175
    if ((min_flag & GEOM_FLAG) ||
        (!(min_flag & NO_MIN_RANGE) &&
	!(min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
unknown's avatar
unknown committed
176 177 178 179
    {
      if (maybe_null && *min_value)
      {
	**min_key=1;
180
	bzero(*min_key+1,length-1);
unknown's avatar
unknown committed
181 182
      }
      else
183 184
	memcpy(*min_key,min_value,length);
      (*min_key)+= length;
unknown's avatar
unknown committed
185 186 187 188 189 190 191
    }
    if (!(max_flag & NO_MAX_RANGE) &&
	!(max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
    {
      if (maybe_null && *max_value)
      {
	**max_key=1;
192
	bzero(*max_key+1,length-1);
unknown's avatar
unknown committed
193 194
      }
      else
195 196
	memcpy(*max_key,max_value,length);
      (*max_key)+= length;
unknown's avatar
unknown committed
197 198 199 200 201 202
    }
  }

  void store_min_key(KEY_PART *key,char **range_key, uint *range_key_flag)
  {
    SEL_ARG *key_tree= first();
203
    key_tree->store(key[key_tree->part].store_length,
unknown's avatar
unknown committed
204 205 206 207 208 209 210 211 212 213 214 215
		    range_key,*range_key_flag,range_key,NO_MAX_RANGE);
    *range_key_flag|= key_tree->min_flag;
    if (key_tree->next_key_part &&
	key_tree->next_key_part->part == key_tree->part+1 &&
	!(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
	key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
      key_tree->next_key_part->store_min_key(key,range_key, range_key_flag);
  }

  void store_max_key(KEY_PART *key,char **range_key, uint *range_key_flag)
  {
    SEL_ARG *key_tree= last();
216
    key_tree->store(key[key_tree->part].store_length,
unknown's avatar
unknown committed
217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281
		    range_key, NO_MIN_RANGE, range_key,*range_key_flag);
    (*range_key_flag)|= key_tree->max_flag;
    if (key_tree->next_key_part &&
	key_tree->next_key_part->part == key_tree->part+1 &&
	!(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
	key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
      key_tree->next_key_part->store_max_key(key,range_key, range_key_flag);
  }

  SEL_ARG *insert(SEL_ARG *key);
  SEL_ARG *tree_delete(SEL_ARG *key);
  SEL_ARG *find_range(SEL_ARG *key);
  SEL_ARG *rb_insert(SEL_ARG *leaf);
  friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par);
#ifdef EXTRA_DEBUG
  friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent);
  void test_use_count(SEL_ARG *root);
#endif
  SEL_ARG *first();
  SEL_ARG *last();
  void make_root();
  inline bool simple_key()
  {
    return !next_key_part && elements == 1;
  }
  void increment_use_count(long count)
  {
    if (next_key_part)
    {
      next_key_part->use_count+=count;
      count*= (next_key_part->use_count-count);
      for (SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next)
	if (pos->next_key_part)
	  pos->increment_use_count(count);
    }
  }
  void free_tree()
  {
    for (SEL_ARG *pos=first(); pos ; pos=pos->next)
      if (pos->next_key_part)
      {
	pos->next_key_part->use_count--;
	pos->next_key_part->free_tree();
      }
  }

  inline SEL_ARG **parent_ptr()
  {
    return parent->left == this ? &parent->left : &parent->right;
  }
  SEL_ARG *clone_tree();
};


class SEL_TREE :public Sql_alloc
{
public:
  enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
  SEL_TREE(enum Type type_arg) :type(type_arg) {}
  SEL_TREE() :type(KEY) { bzero((char*) keys,sizeof(keys));}
  SEL_ARG *keys[MAX_KEY];
};


typedef struct st_qsel_param {
282
  THD	*thd;
unknown's avatar
unknown committed
283 284
  TABLE *table;
  KEY_PART *key_parts,*key_parts_end,*key[MAX_KEY];
285 286
  MEM_ROOT *mem_root;
  table_map prev_tables,read_tables,current_table;
unknown's avatar
unknown committed
287
  uint baseflag, keys, max_key_part, range_count;
unknown's avatar
unknown committed
288 289 290
  uint real_keynr[MAX_KEY];
  char min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
    max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
291
  bool quick;				// Don't calulate possible keys
292
  COND *cond;
unknown's avatar
unknown committed
293 294
} PARAM;

295
static SEL_TREE * get_mm_parts(PARAM *param,COND *cond_func,Field *field,
unknown's avatar
unknown committed
296 297
			       Item_func::Functype type,Item *value,
			       Item_result cmp_type);
298 299
static SEL_ARG *get_mm_leaf(PARAM *param,COND *cond_func,Field *field,
			    KEY_PART *key_part,
unknown's avatar
unknown committed
300 301 302 303 304 305 306 307 308 309
			    Item_func::Functype type,Item *value);
static SEL_TREE *get_mm_tree(PARAM *param,COND *cond);
static ha_rows check_quick_select(PARAM *param,uint index,SEL_ARG *key_tree);
static ha_rows check_quick_keys(PARAM *param,uint index,SEL_ARG *key_tree,
				char *min_key,uint min_key_flag,
				char *max_key, uint max_key_flag);

static QUICK_SELECT *get_quick_select(PARAM *param,uint index,
				      SEL_ARG *key_tree);
#ifndef DBUG_OFF
unknown's avatar
unknown committed
310
static void print_quick(QUICK_SELECT *quick,const key_map* needed_reg);
unknown's avatar
unknown committed
311 312 313 314 315 316 317 318 319 320 321 322 323
#endif
static SEL_TREE *tree_and(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
static SEL_TREE *tree_or(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
static SEL_ARG *key_or(SEL_ARG *key1,SEL_ARG *key2);
static SEL_ARG *key_and(SEL_ARG *key1,SEL_ARG *key2,uint clone_flag);
static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
static bool get_quick_keys(PARAM *param,QUICK_SELECT *quick,KEY_PART *key,
			   SEL_ARG *key_tree,char *min_key,uint min_key_flag,
			   char *max_key,uint max_key_flag);
static bool eq_tree(SEL_ARG* a,SEL_ARG *b);

static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
324
static bool null_part_in_key(KEY_PART *key_part, const char *key, uint length);
unknown's avatar
unknown committed
325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346

/***************************************************************************
** Basic functions for SQL_SELECT and QUICK_SELECT
***************************************************************************/

	/* make a select from mysql info
	   Error is set as following:
	   0 = ok
	   1 = Got some error (out of memory?)
	   */

SQL_SELECT *make_select(TABLE *head, table_map const_tables,
			table_map read_tables, COND *conds, int *error)
{
  SQL_SELECT *select;
  DBUG_ENTER("make_select");

  *error=0;
  if (!conds)
    DBUG_RETURN(0);
  if (!(select= new SQL_SELECT))
  {
347 348
    *error= 1;			// out of memory
    DBUG_RETURN(0);		/* purecov: inspected */
unknown's avatar
unknown committed
349 350 351 352 353 354
  }
  select->read_tables=read_tables;
  select->const_tables=const_tables;
  select->head=head;
  select->cond=conds;

unknown's avatar
unknown committed
355
  if (head->sort.io_cache)
unknown's avatar
unknown committed
356
  {
unknown's avatar
unknown committed
357
    select->file= *head->sort.io_cache;
unknown's avatar
unknown committed
358 359
    select->records=(ha_rows) (select->file.end_of_file/
			       head->file->ref_length);
unknown's avatar
unknown committed
360 361
    my_free((gptr) (head->sort.io_cache),MYF(0));
    head->sort.io_cache=0;
unknown's avatar
unknown committed
362 363 364 365 366 367 368
  }
  DBUG_RETURN(select);
}


SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
{
unknown's avatar
unknown committed
369
  quick_keys.clear_all(); needed_reg.clear_all();
unknown's avatar
unknown committed
370 371 372 373
  my_b_clear(&file);
}


374
void SQL_SELECT::cleanup()
unknown's avatar
unknown committed
375 376
{
  delete quick;
377
  quick= 0;
unknown's avatar
unknown committed
378
  if (free_cond)
379 380
  {
    free_cond=0;
unknown's avatar
unknown committed
381
    delete cond;
382 383
    cond= 0;
  }    
unknown's avatar
unknown committed
384 385 386
  close_cached_file(&file);
}

387 388 389 390 391 392

SQL_SELECT::~SQL_SELECT()
{
  cleanup();
}

unknown's avatar
unknown committed
393
#undef index					// Fix for Unixware 7
unknown's avatar
unknown committed
394

395
QUICK_SELECT::QUICK_SELECT(THD *thd, TABLE *table, uint key_nr, bool no_alloc)
unknown's avatar
unknown committed
396 397
  :dont_free(0),error(0),index(key_nr),max_used_key_length(0),
   used_key_parts(0), head(table), it(ranges),range(0)
unknown's avatar
unknown committed
398 399 400
{
  if (!no_alloc)
  {
401 402
    // Allocates everything through the internal memroot
    init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
unknown's avatar
unknown committed
403 404 405 406 407 408
    my_pthread_setspecific_ptr(THR_MALLOC,&alloc);
  }
  else
    bzero((char*) &alloc,sizeof(alloc));
  file=head->file;
  record=head->record[0];
409
  init();
unknown's avatar
unknown committed
410 411 412 413
}

QUICK_SELECT::~QUICK_SELECT()
{
unknown's avatar
unknown committed
414 415 416 417 418
  if (!dont_free)
  {
    file->index_end();
    free_root(&alloc,MYF(0));
  }
unknown's avatar
unknown committed
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 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
}

QUICK_RANGE::QUICK_RANGE()
  :min_key(0),max_key(0),min_length(0),max_length(0),
   flag(NO_MIN_RANGE | NO_MAX_RANGE)
{}

SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
{
  type=arg.type;
  min_flag=arg.min_flag;
  max_flag=arg.max_flag;
  maybe_flag=arg.maybe_flag;
  maybe_null=arg.maybe_null;
  part=arg.part;
  field=arg.field;
  min_value=arg.min_value;
  max_value=arg.max_value;
  next_key_part=arg.next_key_part;
  use_count=1; elements=1;
}


inline void SEL_ARG::make_root()
{
  left=right= &null_element;
  color=BLACK;
  next=prev=0;
  use_count=0; elements=1;
}

SEL_ARG::SEL_ARG(Field *f,const char *min_value_arg,const char *max_value_arg)
  :min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
   elements(1), use_count(1), field(f), min_value((char*) min_value_arg),
   max_value((char*) max_value_arg), next(0),prev(0),
   next_key_part(0),color(BLACK),type(KEY_RANGE)
{
  left=right= &null_element;
}

SEL_ARG::SEL_ARG(Field *field_,uint8 part_,char *min_value_,char *max_value_,
		 uint8 min_flag_,uint8 max_flag_,uint8 maybe_flag_)
  :min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
   part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
   field(field_), min_value(min_value_), max_value(max_value_),
   next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
{
  left=right= &null_element;
}

SEL_ARG *SEL_ARG::clone(SEL_ARG *new_parent,SEL_ARG **next_arg)
{
  SEL_ARG *tmp;
  if (type != KEY_RANGE)
  {
474 475
    if (!(tmp= new SEL_ARG(type)))
      return 0;					// out of memory
unknown's avatar
unknown committed
476 477 478 479 480 481
    tmp->prev= *next_arg;			// Link into next/prev chain
    (*next_arg)->next=tmp;
    (*next_arg)= tmp;
  }
  else
  {
482 483 484
    if (!(tmp= new SEL_ARG(field,part, min_value,max_value,
			   min_flag, max_flag, maybe_flag)))
      return 0;					// OOM
unknown's avatar
unknown committed
485 486 487 488 489 490 491 492 493 494
    tmp->parent=new_parent;
    tmp->next_key_part=next_key_part;
    if (left != &null_element)
      tmp->left=left->clone(tmp,next_arg);

    tmp->prev= *next_arg;			// Link into next/prev chain
    (*next_arg)->next=tmp;
    (*next_arg)= tmp;

    if (right != &null_element)
495 496
      if (!(tmp->right= right->clone(tmp,next_arg)))
	return 0;				// OOM
unknown's avatar
unknown committed
497 498
  }
  increment_use_count(1);
499
  tmp->color= color;
unknown's avatar
unknown committed
500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522
  return tmp;
}

SEL_ARG *SEL_ARG::first()
{
  SEL_ARG *next_arg=this;
  if (!next_arg->left)
    return 0;					// MAYBE_KEY
  while (next_arg->left != &null_element)
    next_arg=next_arg->left;
  return next_arg;
}

SEL_ARG *SEL_ARG::last()
{
  SEL_ARG *next_arg=this;
  if (!next_arg->right)
    return 0;					// MAYBE_KEY
  while (next_arg->right != &null_element)
    next_arg=next_arg->right;
  return next_arg;
}

523

unknown's avatar
unknown committed
524 525 526
/*
  Check if a compare is ok, when one takes ranges in account
  Returns -2 or 2 if the ranges where 'joined' like  < 2 and >= 2
527
*/
unknown's avatar
unknown committed
528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550

static int sel_cmp(Field *field, char *a,char *b,uint8 a_flag,uint8 b_flag)
{
  int cmp;
  /* First check if there was a compare to a min or max element */
  if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
  {
    if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
	(b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
      return 0;
    return (a_flag & NO_MIN_RANGE) ? -1 : 1;
  }
  if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
    return (b_flag & NO_MIN_RANGE) ? 1 : -1;

  if (field->real_maybe_null())			// If null is part of key
  {
    if (*a != *b)
    {
      return *a ? -1 : 1;
    }
    if (*a)
      goto end;					// NULL where equal
unknown's avatar
unknown committed
551
    a++; b++;					// Skip NULL marker
unknown's avatar
unknown committed
552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575
  }
  cmp=field->key_cmp((byte*) a,(byte*) b);
  if (cmp) return cmp < 0 ? -1 : 1;		// The values differed

  // Check if the compared equal arguments was defined with open/closed range
 end:
  if (a_flag & (NEAR_MIN | NEAR_MAX))
  {
    if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
      return 0;
    if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
      return (a_flag & NEAR_MIN) ? 2 : -2;
    return (a_flag & NEAR_MIN) ? 1 : -1;
  }
  if (b_flag & (NEAR_MIN | NEAR_MAX))
    return (b_flag & NEAR_MIN) ? -2 : 2;
  return 0;					// The elements where equal
}


SEL_ARG *SEL_ARG::clone_tree()
{
  SEL_ARG tmp_link,*next_arg,*root;
  next_arg= &tmp_link;
576
  root= clone((SEL_ARG *) 0, &next_arg);
unknown's avatar
unknown committed
577 578
  next_arg->next=0;				// Fix last link
  tmp_link.next->prev=0;			// Fix first link
579 580
  if (root)					// If not OOM
    root->use_count= 0;
unknown's avatar
unknown committed
581 582 583
  return root;
}

unknown's avatar
unknown committed
584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606
/*
  Test if a key can be used in different ranges

  SYNOPSIS
   SQL_SELECT::test_quick_select(thd,keys_to_use, prev_tables,
                                 limit, force_quick_range)

   Updates the following in the select parameter:
    needed_reg - Bits for keys with may be used if all prev regs are read
    quick      - Parameter to use when reading records.
   In the table struct the following information is updated:
    quick_keys - Which keys can be used
    quick_rows - How many rows the key matches

 RETURN VALUES
  -1 if impossible select
   0 if can't use quick_select
   1 if found usable range

 TODO
   check if the function really needs to modify keys_to_use, and change the
   code to pass it by reference if not
*/
unknown's avatar
unknown committed
607

608 609
int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
				  table_map prev_tables,
unknown's avatar
unknown committed
610 611 612 613 614 615
				  ha_rows limit, bool force_quick_range)
{
  uint basflag;
  uint idx;
  double scan_time;
  DBUG_ENTER("test_quick_select");
unknown's avatar
unknown committed
616 617 618
  DBUG_PRINT("enter",("keys_to_use: %lu  prev_tables: %lu  const_tables: %lu",
		      keys_to_use.to_ulonglong(), (ulong) prev_tables,
		      (ulong) const_tables));
unknown's avatar
unknown committed
619 620 621

  delete quick;
  quick=0;
622
  needed_reg.clear_all(); quick_keys.clear_all();
unknown's avatar
unknown committed
623 624 625
  if (!cond || (specialflag & SPECIAL_SAFE_MODE) && ! force_quick_range ||
      !limit)
    DBUG_RETURN(0); /* purecov: inspected */
626
  if (!((basflag= head->file->table_flags()) & HA_KEYPOS_TO_RNDPOS) &&
627
      keys_to_use.is_set_all() || keys_to_use.is_clear_all())
unknown's avatar
unknown committed
628 629 630 631 632 633
    DBUG_RETURN(0);				/* Not smart database */
  records=head->file->records;
  if (!records)
    records++;					/* purecov: inspected */
  scan_time=(double) records / TIME_FOR_COMPARE+1;
  read_time=(double) head->file->scan_time()+ scan_time + 1.0;
634 635
  if (head->force_index)
    scan_time= read_time= DBL_MAX;
unknown's avatar
unknown committed
636 637 638
  if (limit < records)
    read_time=(double) records+scan_time+1;	// Force to use index
  else if (read_time <= 2.0 && !force_quick_range)
639
    DBUG_RETURN(0);				/* No need for quick select */
unknown's avatar
unknown committed
640

641
  DBUG_PRINT("info",("Time to scan table: %g", read_time));
unknown's avatar
unknown committed
642

643 644
  keys_to_use.intersect(head->keys_in_use_for_query);
  if (!keys_to_use.is_clear_all())
unknown's avatar
unknown committed
645 646 647 648
  {
    MEM_ROOT *old_root,alloc;
    SEL_TREE *tree;
    KEY_PART *key_parts;
649
    KEY *key_info;
unknown's avatar
unknown committed
650
    PARAM param;
unknown's avatar
unknown committed
651

unknown's avatar
unknown committed
652
    /* set up parameter that is passed to all functions */
653
    param.thd= thd;
unknown's avatar
unknown committed
654 655 656 657 658 659
    param.baseflag=basflag;
    param.prev_tables=prev_tables | const_tables;
    param.read_tables=read_tables;
    param.current_table= head->map;
    param.table=head;
    param.keys=0;
660
    param.mem_root= &alloc;
unknown's avatar
unknown committed
661
    thd->no_errors=1;				// Don't warn about NULL
662
    init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
unknown's avatar
unknown committed
663 664 665 666
    if (!(param.key_parts = (KEY_PART*) alloc_root(&alloc,
						   sizeof(KEY_PART)*
						   head->key_parts)))
    {
unknown's avatar
unknown committed
667
      thd->no_errors=0;
668
      free_root(&alloc,MYF(0));			// Return memory & allocator
unknown's avatar
unknown committed
669 670 671 672 673 674
      DBUG_RETURN(0);				// Can't use range
    }
    key_parts= param.key_parts;
    old_root=my_pthread_getspecific_ptr(MEM_ROOT*,THR_MALLOC);
    my_pthread_setspecific_ptr(THR_MALLOC,&alloc);

675 676
    key_info= head->key_info;
    for (idx=0 ; idx < head->keys ; idx++, key_info++)
unknown's avatar
unknown committed
677
    {
678
      KEY_PART_INFO *key_part_info;
679
      if (!keys_to_use.is_set(idx))
unknown's avatar
unknown committed
680 681 682 683 684
	continue;
      if (key_info->flags & HA_FULLTEXT)
	continue;    // ToDo: ft-keys in non-ft ranges, if possible   SerG

      param.key[param.keys]=key_parts;
685
      key_part_info= key_info->key_part;
686 687
      for (uint part=0 ; part < key_info->key_parts ;
	   part++, key_parts++, key_part_info++)
unknown's avatar
unknown committed
688
      {
689 690 691 692 693 694
	key_parts->key=		 param.keys;
	key_parts->part=	 part;
	key_parts->length=       key_part_info->length;
	key_parts->store_length= key_part_info->store_length;
	key_parts->field=	 key_part_info->field;
	key_parts->null_bit=	 key_part_info->null_bit;
695
        key_parts->image_type =
unknown's avatar
unknown committed
696
          (key_info->flags & HA_SPATIAL) ? Field::itMBR : Field::itRAW;
unknown's avatar
unknown committed
697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713
      }
      param.real_keynr[param.keys++]=idx;
    }
    param.key_parts_end=key_parts;

    if ((tree=get_mm_tree(&param,cond)))
    {
      if (tree->type == SEL_TREE::IMPOSSIBLE)
      {
	records=0L;				// Return -1 from this function
	read_time= (double) HA_POS_ERROR;
      }
      else if (tree->type == SEL_TREE::KEY ||
	       tree->type == SEL_TREE::KEY_SMALLER)
      {
	SEL_ARG **key,**end,**best_key=0;

unknown's avatar
unknown committed
714

unknown's avatar
unknown committed
715 716 717 718 719 720 721 722
	for (idx=0,key=tree->keys, end=key+param.keys ;
	     key != end ;
	     key++,idx++)
	{
	  ha_rows found_records;
	  double found_read_time;
	  if (*key)
	  {
723
	    uint keynr= param.real_keynr[idx];
unknown's avatar
unknown committed
724 725
	    if ((*key)->type == SEL_ARG::MAYBE_KEY ||
		(*key)->maybe_flag)
726
	        needed_reg.set_bit(keynr);
unknown's avatar
unknown committed
727

728
	    found_records=check_quick_select(&param, idx, *key);
unknown's avatar
unknown committed
729
	    if (found_records != HA_POS_ERROR && found_records > 2 &&
730
		head->used_keys.is_set(keynr) &&
731
		(head->file->index_flags(keynr) & HA_KEY_READ_ONLY))
unknown's avatar
unknown committed
732 733
	    {
	      /*
734 735 736 737
		We can resolve this by only reading through this key.
		Assume that we will read trough the whole key range
		and that all key blocks are half full (normally things are
		much better).
unknown's avatar
unknown committed
738
	      */
739 740 741
	      uint keys_per_block= (head->file->block_size/2/
				    (head->key_info[keynr].key_length+
				     head->file->ref_length) + 1);
unknown's avatar
unknown committed
742 743 744 745
	      found_read_time=((double) (found_records+keys_per_block-1)/
			       (double) keys_per_block);
	    }
	    else
unknown's avatar
unknown committed
746 747 748 749
	      found_read_time= (head->file->read_time(keynr,
						      param.range_count,
						      found_records)+
				(double) found_records / TIME_FOR_COMPARE);
750
	    if (read_time > found_read_time && found_records != HA_POS_ERROR)
unknown's avatar
unknown committed
751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768
	    {
	      read_time=found_read_time;
	      records=found_records;
	      best_key=key;
	    }
	  }
	}
	if (best_key && records)
	{
	  if ((quick=get_quick_select(&param,(uint) (best_key-tree->keys),
				      *best_key)))
	  {
	    quick->records=records;
	    quick->read_time=read_time;
	  }
	}
      }
    }
769
    free_root(&alloc,MYF(0));			// Return memory & allocator
unknown's avatar
unknown committed
770
    my_pthread_setspecific_ptr(THR_MALLOC,old_root);
unknown's avatar
unknown committed
771
    thd->no_errors=0;
unknown's avatar
unknown committed
772
  }
unknown's avatar
unknown committed
773
  DBUG_EXECUTE("info",print_quick(quick,&needed_reg););
unknown's avatar
unknown committed
774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798
  /*
    Assume that if the user is using 'limit' we will only need to scan
    limit rows if we are using a key
  */
  DBUG_RETURN(records ? test(quick) : -1);
}

	/* make a select tree of all keys in condition */

static SEL_TREE *get_mm_tree(PARAM *param,COND *cond)
{
  SEL_TREE *tree=0;
  DBUG_ENTER("get_mm_tree");

  if (cond->type() == Item::COND_ITEM)
  {
    List_iterator<Item> li(*((Item_cond*) cond)->argument_list());

    if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
    {
      tree=0;
      Item *item;
      while ((item=li++))
      {
	SEL_TREE *new_tree=get_mm_tree(param,item);
799
	if (param->thd->is_fatal_error)
800
	  DBUG_RETURN(0);	// out of memory
unknown's avatar
unknown committed
801 802 803 804 805 806 807 808 809 810 811 812 813 814 815
	tree=tree_and(param,tree,new_tree);
	if (tree && tree->type == SEL_TREE::IMPOSSIBLE)
	  break;
      }
    }
    else
    {						// COND OR
      tree=get_mm_tree(param,li++);
      if (tree)
      {
	Item *item;
	while ((item=li++))
	{
	  SEL_TREE *new_tree=get_mm_tree(param,item);
	  if (!new_tree)
816
	    DBUG_RETURN(0);	// out of memory
unknown's avatar
unknown committed
817 818 819 820 821 822 823 824 825 826 827 828 829 830 831
	  tree=tree_or(param,tree,new_tree);
	  if (!tree || tree->type == SEL_TREE::ALWAYS)
	    break;
	}
      }
    }
    DBUG_RETURN(tree);
  }
  /* Here when simple cond */
  if (cond->const_item())
  {
    if (cond->val_int())
      DBUG_RETURN(new SEL_TREE(SEL_TREE::ALWAYS));
    DBUG_RETURN(new SEL_TREE(SEL_TREE::IMPOSSIBLE));
  }
832

unknown's avatar
unknown committed
833 834 835
  table_map ref_tables=cond->used_tables();
  if (cond->type() != Item::FUNC_ITEM)
  {						// Should be a field
unknown's avatar
unknown committed
836 837
    if ((ref_tables & param->current_table) ||
	(ref_tables & ~(param->prev_tables | param->read_tables)))
unknown's avatar
unknown committed
838 839 840
      DBUG_RETURN(0);
    DBUG_RETURN(new SEL_TREE(SEL_TREE::MAYBE));
  }
841

unknown's avatar
unknown committed
842 843 844 845
  Item_func *cond_func= (Item_func*) cond;
  if (cond_func->select_optimize() == Item_func::OPTIMIZE_NONE)
    DBUG_RETURN(0);				// Can't be calculated

846 847
  param->cond= cond;

unknown's avatar
unknown committed
848 849 850 851 852 853
  if (cond_func->functype() == Item_func::BETWEEN)
  {
    if (cond_func->arguments()[0]->type() == Item::FIELD_ITEM)
    {
      Field *field=((Item_field*) (cond_func->arguments()[0]))->field;
      Item_result cmp_type=field->cmp_type();
854
      DBUG_RETURN(tree_and(param,
855
			   get_mm_parts(param, cond_func, field,
856 857
					Item_func::GE_FUNC,
					cond_func->arguments()[1], cmp_type),
858
			   get_mm_parts(param, cond_func, field,
unknown's avatar
unknown committed
859
					Item_func::LE_FUNC,
860
					cond_func->arguments()[2], cmp_type)));
unknown's avatar
unknown committed
861 862 863 864 865 866 867 868 869 870
    }
    DBUG_RETURN(0);
  }
  if (cond_func->functype() == Item_func::IN_FUNC)
  {						// COND OR
    Item_func_in *func=(Item_func_in*) cond_func;
    if (func->key_item()->type() == Item::FIELD_ITEM)
    {
      Field *field=((Item_field*) (func->key_item()))->field;
      Item_result cmp_type=field->cmp_type();
871
      tree= get_mm_parts(param,cond_func,field,Item_func::EQ_FUNC,
872
			 func->arguments()[1],cmp_type);
unknown's avatar
unknown committed
873 874
      if (!tree)
	DBUG_RETURN(tree);			// Not key field
875
      for (uint i=2 ; i < func->argument_count(); i++)
unknown's avatar
unknown committed
876
      {
877 878
	SEL_TREE *new_tree=get_mm_parts(param,cond_func,field,
					Item_func::EQ_FUNC,
unknown's avatar
unknown committed
879 880 881 882 883 884 885 886
					func->arguments()[i],cmp_type);
	tree=tree_or(param,tree,new_tree);
      }
      DBUG_RETURN(tree);
    }
    DBUG_RETURN(0);				// Can't optimize this IN
  }

887 888 889 890 891 892
  if (ref_tables & ~(param->prev_tables | param->read_tables |
		     param->current_table))
    DBUG_RETURN(0);				// Can't be calculated yet
  if (!(ref_tables & param->current_table))
    DBUG_RETURN(new SEL_TREE(SEL_TREE::MAYBE)); // This may be false or true

unknown's avatar
unknown committed
893 894 895 896
  /* check field op const */
  /* btw, ft_func's arguments()[0] isn't FIELD_ITEM.  SerG*/
  if (cond_func->arguments()[0]->type() == Item::FIELD_ITEM)
  {
897
    tree= get_mm_parts(param, cond_func,
unknown's avatar
unknown committed
898 899 900 901 902 903 904 905 906 907 908 909
		       ((Item_field*) (cond_func->arguments()[0]))->field,
		       cond_func->functype(),
		       cond_func->arg_count > 1 ? cond_func->arguments()[1] :
		       0,
		       ((Item_field*) (cond_func->arguments()[0]))->field->
		       cmp_type());
  }
  /* check const op field */
  if (!tree &&
      cond_func->have_rev_func() &&
      cond_func->arguments()[1]->type() == Item::FIELD_ITEM)
  {
910
    DBUG_RETURN(get_mm_parts(param, cond_func,
unknown's avatar
unknown committed
911 912 913 914 915 916 917 918 919 920 921 922 923
			     ((Item_field*)
			      (cond_func->arguments()[1]))->field,
			     ((Item_bool_func2*) cond_func)->rev_functype(),
			     cond_func->arguments()[0],
			     ((Item_field*)
			      (cond_func->arguments()[1]))->field->cmp_type()
			     ));
  }
  DBUG_RETURN(tree);
}


static SEL_TREE *
924 925
get_mm_parts(PARAM *param, COND *cond_func, Field *field,
	     Item_func::Functype type, 
926
	     Item *value, Item_result cmp_type)
unknown's avatar
unknown committed
927
{
928
  bool ne_func= FALSE;
unknown's avatar
unknown committed
929 930 931 932
  DBUG_ENTER("get_mm_parts");
  if (field->table != param->table)
    DBUG_RETURN(0);

unknown's avatar
unknown committed
933 934 935 936 937 938
  if (type == Item_func::NE_FUNC)
  {
    ne_func= TRUE;
    type= Item_func::LT_FUNC;
  }

939 940
  KEY_PART *key_part = param->key_parts;
  KEY_PART *end = param->key_parts_end;
unknown's avatar
unknown committed
941 942 943 944
  SEL_TREE *tree=0;
  if (value &&
      value->used_tables() & ~(param->prev_tables | param->read_tables))
    DBUG_RETURN(0);
945
  for (; key_part != end ; key_part++)
unknown's avatar
unknown committed
946 947 948 949
  {
    if (field->eq(key_part->field))
    {
      SEL_ARG *sel_arg=0;
950
      if (!tree && !(tree=new SEL_TREE()))
951
	DBUG_RETURN(0);				// OOM
unknown's avatar
unknown committed
952 953
      if (!value || !(value->used_tables() & ~param->read_tables))
      {
954 955
	sel_arg=get_mm_leaf(param,cond_func,
			    key_part->field,key_part,type,value);
unknown's avatar
unknown committed
956 957 958 959 960 961 962 963
	if (!sel_arg)
	  continue;
	if (sel_arg->type == SEL_ARG::IMPOSSIBLE)
	{
	  tree->type=SEL_TREE::IMPOSSIBLE;
	  DBUG_RETURN(tree);
	}
      }
964 965
      else
      {
966
	// This key may be used later
967 968
	if (!(sel_arg= new SEL_ARG(SEL_ARG::MAYBE_KEY))) 
	  DBUG_RETURN(0);			// OOM
969
      }
unknown's avatar
unknown committed
970 971 972 973
      sel_arg->part=(uchar) key_part->part;
      tree->keys[key_part->key]=sel_add(tree->keys[key_part->key],sel_arg);
    }
  }
974 975 976

  if (ne_func)
  {
977 978
    SEL_TREE *tree2= get_mm_parts(param, cond_func,
				  field, Item_func::GT_FUNC,
979 980
                                  value, cmp_type);
    if (tree2)
unknown's avatar
unknown committed
981
      tree= tree_or(param,tree,tree2);
982
  }
unknown's avatar
unknown committed
983 984 985 986 987
  DBUG_RETURN(tree);
}


static SEL_ARG *
988
get_mm_leaf(PARAM *param, COND *conf_func, Field *field, KEY_PART *key_part,
unknown's avatar
unknown committed
989 990
	    Item_func::Functype type,Item *value)
{
991
  uint maybe_null=(uint) field->real_maybe_null(), copies;
unknown's avatar
unknown committed
992 993
  uint field_length=field->pack_length()+maybe_null;
  SEL_ARG *tree;
994
  char *str, *str2;
unknown's avatar
unknown committed
995 996
  DBUG_ENTER("get_mm_leaf");

997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013
  if (!value)					// IS NULL or IS NOT NULL
  {
    if (field->table->outer_join)		// Can't use a key on this
      DBUG_RETURN(0);
    if (!maybe_null)				// Not null field
      DBUG_RETURN(type == Item_func::ISNULL_FUNC ? &null_element : 0);
    if (!(tree=new SEL_ARG(field,is_null_string,is_null_string)))
      DBUG_RETURN(0);		// out of memory
    if (type == Item_func::ISNOTNULL_FUNC)
    {
      tree->min_flag=NEAR_MIN;		    /* IS NOT NULL ->  X > NULL */
      tree->max_flag=NO_MAX_RANGE;
    }
    DBUG_RETURN(tree);
  }

  /*
unknown's avatar
unknown committed
1014
    We can't use an index when comparing strings of 
1015 1016 1017 1018 1019 1020 1021 1022
    different collations 
  */
  if (field->result_type() == STRING_RESULT &&
      value->result_type() == STRING_RESULT &&
      key_part->image_type == Field::itRAW &&
      ((Field_str*)field)->charset() != conf_func->compare_collation())
    DBUG_RETURN(0);

unknown's avatar
unknown committed
1023 1024 1025 1026
  if (type == Item_func::LIKE_FUNC)
  {
    bool like_error;
    char buff1[MAX_FIELD_WIDTH],*min_str,*max_str;
1027
    String tmp(buff1,sizeof(buff1),value->collation.collation),*res;
unknown's avatar
unknown committed
1028 1029
    uint length,offset,min_length,max_length;

unknown's avatar
unknown committed
1030
    if (!field->optimize_range(param->real_keynr[key_part->key]))
unknown's avatar
unknown committed
1031
      DBUG_RETURN(0);				// Can't optimize this
unknown's avatar
unknown committed
1032 1033 1034
    if (!(res= value->val_str(&tmp)))
      DBUG_RETURN(&null_element);

1035 1036 1037 1038 1039
    /*
      TODO:
      Check if this was a function. This should have be optimized away
      in the sql_select.cc
    */
unknown's avatar
unknown committed
1040 1041 1042 1043 1044 1045 1046 1047 1048
    if (res != &tmp)
    {
      tmp.copy(*res);				// Get own copy
      res= &tmp;
    }
    if (field->cmp_type() != STRING_RESULT)
      DBUG_RETURN(0);				// Can only optimize strings

    offset=maybe_null;
1049 1050 1051
    length=key_part->store_length;

    if (length != key_part->length  + maybe_null)
unknown's avatar
unknown committed
1052
    {
1053 1054 1055
      /* key packed with length prefix */
      offset+= HA_KEY_BLOB_LENGTH;
      field_length= length - HA_KEY_BLOB_LENGTH;
unknown's avatar
unknown committed
1056 1057 1058
    }
    else
    {
1059 1060 1061 1062 1063 1064 1065 1066
      if (unlikely(length < field_length))
      {
	/*
	  This can only happen in a table created with UNIREG where one key
	  overlaps many fields
	*/
	length= field_length;
      }
unknown's avatar
unknown committed
1067
      else
1068
	field_length= length;
unknown's avatar
unknown committed
1069 1070
    }
    length+=offset;
1071
    if (!(min_str= (char*) alloc_root(param->mem_root, length*2)))
unknown's avatar
unknown committed
1072 1073 1074 1075
      DBUG_RETURN(0);
    max_str=min_str+length;
    if (maybe_null)
      max_str[0]= min_str[0]=0;
1076 1077

    like_error= my_like_range(field->charset(),
unknown's avatar
unknown committed
1078
			      res->ptr(), res->length(),
unknown's avatar
unknown committed
1079 1080
			      ((Item_func_like*)(param->cond))->escape,
			      wild_one, wild_many,
1081
			      field_length-maybe_null,
unknown's avatar
unknown committed
1082 1083
			      min_str+offset, max_str+offset,
			      &min_length, &max_length);
unknown's avatar
unknown committed
1084 1085
    if (like_error)				// Can't optimize with LIKE
      DBUG_RETURN(0);
unknown's avatar
unknown committed
1086

unknown's avatar
unknown committed
1087 1088 1089 1090 1091 1092 1093 1094
    if (offset != maybe_null)			// Blob
    {
      int2store(min_str+maybe_null,min_length);
      int2store(max_str+maybe_null,max_length);
    }
    DBUG_RETURN(new SEL_ARG(field,min_str,max_str));
  }

unknown's avatar
unknown committed
1095
  if (!field->optimize_range(param->real_keynr[key_part->key]) &&
1096
      type != Item_func::EQ_FUNC &&
unknown's avatar
unknown committed
1097 1098 1099
      type != Item_func::EQUAL_FUNC)
    DBUG_RETURN(0);				// Can't optimize this

1100 1101 1102 1103
  /*
    We can't always use indexes when comparing a string index to a number
    cmp_type() is checked to allow compare of dates to numbers
  */
unknown's avatar
unknown committed
1104 1105 1106 1107
  if (field->result_type() == STRING_RESULT &&
      value->result_type() != STRING_RESULT &&
      field->cmp_type() != value->result_type())
    DBUG_RETURN(0);
1108
 
unknown's avatar
unknown committed
1109
  if (value->save_in_field(field, 1) < 0)
unknown's avatar
unknown committed
1110
  {
1111 1112
    /* This happens when we try to insert a NULL field in a not null column */
    DBUG_RETURN(&null_element);			// cmp with NULL is never true
unknown's avatar
unknown committed
1113
  }
1114 1115 1116 1117 1118
  /* Get local copy of key */
  copies= 1;
  if (field->key_type() == HA_KEYTYPE_VARTEXT)
    copies= 2;
  str= str2= (char*) alloc_root(param->mem_root,
1119
				(key_part->store_length)*copies+1);
unknown's avatar
unknown committed
1120 1121 1122
  if (!str)
    DBUG_RETURN(0);
  if (maybe_null)
1123
    *str= (char) field->is_real_null();		// Set to 1 if null
1124 1125
  field->get_key_image(str+maybe_null, key_part->length,
		       field->charset(), key_part->image_type);
1126 1127 1128 1129 1130 1131 1132 1133
  if (copies == 2)
  {
    /*
      The key is stored as 2 byte length + key
      key doesn't match end space. In other words, a key 'X ' should match
      all rows between 'X' and 'X           ...'
    */
    uint length= uint2korr(str+maybe_null);
1134
    str2= str+ key_part->store_length;
1135 1136
    /* remove end space */
    while (length > 0 && str[length+HA_KEY_BLOB_LENGTH+maybe_null-1] == ' ')
1137 1138 1139
      length--;
    int2store(str+maybe_null, length);
    /* Create key that is space filled */
1140
    memcpy(str2, str, length + HA_KEY_BLOB_LENGTH + maybe_null);
1141 1142 1143 1144
    my_fill_8bit(field->charset(),
		 str2+ length+ HA_KEY_BLOB_LENGTH +maybe_null,
		 key_part->length-length, ' ');
    int2store(str2+maybe_null, key_part->length);
1145 1146
  }
  if (!(tree=new SEL_ARG(field,str,str2)))
1147
    DBUG_RETURN(0);		// out of memory
unknown's avatar
unknown committed
1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169

  switch (type) {
  case Item_func::LT_FUNC:
    if (field_is_equal_to_item(field,value))
      tree->max_flag=NEAR_MAX;
    /* fall through */
  case Item_func::LE_FUNC:
    if (!maybe_null)
      tree->min_flag=NO_MIN_RANGE;		/* From start */
    else
    {						// > NULL
      tree->min_value=is_null_string;
      tree->min_flag=NEAR_MIN;
    }
    break;
  case Item_func::GT_FUNC:
    if (field_is_equal_to_item(field,value))
      tree->min_flag=NEAR_MIN;
    /* fall through */
  case Item_func::GE_FUNC:
    tree->max_flag=NO_MAX_RANGE;
    break;
unknown's avatar
unknown committed
1170
  case Item_func::SP_EQUALS_FUNC:
1171 1172 1173
    tree->min_flag=GEOM_FLAG | HA_READ_MBR_EQUAL;// NEAR_MIN;//512;
    tree->max_flag=NO_MAX_RANGE;
    break;
unknown's avatar
unknown committed
1174
  case Item_func::SP_DISJOINT_FUNC:
1175 1176 1177
    tree->min_flag=GEOM_FLAG | HA_READ_MBR_DISJOINT;// NEAR_MIN;//512;
    tree->max_flag=NO_MAX_RANGE;
    break;
unknown's avatar
unknown committed
1178
  case Item_func::SP_INTERSECTS_FUNC:
1179 1180 1181
    tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512;
    tree->max_flag=NO_MAX_RANGE;
    break;
unknown's avatar
unknown committed
1182
  case Item_func::SP_TOUCHES_FUNC:
1183 1184 1185
    tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512;
    tree->max_flag=NO_MAX_RANGE;
    break;
unknown's avatar
unknown committed
1186 1187

  case Item_func::SP_CROSSES_FUNC:
1188 1189 1190
    tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512;
    tree->max_flag=NO_MAX_RANGE;
    break;
unknown's avatar
unknown committed
1191
  case Item_func::SP_WITHIN_FUNC:
1192 1193 1194
    tree->min_flag=GEOM_FLAG | HA_READ_MBR_WITHIN;// NEAR_MIN;//512;
    tree->max_flag=NO_MAX_RANGE;
    break;
unknown's avatar
unknown committed
1195 1196

  case Item_func::SP_CONTAINS_FUNC:
1197 1198 1199
    tree->min_flag=GEOM_FLAG | HA_READ_MBR_CONTAIN;// NEAR_MIN;//512;
    tree->max_flag=NO_MAX_RANGE;
    break;
unknown's avatar
unknown committed
1200
  case Item_func::SP_OVERLAPS_FUNC:
1201 1202 1203
    tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512;
    tree->max_flag=NO_MAX_RANGE;
    break;
unknown's avatar
unknown committed
1204

unknown's avatar
unknown committed
1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224
  default:
    break;
  }
  DBUG_RETURN(tree);
}


/******************************************************************************
** Tree manipulation functions
** If tree is 0 it means that the condition can't be tested. It refers
** to a non existent table or to a field in current table with isn't a key.
** The different tree flags:
** IMPOSSIBLE:	 Condition is never true
** ALWAYS:	 Condition is always true
** MAYBE:	 Condition may exists when tables are read
** MAYBE_KEY:	 Condition refers to a key that may be used in join loop
** KEY_RANGE:	 Condition uses a key
******************************************************************************/

/*
1225 1226
  Add a new key test to a key when scanning through all keys
  This will never be called for same key parts.
unknown's avatar
unknown committed
1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364
*/

static SEL_ARG *
sel_add(SEL_ARG *key1,SEL_ARG *key2)
{
  SEL_ARG *root,**key_link;

  if (!key1)
    return key2;
  if (!key2)
    return key1;

  key_link= &root;
  while (key1 && key2)
  {
    if (key1->part < key2->part)
    {
      *key_link= key1;
      key_link= &key1->next_key_part;
      key1=key1->next_key_part;
    }
    else
    {
      *key_link= key2;
      key_link= &key2->next_key_part;
      key2=key2->next_key_part;
    }
  }
  *key_link=key1 ? key1 : key2;
  return root;
}

#define CLONE_KEY1_MAYBE 1
#define CLONE_KEY2_MAYBE 2
#define swap_clone_flag(A) ((A & 1) << 1) | ((A & 2) >> 1)


static SEL_TREE *
tree_and(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
{
  DBUG_ENTER("tree_and");
  if (!tree1)
    DBUG_RETURN(tree2);
  if (!tree2)
    DBUG_RETURN(tree1);
  if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
    DBUG_RETURN(tree1);
  if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
    DBUG_RETURN(tree2);
  if (tree1->type == SEL_TREE::MAYBE)
  {
    if (tree2->type == SEL_TREE::KEY)
      tree2->type=SEL_TREE::KEY_SMALLER;
    DBUG_RETURN(tree2);
  }
  if (tree2->type == SEL_TREE::MAYBE)
  {
    tree1->type=SEL_TREE::KEY_SMALLER;
    DBUG_RETURN(tree1);
  }

  /* Join the trees key per key */
  SEL_ARG **key1,**key2,**end;
  for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ;
       key1 != end ; key1++,key2++)
  {
    uint flag=0;
    if (*key1 || *key2)
    {
      if (*key1 && !(*key1)->simple_key())
	flag|=CLONE_KEY1_MAYBE;
      if (*key2 && !(*key2)->simple_key())
	flag|=CLONE_KEY2_MAYBE;
      *key1=key_and(*key1,*key2,flag);
      if ((*key1)->type == SEL_ARG::IMPOSSIBLE)
      {
	tree1->type= SEL_TREE::IMPOSSIBLE;
	break;
      }
#ifdef EXTRA_DEBUG
      (*key1)->test_use_count(*key1);
#endif
    }
  }
  DBUG_RETURN(tree1);
}



static SEL_TREE *
tree_or(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
{
  DBUG_ENTER("tree_or");
  if (!tree1 || !tree2)
    DBUG_RETURN(0);
  if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
    DBUG_RETURN(tree2);
  if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
    DBUG_RETURN(tree1);
  if (tree1->type == SEL_TREE::MAYBE)
    DBUG_RETURN(tree1);				// Can't use this
  if (tree2->type == SEL_TREE::MAYBE)
    DBUG_RETURN(tree2);

  /* Join the trees key per key */
  SEL_ARG **key1,**key2,**end;
  SEL_TREE *result=0;
  for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ;
       key1 != end ; key1++,key2++)
  {
    *key1=key_or(*key1,*key2);
    if (*key1)
    {
      result=tree1;				// Added to tree1
#ifdef EXTRA_DEBUG
      (*key1)->test_use_count(*key1);
#endif
    }
  }
  DBUG_RETURN(result);
}


/* And key trees where key1->part < key2 -> part */

static SEL_ARG *
and_all_keys(SEL_ARG *key1,SEL_ARG *key2,uint clone_flag)
{
  SEL_ARG *next;
  ulong use_count=key1->use_count;

  if (key1->elements != 1)
  {
    key2->use_count+=key1->elements-1;
    key2->increment_use_count((int) key1->elements-1);
  }
  if (key1->type == SEL_ARG::MAYBE_KEY)
  {
1365 1366
    key1->right= key1->left= &null_element;
    key1->next= key1->prev= 0;
unknown's avatar
unknown committed
1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403
  }
  for (next=key1->first(); next ; next=next->next)
  {
    if (next->next_key_part)
    {
      SEL_ARG *tmp=key_and(next->next_key_part,key2,clone_flag);
      if (tmp && tmp->type == SEL_ARG::IMPOSSIBLE)
      {
	key1=key1->tree_delete(next);
	continue;
      }
      next->next_key_part=tmp;
      if (use_count)
	next->increment_use_count(use_count);
    }
    else
      next->next_key_part=key2;
  }
  if (!key1)
    return &null_element;			// Impossible ranges
  key1->use_count++;
  return key1;
}



static SEL_ARG *
key_and(SEL_ARG *key1,SEL_ARG *key2,uint clone_flag)
{
  if (!key1)
    return key2;
  if (!key2)
    return key1;
  if (key1->part != key2->part)
  {
    if (key1->part > key2->part)
    {
1404
      swap_variables(SEL_ARG *, key1, key2);
unknown's avatar
unknown committed
1405 1406 1407 1408 1409
      clone_flag=swap_clone_flag(clone_flag);
    }
    // key1->part < key2->part
    key1->use_count--;
    if (key1->use_count > 0)
1410 1411
      if (!(key1= key1->clone_tree()))
	return 0;				// OOM
unknown's avatar
unknown committed
1412 1413 1414 1415
    return and_all_keys(key1,key2,clone_flag);
  }

  if (((clone_flag & CLONE_KEY2_MAYBE) &&
1416 1417
       !(clone_flag & CLONE_KEY1_MAYBE) &&
       key2->type != SEL_ARG::MAYBE_KEY) ||
unknown's avatar
unknown committed
1418 1419
      key1->type == SEL_ARG::MAYBE_KEY)
  {						// Put simple key in key2
1420
    swap_variables(SEL_ARG *, key1, key2);
unknown's avatar
unknown committed
1421 1422 1423 1424 1425 1426 1427 1428 1429
    clone_flag=swap_clone_flag(clone_flag);
  }

  // If one of the key is MAYBE_KEY then the found region may be smaller
  if (key2->type == SEL_ARG::MAYBE_KEY)
  {
    if (key1->use_count > 1)
    {
      key1->use_count--;
1430 1431
      if (!(key1=key1->clone_tree()))
	return 0;				// OOM
unknown's avatar
unknown committed
1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445
      key1->use_count++;
    }
    if (key1->type == SEL_ARG::MAYBE_KEY)
    {						// Both are maybe key
      key1->next_key_part=key_and(key1->next_key_part,key2->next_key_part,
				 clone_flag);
      if (key1->next_key_part &&
	  key1->next_key_part->type == SEL_ARG::IMPOSSIBLE)
	return key1;
    }
    else
    {
      key1->maybe_smaller();
      if (key2->next_key_part)
1446 1447
      {
	key1->use_count--;			// Incremented in and_all_keys
unknown's avatar
unknown committed
1448
	return and_all_keys(key1,key2,clone_flag);
1449
      }
unknown's avatar
unknown committed
1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474
      key2->use_count--;			// Key2 doesn't have a tree
    }
    return key1;
  }

  key1->use_count--;
  key2->use_count--;
  SEL_ARG *e1=key1->first(), *e2=key2->first(), *new_tree=0;

  while (e1 && e2)
  {
    int cmp=e1->cmp_min_to_min(e2);
    if (cmp < 0)
    {
      if (get_range(&e1,&e2,key1))
	continue;
    }
    else if (get_range(&e2,&e1,key2))
      continue;
    SEL_ARG *next=key_and(e1->next_key_part,e2->next_key_part,clone_flag);
    e1->increment_use_count(1);
    e2->increment_use_count(1);
    if (!next || next->type != SEL_ARG::IMPOSSIBLE)
    {
      SEL_ARG *new_arg= e1->clone_and(e2);
1475 1476
      if (!new_arg)
	return &null_element;			// End of memory
unknown's avatar
unknown committed
1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527
      new_arg->next_key_part=next;
      if (!new_tree)
      {
	new_tree=new_arg;
      }
      else
	new_tree=new_tree->insert(new_arg);
    }
    if (e1->cmp_max_to_max(e2) < 0)
      e1=e1->next;				// e1 can't overlapp next e2
    else
      e2=e2->next;
  }
  key1->free_tree();
  key2->free_tree();
  if (!new_tree)
    return &null_element;			// Impossible range
  return new_tree;
}


static bool
get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1)
{
  (*e1)=root1->find_range(*e2);			// first e1->min < e2->min
  if ((*e1)->cmp_max_to_min(*e2) < 0)
  {
    if (!((*e1)=(*e1)->next))
      return 1;
    if ((*e1)->cmp_min_to_max(*e2) > 0)
    {
      (*e2)=(*e2)->next;
      return 1;
    }
  }
  return 0;
}


static SEL_ARG *
key_or(SEL_ARG *key1,SEL_ARG *key2)
{
  if (!key1)
  {
    if (key2)
    {
      key2->use_count--;
      key2->free_tree();
    }
    return 0;
  }
1528
  if (!key2)
unknown's avatar
unknown committed
1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561
  {
    key1->use_count--;
    key1->free_tree();
    return 0;
  }
  key1->use_count--;
  key2->use_count--;

  if (key1->part != key2->part)
  {
    key1->free_tree();
    key2->free_tree();
    return 0;					// Can't optimize this
  }

  // If one of the key is MAYBE_KEY then the found region may be bigger
  if (key1->type == SEL_ARG::MAYBE_KEY)
  {
    key2->free_tree();
    key1->use_count++;
    return key1;
  }
  if (key2->type == SEL_ARG::MAYBE_KEY)
  {
    key1->free_tree();
    key2->use_count++;
    return key2;
  }

  if (key1->use_count > 0)
  {
    if (key2->use_count == 0 || key1->elements > key2->elements)
    {
1562
      swap_variables(SEL_ARG *,key1,key2);
unknown's avatar
unknown committed
1563
    }
1564 1565
    else if (!(key1=key1->clone_tree()))
      return 0;					// OOM
unknown's avatar
unknown committed
1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590
  }

  // Add tree at key2 to tree at key1
  bool key2_shared=key2->use_count != 0;
  key1->maybe_flag|=key2->maybe_flag;

  for (key2=key2->first(); key2; )
  {
    SEL_ARG *tmp=key1->find_range(key2);	// Find key1.min <= key2.min
    int cmp;

    if (!tmp)
    {
      tmp=key1->first();			// tmp.min > key2.min
      cmp= -1;
    }
    else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
    {						// Found tmp.max < key2.min
      SEL_ARG *next=tmp->next;
      if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
      {
	// Join near ranges like tmp.max < 0 and key2.min >= 0
	SEL_ARG *key2_next=key2->next;
	if (key2_shared)
	{
unknown's avatar
unknown committed
1591
	  if (!(key2=new SEL_ARG(*key2)))
1592
	    return 0;		// out of memory
unknown's avatar
unknown committed
1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632
	  key2->increment_use_count(key1->use_count+1);
	  key2->next=key2_next;			// New copy of key2
	}
	key2->copy_min(tmp);
	if (!(key1=key1->tree_delete(tmp)))
	{					// Only one key in tree
	  key1=key2;
	  key1->make_root();
	  key2=key2_next;
	  break;
	}
      }
      if (!(tmp=next))				// tmp.min > key2.min
	break;					// Copy rest of key2
    }
    if (cmp < 0)
    {						// tmp.min > key2.min
      int tmp_cmp;
      if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
      {
	if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
	{					// ranges are connected
	  tmp->copy_min_to_min(key2);
	  key1->merge_flags(key2);
	  if (tmp->min_flag & NO_MIN_RANGE &&
	      tmp->max_flag & NO_MAX_RANGE)
	  {
	    if (key1->maybe_flag)
	      return new SEL_ARG(SEL_ARG::MAYBE_KEY);
	    return 0;
	  }
	  key2->increment_use_count(-1);	// Free not used tree
	  key2=key2->next;
	  continue;
	}
	else
	{
	  SEL_ARG *next=key2->next;		// Keys are not overlapping
	  if (key2_shared)
	  {
1633 1634 1635 1636
	    SEL_ARG *tmp= new SEL_ARG(*key2);	// Must make copy
	    if (!tmp)
	      return 0;				// OOM
	    key1=key1->insert(tmp);
unknown's avatar
unknown committed
1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681
	    key2->increment_use_count(key1->use_count+1);
	  }
	  else
	    key1=key1->insert(key2);		// Will destroy key2_root
	  key2=next;
	  continue;
	}
      }
    }

    // tmp.max >= key2.min && tmp.min <= key.max  (overlapping ranges)
    if (eq_tree(tmp->next_key_part,key2->next_key_part))
    {
      if (tmp->is_same(key2))
      {
	tmp->merge_flags(key2);			// Copy maybe flags
	key2->increment_use_count(-1);		// Free not used tree
      }
      else
      {
	SEL_ARG *last=tmp;
	while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
	       eq_tree(last->next->next_key_part,key2->next_key_part))
	{
	  SEL_ARG *save=last;
	  last=last->next;
	  key1=key1->tree_delete(save);
	}
	if (last->copy_min(key2) || last->copy_max(key2))
	{					// Full range
	  key1->free_tree();
	  for (; key2 ; key2=key2->next)
	    key2->increment_use_count(-1);	// Free not used tree
	  if (key1->maybe_flag)
	    return new SEL_ARG(SEL_ARG::MAYBE_KEY);
	  return 0;
	}
      }
      key2=key2->next;
      continue;
    }

    if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
    {						// tmp.min <= x < key2.min
      SEL_ARG *new_arg=tmp->clone_first(key2);
1682 1683
      if (!new_arg)
	return 0;				// OOM
unknown's avatar
unknown committed
1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696
      if ((new_arg->next_key_part= key1->next_key_part))
	new_arg->increment_use_count(key1->use_count+1);
      tmp->copy_min_to_min(key2);
      key1=key1->insert(new_arg);
    }

    // tmp.min >= key2.min && tmp.min <= key2.max
    SEL_ARG key(*key2);				// Get copy we can modify
    for (;;)
    {
      if (tmp->cmp_min_to_min(&key) > 0)
      {						// key.min <= x < tmp.min
	SEL_ARG *new_arg=key.clone_first(tmp);
1697 1698
	if (!new_arg)
	  return 0;				// OOM
unknown's avatar
unknown committed
1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712
	if ((new_arg->next_key_part=key.next_key_part))
	  new_arg->increment_use_count(key1->use_count+1);
	key1=key1->insert(new_arg);
      }
      if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
      {						// tmp.min. <= x <= tmp.max
	tmp->maybe_flag|= key.maybe_flag;
	key.increment_use_count(key1->use_count+1);
	tmp->next_key_part=key_or(tmp->next_key_part,key.next_key_part);
	if (!cmp)				// Key2 is ready
	  break;
	key.copy_max_to_min(tmp);
	if (!(tmp=tmp->next))
	{
1713 1714 1715 1716
	  SEL_ARG *tmp2= new SEL_ARG(key);
	  if (!tmp2)
	    return 0;				// OOM
	  key1=key1->insert(tmp2);
unknown's avatar
unknown committed
1717 1718 1719 1720 1721
	  key2=key2->next;
	  goto end;
	}
	if (tmp->cmp_min_to_max(&key) > 0)
	{
1722 1723 1724 1725
	  SEL_ARG *tmp2= new SEL_ARG(key);
	  if (!tmp2)
	    return 0;				// OOM
	  key1=key1->insert(tmp2);
unknown's avatar
unknown committed
1726 1727 1728 1729 1730 1731
	  break;
	}
      }
      else
      {
	SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max
1732 1733
	if (!new_arg)
	  return 0;				// OOM
unknown's avatar
unknown committed
1734 1735
	tmp->copy_max_to_min(&key);
	tmp->increment_use_count(key1->use_count+1);
1736 1737
	/* Increment key count as it may be used for next loop */
	key.increment_use_count(1);
unknown's avatar
unknown committed
1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751
	new_arg->next_key_part=key_or(tmp->next_key_part,key.next_key_part);
	key1=key1->insert(new_arg);
	break;
      }
    }
    key2=key2->next;
  }

end:
  while (key2)
  {
    SEL_ARG *next=key2->next;
    if (key2_shared)
    {
1752 1753 1754
      SEL_ARG *tmp=new SEL_ARG(*key2);		// Must make copy
      if (!tmp)
	return 0;
unknown's avatar
unknown committed
1755
      key2->increment_use_count(key1->use_count+1);
1756
      key1=key1->insert(tmp);
unknown's avatar
unknown committed
1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803
    }
    else
      key1=key1->insert(key2);			// Will destroy key2_root
    key2=next;
  }
  key1->use_count++;
  return key1;
}


/* Compare if two trees are equal */

static bool eq_tree(SEL_ARG* a,SEL_ARG *b)
{
  if (a == b)
    return 1;
  if (!a || !b || !a->is_same(b))
    return 0;
  if (a->left != &null_element && b->left != &null_element)
  {
    if (!eq_tree(a->left,b->left))
      return 0;
  }
  else if (a->left != &null_element || b->left != &null_element)
    return 0;
  if (a->right != &null_element && b->right != &null_element)
  {
    if (!eq_tree(a->right,b->right))
      return 0;
  }
  else if (a->right != &null_element || b->right != &null_element)
    return 0;
  if (a->next_key_part != b->next_key_part)
  {						// Sub range
    if (!a->next_key_part != !b->next_key_part ||
	!eq_tree(a->next_key_part, b->next_key_part))
      return 0;
  }
  return 1;
}


SEL_ARG *
SEL_ARG::insert(SEL_ARG *key)
{
  SEL_ARG *element,**par,*last_element;
  LINT_INIT(par); LINT_INIT(last_element);
unknown's avatar
unknown committed
1804

unknown's avatar
unknown committed
1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168
  for (element= this; element != &null_element ; )
  {
    last_element=element;
    if (key->cmp_min_to_min(element) > 0)
    {
      par= &element->right; element= element->right;
    }
    else
    {
      par = &element->left; element= element->left;
    }
  }
  *par=key;
  key->parent=last_element;
	/* Link in list */
  if (par == &last_element->left)
  {
    key->next=last_element;
    if ((key->prev=last_element->prev))
      key->prev->next=key;
    last_element->prev=key;
  }
  else
  {
    if ((key->next=last_element->next))
      key->next->prev=key;
    key->prev=last_element;
    last_element->next=key;
  }
  key->left=key->right= &null_element;
  SEL_ARG *root=rb_insert(key);			// rebalance tree
  root->use_count=this->use_count;		// copy root info
  root->elements= this->elements+1;
  root->maybe_flag=this->maybe_flag;
  return root;
}


/*
** Find best key with min <= given key
** Because the call context this should never return 0 to get_range
*/

SEL_ARG *
SEL_ARG::find_range(SEL_ARG *key)
{
  SEL_ARG *element=this,*found=0;

  for (;;)
  {
    if (element == &null_element)
      return found;
    int cmp=element->cmp_min_to_min(key);
    if (cmp == 0)
      return element;
    if (cmp < 0)
    {
      found=element;
      element=element->right;
    }
    else
      element=element->left;
  }
}


/*
** Remove a element from the tree
** This also frees all sub trees that is used by the element
*/

SEL_ARG *
SEL_ARG::tree_delete(SEL_ARG *key)
{
  enum leaf_color remove_color;
  SEL_ARG *root,*nod,**par,*fix_par;
  root=this; this->parent= 0;

  /* Unlink from list */
  if (key->prev)
    key->prev->next=key->next;
  if (key->next)
    key->next->prev=key->prev;
  key->increment_use_count(-1);
  if (!key->parent)
    par= &root;
  else
    par=key->parent_ptr();

  if (key->left == &null_element)
  {
    *par=nod=key->right;
    fix_par=key->parent;
    if (nod != &null_element)
      nod->parent=fix_par;
    remove_color= key->color;
  }
  else if (key->right == &null_element)
  {
    *par= nod=key->left;
    nod->parent=fix_par=key->parent;
    remove_color= key->color;
  }
  else
  {
    SEL_ARG *tmp=key->next;			// next bigger key (exist!)
    nod= *tmp->parent_ptr()= tmp->right;	// unlink tmp from tree
    fix_par=tmp->parent;
    if (nod != &null_element)
      nod->parent=fix_par;
    remove_color= tmp->color;

    tmp->parent=key->parent;			// Move node in place of key
    (tmp->left=key->left)->parent=tmp;
    if ((tmp->right=key->right) != &null_element)
      tmp->right->parent=tmp;
    tmp->color=key->color;
    *par=tmp;
    if (fix_par == key)				// key->right == key->next
      fix_par=tmp;				// new parent of nod
  }

  if (root == &null_element)
    return 0;					// Maybe root later
  if (remove_color == BLACK)
    root=rb_delete_fixup(root,nod,fix_par);
  test_rb_tree(root,root->parent);

  root->use_count=this->use_count;		// Fix root counters
  root->elements=this->elements-1;
  root->maybe_flag=this->maybe_flag;
  return root;
}


	/* Functions to fix up the tree after insert and delete */

static void left_rotate(SEL_ARG **root,SEL_ARG *leaf)
{
  SEL_ARG *y=leaf->right;
  leaf->right=y->left;
  if (y->left != &null_element)
    y->left->parent=leaf;
  if (!(y->parent=leaf->parent))
    *root=y;
  else
    *leaf->parent_ptr()=y;
  y->left=leaf;
  leaf->parent=y;
}

static void right_rotate(SEL_ARG **root,SEL_ARG *leaf)
{
  SEL_ARG *y=leaf->left;
  leaf->left=y->right;
  if (y->right != &null_element)
    y->right->parent=leaf;
  if (!(y->parent=leaf->parent))
    *root=y;
  else
    *leaf->parent_ptr()=y;
  y->right=leaf;
  leaf->parent=y;
}


SEL_ARG *
SEL_ARG::rb_insert(SEL_ARG *leaf)
{
  SEL_ARG *y,*par,*par2,*root;
  root= this; root->parent= 0;

  leaf->color=RED;
  while (leaf != root && (par= leaf->parent)->color == RED)
  {					// This can't be root or 1 level under
    if (par == (par2= leaf->parent->parent)->left)
    {
      y= par2->right;
      if (y->color == RED)
      {
	par->color=BLACK;
	y->color=BLACK;
	leaf=par2;
	leaf->color=RED;		/* And the loop continues */
      }
      else
      {
	if (leaf == par->right)
	{
	  left_rotate(&root,leaf->parent);
	  par=leaf;			/* leaf is now parent to old leaf */
	}
	par->color=BLACK;
	par2->color=RED;
	right_rotate(&root,par2);
	break;
      }
    }
    else
    {
      y= par2->left;
      if (y->color == RED)
      {
	par->color=BLACK;
	y->color=BLACK;
	leaf=par2;
	leaf->color=RED;		/* And the loop continues */
      }
      else
      {
	if (leaf == par->left)
	{
	  right_rotate(&root,par);
	  par=leaf;
	}
	par->color=BLACK;
	par2->color=RED;
	left_rotate(&root,par2);
	break;
      }
    }
  }
  root->color=BLACK;
  test_rb_tree(root,root->parent);
  return root;
}


SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key,SEL_ARG *par)
{
  SEL_ARG *x,*w;
  root->parent=0;

  x= key;
  while (x != root && x->color == SEL_ARG::BLACK)
  {
    if (x == par->left)
    {
      w=par->right;
      if (w->color == SEL_ARG::RED)
      {
	w->color=SEL_ARG::BLACK;
	par->color=SEL_ARG::RED;
	left_rotate(&root,par);
	w=par->right;
      }
      if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
      {
	w->color=SEL_ARG::RED;
	x=par;
      }
      else
      {
	if (w->right->color == SEL_ARG::BLACK)
	{
	  w->left->color=SEL_ARG::BLACK;
	  w->color=SEL_ARG::RED;
	  right_rotate(&root,w);
	  w=par->right;
	}
	w->color=par->color;
	par->color=SEL_ARG::BLACK;
	w->right->color=SEL_ARG::BLACK;
	left_rotate(&root,par);
	x=root;
	break;
      }
    }
    else
    {
      w=par->left;
      if (w->color == SEL_ARG::RED)
      {
	w->color=SEL_ARG::BLACK;
	par->color=SEL_ARG::RED;
	right_rotate(&root,par);
	w=par->left;
      }
      if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
      {
	w->color=SEL_ARG::RED;
	x=par;
      }
      else
      {
	if (w->left->color == SEL_ARG::BLACK)
	{
	  w->right->color=SEL_ARG::BLACK;
	  w->color=SEL_ARG::RED;
	  left_rotate(&root,w);
	  w=par->left;
	}
	w->color=par->color;
	par->color=SEL_ARG::BLACK;
	w->left->color=SEL_ARG::BLACK;
	right_rotate(&root,par);
	x=root;
	break;
      }
    }
    par=x->parent;
  }
  x->color=SEL_ARG::BLACK;
  return root;
}


	/* Test that the proporties for a red-black tree holds */

#ifdef EXTRA_DEBUG
int test_rb_tree(SEL_ARG *element,SEL_ARG *parent)
{
  int count_l,count_r;

  if (element == &null_element)
    return 0;					// Found end of tree
  if (element->parent != parent)
  {
    sql_print_error("Wrong tree: Parent doesn't point at parent");
    return -1;
  }
  if (element->color == SEL_ARG::RED &&
      (element->left->color == SEL_ARG::RED ||
       element->right->color == SEL_ARG::RED))
  {
    sql_print_error("Wrong tree: Found two red in a row");
    return -1;
  }
  if (element->left == element->right && element->left != &null_element)
  {						// Dummy test
    sql_print_error("Wrong tree: Found right == left");
    return -1;
  }
  count_l=test_rb_tree(element->left,element);
  count_r=test_rb_tree(element->right,element);
  if (count_l >= 0 && count_r >= 0)
  {
    if (count_l == count_r)
      return count_l+(element->color == SEL_ARG::BLACK);
    sql_print_error("Wrong tree: Incorrect black-count: %d - %d",
	    count_l,count_r);
  }
  return -1;					// Error, no more warnings
}

static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key)
{
  ulong count= 0;
  for (root=root->first(); root ; root=root->next)
  {
    if (root->next_key_part)
    {
      if (root->next_key_part == key)
	count++;
      if (root->next_key_part->part < key->part)
	count+=count_key_part_usage(root->next_key_part,key);
    }
  }
  return count;
}


void SEL_ARG::test_use_count(SEL_ARG *root)
{
2169
  uint e_count=0;
unknown's avatar
unknown committed
2170 2171
  if (this == root && use_count != 1)
  {
2172
    sql_print_error("Note: Use_count: Wrong count %lu for root",use_count);
unknown's avatar
unknown committed
2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184
    return;
  }
  if (this->type != SEL_ARG::KEY_RANGE)
    return;
  for (SEL_ARG *pos=first(); pos ; pos=pos->next)
  {
    e_count++;
    if (pos->next_key_part)
    {
      ulong count=count_key_part_usage(root,pos->next_key_part);
      if (count > pos->next_key_part->use_count)
      {
2185
	sql_print_error("Note: Use_count: Wrong count for key at %lx, %lu should be %lu",
unknown's avatar
unknown committed
2186 2187 2188 2189 2190 2191 2192
			pos,pos->next_key_part->use_count,count);
	return;
      }
      pos->next_key_part->test_use_count(root);
    }
  }
  if (e_count != elements)
2193 2194
    sql_print_error("Warning: Wrong use count: %u (should be %u) for tree at %lx",
		    e_count, elements, (gptr) this);
unknown's avatar
unknown committed
2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212
}

#endif



/*****************************************************************************
** Check how many records we will find by using the found tree
*****************************************************************************/

static ha_rows
check_quick_select(PARAM *param,uint idx,SEL_ARG *tree)
{
  ha_rows records;
  DBUG_ENTER("check_quick_select");

  if (!tree)
    DBUG_RETURN(HA_POS_ERROR);			// Can't use it
unknown's avatar
unknown committed
2213 2214
  param->max_key_part=0;
  param->range_count=0;
unknown's avatar
unknown committed
2215 2216 2217 2218 2219 2220 2221 2222
  if (tree->type == SEL_ARG::IMPOSSIBLE)
    DBUG_RETURN(0L);				// Impossible select. return
  if (tree->type != SEL_ARG::KEY_RANGE || tree->part != 0)
    DBUG_RETURN(HA_POS_ERROR);				// Don't use tree
  records=check_quick_keys(param,idx,tree,param->min_key,0,param->max_key,0);
  if (records != HA_POS_ERROR)
  {
    uint key=param->real_keynr[idx];
2223
    param->table->quick_keys.set_bit(key);
unknown's avatar
unknown committed
2224 2225 2226
    param->table->quick_rows[key]=records;
    param->table->quick_key_parts[key]=param->max_key_part+1;
  }
2227
  DBUG_PRINT("exit", ("Records: %lu", (ulong) records));
unknown's avatar
unknown committed
2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250
  DBUG_RETURN(records);
}


static ha_rows
check_quick_keys(PARAM *param,uint idx,SEL_ARG *key_tree,
		 char *min_key,uint min_key_flag, char *max_key,
		 uint max_key_flag)
{
  ha_rows records=0,tmp;

  param->max_key_part=max(param->max_key_part,key_tree->part);
  if (key_tree->left != &null_element)
  {
    records=check_quick_keys(param,idx,key_tree->left,min_key,min_key_flag,
			     max_key,max_key_flag);
    if (records == HA_POS_ERROR)			// Impossible
      return records;
  }

  uint tmp_min_flag,tmp_max_flag,keynr;
  char *tmp_min_key=min_key,*tmp_max_key=max_key;

2251
  key_tree->store(param->key[idx][key_tree->part].store_length,
unknown's avatar
unknown committed
2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286
		  &tmp_min_key,min_key_flag,&tmp_max_key,max_key_flag);
  uint min_key_length= (uint) (tmp_min_key- param->min_key);
  uint max_key_length= (uint) (tmp_max_key- param->max_key);

  if (key_tree->next_key_part &&
      key_tree->next_key_part->part == key_tree->part+1 &&
      key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
  {						// const key as prefix
    if (min_key_length == max_key_length &&
	!memcmp(min_key,max_key, (uint) (tmp_max_key - max_key)) &&
	!key_tree->min_flag && !key_tree->max_flag)
    {
      tmp=check_quick_keys(param,idx,key_tree->next_key_part,
			   tmp_min_key, min_key_flag | key_tree->min_flag,
			   tmp_max_key, max_key_flag | key_tree->max_flag);
      goto end;					// Ugly, but efficient
    }
    tmp_min_flag=key_tree->min_flag;
    tmp_max_flag=key_tree->max_flag;
    if (!tmp_min_flag)
      key_tree->next_key_part->store_min_key(param->key[idx], &tmp_min_key,
					     &tmp_min_flag);
    if (!tmp_max_flag)
      key_tree->next_key_part->store_max_key(param->key[idx], &tmp_max_key,
					     &tmp_max_flag);
    min_key_length= (uint) (tmp_min_key- param->min_key);
    max_key_length= (uint) (tmp_max_key- param->max_key);
  }
  else
  {
    tmp_min_flag=min_key_flag | key_tree->min_flag;
    tmp_max_flag=max_key_flag | key_tree->max_flag;
  }

  keynr=param->real_keynr[idx];
unknown's avatar
unknown committed
2287
  param->range_count++;
unknown's avatar
unknown committed
2288 2289
  if (!tmp_min_flag && ! tmp_max_flag &&
      (uint) key_tree->part+1 == param->table->key_info[keynr].key_parts &&
2290 2291
      (param->table->key_info[keynr].flags & (HA_NOSAME | HA_END_SPACE_KEY)) ==
      HA_NOSAME &&
unknown's avatar
unknown committed
2292 2293 2294 2295
      min_key_length == max_key_length &&
      !memcmp(param->min_key,param->max_key,min_key_length))
    tmp=1;					// Max one record
  else
unknown's avatar
unknown committed
2296
  {
unknown's avatar
unknown committed
2297
    if (tmp_min_flag & GEOM_FLAG)
unknown's avatar
unknown committed
2298
    {
unknown's avatar
unknown committed
2299 2300 2301 2302 2303 2304 2305 2306
      key_range min_range;
      min_range.key=    (byte*) param->min_key;
      min_range.length= min_key_length;
      /* In this case tmp_min_flag contains the handler-read-function */
      min_range.flag=   (ha_rkey_function) (tmp_min_flag ^ GEOM_FLAG);

      tmp= param->table->file->records_in_range(keynr, &min_range,
                                                (key_range*) 0);
unknown's avatar
unknown committed
2307 2308 2309
    }
    else
    {
unknown's avatar
unknown committed
2310 2311 2312 2313 2314 2315
      key_range min_range, max_range;

      min_range.key=    (byte*) param->min_key;
      min_range.length= min_key_length;
      min_range.flag=   (tmp_min_flag & NEAR_MIN ? HA_READ_AFTER_KEY :
                         HA_READ_KEY_EXACT);
unknown's avatar
unknown committed
2316
      max_range.key=    (byte*) param->max_key;
unknown's avatar
unknown committed
2317 2318 2319 2320 2321 2322 2323 2324
      max_range.length= max_key_length;
      max_range.flag=   (tmp_max_flag & NEAR_MAX ?
                         HA_READ_BEFORE_KEY : HA_READ_AFTER_KEY);
      tmp=param->table->file->records_in_range(keynr,
                                               (min_key_length ? &min_range :
                                                (key_range*) 0),
                                               (max_key_length ? &max_range :
                                                (key_range*) 0));
unknown's avatar
unknown committed
2325 2326
    }
  }
unknown's avatar
unknown committed
2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352
 end:
  if (tmp == HA_POS_ERROR)			// Impossible range
    return tmp;
  records+=tmp;
  if (key_tree->right != &null_element)
  {
    tmp=check_quick_keys(param,idx,key_tree->right,min_key,min_key_flag,
			 max_key,max_key_flag);
    if (tmp == HA_POS_ERROR)
      return tmp;
    records+=tmp;
  }
  return records;
}


/****************************************************************************
** change a tree to a structure to be used by quick_select
** This uses it's own malloc tree
****************************************************************************/

static QUICK_SELECT *
get_quick_select(PARAM *param,uint idx,SEL_ARG *key_tree)
{
  QUICK_SELECT *quick;
  DBUG_ENTER("get_quick_select");
2353 2354 2355 2356 2357 2358 2359 2360

  if (param->table->key_info[param->real_keynr[idx]].flags & HA_SPATIAL)
    quick=new QUICK_SELECT_GEOM(param->thd, param->table, param->real_keynr[idx],
				0);
  else
    quick=new QUICK_SELECT(param->thd, param->table, param->real_keynr[idx]);
			      
  if (quick)
unknown's avatar
unknown committed
2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371
  {
    if (quick->error ||
	get_quick_keys(param,quick,param->key[idx],key_tree,param->min_key,0,
		       param->max_key,0))
    {
      delete quick;
      quick=0;
    }
    else
    {
      quick->key_parts=(KEY_PART*)
2372
	memdup_root(&quick->alloc,(char*) param->key[idx],
unknown's avatar
unknown committed
2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399
		   sizeof(KEY_PART)*
		   param->table->key_info[param->real_keynr[idx]].key_parts);
    }
  }
  DBUG_RETURN(quick);
}


/*
** Fix this to get all possible sub_ranges
*/

static bool
get_quick_keys(PARAM *param,QUICK_SELECT *quick,KEY_PART *key,
	       SEL_ARG *key_tree,char *min_key,uint min_key_flag,
	       char *max_key, uint max_key_flag)
{
  QUICK_RANGE *range;
  uint flag;

  if (key_tree->left != &null_element)
  {
    if (get_quick_keys(param,quick,key,key_tree->left,
		       min_key,min_key_flag, max_key, max_key_flag))
      return 1;
  }
  char *tmp_min_key=min_key,*tmp_max_key=max_key;
2400
  key_tree->store(key[key_tree->part].store_length,
unknown's avatar
unknown committed
2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428
		  &tmp_min_key,min_key_flag,&tmp_max_key,max_key_flag);

  if (key_tree->next_key_part &&
      key_tree->next_key_part->part == key_tree->part+1 &&
      key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
  {						  // const key as prefix
    if (!((tmp_min_key - min_key) != (tmp_max_key - max_key) ||
	  memcmp(min_key,max_key, (uint) (tmp_max_key - max_key)) ||
	  key_tree->min_flag || key_tree->max_flag))
    {
      if (get_quick_keys(param,quick,key,key_tree->next_key_part,
			 tmp_min_key, min_key_flag | key_tree->min_flag,
			 tmp_max_key, max_key_flag | key_tree->max_flag))
	return 1;
      goto end;					// Ugly, but efficient
    }
    {
      uint tmp_min_flag=key_tree->min_flag,tmp_max_flag=key_tree->max_flag;
      if (!tmp_min_flag)
	key_tree->next_key_part->store_min_key(key, &tmp_min_key,
					       &tmp_min_flag);
      if (!tmp_max_flag)
	key_tree->next_key_part->store_max_key(key, &tmp_max_key,
					       &tmp_max_flag);
      flag=tmp_min_flag | tmp_max_flag;
    }
  }
  else
unknown's avatar
unknown committed
2429 2430 2431 2432
  {
    flag = (key_tree->min_flag & GEOM_FLAG) ?
      key_tree->min_flag : key_tree->min_flag | key_tree->max_flag;
  }
unknown's avatar
unknown committed
2433

2434 2435 2436 2437 2438
  /*
    Ensure that some part of min_key and max_key are used.  If not,
    regard this as no lower/upper range
  */
  if ((flag & GEOM_FLAG) == 0)
unknown's avatar
unknown committed
2439 2440 2441 2442 2443 2444 2445 2446 2447 2448
  {
    if (tmp_min_key != param->min_key)
      flag&= ~NO_MIN_RANGE;
    else
      flag|= NO_MIN_RANGE;
    if (tmp_max_key != param->max_key)
      flag&= ~NO_MAX_RANGE;
    else
      flag|= NO_MAX_RANGE;
  }
unknown's avatar
unknown committed
2449 2450 2451 2452 2453 2454 2455 2456
  if (flag == 0)
  {
    uint length= (uint) (tmp_min_key - param->min_key);
    if (length == (uint) (tmp_max_key - param->max_key) &&
	!memcmp(param->min_key,param->max_key,length))
    {
      KEY *table_key=quick->head->key_info+quick->index;
      flag=EQ_RANGE;
2457 2458
      if ((table_key->flags & (HA_NOSAME | HA_END_SPACE_KEY)) == HA_NOSAME &&
	  key->part == table_key->key_parts-1)
2459 2460 2461 2462 2463 2464 2465 2466 2467
      {
	if (!(table_key->flags & HA_NULL_PART_KEY) ||
	    !null_part_in_key(key,
			      param->min_key,
			      (uint) (tmp_min_key - param->min_key)))
	  flag|= UNIQUE_RANGE;
	else
	  flag|= NULL_RANGE;
      }
unknown's avatar
unknown committed
2468 2469 2470 2471
    }
  }

  /* Get range for retrieving rows in QUICK_SELECT::get_next */
2472
  if (!(range= new QUICK_RANGE((const char *) param->min_key,
2473
			       (uint) (tmp_min_key - param->min_key),
2474
			       (const char *) param->max_key,
2475 2476
			       (uint) (tmp_max_key - param->max_key),
			       flag)))
2477 2478
    return 1;			// out of memory

unknown's avatar
unknown committed
2479 2480
  set_if_bigger(quick->max_used_key_length,range->min_length);
  set_if_bigger(quick->max_used_key_length,range->max_length);
unknown's avatar
unknown committed
2481
  set_if_bigger(quick->used_key_parts, (uint) key_tree->part+1);
unknown's avatar
unknown committed
2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500
  quick->ranges.push_back(range);

 end:
  if (key_tree->right != &null_element)
    return get_quick_keys(param,quick,key,key_tree->right,
			  min_key,min_key_flag,
			  max_key,max_key_flag);
  return 0;
}

/*
  Return 1 if there is only one range and this uses the whole primary key
*/

bool QUICK_SELECT::unique_key_range()
{
  if (ranges.elements == 1)
  {
    QUICK_RANGE *tmp;
2501
    if (((tmp=ranges.head())->flag & (EQ_RANGE | NULL_RANGE)) == EQ_RANGE)
unknown's avatar
unknown committed
2502 2503
    {
      KEY *key=head->key_info+index;
2504
      return ((key->flags & (HA_NOSAME | HA_END_SPACE_KEY)) == HA_NOSAME &&
unknown's avatar
unknown committed
2505 2506 2507 2508 2509 2510
	      key->key_length == tmp->min_length);
    }
  }
  return 0;
}

2511 2512 2513 2514 2515 2516 2517

/* Returns true if any part of the key is NULL */

static bool null_part_in_key(KEY_PART *key_part, const char *key, uint length)
{
  for (const char *end=key+length ; 
       key < end;
2518
       key+= key_part++->store_length)
2519
  {
2520 2521
    if (key_part->null_bit && *key)
      return 1;
2522 2523 2524 2525
  }
  return 0;
}

2526

unknown's avatar
unknown committed
2527
/****************************************************************************
2528
  Create a QUICK RANGE based on a key
unknown's avatar
unknown committed
2529 2530
****************************************************************************/

2531
QUICK_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table, TABLE_REF *ref)
unknown's avatar
unknown committed
2532
{
2533
  table->file->index_end();			// Remove old cursor
2534
  QUICK_SELECT *quick=new QUICK_SELECT(thd, table, ref->key, 1);
unknown's avatar
unknown committed
2535 2536
  KEY *key_info = &table->key_info[ref->key];
  KEY_PART *key_part;
unknown's avatar
unknown committed
2537
  QUICK_RANGE *range;
unknown's avatar
unknown committed
2538 2539 2540
  uint part;

  if (!quick)
2541
    return 0;			/* no ranges found */
2542
  if (cp_buffer_from_ref(ref))
unknown's avatar
unknown committed
2543
  {
2544
    if (thd->is_fatal_error)
unknown's avatar
unknown committed
2545
      goto err;					// out of memory
unknown's avatar
unknown committed
2546 2547
    return quick;				// empty range
  }
2548

unknown's avatar
unknown committed
2549
  if (!(range= new QUICK_RANGE()))
2550
    goto err;			// out of memory
2551

unknown's avatar
unknown committed
2552 2553 2554
  range->min_key=range->max_key=(char*) ref->key_buff;
  range->min_length=range->max_length=ref->key_length;
  range->flag= ((ref->key_length == key_info->key_length &&
2555 2556
		 (key_info->flags & (HA_NOSAME | HA_END_SPACE_KEY)) ==
		 HA_NOSAME) ? EQ_RANGE : 0);
unknown's avatar
unknown committed
2557 2558

  if (!(quick->key_parts=key_part=(KEY_PART *)
2559
	alloc_root(&quick->alloc,sizeof(KEY_PART)*ref->key_parts)))
unknown's avatar
unknown committed
2560 2561 2562 2563 2564 2565
    goto err;

  for (part=0 ; part < ref->key_parts ;part++,key_part++)
  {
    key_part->part=part;
    key_part->field=        key_info->key_part[part].field;
2566 2567
    key_part->length=  	    key_info->key_part[part].length;
    key_part->store_length= key_info->key_part[part].store_length;
unknown's avatar
unknown committed
2568 2569
    key_part->null_bit=     key_info->key_part[part].null_bit;
  }
2570 2571 2572
  if (quick->ranges.push_back(range))
    goto err;

2573 2574 2575 2576 2577 2578
  /* 
     Add a NULL range if REF_OR_NULL optimization is used.
     For example:
       if we have "WHERE A=2 OR A IS NULL" we created the (A=2) range above
       and have ref->null_ref_key set. Will create a new NULL range here.
  */
2579 2580 2581 2582 2583
  if (ref->null_ref_key)
  {
    QUICK_RANGE *null_range;

    *ref->null_ref_key= 1;		// Set null byte then create a range
unknown's avatar
unknown committed
2584 2585
    if (!(null_range= new QUICK_RANGE((char*)ref->key_buff, ref->key_length,
				      (char*)ref->key_buff, ref->key_length,
2586 2587 2588 2589 2590 2591 2592 2593
				      EQ_RANGE)))
      goto err;
    *ref->null_ref_key= 0;		// Clear null byte
    if (quick->ranges.push_back(null_range))
      goto err;
  }

  return quick;
unknown's avatar
unknown committed
2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607

err:
  delete quick;
  return 0;
}

	/* get next possible record using quick-struct */

int QUICK_SELECT::get_next()
{
  DBUG_ENTER("get_next");

  for (;;)
  {
2608
    int result;
2609
    key_range start_key, end_key;
unknown's avatar
unknown committed
2610
    if (range)
2611 2612
    {
      // Already read through key
unknown's avatar
unknown committed
2613
      result= file->read_range_next();
2614
      if (result != HA_ERR_END_OF_FILE)
2615
	DBUG_RETURN(result);
unknown's avatar
unknown committed
2616
    }
2617

2618
    if (!(range= it++))
unknown's avatar
unknown committed
2619
      DBUG_RETURN(HA_ERR_END_OF_FILE);		// All ranges used
unknown's avatar
unknown committed
2620

2621
    start_key.key=    (const byte*) range->min_key;
2622 2623 2624 2625
    start_key.length= range->min_length;
    start_key.flag=   ((range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
		       (range->flag & EQ_RANGE) ?
		       HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
2626
    end_key.key=      (const byte*) range->max_key;
2627 2628 2629 2630 2631 2632 2633
    end_key.length=   range->max_length;
    /*
      We use READ_AFTER_KEY here because if we are reading on a key
      prefix we want to find all keys with this prefix
    */
    end_key.flag=     (range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
		       HA_READ_AFTER_KEY);
unknown's avatar
unknown committed
2634

2635 2636
    result= file->read_range_first(range->min_length ? &start_key : 0,
				   range->max_length ? &end_key : 0,
unknown's avatar
unknown committed
2637
                                   test(range->flag & EQ_RANGE),
2638 2639 2640
				   sorted);
    if (range->flag == (UNIQUE_RANGE | EQ_RANGE))
      range=0;				// Stop searching
unknown's avatar
unknown committed
2641

2642 2643 2644
    if (result != HA_ERR_END_OF_FILE)
      DBUG_RETURN(result);
    range=0;				// No matching rows; go to next range
unknown's avatar
unknown committed
2645 2646 2647
  }
}

2648

2649
/* Get next for geometrical indexes */
unknown's avatar
unknown committed
2650

2651
int QUICK_SELECT_GEOM::get_next()
unknown's avatar
unknown committed
2652
{
2653
  DBUG_ENTER(" QUICK_SELECT_GEOM::get_next");
unknown's avatar
unknown committed
2654

2655
  for (;;)
unknown's avatar
unknown committed
2656
  {
2657 2658
    int result;
    if (range)
unknown's avatar
unknown committed
2659
    {
2660 2661 2662 2663 2664
      // Already read through key
      result= file->index_next_same(record, (byte*) range->min_key,
				    range->min_length);
      if (result != HA_ERR_END_OF_FILE)
	DBUG_RETURN(result);
unknown's avatar
unknown committed
2665
    }
2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676

    if (!(range= it++))
      DBUG_RETURN(HA_ERR_END_OF_FILE);		// All ranges used

    result= file->index_read(record,
			     (byte*) range->min_key,
			     range->min_length,
			     (ha_rkey_function)(range->flag ^ GEOM_FLAG));
    if (result != HA_ERR_KEY_NOT_FOUND)
      DBUG_RETURN(result);
    range=0;				// Not found, to next range
unknown's avatar
unknown committed
2677 2678 2679
  }
}

unknown's avatar
unknown committed
2680

2681
/*
2682 2683 2684 2685 2686 2687 2688
  This is a hack: we inherit from QUICK_SELECT so that we can use the
  get_next() interface, but we have to hold a pointer to the original
  QUICK_SELECT because its data are used all over the place.  What
  should be done is to factor out the data that is needed into a base
  class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
  which handle the ranges and implement the get_next() function.  But
  for now, this seems to work right at least.
2689
 */
unknown's avatar
unknown committed
2690 2691 2692

QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_SELECT *q, uint used_key_parts)
  : QUICK_SELECT(*q), rev_it(rev_ranges)
2693
{
2694
  bool not_read_after_key = file->table_flags() & HA_NOT_READ_AFTER_KEY;
unknown's avatar
unknown committed
2695 2696
  QUICK_RANGE *r;

2697
  it.rewind();
unknown's avatar
unknown committed
2698
  for (r = it++; r; r = it++)
2699 2700
  {
    rev_ranges.push_front(r);
unknown's avatar
unknown committed
2701
    if (not_read_after_key && range_reads_after_key(r))
2702
    {
unknown's avatar
unknown committed
2703
      it.rewind();				// Reset range
2704
      error = HA_ERR_UNSUPPORTED;
unknown's avatar
unknown committed
2705 2706
      dont_free=1;				// Don't free memory from 'q'
      return;
2707 2708
    }
  }
unknown's avatar
unknown committed
2709
  /* Remove EQ_RANGE flag for keys that are not using the full key */
unknown's avatar
unknown committed
2710
  for (r = rev_it++; r; r = rev_it++)
unknown's avatar
unknown committed
2711 2712 2713 2714 2715 2716 2717 2718
  {
    if ((r->flag & EQ_RANGE) &&
	head->key_info[index].key_length != r->max_length)
      r->flag&= ~EQ_RANGE;
  }
  rev_it.rewind();
  q->dont_free=1;				// Don't free shared mem
  delete q;
2719 2720
}

unknown's avatar
unknown committed
2721

2722 2723 2724 2725 2726 2727
int QUICK_SELECT_DESC::get_next()
{
  DBUG_ENTER("QUICK_SELECT_DESC::get_next");

  /* The max key is handled as follows:
   *   - if there is NO_MAX_RANGE, start at the end and move backwards
unknown's avatar
unknown committed
2728 2729
   *   - if it is an EQ_RANGE, which means that max key covers the entire
   *     key, go directly to the key and read through it (sorting backwards is
2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741
   *     same as sorting forwards)
   *   - if it is NEAR_MAX, go to the key or next, step back once, and
   *     move backwards
   *   - otherwise (not NEAR_MAX == include the key), go after the key,
   *     step back once, and move backwards
   */

  for (;;)
  {
    int result;
    if (range)
    {						// Already read through key
unknown's avatar
unknown committed
2742 2743 2744
      result = ((range->flag & EQ_RANGE)
		? file->index_next_same(record, (byte*) range->min_key,
					range->min_length) :
2745 2746 2747 2748 2749 2750 2751 2752 2753 2754 2755 2756 2757 2758 2759
		file->index_prev(record));
      if (!result)
      {
	if (cmp_prev(*rev_it.ref()) == 0)
	  DBUG_RETURN(0);
      }
      else if (result != HA_ERR_END_OF_FILE)
	DBUG_RETURN(result);
    }

    if (!(range=rev_it++))
      DBUG_RETURN(HA_ERR_END_OF_FILE);		// All ranges used

    if (range->flag & NO_MAX_RANGE)		// Read last record
    {
2760 2761 2762
      int local_error;
      if ((local_error=file->index_last(record)))
	DBUG_RETURN(local_error);		// Empty table
2763 2764 2765 2766 2767 2768
      if (cmp_prev(range) == 0)
	DBUG_RETURN(0);
      range=0;			// No matching records; go to next range
      continue;
    }

unknown's avatar
unknown committed
2769
    if (range->flag & EQ_RANGE)
2770 2771 2772 2773 2774 2775
    {
      result = file->index_read(record, (byte*) range->max_key,
				range->max_length, HA_READ_KEY_EXACT);
    }
    else
    {
2776
      DBUG_ASSERT(range->flag & NEAR_MAX || range_reads_after_key(range));
2777
#ifndef NOT_IMPLEMENTED_YET
2778 2779 2780 2781 2782
      result=file->index_read(record, (byte*) range->max_key,
			      range->max_length,
			      ((range->flag & NEAR_MAX) ?
			       HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV));
#else
2783 2784 2785 2786 2787
      /*
	Heikki changed Sept 11, 2002: since InnoDB does not store the cursor
	position if READ_KEY_EXACT is used to a primary key with all
	key columns specified, we must use below HA_READ_KEY_OR_NEXT,
	so that InnoDB stores the cursor position and is able to move
unknown's avatar
unknown committed
2788 2789
	the cursor one step backward after the search.
      */
2790 2791 2792 2793
      /*
	Note: even if max_key is only a prefix, HA_READ_AFTER_KEY will
	do the right thing - go past all keys which match the prefix
      */
unknown's avatar
unknown committed
2794 2795 2796
      result=file->index_read(record, (byte*) range->max_key,
			      range->max_length,
			      ((range->flag & NEAR_MAX) ?
unknown's avatar
unknown committed
2797
			       HA_READ_KEY_OR_NEXT : HA_READ_AFTER_KEY));
2798
      result = file->index_prev(record);
2799
#endif
2800 2801 2802 2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817
    }
    if (result)
    {
      if (result != HA_ERR_KEY_NOT_FOUND)
	DBUG_RETURN(result);
      range=0;					// Not found, to next range
      continue;
    }
    if (cmp_prev(range) == 0)
    {
      if (range->flag == (UNIQUE_RANGE | EQ_RANGE))
	range = 0;				// Stop searching
      DBUG_RETURN(0);				// Found key is in range
    }
    range = 0;					// To next range
  }
}

2818

2819
/*
2820 2821 2822 2823
  Returns 0 if found key is inside range (found key >= range->min_key).
*/

int QUICK_SELECT_DESC::cmp_prev(QUICK_RANGE *range_arg)
2824
{
unknown's avatar
unknown committed
2825
  int cmp;
2826
  if (range_arg->flag & NO_MIN_RANGE)
unknown's avatar
unknown committed
2827
    return 0;					/* key can't be to small */
2828

unknown's avatar
unknown committed
2829 2830
  cmp= key_cmp(key_part_info, (byte*) range_arg->min_key,
               range_arg->min_length);
unknown's avatar
unknown committed
2831 2832 2833
  if (cmp > 0 || cmp == 0 && !(range_arg->flag & NEAR_MIN))
    return 0;
  return 1;                                     // outside of range
2834 2835
}

2836

2837 2838
/*
 * True if this range will require using HA_READ_AFTER_KEY
unknown's avatar
unknown committed
2839
   See comment in get_next() about this
2840
 */
unknown's avatar
unknown committed
2841

2842
bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range_arg)
2843
{
unknown's avatar
unknown committed
2844
  return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
2845
	  !(range_arg->flag & EQ_RANGE) ||
unknown's avatar
unknown committed
2846
	  head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
2847 2848
}

2849

unknown's avatar
unknown committed
2850 2851
/* True if we are reading over a key that may have a NULL value */

unknown's avatar
unknown committed
2852
#ifdef NOT_USED
2853
bool QUICK_SELECT_DESC::test_if_null_range(QUICK_RANGE *range_arg,
unknown's avatar
unknown committed
2854 2855
					   uint used_key_parts)
{
2856
  uint offset, end;
unknown's avatar
unknown committed
2857 2858 2859
  KEY_PART *key_part = key_parts,
           *key_part_end= key_part+used_key_parts;

2860
  for (offset= 0,  end = min(range_arg->min_length, range_arg->max_length) ;
unknown's avatar
unknown committed
2861
       offset < end && key_part != key_part_end ;
2862
       offset+= key_part++->store_length)
unknown's avatar
unknown committed
2863
  {
2864 2865
    if (!memcmp((char*) range_arg->min_key+offset,
		(char*) range_arg->max_key+offset,
2866
		key_part->store_length))
unknown's avatar
unknown committed
2867
      continue;
2868 2869

    if (key_part->null_bit && range_arg->min_key[offset])
unknown's avatar
unknown committed
2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 2881
      return 1;				// min_key is null and max_key isn't
    // Range doesn't cover NULL. This is ok if there is no more null parts
    break;
  }
  /*
    If the next min_range is > NULL, then we can use this, even if
    it's a NULL key
    Example:  SELECT * FROM t1 WHERE a = 2 AND b >0 ORDER BY a DESC,b DESC;

  */
  if (key_part != key_part_end && key_part->null_bit)
  {
2882
    if (offset >= range_arg->min_length || range_arg->min_key[offset])
unknown's avatar
unknown committed
2883 2884 2885 2886 2887 2888 2889 2890 2891 2892 2893 2894
      return 1;					// Could be null
    key_part++;
  }
  /*
    If any of the key parts used in the ORDER BY could be NULL, we can't
    use the key to sort the data.
  */
  for (; key_part != key_part_end ; key_part++)
    if (key_part->null_bit)
      return 1;					// Covers null part
  return 0;
}
unknown's avatar
unknown committed
2895
#endif
unknown's avatar
unknown committed
2896 2897


unknown's avatar
unknown committed
2898 2899 2900 2901 2902 2903 2904 2905 2906 2907 2908 2909 2910
/*****************************************************************************
** Print a quick range for debugging
** TODO:
** This should be changed to use a String to store each row instead
** of locking the DEBUG stream !
*****************************************************************************/

#ifndef DBUG_OFF

static void
print_key(KEY_PART *key_part,const char *key,uint used_length)
{
  char buff[1024];
2911
  const char *key_end= key+used_length;
unknown's avatar
unknown committed
2912
  String tmp(buff,sizeof(buff),&my_charset_bin);
2913
  uint store_length;
unknown's avatar
unknown committed
2914

2915
  for (; key < key_end; key+=store_length, key_part++)
unknown's avatar
unknown committed
2916
  {
2917
    Field *field=      key_part->field;
2918
    store_length= key_part->store_length;
2919

unknown's avatar
unknown committed
2920 2921
    if (field->real_maybe_null())
    {
2922
      if (*key)
unknown's avatar
unknown committed
2923 2924 2925 2926
      {
	fwrite("NULL",sizeof(char),4,DBUG_FILE);
	continue;
      }
2927
      key++;					// Skip null byte
2928
      store_length--;
unknown's avatar
unknown committed
2929
    }
2930
    field->set_key_image((char*) key, key_part->length, field->charset());
2931
    field->val_str(&tmp);
unknown's avatar
unknown committed
2932
    fwrite(tmp.ptr(),sizeof(char),tmp.length(),DBUG_FILE);
2933 2934
    if (key+store_length < key_end)
      fputc('/',DBUG_FILE);
unknown's avatar
unknown committed
2935 2936 2937
  }
}

2938

unknown's avatar
unknown committed
2939
static void print_quick(QUICK_SELECT *quick,const key_map* needed_reg)
unknown's avatar
unknown committed
2940 2941
{
  QUICK_RANGE *range;
2942
  char buf[MAX_KEY/8+1];
unknown's avatar
unknown committed
2943 2944 2945 2946 2947 2948
  DBUG_ENTER("print_param");
  if (! _db_on_ || !quick)
    DBUG_VOID_RETURN;

  List_iterator<QUICK_RANGE> li(quick->ranges);
  DBUG_LOCK_FILE;
unknown's avatar
unknown committed
2949 2950
  fprintf(DBUG_FILE,"Used quick_range on key: %d (other_keys: 0x%s):\n",
	  quick->index, needed_reg->print(buf));
unknown's avatar
unknown committed
2951 2952 2953 2954 2955 2956 2957 2958 2959 2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986
  while ((range=li++))
  {
    if (!(range->flag & NO_MIN_RANGE))
    {
      print_key(quick->key_parts,range->min_key,range->min_length);
      if (range->flag & NEAR_MIN)
	fputs(" < ",DBUG_FILE);
      else
	fputs(" <= ",DBUG_FILE);
    }
    fputs("X",DBUG_FILE);

    if (!(range->flag & NO_MAX_RANGE))
    {
      if (range->flag & NEAR_MAX)
	fputs(" < ",DBUG_FILE);
      else
	fputs(" <= ",DBUG_FILE);
      print_key(quick->key_parts,range->max_key,range->max_length);
    }
    fputs("\n",DBUG_FILE);
  }
  DBUG_UNLOCK_FILE;
  DBUG_VOID_RETURN;
}

#endif

/*****************************************************************************
** Instansiate templates
*****************************************************************************/

#ifdef __GNUC__
template class List<QUICK_RANGE>;
template class List_iterator<QUICK_RANGE>;
#endif