filesort.cc 36.3 KB
Newer Older
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi 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);
52 53
static uint sortlength(SORT_FIELD *sortorder, uint s_length,
		       bool *multi_byte_charset);
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
54 55 56 57
static SORT_ADDON_FIELD *get_addon_fields(THD *thd, Field **ptabfield,
                                          uint sortlength, uint *plength);
static void unpack_addon_fields(struct st_sort_addon_field *addon_field,
                                byte *buff);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
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 86 87 88 89 90
/*
  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
*/
91

92 93
ha_rows filesort(THD *thd, TABLE *table, SORT_FIELD *sortorder, uint s_length,
		 SQL_SELECT *select, ha_rows max_rows, ha_rows *examined_rows)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
94 95
{
  int error;
96
  ulong memavl, min_sort_memory;
97
  uint maxbuffer;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
98
  BUFFPEK *buffpek;
monty@mashka.mysql.fi's avatar
monty@mashka.mysql.fi committed
99
  ha_rows records= HA_POS_ERROR;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
100
  uchar **sort_keys;
101
  IO_CACHE tempfile, buffpek_pointers, *selected_records_file, *outfile; 
bk@work.mysql.com's avatar
bk@work.mysql.com committed
102
  SORTPARAM param;
103
  bool multi_byte_charset;
104 105
  DBUG_ENTER("filesort");
  DBUG_EXECUTE("info",TEST_filesort(sortorder,s_length););
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
106
#ifdef SKIP_DBUG_IN_FILESORT
bk@work.mysql.com's avatar
bk@work.mysql.com committed
107 108 109
  DBUG_PUSH("");		/* No DBUG here */
#endif

igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
110
  outfile= table->sort.io_cache;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
111
  my_b_clear(&tempfile);
112 113 114 115
  my_b_clear(&buffpek_pointers);
  buffpek=0;
  sort_keys= (uchar **) NULL;
  error= 1;
116
  bzero((char*) &param,sizeof(param));
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
117
  param.sort_length= sortlength(sortorder, s_length, &multi_byte_charset);
118
  param.ref_length= table->file->ref_length;
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
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
  param.addon_field= 0;
  param.addon_length= 0;
  if (!(table->tmp_table || table->fulltext_searched))
  {
    /* 
      Get the descriptors of all fields whose values are appended 
      to sorted fields and get its total length in param.spack_length.
    */
    param.addon_field= get_addon_fields(thd, table->field, 
                                        param.sort_length,
                                        &param.addon_length);
  }
  table->sort.addon_buf= 0;
  table->sort.addon_length= param.addon_length;
  table->sort.addon_field= param.addon_field;
  table->sort.unpack= unpack_addon_fields;
  if (param.addon_field)
  {
    param.res_length= param.addon_length;
    if (!(table->sort.addon_buf= (byte *) my_malloc(param.addon_length,
                                                    MYF(MY_WME))))
      goto err;
  }
  else
  {
    param.res_length= param.ref_length;
    /* 
      The reference to the record is considered 
      as an additional sorted field
    */
    param.sort_length+= param.ref_length;
  }
  param.rec_length= param.sort_length+param.addon_length;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
152
  param.max_rows= max_rows;
153

154 155
  if (select && select->quick)
  {
156
    statistic_increment(filesort_range_count, &LOCK_status);
157 158 159 160 161
  }
  else
  {
    statistic_increment(filesort_scan_count, &LOCK_status);
  }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
162
#ifdef CAN_TRUST_RANGE
163
  if (select && select->quick && select->quick->records > 0L)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
164 165
  {
    records=min((ha_rows) (select->quick->records*2+EXTRA_RECORDS*2),
166
		table->file->records)+EXTRA_RECORDS;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
167 168 169
    selected_records_file=0;
  }
  else
170
#endif
bk@work.mysql.com's avatar
bk@work.mysql.com committed
171
  {
172
    records=table->file->estimate_number_of_rows();
bk@work.mysql.com's avatar
bk@work.mysql.com committed
173 174 175
    selected_records_file= 0;
  }

176
  if (multi_byte_charset &&
bk@work.mysql.com's avatar
bk@work.mysql.com committed
177 178 179
      !(param.tmp_buffer=my_malloc(param.sort_length,MYF(MY_WME))))
    goto err;

180
  memavl= thd->variables.sortbuff_size;
monty@mashka.mysql.fi's avatar
monty@mashka.mysql.fi committed
181 182
  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
183
  {
184
    ulong old_memavl;
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
185
    ulong keys= memavl/(param.rec_length+sizeof(char*));
186
    param.keys=(uint) min(records+1, keys);
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
187
    if ((sort_keys= (uchar **) make_char_array(param.keys, param.rec_length,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
188
					       MYF(0))))
189
      break;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
190
    old_memavl=memavl;
monty@mashka.mysql.fi's avatar
monty@mashka.mysql.fi committed
191
    if ((memavl=memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
192
      memavl= min_sort_memory;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
193
  }
monty@mashka.mysql.fi's avatar
monty@mashka.mysql.fi committed
194
  if (memavl < min_sort_memory)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
195
  {
196 197
    my_error(ER_OUTOFMEMORY,MYF(ME_ERROR+ME_WAITTANG),
	     thd->variables.sortbuff_size);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
198 199
    goto err;
  }
200 201 202 203
  if (open_cached_file(&buffpek_pointers,mysql_tmpdir,TEMP_PREFIX,
		       DISK_BUFFER_SIZE, MYF(MY_WME)))
    goto err;

204
  param.keys--;  			/* TODO: check why we do this */
205
  param.sort_form= table;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
206
  param.end=(param.local_sortorder=sortorder)+s_length;
207
  if ((records=find_all_keys(&param,select,sort_keys, &buffpek_pointers,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
208 209 210
			     &tempfile, selected_records_file)) ==
      HA_POS_ERROR)
    goto err;
211
  maxbuffer= (uint) (my_b_tell(&buffpek_pointers)/sizeof(*buffpek));
212

213
  if (maxbuffer == 0)			// The whole set is in memory
bk@work.mysql.com's avatar
bk@work.mysql.com committed
214 215 216 217 218 219
  {
    if (save_index(&param,sort_keys,(uint) records))
      goto err;
  }
  else
  {
220 221 222
    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
223 224 225 226 227 228 229
	/* 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);

230 231 232 233
    /*
      Use also the space previously used by string pointers in sort_buffer
      for temporary key storage.
    */
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
234 235
    param.keys=((param.keys*(param.rec_length+sizeof(char*))) /
		param.rec_length-1);
236
    maxbuffer--;				// Offset from 0
237 238
    if (merge_many_buff(&param,(uchar*) sort_keys,buffpek,&maxbuffer,
			&tempfile))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
239 240 241 242
      goto err;
    if (flush_io_cache(&tempfile) ||
	reinit_io_cache(&tempfile,READ_CACHE,0L,0,0))
      goto err;
243 244
    if (merge_index(&param,(uchar*) sort_keys,buffpek,maxbuffer,&tempfile,
		    outfile))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
245 246 247 248 249 250 251
      goto err;
  }
  if (records > param.max_rows)
    records=param.max_rows;
  error =0;

 err:
252
  if (param.tmp_buffer)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
253 254 255 256
    x_free(param.tmp_buffer);
  x_free((gptr) sort_keys);
  x_free((gptr) buffpek);
  close_cached_file(&tempfile);
257
  close_cached_file(&buffpek_pointers);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
258 259 260 261 262 263 264 265 266 267 268 269 270 271
  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));
272
  else
273
    statistic_add(filesort_rows, (ulong) records, &LOCK_status);
274
  *examined_rows= param.examined_rows;
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
275
#ifdef SKIP_DBUG_IN_FILESORT
bk@work.mysql.com's avatar
bk@work.mysql.com committed
276 277 278 279 280 281 282
  DBUG_POP();			/* Ok to DBUG */
#endif
  DBUG_PRINT("exit",("records: %ld",records));
  DBUG_RETURN(error ? HA_POS_ERROR : records);
} /* filesort */


