filesort.cc 28.3 KB
Newer Older
bk@work.mysql.com's avatar
bk@work.mysql.com committed
1
/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
2

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

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

bk@work.mysql.com's avatar
bk@work.mysql.com committed
13 14 15 16 17 18 19 20 21 22 23 24
   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 */


/* Sorts a database */

#include "mysql_priv.h"
#ifdef HAVE_STDDEF_H
#include <stddef.h>			/* for macro offsetof */
#endif
#include <m_ctype.h>
25 26
#include "sql_sort.h"

bk@work.mysql.com's avatar
bk@work.mysql.com committed
27
#ifndef THREAD
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
28
#define SKIP_DBUG_IN_FILESORT
bk@work.mysql.com's avatar
bk@work.mysql.com committed
29 30 31 32 33 34 35 36 37 38 39
#endif

	/* How to write record_ref. */

#define WRITE_REF(file,from) \
if (my_b_write((file),(byte*) (from),param->ref_length)) \
  DBUG_RETURN(1);

	/* functions defined in this file */

static char **make_char_array(register uint fields, uint length, myf my_flag);
40
static BUFFPEK *read_buffpek_from_file(IO_CACHE *buffer_file, uint count);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
41
static ha_rows find_all_keys(SORTPARAM *param,SQL_SELECT *select,
42
			     uchar * *sort_keys, IO_CACHE *buffer_file,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
43 44
			     IO_CACHE *tempfile,IO_CACHE *indexfile);
static int write_keys(SORTPARAM *param,uchar * *sort_keys,
45 46
		      uint count, IO_CACHE *buffer_file, IO_CACHE *tempfile);
static void make_sortkey(SORTPARAM *param,uchar *to, byte *ref_pos);
47
static int merge_index(SORTPARAM *param,uchar *sort_buffer,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
48 49 50
		       BUFFPEK *buffpek,
		       uint maxbuffer,IO_CACHE *tempfile,
		       IO_CACHE *outfile);
51
static bool save_index(SORTPARAM *param,uchar **sort_keys, uint count);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
52 53
static uint sortlength(SORT_FIELD *sortorder,uint length);

54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
/*
  Sort a table

  SYNOPSIS
    filesort()
    table		Table to sort
    sortorder		How to sort the table
    s_length		Number of elements in sortorder	
    select		condition to apply to the rows
    special		Not used.
			(This could be used to sort the rows pointed on by
			select->file)
   examined_rows	Store number of examined rows here

  IMPLEMENTATION
    Creates a set of pointers that can be used to read the rows
    in sorted order. This should be done with the functions
    in records.cc
  
  REQUIREMENTS
    Before calling filesort, one must have done
    table->file->info(HA_STATUS_VARIABLE)

  RETURN
    HA_POS_ERROR	Error
    #			Number of rows

    examined_rows	will be set to number of examined rows

    The result set is stored in table->io_cache or
    table->record_pointers
*/
86 87

ha_rows filesort(TABLE *table, SORT_FIELD *sortorder, uint s_length,
88 89
		 SQL_SELECT *select, ha_rows special, ha_rows max_rows,
		 ha_rows *examined_rows)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
