← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/filesort.cc

  • Committer: Brian Aker
  • Date: 2008-10-06 06:47:29 UTC
  • Revision ID: brian@tangent.org-20081006064729-2i9mhjkzyvow9xsm
Remove uint.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/filesort.cc
1
 
/* Copyright (C) 2000-2006 MySQL AB
 
1
/* Copyright (C) 2000-2006 MySQL AB  
2
2
 
3
3
   This program is free software; you can redistribute it and/or modify
4
4
   it under the terms of the GNU General Public License as published by
22
22
*/
23
23
 
24
24
#include <drizzled/server_includes.h>
25
 
#include <drizzled/sql_sort.h>
26
 
#include <drizzled/error.h>
27
 
#include <drizzled/probes.h>
28
 
#include <drizzled/session.h>
29
 
#include <drizzled/table.h>
30
 
#include <drizzled/table_list.h>
31
 
 
32
 
#include <queue>
33
 
#include <algorithm>
34
 
 
35
 
using namespace std;
36
 
 
37
 
/* functions defined in this file */
 
25
#include "sql_sort.h"
 
26
#include <drizzled/drizzled_error_messages.h>
 
27
 
 
28
        /* functions defined in this file */
38
29
 
39
30
static char **make_char_array(char **old_pos, register uint32_t fields,
40
 
                              uint32_t length);
 
31
                              uint32_t length, myf my_flag);
41
32
static unsigned char *read_buffpek_from_file(IO_CACHE *buffer_file, uint32_t count,
42
33
                                     unsigned char *buf);
43
34
static ha_rows find_all_keys(SORTPARAM *param,SQL_SELECT *select,
51
42
                       BUFFPEK *buffpek,
52
43
                       uint32_t maxbuffer,IO_CACHE *tempfile,
53
44
                       IO_CACHE *outfile);
54
 