283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298
void filesort_free_buffers(TABLE *table)
{
  if (table->sort.record_pointers)
  {
    my_free((gptr) table->sort.record_pointers,MYF(0));
    table->sort.record_pointers=0;
  }
  if (table->sort.addon_buf)
  {
    my_free((char *) table->sort.addon_buf, MYF(0));
    my_free((char *) table->sort.addon_field, MYF(MY_ALLOW_ZERO_PTR));
    table->sort.addon_buf=0;
    table->sort.addon_field=0;
  }
}

bk@work.mysql.com's avatar
bk@work.mysql.com committed
299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317
	/* 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 */


318 319 320 321 322 323 324 325 326 327 328
	/* 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) ||
329
	my_b_read(buffpek_pointers, (byte*) tmp, length))
330 331 332
    {
      my_free((char*) tmp, MYF(0));
      tmp=0;
333
    }
334 335
  }
  DBUG_RETURN(tmp);
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
336
}
337 338 339



bk@work.mysql.com's avatar
bk@work.mysql.com committed
340 341 342 343
	/* 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,
344
			     IO_CACHE *buffpek_pointers,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
345 346 347 348 349 350 351
			     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;
352
  volatile my_bool *killed= &current_thd->killed;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
353 354
  handler *file;
  DBUG_ENTER("find_all_keys");
355
  DBUG_PRINT("info",("using: %s",(select?select->quick?"ranges":"where":"every row")));
bk@work.mysql.com's avatar
bk@work.mysql.com committed
356 357 358 359 360 361 362 363 364

  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;
365
  flag= ((!indexfile && file->table_flags() & HA_REC_NOT_IN_SEQ)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
366 367 368 369 370 371
	 || quick_select);
  if (indexfile || flag)
    ref_pos= &file->ref[0];
  next_pos=ref_pos;
  if (! indexfile && ! quick_select)
  {
372
    file->reset();			// QQ; Shouldn't be needed
373
    if (sort_form->key_read)		// QQ Can be removed after the reset
374
      file->extra(HA_EXTRA_KEYREAD);	// QQ is removed
bk@work.mysql.com's avatar
bk@work.mysql.com committed
375
    next_pos=(byte*) 0;			/* Find records in sequence */