90 91
{
  int error;
92
  ulong memavl, min_sort_memory;
93
  uint maxbuffer;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
94 95 96
  BUFFPEK *buffpek;
  ha_rows records;
  uchar **sort_keys;
97
  IO_CACHE tempfile, buffpek_pointers, *selected_records_file, *outfile; 
bk@work.mysql.com's avatar
bk@work.mysql.com committed
98
  SORTPARAM param;
99 100
  THD *thd= current_thd;

bk@work.mysql.com's avatar
bk@work.mysql.com committed
101
  DBUG_ENTER("filesort");
102
  DBUG_EXECUTE("info",TEST_filesort(sortorder,s_length,special););
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
103
#ifdef SKIP_DBUG_IN_FILESORT
bk@work.mysql.com's avatar
bk@work.mysql.com committed
104 105 106
  DBUG_PUSH("");		/* No DBUG here */
#endif

107
  outfile= table->io_cache;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
108
  my_b_clear(&tempfile);
109 110 111 112
  my_b_clear(&buffpek_pointers);
  buffpek=0;
  sort_keys= (uchar **) NULL;
  error= 1;
113
  bzero((char*) &param,sizeof(param));
114
  param.ref_length= table->file->ref_length;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
115 116
  param.sort_length=sortlength(sortorder,s_length)+ param.ref_length;
  param.max_rows= max_rows;
117

118 119
  if (select && select->quick)
  {
120
    statistic_increment(filesort_range_count, &LOCK_status);
121 122 123 124 125
  }
  else
  {
    statistic_increment(filesort_scan_count, &LOCK_status);
  }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141
  if (select && my_b_inited(&select->file))
  {
    records=special=select->records;		/* purecov: deadcode */
    selected_records_file= &select->file;	/* purecov: deadcode */
    reinit_io_cache(selected_records_file,READ_CACHE,0L,0,0); /* purecov: deadcode */
  }
  else if (special)
  {
    records=special;				/* purecov: deadcode */
    selected_records_file= outfile;		/* purecov: deadcode */
    reinit_io_cache(selected_records_file,READ_CACHE,0L,0,0); /* purecov: deadcode */
  }
#ifdef CAN_TRUST_RANGE
  else if (select && select->quick && select->quick->records > 0L)
  {
    records=min((ha_rows) (select->quick->records*2+EXTRA_RECORDS*2),
142
		table->file->records)+EXTRA_RECORDS;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
143 144 145 146 147
    selected_records_file=0;
  }
#endif
  else
  {
148
    records=table->file->estimate_number_of_rows();
bk@work.mysql.com's avatar
bk@work.mysql.com committed
149 150 151 152 153 154 155 156 157
    selected_records_file= 0;
  }

#ifdef USE_STRCOLL
  if (use_strcoll(default_charset_info) &&
      !(param.tmp_buffer=my_malloc(param.sort_length,MYF(MY_WME))))
    goto err;
#endif

158
  memavl= thd->variables.sortbuff_size;
monty@mashka.mysql.fi's avatar
monty@mashka.mysql.fi committed
159 160
  min_sort_memory= max(MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2);
  while (memavl >= min_sort_memory)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
161
  {
162 163 164 165
    ulong old_memavl;
    ulong keys= memavl/(param.sort_length+sizeof(char*));
    param.keys=(uint) min(records+1, keys);
    if ((sort_keys= (uchar **) make_char_array(param.keys, param.sort_length,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
166
					       MYF(0))))
167
      break;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
168
    old_memavl=memavl;
monty@mashka.mysql.fi's avatar
monty@mashka.mysql.fi committed
169
    if ((memavl=memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
170
      memavl= min_sort_memory;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
171
  }
monty@mashka.mysql.fi's avatar
monty@mashka.mysql.fi committed
172
  if (memavl < min_sort_memory)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
173
  {
174 175
    my_error(ER_OUTOFMEMORY,MYF(ME_ERROR+ME_WAITTANG),
	     thd->variables.sortbuff_size);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
176 177
    goto err;
  }
178 179 180 181 182
  if (open_cached_file(&buffpek_pointers,mysql_tmpdir,TEMP_PREFIX,
		       DISK_BUFFER_SIZE, MYF(MY_WME)))
    goto err;

  param.keys--;
183
  param.sort_form= table;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
184
  param.end=(param.local_sortorder=sortorder)+s_length;
185
  if ((records=find_all_keys(&param,select,sort_keys, &buffpek_pointers,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
186 187 188
			     &tempfile, selected_records_file)) ==
      HA_POS_ERROR)
    goto err;
189
  maxbuffer= (uint) (my_b_tell(&buffpek_pointers)/sizeof(*buffpek));
190

191
  if (maxbuffer == 0)			// The whole set is in memory
bk@work.mysql.com's avatar
bk@work.mysql.com committed
192 193 194 195 196 197
  {
    if (save_index(&param,sort_keys,(uint) records))
      goto err;
  }
  else
  {
198 199 200
    if (!(buffpek=read_buffpek_from_file(&buffpek_pointers, maxbuffer)))
      goto err;
    close_cached_file(&buffpek_pointers);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
201 202 203 204 205 206 207
	/* Open cached file if it isn't open */
    if (! my_b_inited(outfile) &&
	open_cached_file(outfile,mysql_tmpdir,TEMP_PREFIX,READ_RECORD_BUFFER,
			  MYF(MY_WME)))
      goto err;
    reinit_io_cache(outfile,WRITE_CACHE,0L,0,0);

208 209 210 211
    /*
      Use also the space previously used by string pointers in sort_buffer
      for temporary key storage.
    */
bk@work.mysql.com's avatar
bk@work.mysql.com committed
212 213
    param.keys=((param.keys*(param.sort_length+sizeof(char*))) /
		param.sort_length-1);
214
    maxbuffer--;				// Offset from 0
215 216
    if (merge_many_buff(&param,(uchar*) sort_keys,buffpek,&maxbuffer,
			&tempfile))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
217 218 219 220
      goto err;
    if (flush_io_cache(&tempfile) ||
	reinit_io_cache(&tempfile,READ_CACHE,0L,0,0))
      goto err;
221 222
    if (merge_index(&param,(uchar*) sort_keys,buffpek,maxbuffer,&tempfile,
		    outfile))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
223 224 225 226 227 228 229 230 231 232 233 234 235 236
      goto err;
  }
  if (records > param.max_rows)
    records=param.max_rows;
  error =0;

 err:
#ifdef USE_STRCOLL
  if (use_strcoll(default_charset_info))
    x_free(param.tmp_buffer);
#endif
  x_free((gptr) sort_keys);
  x_free((gptr) buffpek);
  close_cached_file(&tempfile);
237
  close_cached_file(&buffpek_pointers);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
238 239 240 241 242 243 244 245 246 247 248 249 250 251
  if (my_b_inited(outfile))
  {
    if (flush_io_cache(outfile))
      error=1;
    {
      my_off_t save_pos=outfile->pos_in_file;
      /* For following reads */
      if (reinit_io_cache(outfile,READ_CACHE,0L,0,0))
	error=1;
      outfile->end_of_file=save_pos;
    }
  }
  if (error)
    my_error(ER_FILSORT_ABORT,MYF(ME_ERROR+ME_WAITTANG));
252
  else
253
    statistic_add(filesort_rows, (ulong) records, &LOCK_status);
254
  *examined_rows= param.examined_rows;
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
255
#ifdef SKIP_DBUG_IN_FILESORT
bk@work.mysql.com's avatar
bk@work.mysql.com committed
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
  DBUG_POP();			/* Ok to DBUG */
#endif
  DBUG_PRINT("exit",("records: %ld",records));
  DBUG_RETURN(error ? HA_POS_ERROR : records);
} /* filesort */


	/* Make a array of string pointers */

static char **make_char_array(register uint fields, uint length, myf my_flag)
{
  register char **pos;
  char **old_pos,*char_pos;
  DBUG_ENTER("make_char_array");

  if ((old_pos= (char**) my_malloc((uint) fields*(length+sizeof(char*)),
				    my_flag)))
  {
    pos=old_pos; char_pos=((char*) (pos+fields)) -length;
    while (fields--) *(pos++) = (char_pos+= length);
  }

  DBUG_RETURN(old_pos);
} /* make_char_array */


282 283 284 285 286 287 288 289 290 291 292
	/* Read all buffer pointers into memory */

static BUFFPEK *read_buffpek_from_file(IO_CACHE *buffpek_pointers, uint count)
{
  ulong length;
  BUFFPEK *tmp;
  DBUG_ENTER("read_buffpek_from_file");
  tmp=(BUFFPEK*) my_malloc(length=sizeof(BUFFPEK)*count, MYF(MY_WME));
  if (tmp)
  {
    if (reinit_io_cache(buffpek_pointers,READ_CACHE,0L,0,0) ||
293
	my_b_read(buffpek_pointers, (byte*) tmp, length))
294 295 296 297 298 299
    {
      my_free((char*) tmp, MYF(0));
      tmp=0;
    }      
  }
  DBUG_RETURN(tmp);
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
300
}
301 302 303



bk@work.mysql.com's avatar
bk@work.mysql.com committed
304 305 306 307
	/* Search after sort_keys and place them in a temp. file */

static ha_rows find_all_keys(SORTPARAM *param, SQL_SELECT *select,
			     uchar **sort_keys,
308
			     IO_CACHE *buffpek_pointers,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
309 310 311 312 313 314 315 316 317 318
			     IO_CACHE *tempfile, IO_CACHE *indexfile)
{
  int error,flag,quick_select;
  uint idx,indexpos,ref_length;
  byte *ref_pos,*next_pos,ref_buff[MAX_REFLENGTH];
  my_off_t record;
  TABLE *sort_form;
  volatile bool *killed= &current_thd->killed;
  handler *file;
  DBUG_ENTER("find_all_keys");
319
  DBUG_PRINT("info",("using: %s",(select?select->quick?"ranges":"where":"every row")));
bk@work.mysql.com's avatar
bk@work.mysql.com committed
320 321 322 323 324 325 326 327 328

  idx=indexpos=0;
  error=quick_select=0;
  sort_form=param->sort_form;
  file=sort_form->file;
  ref_length=param->ref_length;
  ref_pos= ref_buff;
  quick_select=select && select->quick;
  record=0;
329
  flag= ((!indexfile && file->table_flags() & HA_REC_NOT_IN_SEQ)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
330 331 332 333 334 335
	 || quick_select);
  if (indexfile || flag)
    ref_pos= &file->ref[0];
  next_pos=ref_pos;
  if (! indexfile && ! quick_select)
  {
336
    file->reset();			// QQ; Shouldn't be needed
337
    if (sort_form->key_read)		// QQ Can be removed after the reset
338
      file->extra(HA_EXTRA_KEYREAD);	// QQ is removed
bk@work.mysql.com's avatar
bk@work.mysql.com committed
339 340
    next_pos=(byte*) 0;			/* Find records in sequence */
    file->rnd_init();
341 342
    file->extra_opt(HA_EXTRA_CACHE,
		    current_thd->variables.read_buff_size);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372
  }

  for (;;)
  {
    if (quick_select)
    {
      if ((error=select->quick->get_next()))
	break;
      file->position(sort_form->record[0]);
    }
    else					/* Not quick-select */
    {
      if (indexfile)
      {
	if (my_b_read(indexfile,(byte*) ref_pos,ref_length)) /* purecov: deadcode */
	{
	  error= my_errno ? my_errno : -1;		/* Abort */
	  break;
	}
	error=file->rnd_pos(sort_form->record[0],next_pos);
      }
      else
      {
	error=file->rnd_next(sort_form->record[0]);
	if (!flag)
	{
	  ha_store_ptr(ref_pos,ref_length,record); // Position to row
	  record+=sort_form->db_record_offset;
	}
	else
373
	  file->position(sort_form->record[0]);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
374 375 376 377 378 379
      }
      if (error && error != HA_ERR_RECORD_DELETED)
	break;
    }
    if (*killed)
    {
380
      DBUG_PRINT("info",("Sort killed by user"));
bk@work.mysql.com's avatar
bk@work.mysql.com committed
381 382 383 384
      (void) file->extra(HA_EXTRA_NO_CACHE);
      file->rnd_end();
      DBUG_RETURN(HA_POS_ERROR);		/* purecov: inspected */
    }
385 386
    if (error == 0)
      param->examined_rows++;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
387 388 389 390
    if (error == 0 && (!select || select->skipp_record() == 0))
    {
      if (idx == param->keys)
      {
391 392
	if (write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
	  DBUG_RETURN(HA_POS_ERROR);
393 394
	idx=0;
	indexpos++;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
395 396 397
      }
      make_sortkey(param,sort_keys[idx++],ref_pos);
    }
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
398 399
    else
      file->unlock_row();
bk@work.mysql.com's avatar
bk@work.mysql.com committed
400 401 402 403 404 405 406 407 408
  }
  (void) file->extra(HA_EXTRA_NO_CACHE);	/* End cacheing of records */
  file->rnd_end();
  DBUG_PRINT("test",("error: %d  indexpos: %d",error,indexpos));
  if (error != HA_ERR_END_OF_FILE)
  {
    file->print_error(error,MYF(ME_ERROR | ME_WAITTANG)); /* purecov: inspected */
    DBUG_RETURN(HA_POS_ERROR);			/* purecov: inspected */
  }
409
  if (indexpos && idx &&
410 411
      write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
    DBUG_RETURN(HA_POS_ERROR);			/* purecov: inspected */
bk@work.mysql.com's avatar
bk@work.mysql.com committed
412 413 414 415 416 417 418 419
  DBUG_RETURN(my_b_inited(tempfile) ?
	      (ha_rows) (my_b_tell(tempfile)/param->sort_length) :
	      idx);
} /* find_all_keys */


	/* Skriver en buffert med nycklar till filen */

420 421 422
static int
write_keys(SORTPARAM *param, register uchar **sort_keys, uint count,
	   IO_CACHE *buffpek_pointers, IO_CACHE *tempfile)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
423 424
{
  uint sort_length;
425
  uchar **end;
426
  BUFFPEK buffpek;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
427 428 429 430 431 432 433 434 435 436 437
  DBUG_ENTER("write_keys");

  sort_length=param->sort_length;
#ifdef MC68000
  quicksort(sort_keys,count,sort_length);
#else
  my_string_ptr_sort((gptr) sort_keys,(uint) count,sort_length);
#endif
  if (!my_b_inited(tempfile) &&
      open_cached_file(tempfile,mysql_tmpdir,TEMP_PREFIX,DISK_BUFFER_SIZE,
			MYF(MY_WME)))
438 439
    goto err;					/* purecov: inspected */
  buffpek.file_pos=my_b_tell(tempfile);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
440 441
  if ((ha_rows) count > param->max_rows)
    count=(uint) param->max_rows;		/* purecov: inspected */
442
  buffpek.count=(ha_rows) count;
443
  for (end=sort_keys+count ; sort_keys != end ; sort_keys++)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
444
    if (my_b_write(tempfile,(byte*) *sort_keys,(uint) sort_length))
445
      goto err;
446
  if (my_b_write(buffpek_pointers, (byte*) &buffpek, sizeof(buffpek)))
447
    goto err;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
448
  DBUG_RETURN(0);
449 450 451

err:
  DBUG_RETURN(1);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467
} /* write_keys */


	/* makes a sort-key from record */

static void make_sortkey(register SORTPARAM *param,
			 register uchar *to, byte *ref_pos)
{
  reg3 Field *field;
  reg1 SORT_FIELD *sort_field;
  reg5 uint length;

  for (sort_field=param->local_sortorder ;
       sort_field != param->end ;
       sort_field++)
  {
468
    bool maybe_null=0;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
469 470 471 472 473 474
    if ((field=sort_field->field))
    {						// Field
      if (field->maybe_null())
      {
	if (field->is_null())
	{
475 476 477 478
	  if (sort_field->reverse)
	    bfill(to,sort_field->length+1,(char) 255);
	  else
	    bzero((char*) to,sort_field->length+1);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
479 480 481 482 483 484 485 486 487 488 489 490 491 492
	  to+= sort_field->length+1;
	  continue;
	}
	else
	  *to++=1;
      }
      field->sort_string((char*) to,sort_field->length);
    }
    else
    {						// Item
      Item *item=sort_field->item;
      switch (sort_field->result_type) {
      case STRING_RESULT:
	{
493
	  if ((maybe_null=item->maybe_null))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558
	    *to++=1;
	  /* All item->str() to use some extra byte for end null.. */
	  String tmp((char*) to,sort_field->length+4);
	  String *res=item->val_str(&tmp);
	  if (!res)
	  {
	    if (item->maybe_null)
	      bzero((char*) to-1,sort_field->length+1);
	    else
	    {
	      DBUG_PRINT("warning",
			 ("Got null on something that shouldn't be null"));
	      bzero((char*) to,sort_field->length);	// Avoid crash
	    }
	    break;
	  }
	  length=res->length();
	  int diff=(int) (sort_field->length-length);
	  if (diff < 0)
	  {
	    diff=0;				/* purecov: inspected */
	    length=sort_field->length;
	  }
#ifdef USE_STRCOLL
          if (use_strcoll(default_charset_info))
          {
            if (item->binary)
            {
              if (res->ptr() != (char*) to)
                memcpy(to,res->ptr(),length);
              bzero((char*) to+length,diff);
            }
            else
            {
              char *from=(char*) res->ptr();
              if ((unsigned char *)from == to)
              {
                set_if_smaller(length,sort_field->length);
                memcpy(param->tmp_buffer,from,length);
                from=param->tmp_buffer;
              }
              uint tmp_length=my_strnxfrm(default_charset_info,
                                          to,(unsigned char *) from,
                                          sort_field->length,
                                          length);
              if (tmp_length < sort_field->length)
                bzero((char*) to+tmp_length,sort_field->length-tmp_length);
            }
          }
          else
          {
#endif
            if (res->ptr() != (char*) to)
              memcpy(to,res->ptr(),length);
            bzero((char *)to+length,diff);
            if (!item->binary)
              case_sort((char*) to,length);
#ifdef USE_STRCOLL
          }
#endif
	  break;
	}
      case INT_RESULT:
	{
	  longlong value=item->val_int();
559
	  if ((maybe_null=item->maybe_null))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592
	    *to++=1;				/* purecov: inspected */
	  if (item->null_value)
	  {
	    if (item->maybe_null)
	      bzero((char*) to-1,sort_field->length+1);
	    else
	    {
	      DBUG_PRINT("warning",
			 ("Got null on something that shouldn't be null"));
	      bzero((char*) to,sort_field->length);
	    }
	    break;
	  }
#if SIZEOF_LONG_LONG > 4
	  to[7]= (uchar) value;
	  to[6]= (uchar) (value >> 8);
	  to[5]= (uchar) (value >> 16);
	  to[4]= (uchar) (value >> 24);
	  to[3]= (uchar) (value >> 32);
	  to[2]= (uchar) (value >> 40);
	  to[1]= (uchar) (value >> 48);
	  to[0]= (uchar) (value >> 56) ^ 128;	// Fix sign
#else
	  to[3]= (uchar) value;
	  to[2]= (uchar) (value >> 8);
	  to[1]= (uchar) (value >> 16);
	  to[0]= (uchar) (value >> 24) ^ 128;	// Fix sign
#endif
	  break;
	}
      case REAL_RESULT:
	{
	  double value=item->val();
593
	  if ((maybe_null=item->null_value))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
594 595 596 597 598
	  {
	    bzero((char*) to,sort_field->length+1);
	    to++;
	    break;
	  }
599
	  if ((maybe_null=item->maybe_null))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
600 601 602 603 604 605 606 607
	    *to++=1;
	  change_double_for_sort(value,(byte*) to);
	  break;
	}
      }
    }
    if (sort_field->reverse)
    {							/* Revers key */
608 609
      if (maybe_null)
        to[-1]= ~to[-1];
bk@work.mysql.com's avatar
bk@work.mysql.com committed
610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649
      length=sort_field->length;
      while (length--)
      {
	*to = (uchar) (~ *to);
	to++;
      }
    }
    else
      to+= sort_field->length;
  }
  memcpy((byte*) to,ref_pos,(size_s) param->ref_length);/* Save filepos last */
  return;
}


static bool save_index(SORTPARAM *param, uchar **sort_keys, uint count)
{
  uint offset,ref_length;
  byte *to;
  DBUG_ENTER("save_index");

  my_string_ptr_sort((gptr) sort_keys,(uint) count,param->sort_length);
  ref_length=param->ref_length;
  offset=param->sort_length-ref_length;
  if ((ha_rows) count > param->max_rows)
    count=(uint) param->max_rows;
  if (!(to=param->sort_form->record_pointers=
	(byte*) my_malloc(ref_length*count,MYF(MY_WME))))
    DBUG_RETURN(1);				/* purecov: inspected */
  for (uchar **end=sort_keys+count ; sort_keys != end ; sort_keys++)
  {
    memcpy(to,*sort_keys+offset,ref_length);
    to+=ref_length;
  }
  DBUG_RETURN(0);
}


	/* Merge buffers to make < MERGEBUFF2 buffers */

650 651
int merge_many_buff(SORTPARAM *param, uchar *sort_buffer,
		    BUFFPEK *buffpek, uint *maxbuffer, IO_CACHE *t_file)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672
{
  register int i;
  IO_CACHE t_file2,*from_file,*to_file,*temp;
  BUFFPEK *lastbuff;
  DBUG_ENTER("merge_many_buff");

  if (*maxbuffer < MERGEBUFF2)
    DBUG_RETURN(0);				/* purecov: inspected */
  if (flush_io_cache(t_file) ||
      open_cached_file(&t_file2,mysql_tmpdir,TEMP_PREFIX,DISK_BUFFER_SIZE,
			MYF(MY_WME)))
    DBUG_RETURN(1);				/* purecov: inspected */

  from_file= t_file ; to_file= &t_file2;
  while (*maxbuffer >= MERGEBUFF2)
  {
    reinit_io_cache(from_file,READ_CACHE,0L,0,0);
    reinit_io_cache(to_file,WRITE_CACHE,0L,0,0);
    lastbuff=buffpek;
    for (i=0 ; i <= (int) *maxbuffer-MERGEBUFF*3/2 ; i+=MERGEBUFF)
    {
673
      if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
674 675 676
			buffpek+i,buffpek+i+MERGEBUFF-1,0))
	break;					/* purecov: inspected */
    }
677
    if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695
		      buffpek+i,buffpek+ *maxbuffer,0))
      break;					/* purecov: inspected */
    if (flush_io_cache(to_file))
      break;					/* purecov: inspected */
    temp=from_file; from_file=to_file; to_file=temp;
    *maxbuffer= (uint) (lastbuff-buffpek)-1;
  }
  close_cached_file(to_file);			// This holds old result
  if (to_file == t_file)
    *t_file=t_file2;				// Copy result file

  DBUG_RETURN(*maxbuffer >= MERGEBUFF2);	/* Return 1 if interrupted */
} /* merge_many_buff */


	/* Read data to buffer */
	/* This returns (uint) -1 if something goes wrong */