static bool save_index(SORTPARAM *param,unsigned char **sort_keys, uint32_t count,
 
45
static bool save_index(SORTPARAM *param,unsigned char **sort_keys, uint32_t count, 
55
46
                       filesort_info_st *table_sort);
56
47
static uint32_t suffix_length(uint32_t string_length);
57
 
static uint32_t sortlength(Session *session, SORT_FIELD *sortorder, uint32_t s_length,
 
48
static uint32_t sortlength(THD *thd, SORT_FIELD *sortorder, uint32_t s_length,
58
49
                       bool *multi_byte_charset);
59
 
static SORT_ADDON_FIELD *get_addon_fields(Session *session, Field **ptabfield,
 
50
static SORT_ADDON_FIELD *get_addon_fields(THD *thd, Field **ptabfield,
60
51
                                          uint32_t sortlength, uint32_t *plength);
61
52
static void unpack_addon_fields(struct st_sort_addon_field *addon_field,
62
53
                                unsigned char *buff);
72
63
  The result set is stored in table->io_cache or
73
64
  table->record_pointers.
74
65
 
75
 
  @param session           Current thread
 
66
  @param thd           Current thread
76
67
  @param table          Table to sort
77
68
  @param sortorder      How to sort the table
78
69
  @param s_length       Number of elements in sortorder
96
87
    examined_rows       will be set to number of examined rows
97
88
*/
98
89
 
99
 
ha_rows filesort(Session *session, Table *table, SORT_FIELD *sortorder, uint32_t s_length,
 
90
ha_rows filesort(THD *thd, Table *table, SORT_FIELD *sortorder, uint32_t s_length,
100
91
                 SQL_SELECT *select, ha_rows max_rows,
101
92
                 bool sort_positions, ha_rows *examined_rows)
102
93
{
106
97
  BUFFPEK *buffpek;
107
98
  ha_rows records= HA_POS_ERROR;
108
99
  unsigned char **sort_keys= 0;
109
 
  IO_CACHE tempfile, buffpek_pointers, *selected_records_file, *outfile;
 
100
  IO_CACHE tempfile, buffpek_pointers, *selected_records_file, *outfile; 
110
101
  SORTPARAM param;
111
102
  bool multi_byte_charset;
112
103
 
114
105
  TableList *tab= table->pos_in_table_list;
115
106
  Item_subselect *subselect= tab ? tab->containing_subselect() : 0;
116
107
 
117
 
  DRIZZLE_FILESORT_START(table->s->db.str, table->s->table_name.str);
 
108
  DRIZZLE_FILESORT_START();
118
109
 
119
110
  /*
120
111
   Release InnoDB's adaptive hash index latch (if holding) before
121
112
   running a sort.
122
113
  */
123
 
  ha_release_temporary_latches(session);
 
114
  ha_release_temporary_latches(thd);
124
115
 
125
 
  /*
126
 
    Don't use table->sort in filesort as it is also used by
127
 
    QUICK_INDEX_MERGE_SELECT. Work with a copy and put it back at the end
 
116
  /* 
 
117
    Don't use table->sort in filesort as it is also used by 
 
118
    QUICK_INDEX_MERGE_SELECT. Work with a copy and put it back at the end 
128
119
    when index_merge select has finished with it.
129
120
  */
130
121
  memcpy(&table_sort, &table->sort, sizeof(filesort_info_st));
131
122
  table->sort.io_cache= NULL;
132
 
 
 
123
  
133
124
  outfile= table_sort.io_cache;
134
125
  my_b_clear(&tempfile);
135
126
  my_b_clear(&buffpek_pointers);
136
127
  buffpek=0;
137
128
  error= 1;
138
129
  memset(&param, 0, sizeof(param));
139
 
  param.sort_length= sortlength(session, sortorder, s_length, &multi_byte_charset);
 
130
  param.sort_length= sortlength(thd, sortorder, s_length, &multi_byte_charset);
140
131
  param.ref_length= table->file->ref_length;
141
132
  param.addon_field= 0;
142
133
  param.addon_length= 0;
143
134
  if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) && !sort_positions)
144
135
  {
145
 
    /*
146
 
      Get the descriptors of all fields whose values are appended
 
136
    /* 
 
137
      Get the descriptors of all fields whose values are appended 
147
138
      to sorted fields and get its total length in param.spack_length.
148
139
    */
149
 
    param.addon_field= get_addon_fields(session, table->field,
 
140
    param.addon_field= get_addon_fields(thd, table->field, 
150
141
                                        param.sort_length,
151
142
                                        &param.addon_length);
152
143
  }
158
149
  if (param.addon_field)
159
150
  {
160
151
    param.res_length= param.addon_length;
161
 
    if (!(table_sort.addon_buf= (unsigned char *) malloc(param.addon_length)))
 
152
    if (!(table_sort.addon_buf= (unsigned char *) my_malloc(param.addon_length,
 
153
                                                    MYF(MY_WME))))
162
154
      goto err;
163
155
  }
164
156
  else
165
157
  {
166
158
    param.res_length= param.ref_length;
167
 
    /*
168
 
      The reference to the record is considered
 
159
    /* 
 
160
      The reference to the record is considered 
169
161
      as an additional sorted field
170
162
    */
171
163
    param.sort_length+= param.ref_length;
175
167
 
176
168
  if (select && select->quick)
177
169
  {
178
 
    status_var_increment(session->status_var.filesort_range_count);
 
170
    status_var_increment(thd->status_var.filesort_range_count);
179
171
  }
180
172
  else
181
173
  {
182
 
    status_var_increment(session->status_var.filesort_scan_count);
 
174
    status_var_increment(thd->status_var.filesort_scan_count);
183
175
  }
184
176
#ifdef CAN_TRUST_RANGE
185
177
  if (select && select->quick && select->quick->records > 0L)
186
178
  {
187
 
    records= min((ha_rows) (select->quick->records*2+EXTRA_RECORDS*2),
188
 
                 table->file->stats.records)+EXTRA_RECORDS;
 
179
    records=cmin((ha_rows) (select->quick->records*2+EXTRA_RECORDS*2),
 
180
                table->file->stats.records)+EXTRA_RECORDS;
189
181
    selected_records_file=0;
190
182
  }
191
183
  else
193
185
  {
194
186
    records= table->file->estimate_rows_upper_bound();
195
187
    /*
196
 
      If number of records is not known, use as much of sort buffer
197
 
      as possible.
 
188
      If number of records is not known, use as much of sort buffer 
 
189
      as possible. 
198
190
    */
199
191
    if (records == HA_POS_ERROR)
200
192
      records--;  // we use 'records+1' below.
202
194
  }
203
195
 
204
196
  if (multi_byte_charset &&
205
 
      !(param.tmp_buffer= (char*) malloc(param.sort_length)))
 
197
      !(param.tmp_buffer= (char*) my_malloc(param.sort_length,MYF(MY_WME))))
206
198
    goto err;
207
199
 
208
 
  memavl= session->variables.sortbuff_size;
209
 
  min_sort_memory= max((uint32_t)MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2);
 
200
  memavl= thd->variables.sortbuff_size;
 
201
  min_sort_memory= cmax((uint32_t)MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2);
210
202
  while (memavl >= min_sort_memory)
211
203
  {
212
204
    uint32_t old_memavl;
213
205
    uint32_t keys= memavl/(param.rec_length+sizeof(char*));
214
 
    param.keys= (uint32_t) min(records+1, (ha_rows)keys);
 
206
    param.keys=(uint32_t) cmin(records+1, keys);
215
207
    if ((table_sort.sort_keys=
216
208
         (unsigned char **) make_char_array((char **) table_sort.sort_keys,
217
 
                                            param.keys, param.rec_length)))
 
209
                                    param.keys, param.rec_length, MYF(0))))
218
210
      break;
219
 
    old_memavl= memavl;
220
 
    if ((memavl= memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
 
211
    old_memavl=memavl;
 
212
    if ((memavl=memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
221
213
      memavl= min_sort_memory;
222
214
  }
223
215
  sort_keys= table_sort.sort_keys;
226
218
    my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR+ME_WAITTANG));
227
219
    goto err;
228
220
  }
229
 
  if (open_cached_file(&buffpek_pointers,drizzle_tmpdir,TEMP_PREFIX,
 
221
  if (open_cached_file(&buffpek_pointers,mysql_tmpdir,TEMP_PREFIX,
230
222
                       DISK_BUFFER_SIZE, MYF(MY_WME)))
231
223
    goto err;
232
224
 
261
253
    close_cached_file(&buffpek_pointers);
262
254
        /* Open cached file if it isn't open */
263
255
    if (! my_b_inited(outfile) &&
264
 
        open_cached_file(outfile,drizzle_tmpdir,TEMP_PREFIX,READ_RECORD_BUFFER,
 
256
        open_cached_file(outfile,mysql_tmpdir,TEMP_PREFIX,READ_RECORD_BUFFER,
265
257
                          MYF(MY_WME)))
266
258
      goto err;
267
259
    if (reinit_io_cache(outfile,WRITE_CACHE,0L,0,0))
320
312
    my_message(ER_FILSORT_ABORT, ER(ER_FILSORT_ABORT),
321
313
               MYF(ME_ERROR+ME_WAITTANG));
322
314
  else
323
 
    statistic_add(session->status_var.filesort_rows,
 
315
    statistic_add(thd->status_var.filesort_rows,
324
316
                  (uint32_t) records, &LOCK_status);
325
317
  *examined_rows= param.examined_rows;
326
318
  memcpy(&table->sort, &table_sort, sizeof(filesort_info_st));
327
 
  DRIZZLE_FILESORT_DONE(error, records);
328
 
  return (error ? HA_POS_ERROR : records);
 
319
  DRIZZLE_FILESORT_END();
 
320
  return(error ? HA_POS_ERROR : records);
329
321
} /* filesort */
330
322
 
331
323
 
332
 
void Table::filesort_free_buffers(bool full)
 
324
void filesort_free_buffers(Table *table, bool full)
333
325
{
334
 
  if (sort.record_pointers)
 
326
  if (table->sort.record_pointers)
335
327
  {
336
 
    free((unsigned char*) sort.record_pointers);
337
 
    sort.record_pointers=0;
 
328
    free((unsigned char*) table->sort.record_pointers);
 
329
    table->sort.record_pointers=0;
338
330
  }
339
331
  if (full)
340
332
  {
341
 
    if (sort.sort_keys )
 
333
    if (table->sort.sort_keys )
342
334
    {
343
 
      if ((unsigned char*) sort.sort_keys)
344
 
        free((unsigned char*) sort.sort_keys);
345
 
      sort.sort_keys= 0;
 
335
      if ((unsigned char*) table->sort.sort_keys)
 
336
        free((unsigned char*) table->sort.sort_keys);
 
337
      table->sort.sort_keys= 0;
346
338
    }
347
 
    if (sort.buffpek)
 
339
    if (table->sort.buffpek)
348
340
    {
349
 
      if ((unsigned char*) sort.buffpek)
350
 
        free((unsigned char*) sort.buffpek);
351
 
      sort.buffpek= 0;
352
 
      sort.buffpek_len= 0;
 
341
      if ((unsigned char*) table->sort.buffpek)
 
342
        free((unsigned char*) table->sort.buffpek);
 
343
      table->sort.buffpek= 0;
 
344
      table->sort.buffpek_len= 0;
353
345
    }
354
346
  }
355
 
  if (sort.addon_buf)
 
347
  if (table->sort.addon_buf)
356
348
  {
357
 
    free((char *) sort.addon_buf);
358
 
    free((char *) sort.addon_field);
359
 
    sort.addon_buf=0;
360
 
    sort.addon_field=0;
 
349
    free((char *) table->sort.addon_buf);
 
350
    free((char *) table->sort.addon_field);
 
351
    table->sort.addon_buf=0;
 
352
    table->sort.addon_field=0;
361
353
  }
362
354
}
363
355
 
364
356
/** Make a array of string pointers. */
365
357
 
366
358
static char **make_char_array(char **old_pos, register uint32_t fields,
367
 
                              uint32_t length)
 
359
                              uint32_t length, myf my_flag)
368
360
{
369
361
  register char **pos;
370
362
  char *char_pos;
371
363
 
372
364
  if (old_pos ||
373
 
      (old_pos= (char**) malloc((uint32_t) fields*(length+sizeof(char*)))))
 
365
      (old_pos= (char**) my_malloc((uint32_t) fields*(length+sizeof(char*)),
 
366
                                   my_flag)))
374
367
  {
375
368
    pos=old_pos; char_pos=((char*) (pos+fields)) -length;
376
369
    while (fields--) *(pos++) = (char_pos+= length);
390
383
  if (count > UINT_MAX/sizeof(BUFFPEK))
391
384
    return 0; /* sizeof(BUFFPEK)*count will overflow */
392
385
  if (!tmp)
393
 
    tmp= (unsigned char *)malloc(length);
 
386
    tmp= (unsigned char *)my_malloc(length, MYF(MY_WME));
394
387
  if (tmp)
395
388
  {
396
389
    if (reinit_io_cache(buffpek_pointers,READ_CACHE,0L,0,0) ||
451
444
  unsigned char *ref_pos,*next_pos,ref_buff[MAX_REFLENGTH];
452
445
  my_off_t record;
453
446
  Table *sort_form;
454
 
  Session *session= current_session;
455
 
  volatile Session::killed_state *killed= &session->killed;
 
447
  THD *thd= current_thd;
 
448
  volatile THD::killed_state *killed= &thd->killed;
456
449
  handler *file;
457
 
  MyBitmap *save_read_set, *save_write_set;
 
450
  MY_BITMAP *save_read_set, *save_write_set;
458
451
 
459
452
  idx=indexpos=0;
460
453
  error=quick_select=0;
474
467
    next_pos=(unsigned char*) 0;                        /* Find records in sequence */
475
468
    file->ha_rnd_init(1);
476
469
    file->extra_opt(HA_EXTRA_CACHE,
477
 
                    current_session->variables.read_buff_size);
 
470
                    current_thd->variables.read_buff_size);
478
471
  }
479
472
 
480
473
  READ_RECORD read_record_info;
482
475
  {
483
476
    if (select->quick->reset())
484
477
      return(HA_POS_ERROR);
485
 
    init_read_record(&read_record_info, current_session, select->quick->head,
 
478
    init_read_record(&read_record_info, current_thd, select->quick->head,
486
479
                     select, 1, 1);
487
480
  }
488
481
 
490
483
  save_read_set=  sort_form->read_set;
491
484
  save_write_set= sort_form->write_set;
492
485
  /* Set up temporary column read map for columns used by sort */
493
 
  sort_form->tmp_set.clearAll();
 
486
  bitmap_clear_all(&sort_form->tmp_set);
494
487
  /* Temporary set for register_used_fields and register_field_in_read_map */
495
488
  sort_form->read_set= &sort_form->tmp_set;
496
489
  register_used_fields(param);
514
507
    {
515
508
      if (indexfile)
516
509
      {
517
 
        if (my_b_read(indexfile,(unsigned char*) ref_pos,ref_length))
 
510
        if (my_b_read(indexfile,(unsigned char*) ref_pos,ref_length)) /* purecov: deadcode */
518
511
        {
519
512
          error= my_errno ? my_errno : -1;              /* Abort */
520
513
          break;
524
517
      else
525
518
      {
526
519
        error=file->rnd_next(sort_form->record[0]);
527
 
 
528
520
        if (!flag)
529
521
        {
530
522
          my_store_ptr(ref_pos,ref_length,record); // Position to row
544
536
        (void) file->extra(HA_EXTRA_NO_CACHE);
545
537
        file->ha_rnd_end();
546
538
      }
547
 
      return(HA_POS_ERROR);
 
539
      return(HA_POS_ERROR);             /* purecov: inspected */
548
540
    }
549
541
    if (error == 0)
550
542
      param->examined_rows++;
562
554
    else
563
555
      file->unlock_row();
564
556
    /* It does not make sense to read more keys in case of a fatal error */
565
 
    if (session->is_error())
 
557
    if (thd->is_error())
566
558
      break;
567
559
  }
568
560
  if (quick_select)
580
572
      file->ha_rnd_end();
581
573
  }
582
574
 
583
 
  if (session->is_error())
 
575
  if (thd->is_error())
584
576
    return(HA_POS_ERROR);
585
 
 
 
577
  
586
578
  /* Signal we should use orignal column read and write maps */
587
579
  sort_form->column_bitmaps_set(save_read_set, save_write_set);
588
580
 
589
581
  if (error != HA_ERR_END_OF_FILE)
590
582
  {
591
 
    file->print_error(error,MYF(ME_ERROR | ME_WAITTANG));
592
 
    return(HA_POS_ERROR);
 
583
    file->print_error(error,MYF(ME_ERROR | ME_WAITTANG)); /* purecov: inspected */
 
584
    return(HA_POS_ERROR);                       /* purecov: inspected */
593
585
  }
594
586
  if (indexpos && idx &&
595
587
      write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
596
 
    return(HA_POS_ERROR);
 
588
    return(HA_POS_ERROR);                       /* purecov: inspected */
597
589
  return(my_b_inited(tempfile) ?
598
590
              (ha_rows) (my_b_tell(tempfile)/param->rec_length) :
599
591
              idx);
634
626
  rec_length= param->rec_length;
635
627
  my_string_ptr_sort((unsigned char*) sort_keys, (uint32_t) count, sort_length);
636
628
  if (!my_b_inited(tempfile) &&
637
 
      open_cached_file(tempfile, drizzle_tmpdir, TEMP_PREFIX, DISK_BUFFER_SIZE,
 
629
      open_cached_file(tempfile, mysql_tmpdir, TEMP_PREFIX, DISK_BUFFER_SIZE,
638
630
                       MYF(MY_WME)))
639
 
    goto err;
 
631
    goto err;                                   /* purecov: inspected */
640
632
  /* check we won't have more buffpeks than we can possibly keep in memory */
641
633
  if (my_b_tell(buffpek_pointers) + sizeof(BUFFPEK) > (uint64_t)UINT_MAX)
642
634
    goto err;
643
635
  buffpek.file_pos= my_b_tell(tempfile);
644
636
  if ((ha_rows) count > param->max_rows)
645
 
    count=(uint32_t) param->max_rows;
 
637
    count=(uint32_t) param->max_rows;               /* purecov: inspected */
646
638
  buffpek.count=(ha_rows) count;
647
639
  for (end=sort_keys+count ; sort_keys != end ; sort_keys++)
648
640
    if (my_b_write(tempfile, (unsigned char*) *sort_keys, (uint32_t) rec_length))
686
678
{
687
679
  register Field *field;
688
680
  register SORT_FIELD *sort_field;
689
 
  size_t length;
 
681
  register uint32_t length;
690
682
 
691
683
  for (sort_field=param->local_sortorder ;
692
684
       sort_field != param->end ;
734
726
            memset(to-1, 0, sort_field->length+1);
735
727
          else
736
728
          {
 
729
            /* purecov: begin deadcode */
737
730
            /*
738
731
              This should only happen during extreme conditions if we run out
739
732
              of memory or have an item marked not null when it can be null.
741
734
            */
742
735
            assert(0);
743
736
            memset(to, 0, sort_field->length);  // Avoid crash
 
737
            /* purecov: end */
744
738
          }
745
739
          break;
746
740
        }
784
778
          int64_t value= item->val_int_result();
785
779
          if (maybe_null)
786
780
          {
787
 
            *to++=1;
 
781
            *to++=1;                            /* purecov: inspected */
788
782
            if (item->null_value)
789
783
            {
790
784
              if (maybe_null)
796
790
              break;
797
791
            }
798
792
          }
 
793
#if SIZEOF_LONG_LONG > 4
799
794
          to[7]= (unsigned char) value;
800
795
          to[6]= (unsigned char) (value >> 8);
801
796
          to[5]= (unsigned char) (value >> 16);
807
802
            to[0]= (unsigned char) (value >> 56);
808
803
          else
809
804
            to[0]= (unsigned char) (value >> 56) ^ 128; /* Reverse signbit */
 
805
#else
 
806
          to[3]= (unsigned char) value;
 
807
          to[2]= (unsigned char) (value >> 8);
 
808
          to[1]= (unsigned char) (value >> 16);
 
809
          if (item->unsigned_flag)                    /* Fix sign */
 
810
            to[0]= (unsigned char) (value >> 24);
 
811
          else
 
812
            to[0]= (unsigned char) (value >> 24) ^ 128; /* Reverse signbit */
 
813
#endif
810
814
          break;
811
815
        }
812
816
      case DECIMAL_RESULT:
815
819
          if (maybe_null)
816
820
          {
817
821
            if (item->null_value)
818
 
            {
 
822
            { 
819
823
              memset(to, 0, sort_field->length+1);
820
824
              to++;
821
825
              break;
844
848
          break;
845
849
        }
846
850
      case ROW_RESULT:
847
 
      default:
 
851
      default: 
848
852
        // This case should never be choosen
849
853
        assert(0);
850
854
        break;
867
871
 
868
872
  if (param->addon_field)
869
873
  {
870
 
    /*
 
874
    /* 
871
875
      Save field values appended to sorted fields.
872
876
      First null bit indicators are appended then field values follow.
873
877
      In this implementation we use fixed layout for field values -
919
923
{
920
924
  register SORT_FIELD *sort_field;
921
925
  Table *table=param->sort_form;
 
926
  MY_BITMAP *bitmap= table->read_set;
922
927
 
923
928
  for (sort_field= param->local_sortorder ;
924
929
       sort_field != param->end ;
928
933
    if ((field= sort_field->field))
929
934
    {
930
935
      if (field->table == table)
931
 
        table->setReadSet(field->field_index);
 
936
      bitmap_set_bit(bitmap, field->field_index);
932
937
    }
933
938
    else
934
939
    {                                           // Item
942
947
    SORT_ADDON_FIELD *addonf= param->addon_field;
943
948
    Field *field;
944
949
    for ( ; (field= addonf->field) ; addonf++)
945
 
      table->setReadSet(field->field_index);
 
950
      bitmap_set_bit(bitmap, field->field_index);
946
951
  }
947
952
  else
948
953
  {
952
957
}
953
958
 
954
959
 
955
 
static bool save_index(SORTPARAM *param, unsigned char **sort_keys, uint32_t count,
 
960
static bool save_index(SORTPARAM *param, unsigned char **sort_keys, uint32_t count, 
956
961
                       filesort_info_st *table_sort)
957
962
{
958
963
  uint32_t offset,res_length;
963
968
  offset= param->rec_length-res_length;
964
969
  if ((ha_rows) count > param->max_rows)
965
970
    count=(uint32_t) param->max_rows;
966
 
  if (!(to= table_sort->record_pointers=
967
 
        (unsigned char*) malloc(res_length*count)))
968
 
    return(1);
 
971
  if (!(to= table_sort->record_pointers= 
 
972
        (unsigned char*) my_malloc(res_length*count, MYF(MY_WME))))
 
973
    return(1);                 /* purecov: inspected */
969
974
  for (unsigned char **end= sort_keys+count ; sort_keys != end ; sort_keys++)
970
975
  {
971
976
    memcpy(to, *sort_keys+offset, res_length);
985
990
  BUFFPEK *lastbuff;
986
991
 
987
992
  if (*maxbuffer < MERGEBUFF2)
988
 
    return(0);
 
993
    return(0);                          /* purecov: inspected */
989
994
  if (flush_io_cache(t_file) ||
990
 
      open_cached_file(&t_file2,drizzle_tmpdir,TEMP_PREFIX,DISK_BUFFER_SIZE,
 
995
      open_cached_file(&t_file2,mysql_tmpdir,TEMP_PREFIX,DISK_BUFFER_SIZE,
991
996
                        MYF(MY_WME)))
992
 
    return(1);
 
997
    return(1);                          /* purecov: inspected */
993
998
 
994
999
  from_file= t_file ; to_file= &t_file2;
995
1000
  while (*maxbuffer >= MERGEBUFF2)
1007
1012
    }
1008
1013
    if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
1009
1014
                      buffpek+i,buffpek+ *maxbuffer,0))
1010
 
      break;
 
1015
      break;                                    /* purecov: inspected */
1011
1016
    if (flush_io_cache(to_file))
1012
 
      break;
 
1017
      break;                                    /* purecov: inspected */
1013
1018
    temp=from_file; from_file=to_file; to_file=temp;
1014
1019
    setup_io_cache(from_file);
1015
1020
    setup_io_cache(to_file);
1035
1040
*/
1036
1041
 
1037
1042
uint32_t read_to_buffer(IO_CACHE *fromfile, BUFFPEK *buffpek,
1038
 
                        uint32_t rec_length)
 
1043
                    uint32_t rec_length)
1039
1044
{
1040
1045
  register uint32_t count;
1041
1046
  uint32_t length;
1042
1047
 
1043
 
  if ((count= (uint32_t) min((ha_rows) buffpek->max_keys,buffpek->count)))
 
1048
  if ((count=(uint32_t) cmin((ha_rows) buffpek->max_keys,buffpek->count)))
1044
1049
  {
1045
1050
    if (pread(fromfile->file,(unsigned char*) buffpek->base, (length= rec_length*count),buffpek->file_pos) == 0)
1046
 
      return((uint32_t) -1);
1047
 
 
1048
 
    buffpek->key= buffpek->base;
 
1051
      return((uint32_t) -1);                    /* purecov: inspected */
 
1052
    buffpek->key=buffpek->base;
1049
1053
    buffpek->file_pos+= length;                 /* New filepos */
1050
 
    buffpek->count-= count;
 
1054
    buffpek->count-=    count;
1051
1055
    buffpek->mem_count= count;
1052
1056
  }
1053
1057
  return (count*rec_length);
1054
1058
} /* read_to_buffer */
1055
1059
 
1056
1060
 
1057
 
class compare_functor
 
1061
/**
 
1062
  Put all room used by freed buffer to use in adjacent buffer.
 
1063
 
 
1064
  Note, that we can't simply distribute memory evenly between all buffers,
 
1065
  because new areas must not overlap with old ones.
 
1066
 
 
1067
  @param[in] queue      list of non-empty buffers, without freed buffer
 
1068
  @param[in] reuse      empty buffer
 
1069
  @param[in] key_length key length
 
1070
*/
 
1071
 
 
1072
void reuse_freed_buff(QUEUE *queue, BUFFPEK *reuse, uint32_t key_length)
1058
1073
{
1059
 
  qsort2_cmp key_compare;
1060
 
  void *key_compare_arg;
1061
 
  public:
1062
 
  compare_functor(qsort2_cmp in_key_compare, void *in_compare_arg)
1063
 
    : key_compare(in_key_compare), key_compare_arg(in_compare_arg) { }
1064
 
  inline bool operator()(const BUFFPEK *i, const BUFFPEK *j) const
 
1074
  unsigned char *reuse_end= reuse->base + reuse->max_keys * key_length;
 
1075
  for (uint32_t i= 0; i < queue->elements; ++i)
1065
1076
  {
1066
 
    int val= key_compare(key_compare_arg,
1067
 
                      &i->key, &j->key);
1068
 
    return (val >= 0);
 
1077
    BUFFPEK *bp= (BUFFPEK *) queue_element(queue, i);
 
1078
    if (bp->base + bp->max_keys * key_length == reuse->base)
 
1079
    {
 
1080
      bp->max_keys+= reuse->max_keys;
 
1081
      return;
 
1082
    }
 
1083
    else if (bp->base == reuse_end)
 
1084
    {
 
1085
      bp->base= reuse->base;
 
1086
      bp->max_keys+= reuse->max_keys;
 
1087
      return;
 
1088
    }
1069
1089
  }
1070
 
};
 
1090
  assert(0);
 
1091
}
1071
1092
 
1072
1093
 
1073
1094
/**
1101
1122
  my_off_t to_start_filepos;
1102
1123
  unsigned char *strpos;
1103
1124
  BUFFPEK *buffpek;
 
1125
  QUEUE queue;
1104
1126
  qsort2_cmp cmp;
1105
1127
  void *first_cmp_arg;
1106
 
  volatile Session::killed_state *killed= &current_session->killed;
1107
 
  Session::killed_state not_killable;
 
1128
  volatile THD::killed_state *killed= &current_thd->killed;
 
1129
  THD::killed_state not_killable;
1108
1130
 
1109
 
  status_var_increment(current_session->status_var.filesort_merge_passes);
 
1131
  status_var_increment(current_thd->status_var.filesort_merge_passes);
1110
1132
  if (param->not_killable)
1111
1133
  {
1112
1134
    killed= &not_killable;
1113
 
    not_killable= Session::NOT_KILLED;
 
1135
    not_killable= THD::NOT_KILLED;
1114
1136
  }
1115
1137
 
1116
1138
  error=0;
1125
1147
 
1126
1148
  /* The following will fire if there is not enough space in sort_buffer */
1127
1149
  assert(maxcount!=0);
1128
 
 
 
1150
  
1129
1151
  if (param->unique_buff)
1130
1152
  {
1131
1153
    cmp= param->compare;
1136
1158
    cmp= get_ptr_compare(sort_length);
1137
1159
    first_cmp_arg= (void*) &sort_length;
1138
1160
  }
1139
 
  priority_queue<BUFFPEK *, vector<BUFFPEK *>, compare_functor > 
1140
 
    queue(compare_functor(cmp, first_cmp_arg));
 
1161
  if (init_queue(&queue, (uint32_t) (Tb-Fb)+1, offsetof(BUFFPEK,key), 0,
 
1162
                 (queue_compare) cmp, first_cmp_arg))
 
1163
    return(1);                                /* purecov: inspected */
1141
1164
  for (buffpek= Fb ; buffpek <= Tb ; buffpek++)
1142
1165
  {
1143
1166
    buffpek->base= strpos;
1145
1168
    strpos+= (uint32_t) (error= (int) read_to_buffer(from_file, buffpek,
1146
1169
                                                                         rec_length));
1147
1170
    if (error == -1)
1148
 
      goto err;
 
1171
      goto err;                                 /* purecov: inspected */
1149
1172
    buffpek->max_keys= buffpek->mem_count;      // If less data in buffers than expected
1150
 
    queue.push(buffpek);
 
1173
    queue_insert(&queue, (unsigned char*) buffpek);
1151
1174
  }
1152
1175
 
1153
1176
  if (param->unique_buff)
1154
1177
  {
1155
 
    /*
 
1178
    /* 
1156
1179
       Called by Unique::get()
1157
1180
       Copy the first argument to param->unique_buff for unique removal.
1158
1181
       Store it also in 'to_file'.
1160
1183
       This is safe as we know that there is always more than one element
1161
1184
       in each block to merge (This is guaranteed by the Unique:: algorithm
1162
1185
    */
1163
 
    buffpek= queue.top();
 
1186
    buffpek= (BUFFPEK*) queue_top(&queue);
1164
1187
    memcpy(param->unique_buff, buffpek->key, rec_length);
1165
1188
    if (my_b_write(to_file, (unsigned char*) buffpek->key, rec_length))
1166
1189
    {
1167
 
      error=1; goto err;
 
1190
      error=1; goto err;                        /* purecov: inspected */
1168
1191
    }
1169
1192
    buffpek->key+= rec_length;
1170
1193
    buffpek->mem_count--;
1171
1194
    if (!--max_rows)
1172
1195
    {
1173
 
      error= 0;
1174
 
      goto end;
 
1196
      error= 0;                                       /* purecov: inspected */
 
1197
      goto end;                                       /* purecov: inspected */
1175
1198
    }
1176
 
    /* Top element has been used */
1177
 
    queue.pop();
1178
 
    queue.push(buffpek);
 
1199
    queue_replaced(&queue);                        // Top element has been used
1179
1200
  }
1180
1201
  else
1181
1202
    cmp= 0;                                        // Not unique
1182
1203
 
1183
 
  while (queue.size() > 1)
 
1204
  while (queue.elements > 1)
1184
1205
  {
1185
1206
    if (*killed)
1186
1207
    {
1187
 
      error= 1; goto err;
 
1208
      error= 1; goto err;                        /* purecov: inspected */
1188
1209
    }
1189
1210
    for (;;)
1190
1211
    {
1191
 
      buffpek= queue.top();
 
1212
      buffpek= (BUFFPEK*) queue_top(&queue);
1192
1213
      if (cmp)                                        // Remove duplicates
1193
1214
      {
1194
1215
        if (!(*cmp)(first_cmp_arg, &(param->unique_buff),
1200
1221
      {
1201
1222
        if (my_b_write(to_file,(unsigned char*) buffpek->key, rec_length))
1202
1223
        {
1203
 
          error=1; goto err;
 
1224
          error=1; goto err;                        /* purecov: inspected */
1204
1225
        }
1205
1226
      }
1206
1227
      else
1207
1228
      {
1208
1229
        if (my_b_write(to_file, (unsigned char*) buffpek->key+offset, res_length))
1209
1230
        {
1210
 
          error=1; goto err;
 
1231
          error=1; goto err;                        /* purecov: inspected */
1211
1232
        }
1212
1233
      }
1213
1234
      if (!--max_rows)
1214
1235
      {
1215
 
        error= 0;
1216
 
        goto end;
 
1236
        error= 0;                               /* purecov: inspected */
 
1237
        goto end;                               /* purecov: inspected */
1217
1238
      }
1218
1239
 
1219
1240
    skip_duplicate:
1223
1244
        if (!(error= (int) read_to_buffer(from_file,buffpek,
1224
1245
                                          rec_length)))
1225
1246
        {
1226
 
          queue.pop();
 
1247
          queue_remove(&queue,0);
 
1248
          reuse_freed_buff(&queue, buffpek, rec_length);
1227
1249
          break;                        /* One buffer have been removed */
1228
1250
        }
1229
1251
        else if (error == -1)
1230
 
          goto err;
 
1252
          goto err;                        /* purecov: inspected */
1231
1253
      }
1232
 
      /* Top element has been replaced */
1233
 
      queue.pop();
1234
 
      queue.push(buffpek);
 
1254
      queue_replaced(&queue);              /* Top element has been replaced */
1235
1255
    }
1236
1256
  }
1237
 
  buffpek= queue.top();
 
1257
  buffpek= (BUFFPEK*) queue_top(&queue);
1238
1258
  buffpek->base= sort_buffer;
1239
1259
  buffpek->max_keys= param->keys;
1240
1260
 
1264
1284
      if (my_b_write(to_file,(unsigned char*) buffpek->key,
1265
1285
                     (rec_length*buffpek->mem_count)))
1266
1286
      {
1267
 
        error= 1; goto err;
 
1287
        error= 1; goto err;                        /* purecov: inspected */
1268
1288
      }
1269
1289
    }
1270
1290
    else
1274
1294
      for (end= strpos+buffpek->mem_count*rec_length ;
1275
1295
           strpos != end ;
1276
1296
           strpos+= rec_length)
1277
 
      {
 
1297
      {     
1278
1298
        if (my_b_write(to_file, (unsigned char *) strpos, res_length))
1279
1299
        {
1280
 
          error=1; goto err;
 
1300
          error=1; goto err;                        
1281
1301
        }
1282
1302
      }
1283
1303
    }
1286
1306
         != -1 && error != 0);
1287
1307
 
1288
1308
end:
1289
 
  lastbuff->count= min(org_max_rows-max_rows, param->max_rows);
 
1309
  lastbuff->count= cmin(org_max_rows-max_rows, param->max_rows);
1290
1310
  lastbuff->file_pos= to_start_filepos;
1291
1311
err:
 
1312
  delete_queue(&queue);
1292
1313
  return(error);
1293
1314
} /* merge_buffers */
1294
1315
 
1301
1322
{
1302
1323
  if (merge_buffers(param,tempfile,outfile,sort_buffer,buffpek,buffpek,
1303
1324
                    buffpek+maxbuffer,1))
1304
 
    return(1);
 
1325
    return(1);                          /* purecov: inspected */
1305
1326
  return(0);
1306
1327
} /* merge_index */
1307
1328
 
1322
1343
/**
1323
1344
  Calculate length of sort key.
1324
1345
 
1325
 
  @param session                          Thread handler
 
1346
  @param thd                      Thread handler
1326
1347
  @param sortorder                Order of items to sort
1327
1348
  @param s_length                 Number of items to sort
1328
1349
  @param[out] multi_byte_charset Set to 1 if we are using multi-byte charset
1338
1359
*/
1339
1360
 
1340
1361
static uint32_t
1341
 
sortlength(Session *session, SORT_FIELD *sortorder, uint32_t s_length,
 
1362
sortlength(THD *thd, SORT_FIELD *sortorder, uint32_t s_length,
1342
1363
           bool *multi_byte_charset)
1343
1364
{
1344
1365
  register uint32_t length;
1372
1393
      switch (sortorder->result_type) {
1373
1394
      case STRING_RESULT:
1374
1395
        sortorder->length=sortorder->item->max_length;
1375
 
        set_if_smaller(sortorder->length,
1376
 
                       session->variables.max_sort_length);
 
1396
        set_if_smaller(sortorder->length, thd->variables.max_sort_length);
1377
1397
        if (use_strnxfrm((cs=sortorder->item->collation.collation)))
1378
 
        {
 
1398
        { 
1379
1399
          sortorder->length= cs->coll->strnxfrmlen(cs, sortorder->length);
1380
1400
          sortorder->need_strxnfrm= 1;
1381
1401
          *multi_byte_charset= 1;
1388
1408
        }
1389
1409
        break;
1390
1410
      case INT_RESULT:
 
1411
#if SIZEOF_LONG_LONG > 4
1391
1412
        sortorder->length=8;                    // Size of intern int64_t
 
1413
#else
 
1414
        sortorder->length=4;
 
1415
#endif
1392
1416
        break;
1393
1417
      case DECIMAL_RESULT:
1394
1418
        sortorder->length=
1395
 
          my_decimal_get_binary_size(sortorder->item->max_length -
 
1419
          my_decimal_get_binary_size(sortorder->item->max_length - 
1396
1420
                                     (sortorder->item->decimals ? 1 : 0),
1397
1421
                                     sortorder->item->decimals);
1398
1422
        break;
1400
1424
        sortorder->length=sizeof(double);
1401
1425
        break;
1402
1426
      case ROW_RESULT:
1403
 
      default:
 
1427
      default: 
1404
1428
        // This case should never be choosen
1405
1429
        assert(0);
1406
1430
        break;
1408
1432
      if (sortorder->item->maybe_null)
1409
1433
        length++;                               // Place for NULL marker
1410
1434
    }
1411
 
    set_if_smaller(sortorder->length,
1412
 
                   (size_t)session->variables.max_sort_length);
 
1435
    set_if_smaller(sortorder->length, thd->variables.max_sort_length);
1413
1436
    length+=sortorder->length;
1414
1437
  }
1415
1438
  sortorder->field= (Field*) 0;                 // end marker
1423
1446
 
1424
1447
  The function first finds out what fields are used in the result set.
1425
1448
  Then it calculates the length of the buffer to store the values of
1426
 
  these fields together with the value of sort values.
 
1449
  these fields together with the value of sort values. 
1427
1450
  If the calculated length is not greater than max_length_for_sort_data
1428
1451
  the function allocates memory for an array of descriptors containing
1429
1452
  layouts for the values of the non-sorted fields in the buffer and
1430
1453
  fills them.
1431
1454
 
1432
 
  @param session                 Current thread
 
1455
  @param thd                 Current thread
1433
1456
  @param ptabfield           Array of references to the table fields
1434
1457
  @param sortlength          Total length of sorted fields
1435
1458
  @param[out] plength        Total length of appended fields
1445
1468
*/
1446
1469
 
1447
1470
static SORT_ADDON_FIELD *
1448
 
get_addon_fields(Session *session, Field **ptabfield, uint32_t sortlength, uint32_t *plength)
 
1471
get_addon_fields(THD *thd, Field **ptabfield, uint32_t sortlength, uint32_t *plength)
1449
1472
{
1450
1473
  Field **pfield;
1451
1474
  Field *field;
1453
1476
  uint32_t length= 0;
1454
1477
  uint32_t fields= 0;
1455
1478
  uint32_t null_fields= 0;
 
1479
  MY_BITMAP *read_set= (*ptabfield)->table->read_set;
1456
1480
 
1457
1481
  /*
1458
1482
    If there is a reference to a field in the query add it
1460
1484
    Note for future refinement:
1461
1485
    This this a too strong condition.
1462
1486
    Actually we need only the fields referred in the
1463
 
    result set. And for some of them it makes sense to use
 
1487
    result set. And for some of them it makes sense to use 
1464
1488
    the values directly from sorted fields.
1465
1489
  */
1466
1490
  *plength= 0;
1467
1491
 
1468
1492
  for (pfield= ptabfield; (field= *pfield) ; pfield++)
1469
1493
  {
1470
 
    if (!(field->isReadSet()))
 
1494
    if (!bitmap_is_set(read_set, field->field_index))
1471
1495
      continue;
1472
1496
    if (field->flags & BLOB_FLAG)
1473
1497
      return 0;
1475
1499
    if (field->maybe_null())
1476
1500
      null_fields++;
1477
1501
    fields++;
1478
 
  }
 
1502
  } 
1479
1503
  if (!fields)
1480
1504
    return 0;
1481
1505
  length+= (null_fields+7)/8;
1482
1506
 
1483
 
  if (length+sortlength > session->variables.max_length_for_sort_data ||
1484
 
      !(addonf= (SORT_ADDON_FIELD *) malloc(sizeof(SORT_ADDON_FIELD)*
1485
 
                                            (fields+1))))
 
1507
  if (length+sortlength > thd->variables.max_length_for_sort_data ||
 
1508
      !(addonf= (SORT_ADDON_FIELD *) my_malloc(sizeof(SORT_ADDON_FIELD)*
 
1509
                                               (fields+1), MYF(MY_WME))))
1486
1510
    return 0;
1487
1511
 
1488
1512
  *plength= length;
1490
1514
  null_fields= 0;
1491
1515
  for (pfield= ptabfield; (field= *pfield) ; pfield++)
1492
1516
  {
1493
 
    if (!(field->isReadSet()))
 
1517
    if (!bitmap_is_set(read_set, field->field_index))
1494
1518
      continue;
1495
1519
    addonf->field= field;
1496
1520
    addonf->offset= length;
1510
1534
    addonf++;
1511
1535
  }
1512
1536
  addonf->field= 0;     // Put end marker
1513
 
 
 
1537
  
1514
1538
  return (addonf-fields);
1515
1539
}
1516
1540
 
1530
1554
    void.
1531
1555
*/
1532
1556
 
1533
 
static void
 
1557
static void 
1534
1558
unpack_addon_fields(struct st_sort_addon_field *addon_field, unsigned char *buff)
1535
1559
{
1536
1560
  Field *field;