376
    file->ha_rnd_init(1);
377 378
    file->extra_opt(HA_EXTRA_CACHE,
		    current_thd->variables.read_buff_size);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408
  }

  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
409
	  file->position(sort_form->record[0]);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
410 411 412 413 414 415
      }
      if (error && error != HA_ERR_RECORD_DELETED)
	break;
    }
    if (*killed)
    {
416
      DBUG_PRINT("info",("Sort killed by user"));
bk@work.mysql.com's avatar
bk@work.mysql.com committed
417
      (void) file->extra(HA_EXTRA_NO_CACHE);
418
      file->ha_rnd_end();
bk@work.mysql.com's avatar
bk@work.mysql.com committed
419 420
      DBUG_RETURN(HA_POS_ERROR);		/* purecov: inspected */
    }
421 422
    if (error == 0)
      param->examined_rows++;
423
    if (error == 0 && (!select || select->skip_record() == 0))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
424 425 426
    {
      if (idx == param->keys)
      {
427 428
	if (write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
	  DBUG_RETURN(HA_POS_ERROR);
429 430
	idx=0;
	indexpos++;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
431 432 433
      }
      make_sortkey(param,sort_keys[idx++],ref_pos);
    }
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
434 435
    else
      file->unlock_row();
bk@work.mysql.com's avatar
bk@work.mysql.com committed
436 437
  }
  (void) file->extra(HA_EXTRA_NO_CACHE);	/* End cacheing of records */
438 439
  if (!next_pos)
    file->ha_rnd_end();
bk@work.mysql.com's avatar
bk@work.mysql.com committed
440 441 442 443 444 445
  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 */
  }
446
  if (indexpos && idx &&
447 448
      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
449
  DBUG_RETURN(my_b_inited(tempfile) ?
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
450
	      (ha_rows) (my_b_tell(tempfile)/param->rec_length) :
bk@work.mysql.com's avatar
bk@work.mysql.com committed
451 452 453 454 455 456
	      idx);
} /* find_all_keys */


	/* Skriver en buffert med nycklar till filen */

457 458
static int
write_keys(SORTPARAM *param, register uchar **sort_keys, uint count,
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
459
           IO_CACHE *buffpek_pointers, IO_CACHE *tempfile)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