696 697
uint read_to_buffer(IO_CACHE *fromfile, BUFFPEK *buffpek,
		    uint sort_length)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717
{
  register uint count;
  uint length;

  if ((count=(uint) min((ha_rows) buffpek->max_keys,buffpek->count)))
  {
    if (my_pread(fromfile->file,(byte*) buffpek->base,
		 (length= sort_length*count),buffpek->file_pos,MYF_RW))
      return((uint) -1);			/* purecov: inspected */
    buffpek->key=buffpek->base;
    buffpek->file_pos+= length;			/* New filepos */
    buffpek->count-=	count;
    buffpek->mem_count= count;
  }
  return (count*sort_length);
} /* read_to_buffer */


	/* Merge buffers to one buffer */

718 719 720 721
int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
		  IO_CACHE *to_file, uchar *sort_buffer,
		  BUFFPEK *lastbuff, BUFFPEK *Fb, BUFFPEK *Tb,
		  int flag)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
722 723 724 725
{
  int error;
  uint sort_length,offset;
  ulong maxcount;
726
  ha_rows max_rows,org_max_rows;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
727 728 729 730
  my_off_t to_start_filepos;
  uchar *strpos;
  BUFFPEK *buffpek,**refpek;
  QUEUE queue;
731
  qsort2_cmp    cmp;
732 733
  volatile bool *killed= &current_thd->killed;
  bool not_killable;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
734 735
  DBUG_ENTER("merge_buffers");

736
  statistic_increment(filesort_merge_passes, &LOCK_status);
737 738 739 740 741
  if (param->not_killable)
  {
    killed= &not_killable;
    not_killable=0;
  }
742

743
  error=0;
744
  offset=(sort_length=param->sort_length)-param->ref_length;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
745 746
  maxcount=(ulong) (param->keys/((uint) (Tb-Fb) +1));
  to_start_filepos=my_b_tell(to_file);
747
  strpos=(uchar*) sort_buffer;
748
  org_max_rows=max_rows=param->max_rows;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
749 750

  if (init_queue(&queue,(uint) (Tb-Fb)+1,offsetof(BUFFPEK,key),0,
751
		 (queue_compare)
752
		 (cmp=get_ptr_compare(sort_length)),(void*) &sort_length))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
753 754 755 756 757 758 759 760 761
    DBUG_RETURN(1);				/* purecov: inspected */
  for (buffpek= Fb ; buffpek <= Tb ; buffpek++)
  {
    buffpek->base= strpos;
    buffpek->max_keys=maxcount;
    strpos+= (uint) (error=(int) read_to_buffer(from_file,buffpek,
						sort_length));
    if (error == -1)
      goto err;					/* purecov: inspected */
762
    buffpek->max_keys= buffpek->mem_count;	// If less data in buffers than expected
bk@work.mysql.com's avatar
bk@work.mysql.com committed
763 764 765
    queue_insert(&queue,(byte*) buffpek);
  }

766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781
  if (param->unique_buff)
  {
    /* 
       Called by Unique::get()
       Copy the first argument to param->unique_buff for unique removal.
       Store it also in 'to_file'.

       This is safe as we know that there is always more than one element
       in each block to merge (This is guaranteed by the Unique:: algorithm
    */
    buffpek=(BUFFPEK*) queue_top(&queue);
    memcpy(param->unique_buff, buffpek->key, sort_length);
    if (my_b_write(to_file,(byte*) buffpek->key, sort_length))
    {
      error=1; goto err;			/* purecov: inspected */
    }
782
    buffpek->key+=sort_length;
783
    buffpek->mem_count--;
784 785 786 787 788
    if (!--max_rows)
    {
      error=0;					/* purecov: inspected */
      goto end;					/* purecov: inspected */
    }
789
    queue_replaced(&queue);			// Top element has been used
790 791 792 793
  }
  else
    cmp=0;					// Not unique

bk@work.mysql.com's avatar
bk@work.mysql.com committed
794 795
  while (queue.elements > 1)
  {
796 797 798 799
    if (*killed)
    {
      error=1; goto err;                        /* purecov: inspected */
    }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
800 801 802
    for (;;)
    {
      buffpek=(BUFFPEK*) queue_top(&queue);
803 804
      if (cmp)					// Remove duplicates
      {
805 806
	if (!(*cmp)(&sort_length, &(param->unique_buff),
		    (uchar**) &buffpek->key))
807 808 809
	  goto skip_duplicate;
	memcpy(param->unique_buff, (uchar*) buffpek->key,sort_length);
      }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825
      if (flag == 0)
      {
	if (my_b_write(to_file,(byte*) buffpek->key, sort_length))
	{
	  error=1; goto err;			/* purecov: inspected */
	}
      }
      else
      {
	WRITE_REF(to_file,(byte*) buffpek->key+offset);
      }
      if (!--max_rows)
      {
	error=0;				/* purecov: inspected */
	goto end;				/* purecov: inspected */
      }
826 827

    skip_duplicate:
bk@work.mysql.com's avatar
bk@work.mysql.com committed
828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859
      buffpek->key+=sort_length;
      if (! --buffpek->mem_count)
      {
	if (!(error=(int) read_to_buffer(from_file,buffpek,
					 sort_length)))
	{
	  uchar *base=buffpek->base;
	  ulong max_keys=buffpek->max_keys;

	  VOID(queue_remove(&queue,0));

	  /* Put room used by buffer to use in other buffer */
	  for (refpek= (BUFFPEK**) &queue_top(&queue);
	       refpek <= (BUFFPEK**) &queue_end(&queue);
	       refpek++)
	  {
	    buffpek= *refpek;
	    if (buffpek->base+buffpek->max_keys*sort_length == base)
	    {
	      buffpek->max_keys+=max_keys;
	      break;
	    }
	    else if (base+max_keys*sort_length == buffpek->base)
	    {
	      buffpek->base=base;
	      buffpek->max_keys+=max_keys;
	      break;
	    }
	  }
	  break;			/* One buffer have been removed */
	}
	else if (error == -1)
860
	  goto err;			/* purecov: inspected */
bk@work.mysql.com's avatar
bk@work.mysql.com committed
861 862 863 864 865
      }
      queue_replaced(&queue);		/* Top element has been replaced */
    }
  }
  buffpek=(BUFFPEK*) queue_top(&queue);
866
  buffpek->base= sort_buffer;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
867
  buffpek->max_keys=param->keys;
868 869 870 871 872 873 874 875 876 877 878 879 880 881

  /*
    As we know all entries in the buffer are unique, we only have to
    check if the first one is the same as the last one we wrote
  */
  if (cmp)
  {
    if (!(*cmp)(&sort_length, &(param->unique_buff), (uchar**) &buffpek->key))
    {
      buffpek->key+=sort_length;	// Remove duplicate
      --buffpek->mem_count;
    }
  }

bk@work.mysql.com's avatar
bk@work.mysql.com committed
882 883 884 885 886 887 888
  do
  {
    if ((ha_rows) buffpek->mem_count > max_rows)
    {					/* Don't write too many records */
      buffpek->mem_count=(uint) max_rows;
      buffpek->count=0;			/* Don't read more */
    }
889
    max_rows-=buffpek->mem_count;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913
    if (flag == 0)
    {
      if (my_b_write(to_file,(byte*) buffpek->key,
		     (sort_length*buffpek->mem_count)))
      {
	error=1; goto err;			/* purecov: inspected */
      }
    }
    else
    {
      register uchar *end;
      strpos= buffpek->key+offset;
      for (end=strpos+buffpek->mem_count*sort_length;
	   strpos != end ;
	   strpos+=sort_length)
      {
	WRITE_REF(to_file,strpos);
      }
    }
  }
  while ((error=(int) read_to_buffer(from_file,buffpek,sort_length))
	 != -1 && error != 0);

end:
914
  lastbuff->count=min(org_max_rows-max_rows,param->max_rows);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
915 916 917 918 919 920 921 922 923
  lastbuff->file_pos=to_start_filepos;
err:
  delete_queue(&queue);
  DBUG_RETURN(error);
} /* merge_buffers */


	/* Do a merge to output-file (save only positions) */