460
{
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
461
  uint sort_length, rec_length;
462
  uchar **end;
463
  BUFFPEK buffpek;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
464 465
  DBUG_ENTER("write_keys");

igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
466 467
  sort_length= param->sort_length;
  rec_length= param->rec_length;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
468 469 470
#ifdef MC68000
  quicksort(sort_keys,count,sort_length);
#else
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
471
  my_string_ptr_sort((gptr) sort_keys, (uint) count, sort_length);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
472 473
#endif
  if (!my_b_inited(tempfile) &&
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
474 475 476 477
      open_cached_file(tempfile, mysql_tmpdir, TEMP_PREFIX, DISK_BUFFER_SIZE,
                       MYF(MY_WME)))
    goto err;                                        /* purecov: inspected */
  buffpek.file_pos= my_b_tell(tempfile);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
478
  if ((ha_rows) count > param->max_rows)
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
479
    count=(uint) param->max_rows;                /* purecov: inspected */
480
  buffpek.count=(ha_rows) count;
481
  for (end=sort_keys+count ; sort_keys != end ; sort_keys++)
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
482
    if (my_b_write(tempfile, (byte*) *sort_keys, (uint) rec_length))
483
      goto err;
484
  if (my_b_write(buffpek_pointers, (byte*) &buffpek, sizeof(buffpek)))
485
    goto err;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
486
  DBUG_RETURN(0);
487 488 489

err:
  DBUG_RETURN(1);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505
} /* 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++)
  {
506
    bool maybe_null=0;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
507 508 509 510 511 512
    if ((field=sort_field->field))
    {						// Field
      if (field->maybe_null())
      {
	if (field->is_null())
	{
513 514 515 516
	  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
517 518 519 520 521 522 523 524 525 526 527 528 529 530
	  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:
	{
531
          CHARSET_INFO *cs=item->collation.collation;
532 533
	  char fill_char= ((cs->state & MY_CS_BINSORT) ? (char) 0 : ' ');

534
	  if ((maybe_null=item->maybe_null))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
535 536
	    *to++=1;
	  /* All item->str() to use some extra byte for end null.. */
537
	  String tmp((char*) to,sort_field->length+4,cs);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557
	  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;
	  }
558
          if (sort_field->need_strxnfrm)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
559
          {
560 561 562 563 564 565 566 567 568 569
	    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(cs,to,sort_field->length,
					(unsigned char *) from, length);
	    if (tmp_length < sort_field->length)
570 571 572
	      cs->cset->fill(cs, (char*) to+tmp_length,
			     sort_field->length-tmp_length,
			     fill_char);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
573 574 575
          }
          else
          {
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
576
             my_strnxfrm(cs,(uchar*)to,length,(const uchar*)res->ptr(),length);
577
             cs->cset->fill(cs, (char *)to+length,diff,fill_char);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
578
          }
579
	  break;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
580 581 582 583
	}
      case INT_RESULT:
	{
	  longlong value=item->val_int();
584
	  if ((maybe_null=item->maybe_null))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617
	    *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();
618
	  if ((maybe_null=item->null_value))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
619 620 621 622 623
	  {
	    bzero((char*) to,sort_field->length+1);
	    to++;
	    break;
	  }
624
	  if ((maybe_null=item->maybe_null))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
625 626 627 628
	    *to++=1;
	  change_double_for_sort(value,(byte*) to);
	  break;
	}
629
      case ROW_RESULT:
630
      default: 
631 632 633
	// This case should never be choosen
	DBUG_ASSERT(0);
	break;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
634 635 636 637
      }
    }
    if (sort_field->reverse)
    {							/* Revers key */
638 639
      if (maybe_null)
        to[-1]= ~to[-1];
bk@work.mysql.com's avatar
bk@work.mysql.com committed
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;
  }
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666

  if (param->addon_field)
  {
    /* 
      Save field values appended to sorted fields.
      First null bit indicators are appended then field values follow.
      In this implementation we use fixed layout for field values -
      the same for all records.
    */
    SORT_ADDON_FIELD *addonf= param->addon_field;
    uchar *nulls= to;
    DBUG_ASSERT(addonf);
    bzero((char *) nulls, addonf->offset);
    to+= addonf->offset;
    for ( ; (field= addonf->field) ; addonf++)
    {
      if (addonf->null_bit && field->is_null())
667
      {
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
668
        nulls[addonf->null_offset]|= addonf->null_bit;
669 670 671 672
#ifdef HAVE_purify
	bzero(to, addonf->length);
#endif
      }
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
673
      else
674 675 676 677 678 679 680 681 682
      {
        uchar *end= (uchar*) field->pack((char *) to, field->ptr);
#ifdef HAVE_purify
	uint length= (uint) ((to + addonf->length) - end);
	DBUG_ASSERT((int) length >= 0);
	if (length)
	  bzero(end, length);
#endif
      }
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
683 684 685 686 687 688 689 690
      to+= addonf->length;
    }
  }
  else
  {
    /* Save filepos last */
    memcpy((byte*) to, ref_pos, (size_s) param->ref_length);
  }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
691 692 693 694 695 696
  return;
}


static bool save_index(SORTPARAM *param, uchar **sort_keys, uint count)
{
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
697
  uint offset,res_length;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
698 699 700
  byte *to;
  DBUG_ENTER("save_index");

igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
701 702 703
  my_string_ptr_sort((gptr) sort_keys, (uint) count, param->sort_length);
  res_length= param->res_length;
  offset= param->rec_length-res_length;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
704 705
  if ((ha_rows) count > param->max_rows)
    count=(uint) param->max_rows;
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
706 707 708 709
  if (!(to= param->sort_form->sort.record_pointers=
        (byte*) my_malloc(res_length*count, MYF(MY_WME))))
    DBUG_RETURN(1);                 /* purecov: inspected */
  for (uchar **end= sort_keys+count ; sort_keys != end ; sort_keys++)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
710
  {
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
711 712
    memcpy(to, *sort_keys+offset, res_length);
    to+= res_length;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
713 714 715 716 717 718 719
  }
  DBUG_RETURN(0);
}


	/* Merge buffers to make < MERGEBUFF2 buffers */

720 721
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
722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742
{
  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)
    {
743
      if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
744 745 746
			buffpek+i,buffpek+i+MERGEBUFF-1,0))
	break;					/* purecov: inspected */
    }
747
    if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765
		      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 */

766
uint read_to_buffer(IO_CACHE *fromfile, BUFFPEK *buffpek,
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
767
		    uint rec_length)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
768 769 770 771 772 773 774
{
  register uint count;
  uint length;

  if ((count=(uint) min((ha_rows) buffpek->max_keys,buffpek->count)))
  {
    if (my_pread(fromfile->file,(byte*) buffpek->base,
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
775
		 (length= rec_length*count),buffpek->file_pos,MYF_RW))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
776 777 778 779 780 781
      return((uint) -1);			/* purecov: inspected */
    buffpek->key=buffpek->base;
    buffpek->file_pos+= length;			/* New filepos */
    buffpek->count-=	count;
    buffpek->mem_count= count;
  }
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
782
  return (count*rec_length);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
783 784 785
} /* read_to_buffer */


igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
786 787 788
/* 
   Merge buffers to one buffer 
*/
bk@work.mysql.com's avatar
bk@work.mysql.com committed
789

790
int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
791 792 793
                  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
794 795
{
  int error;
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
796
  uint rec_length,sort_length,res_length,offset;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
797
  ulong maxcount;
798
  ha_rows max_rows,org_max_rows;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
799 800 801 802
  my_off_t to_start_filepos;
  uchar *strpos;
  BUFFPEK *buffpek,**refpek;
  QUEUE queue;
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
803
  qsort2_cmp cmp;
804 805
  volatile my_bool *killed= &current_thd->killed;
  my_bool not_killable;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
806 807
  DBUG_ENTER("merge_buffers");

808
  statistic_increment(filesort_merge_passes, &LOCK_status);
809 810 811
  if (param->not_killable)
  {
    killed= &not_killable;
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
812
    not_killable= 0;
813
  }
814

815
  error=0;
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
816 817 818 819 820 821 822 823 824 825 826 827 828
  rec_length= param->rec_length;
  res_length= param->res_length;
  sort_length= param->sort_length;
  offset= rec_length-res_length;
  maxcount= (ulong) (param->keys/((uint) (Tb-Fb) +1));
  to_start_filepos= my_b_tell(to_file);
  strpos= (uchar*) sort_buffer;
  org_max_rows=max_rows= param->max_rows;

  if (init_queue(&queue, (uint) (Tb-Fb)+1, offsetof(BUFFPEK,key), 0,
                 (queue_compare) (cmp= get_ptr_compare(sort_length)),
                 (void*) &sort_length))
    DBUG_RETURN(1);                                /* purecov: inspected */
bk@work.mysql.com's avatar
bk@work.mysql.com committed
829 830 831
  for (buffpek= Fb ; buffpek <= Tb ; buffpek++)
  {
    buffpek->base= strpos;
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
832 833 834
    buffpek->max_keys= maxcount;
    strpos+= (uint) (error= (int) read_to_buffer(from_file, buffpek,
                                                                         rec_length));
bk@work.mysql.com's avatar
bk@work.mysql.com committed
835 836
    if (error == -1)
      goto err;					/* purecov: inspected */
837
    buffpek->max_keys= buffpek->mem_count;	// If less data in buffers than expected
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
838
    queue_insert(&queue, (byte*) buffpek);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
839 840
  }

841 842 843 844 845 846 847 848 849 850
  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
    */
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
851 852 853
    buffpek= (BUFFPEK*) queue_top(&queue);
    memcpy(param->unique_buff, buffpek->key, rec_length);
    if (my_b_write(to_file, (byte*) buffpek->key, rec_length))
854
    {
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
855
      error=1; goto err;                        /* purecov: inspected */
856
    }
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
857
    buffpek->key+= rec_length;
858
    buffpek->mem_count--;
859 860
    if (!--max_rows)
    {
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
861 862
      error= 0;                                       /* purecov: inspected */
      goto end;                                       /* purecov: inspected */
863
    }
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
864
    queue_replaced(&queue);                        // Top element has been used
865 866
  }
  else
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
867
    cmp= 0;                                        // Not unique