924
static int merge_index(SORTPARAM *param, uchar *sort_buffer,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
925 926 927 928
		       BUFFPEK *buffpek, uint maxbuffer,
		       IO_CACHE *tempfile, IO_CACHE *outfile)
{
  DBUG_ENTER("merge_index");
929
  if (merge_buffers(param,tempfile,outfile,sort_buffer,buffpek,buffpek,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
930 931 932 933 934 935 936 937 938 939 940 941
		    buffpek+maxbuffer,1))
    DBUG_RETURN(1);				/* purecov: inspected */
  DBUG_RETURN(0);
} /* merge_index */


	/* Calculate length of sort key */

static uint
sortlength(SORT_FIELD *sortorder, uint s_length)
{
  reg2 uint length;
942
  THD *thd= current_thd;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
943 944 945 946 947 948 949

  length=0;
  for (; s_length-- ; sortorder++)
  {
    if (sortorder->field)
    {
      if (sortorder->field->type() == FIELD_TYPE_BLOB)
950
	sortorder->length= thd->variables.max_sort_length;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985
      else
      {
	sortorder->length=sortorder->field->pack_length();
#ifdef USE_STRCOLL
	if (use_strcoll(default_charset_info) && !sortorder->field->binary())
	  sortorder->length= sortorder->length*MY_STRXFRM_MULTIPLY;
#endif
      }
      if (sortorder->field->maybe_null())
	length++;				// Place for NULL marker
    }
    else
    {
      switch ((sortorder->result_type=sortorder->item->result_type())) {
      case STRING_RESULT:
	sortorder->length=sortorder->item->max_length;
#ifdef USE_STRCOLL
	if (use_strcoll(default_charset_info) && !sortorder->item->binary)
	  sortorder->length= sortorder->length*MY_STRXFRM_MULTIPLY;
#endif
	break;
      case INT_RESULT:
#if SIZEOF_LONG_LONG > 4
	sortorder->length=8;			// Size of intern longlong
#else
	sortorder->length=4;
#endif
	break;
      case REAL_RESULT:
	sortorder->length=sizeof(double);
	break;
      }
      if (sortorder->item->maybe_null)
	length++;				// Place for NULL marker
    }
986
    set_if_smaller(sortorder->length, thd->variables.max_sort_length);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016
    length+=sortorder->length;
  }
  sortorder->field= (Field*) 0;			// end marker
  DBUG_PRINT("info",("sort_length: %d",length));
  return length;
}