868

bk@work.mysql.com's avatar
bk@work.mysql.com committed
869 870
  while (queue.elements > 1)
  {
871 872
    if (*killed)
    {
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
873
      error= 1; goto err;                        /* purecov: inspected */
874
    }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
875 876
    for (;;)
    {
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
877 878
      buffpek= (BUFFPEK*) queue_top(&queue);
      if (cmp)                                        // Remove duplicates
879
      {
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
880 881 882 883
        if (!(*cmp)(&sort_length, &(param->unique_buff),
                    (uchar**) &buffpek->key))
              goto skip_duplicate;
            memcpy(param->unique_buff, (uchar*) buffpek->key, rec_length);
884
      }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
885 886
      if (flag == 0)
      {
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
887 888 889 890
        if (my_b_write(to_file,(byte*) buffpek->key, rec_length))
        {
          error=1; goto err;                        /* purecov: inspected */
        }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
891 892 893
      }
      else
      {
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
894 895 896 897
        if (my_b_write(to_file, (byte*) buffpek->key+offset, res_length))
        {
          error=1; goto err;                        /* purecov: inspected */
        }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
898 899 900
      }
      if (!--max_rows)
      {
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
901 902
        error= 0;                               /* purecov: inspected */
        goto end;                               /* purecov: inspected */
bk@work.mysql.com's avatar
bk@work.mysql.com committed
903
      }
904 905

    skip_duplicate:
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
906
      buffpek->key+= rec_length;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
907 908
      if (! --buffpek->mem_count)
      {
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938
        if (!(error= (int) read_to_buffer(from_file,buffpek,
                                          rec_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*rec_length == base)
            {
              buffpek->max_keys+= max_keys;
              break;
            }
            else if (base+max_keys*rec_length == buffpek->base)
            {
              buffpek->base= base;
              buffpek->max_keys+= max_keys;
              break;
            }
          }
          break;                        /* One buffer have been removed */
        }
        else if (error == -1)
          goto err;                        /* purecov: inspected */
bk@work.mysql.com's avatar
bk@work.mysql.com committed
939
      }
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
940
      queue_replaced(&queue);              /* Top element has been replaced */
bk@work.mysql.com's avatar
bk@work.mysql.com committed
941 942
    }
  }
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
943
  buffpek= (BUFFPEK*) queue_top(&queue);
944
  buffpek->base= sort_buffer;
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
945
  buffpek->max_keys= param->keys;
946 947 948 949 950 951 952 953 954

  /*
    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))
    {
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
955
      buffpek->key+= rec_length;         // Remove duplicate
956 957 958 959
      --buffpek->mem_count;
    }
  }

bk@work.mysql.com's avatar
bk@work.mysql.com committed
960 961 962
  do
  {
    if ((ha_rows) buffpek->mem_count > max_rows)
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
963 964 965
    {                                        /* Don't write too many records */
      buffpek->mem_count= (uint) max_rows;
      buffpek->count= 0;                        /* Don't read more */
bk@work.mysql.com's avatar
bk@work.mysql.com committed
966
    }
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
967
    max_rows-= buffpek->mem_count;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