/*
** functions to change a double or float to a sortable string
** The following should work for IEEE
*/

#define DBL_EXP_DIG (sizeof(double)*8-DBL_MANT_DIG)

void change_double_for_sort(double nr,byte *to)
{
  uchar *tmp=(uchar*) to;
  if (nr == 0.0)
  {						/* Change to zero string */
    tmp[0]=(uchar) 128;
    bzero((char*) tmp+1,sizeof(nr)-1);
  }
  else
  {
#ifdef WORDS_BIGENDIAN
    memcpy_fixed(tmp,&nr,sizeof(nr));
#else
    {
      uchar *ptr= (uchar*) &nr;
1017
#if defined(__FLOAT_WORD_ORDER) && (__FLOAT_WORD_ORDER == __BIG_ENDIAN)
1018 1019 1020
      tmp[0]= ptr[3]; tmp[1]=ptr[2]; tmp[2]= ptr[1]; tmp[3]=ptr[0];
      tmp[4]= ptr[7]; tmp[5]=ptr[6]; tmp[6]= ptr[5]; tmp[7]=ptr[4];
#else
bk@work.mysql.com's avatar
bk@work.mysql.com committed
1021 1022
      tmp[0]= ptr[7]; tmp[1]=ptr[6]; tmp[2]= ptr[5]; tmp[3]=ptr[4];
      tmp[4]= ptr[3]; tmp[5]=ptr[2]; tmp[6]= ptr[1]; tmp[7]=ptr[0];
1023
#endif
bk@work.mysql.com's avatar
bk@work.mysql.com committed
1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041
    }
#endif
    if (tmp[0] & 128)				/* Negative */
    {						/* make complement */
      uint i;
      for (i=0 ; i < sizeof(nr); i++)
	tmp[i]=tmp[i] ^ (uchar) 255;
    }
    else
    {					/* Set high and move exponent one up */
      ushort exp_part=(((ushort) tmp[0] << 8) | (ushort) tmp[1] |
		       (ushort) 32768);
      exp_part+= (ushort) 1 << (16-1-DBL_EXP_DIG);
      tmp[0]= (uchar) (exp_part >> 8);
      tmp[1]= (uchar) exp_part;
    }
  }
}