968 969 970
    if (flag == 0)
    {
      if (my_b_write(to_file,(byte*) buffpek->key,
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
971
                     (rec_length*buffpek->mem_count)))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
972
      {
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
973
        error= 1; goto err;                        /* purecov: inspected */
bk@work.mysql.com's avatar
bk@work.mysql.com committed
974 975 976 977 978 979
      }
    }
    else
    {
      register uchar *end;
      strpos= buffpek->key+offset;
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
980 981 982 983 984 985 986 987
      for (end= strpos+buffpek->mem_count*rec_length ;
           strpos != end ;
           strpos+= rec_length)
      {     
        if (my_b_write(to_file, (byte *) strpos, res_length))
        {
          error=1; goto err;                        
        }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
988 989 990
      }
    }
  }
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
991 992
  while ((error=(int) read_to_buffer(from_file,buffpek, rec_length))
         != -1 && error != 0);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
993 994

end:
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
995 996
  lastbuff->count= min(org_max_rows-max_rows, param->max_rows);
  lastbuff->file_pos= to_start_filepos;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
997 998 999 1000 1001 1002 1003 1004
err:
  delete_queue(&queue);
  DBUG_RETURN(error);
} /* merge_buffers */


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

1005
static int merge_index(SORTPARAM *param, uchar *sort_buffer,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
1006 1007 1008 1009
		       BUFFPEK *buffpek, uint maxbuffer,
		       IO_CACHE *tempfile, IO_CACHE *outfile)
{
  DBUG_ENTER("merge_index");
1010
  if (merge_buffers(param,tempfile,outfile,sort_buffer,buffpek,buffpek,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
1011 1012 1013 1014 1015 1016
		    buffpek+maxbuffer,1))
    DBUG_RETURN(1);				/* purecov: inspected */
  DBUG_RETURN(0);
} /* merge_index */


1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034
/*
  Calculate length of sort key

  SYNOPSIS
    sortlength()
    sortorder		Order of items to sort
    uint s_length	Number of items to sort
    multi_byte_charset  (out)
			Set to 1 if we are using multi-byte charset
			(In which case we have to use strxnfrm())

  NOTES
    sortorder->length is updated for each sort item
    sortorder->need_strxnfrm is set 1 if we have to use strxnfrm

  RETURN
    Total length of sort buffer in bytes
*/
bk@work.mysql.com's avatar
bk@work.mysql.com committed
1035 1036

static uint
1037
sortlength(SORT_FIELD *sortorder, uint s_length, bool *multi_byte_charset)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
1038 1039
{
  reg2 uint length;
1040
  THD *thd= current_thd;
1041
  CHARSET_INFO *cs;
1042
  *multi_byte_charset= 0;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
1043 1044 1045 1046

  length=0;
  for (; s_length-- ; sortorder++)
  {
1047
    sortorder->need_strxnfrm= 0;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
1048 1049 1050
    if (sortorder->field)
    {
      if (sortorder->field->type() == FIELD_TYPE_BLOB)
1051
	sortorder->length= thd->variables.max_sort_length;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
1052 1053 1054
      else
      {
	sortorder->length=sortorder->field->pack_length();
1055
	if (use_strnxfrm((cs=sortorder->field->charset())))
1056
	{
1057 1058 1059
	  sortorder->need_strxnfrm= 1;
	  *multi_byte_charset= 1;
	  sortorder->length= sortorder->length*cs->strxfrm_multiply;
1060
	}
bk@work.mysql.com's avatar
bk@work.mysql.com committed
1061 1062 1063 1064 1065 1066 1067 1068 1069
      }
      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;
1070
	if (use_strnxfrm((cs=sortorder->item->collation.collation)))
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
1071
	{ 
1072 1073 1074
	  sortorder->length= sortorder->length*cs->strxfrm_multiply;
	  sortorder->need_strxnfrm= 1;
	  *multi_byte_charset= 1;
1075
	}
bk@work.mysql.com's avatar
bk@work.mysql.com committed
1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086
	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;
1087
      case ROW_RESULT:
1088
      default: 
1089 1090
	// This case should never be choosen
	DBUG_ASSERT(0);
bell@sanja.is.com.ua's avatar
bell@sanja.is.com.ua committed
1091
	break;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
1092 1093 1094 1095
      }
      if (sortorder->item->maybe_null)
	length++;				// Place for NULL marker
    }
1096
    set_if_smaller(sortorder->length, thd->variables.max_sort_length);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
1097 1098 1099 1100 1101 1102 1103 1104
    length+=sortorder->length;
  }
  sortorder->field= (Field*) 0;			// end marker
  DBUG_PRINT("info",("sort_length: %d",length));
  return length;
}


igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158
/*
  Get descriptors of fields appended to sorted fields and
  calculate its total length

  SYNOPSIS
    get_addon_fields()
    thd                 Current thread
    ptabfields          Array of references to the table fields
    sortlength          Total length of sorted fields
    plength    out:     Total length of appended fields

  DESCRIPTION
    The function first finds out what fields are used in the result set.
    Then it calculates the length of the buffer to store the values of
    these fields together with the value of sort values. 
    If the calculated length is not greater than max_length_for_sort_data
    the function allocates memory for an array of descriptors containing
    layouts for the values of the non-sorted fields in the buffer and
    fills them.

  NOTES
    The null bits for the appended values are supposed to be put together
    and stored the buffer just ahead of the value of the first field.

  RETURN
    Pointer to the layout descriptors for the appended fields, if any
    NULL - if we do not store field values with sort data.
*/

static SORT_ADDON_FIELD *
get_addon_fields(THD *thd, Field **ptabfield, uint sortlength, uint *plength)
{
  Field **pfield;
  Field *field;
  SORT_ADDON_FIELD *addonf;
  uint length= 0;
  uint fields= 0;
  uint null_fields= 0;

  /* 
     If there is a reference to a field in the query add it
     to the the set of appended fields.
     Note for future refinement:
     This this a too strong condition.
     Actually we need only the fields referred in the
     result set. And for some of them it makes sense to use 
     the values directly from sorted fields.
  */
  *plength= 0;
  /*
     The following statement is added to avoid sorting in alter_table.
     The fact is the filter 'field->query_id != thd->query_id'
     doesn't work for alter table
  */
1159
  if (thd->lex->sql_command != SQLCOM_SELECT)
igor@hundin.mysql.fi's avatar
igor@hundin.mysql.fi committed
1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246
    return 0;
  for (pfield= ptabfield; (field= *pfield) ; pfield++)
  {
    if (field->query_id != thd->query_id)
      continue;
    if (field->flags & BLOB_FLAG)
      return 0;
    length+= field->max_packed_col_length(field->pack_length());
    if (field->maybe_null())
      null_fields++;
    fields++;
  } 
  if (!fields)
    return 0;
  length+= (null_fields+7)/8;

  if (length+sortlength > thd->variables.max_length_for_sort_data ||
      !(addonf= (SORT_ADDON_FIELD *) my_malloc(sizeof(SORT_ADDON_FIELD)*
                                               (fields+1), MYF(MY_WME))))
    return 0;

  *plength= length;
  length= (null_fields+7)/8;
  null_fields= 0;
  for (pfield= ptabfield; (field= *pfield) ; pfield++)
  {
    if (field->query_id != thd->query_id)
      continue;
    addonf->field= field;
    addonf->offset= length;
    if (field->maybe_null())
    {
      addonf->null_offset= null_fields/8;
      addonf->null_bit= 1<<(null_fields & 7);
      null_fields++;
    }
    else
    {
      addonf->null_offset= 0;
      addonf->null_bit= 0;
    }
    addonf->length= field->max_packed_col_length(field->pack_length());
    length+= addonf->length;
    addonf++;
  }
  addonf->field= 0;     // Put end marker
  
  DBUG_PRINT("info",("addon_length: %d",length));
  return (addonf-fields);
}


/*
  Copy (unpack) values appended to sorted fields from a buffer back to 
  their regular positions specified by the Field::ptr pointers.

  SYNOPSIS
    unpack_addon_fields()
    addon_field     Array of descriptors for appended fields
    buff            Buffer which to unpack the value from

  NOTES
    The function is supposed to be used only as a callback function
    when getting field values for the sorted result set.

  RETURN
    void.
*/

static void 
unpack_addon_fields(struct st_sort_addon_field *addon_field, byte *buff)
{
  Field *field;
  SORT_ADDON_FIELD *addonf= addon_field;

  for ( ; (field= addonf->field) ; addonf++)
  {
    if (addonf->null_bit && (addonf->null_bit & buff[addonf->null_offset]))
    {
      field->set_null();
      continue;
    }
    field->set_notnull();
    field->unpack(field->ptr, (char *) buff+addonf->offset);
  }
}

bk@work.mysql.com's avatar
bk@work.mysql.com committed
1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268
/*
** 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;
1269
#if defined(__FLOAT_WORD_ORDER) && (__FLOAT_WORD_ORDER == __BIG_ENDIAN)
1270 1271 1272
      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
1273 1274
      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];
1275
#endif
bk@work.mysql.com's avatar
bk@work.mysql.com committed
1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293
    }
#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;
    }
  }
}