← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to server/filesort.cc

Merge/fix in FAQ.

Show diffs side-by-side

added added

removed removed

Lines of Context:
server/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
11
11
 
12
12
   You should have received a copy of the GNU General Public License
13
13
   along with this program; if not, write to the Free Software
14
 
   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA */
 
14
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
15
15
 
16
16
 
17
17
/**
21
21
  Sorts a database
22
22
*/
23
23
 
24
 
#include <config.h>
25
 
 
26
 
#include <float.h>
27
 
#include <limits.h>
28
 
 
29
 
#include <queue>
30
 
#include <algorithm>
31
 
#include <iostream>
32
 
 
33
 
#include <drizzled/drizzled.h>
34
 
#include <drizzled/sql_sort.h>
35
 
#include <drizzled/filesort.h>
36
 
#include <drizzled/error.h>
37
 
#include <drizzled/probes.h>
38
 
#include <drizzled/session.h>
39
 
#include <drizzled/table.h>
40
 
#include <drizzled/table_list.h>
41
 
#include <drizzled/optimizer/range.h>
42
 
#include <drizzled/records.h>
43
 
#include <drizzled/internal/iocache.h>
44
 
#include <drizzled/internal/my_sys.h>
45
 
#include <plugin/myisam/myisam.h>
46
 
#include <drizzled/plugin/transactional_storage_engine.h>
47
 
#include <drizzled/atomics.h>
48
 
#include <drizzled/global_buffer.h>
49
 
 
50
 
#include <drizzled/sort_field.h>
51
 
 
52
 
 
53
 
using namespace std;
54
 
 
55
 
namespace drizzled
56
 
{
57
 
 
58
 
/* Defines used by filesort and uniques */
59
 
#define MERGEBUFF               7
60
 
#define MERGEBUFF2              15
61
 
 
62
 
class BufferCompareContext
63
 
{
64
 
public:
65
 
  qsort_cmp2 key_compare;
66
 
  void *key_compare_arg;
67
 
 
68
 
  BufferCompareContext() :
69
 
    key_compare(0),
70
 
    key_compare_arg(0)
71
 
  { }
72
 
 
73
 
};
74
 
 
75
 
class SortParam {
76
 
public:
77
 
  uint32_t rec_length;          /* Length of sorted records */
78
 
  uint32_t sort_length;                 /* Length of sorted columns */
79
 
  uint32_t ref_length;                  /* Length of record ref. */
80
 
  uint32_t addon_length;        /* Length of added packed fields */
81
 
  uint32_t res_length;          /* Length of records in final sorted file/buffer */
82
 
  uint32_t keys;                                /* Max keys / buffer */
83
 
  ha_rows max_rows,examined_rows;
84
 
  Table *sort_form;                     /* For quicker make_sortkey */
85
 
  SortField *local_sortorder;
86
 
  SortField *end;
87
 
  sort_addon_field *addon_field; /* Descriptors for companion fields */
88
 
  unsigned char *unique_buff;
89
 
  bool not_killable;
90
 
  char *tmp_buffer;
91
 
  /* The fields below are used only by Unique class */
92
 
  qsort2_cmp compare;
93
 
  BufferCompareContext cmp_context;
94
 
 
95
 
  SortParam() :
96
 
    rec_length(0),
97
 
    sort_length(0),
98
 
    ref_length(0),
99
 
    addon_length(0),
100
 
    res_length(0),
101
 
    keys(0),
102
 
    max_rows(0),
103
 
    examined_rows(0),
104
 
    sort_form(0),
105
 
    local_sortorder(0),
106
 
    end(0),
107
 
    addon_field(0),
108
 
    unique_buff(0),
109
 
    not_killable(0),
110
 
    tmp_buffer(0),
111
 
    compare(0)
112
 
  {
113
 
  }
114
 
 
115
 
  ~SortParam()
116
 
  {
117
 
    if (tmp_buffer)
118
 
      free(tmp_buffer);
119
 
  }
120
 
 
121
 
  int write_keys(unsigned char * *sort_keys,
122
 
                 uint32_t count,
123
 
                 internal::IO_CACHE *buffer_file,
124
 
                 internal::IO_CACHE *tempfile);
125
 
 
126
 
  void make_sortkey(unsigned char *to,
127
 
                    unsigned char *ref_pos);
128
 
  void register_used_fields();
129
 
  bool save_index(unsigned char **sort_keys,
130
 
                  uint32_t count,
131
 
                  filesort_info *table_sort);
132
 
 
133
 
};
134
 
 
135
 
/* functions defined in this file */
136
 
 
137
 
static char **make_char_array(char **old_pos, uint32_t fields,
138
 
                              uint32_t length);
139
 
 
140
 
static unsigned char *read_buffpek_from_file(internal::IO_CACHE *buffer_file,
141
 
                                             uint32_t count,
142
 
                                             unsigned char *buf);
143
 
 
144
 
static uint32_t suffix_length(uint32_t string_length);
145
 
static void unpack_addon_fields(sort_addon_field *addon_field,
146
 
                                unsigned char *buff);
147
 
 
148
 
FileSort::FileSort(Session &arg) :
149
 
  _session(arg)
150
 
{ 
151
 
}
152
 
 
 
24
#include "mysql_priv.h"
 
25
#include <m_ctype.h>
 
26
#include "sql_sort.h"
 
27
 
 
28
/// How to write record_ref.
 
29
#define WRITE_REF(file,from) \
 
30
if (my_b_write((file),(uchar*) (from),param->ref_length)) \
 
31
  return(1);
 
32
 
 
33
        /* functions defined in this file */
 
34
 
 
35
static char **make_char_array(char **old_pos, register uint fields,
 
36
                              uint length, myf my_flag);
 
37
static uchar *read_buffpek_from_file(IO_CACHE *buffer_file, uint count,
 
38
                                     uchar *buf);
 
39
static ha_rows find_all_keys(SORTPARAM *param,SQL_SELECT *select,
 
40
                             uchar * *sort_keys, IO_CACHE *buffer_file,
 
41
                             IO_CACHE *tempfile,IO_CACHE *indexfile);
 
42
static int write_keys(SORTPARAM *param,uchar * *sort_keys,
 
43
                      uint count, IO_CACHE *buffer_file, IO_CACHE *tempfile);
 
44
static void make_sortkey(SORTPARAM *param,uchar *to, uchar *ref_pos);
 
45
static void register_used_fields(SORTPARAM *param);
 
46
static int merge_index(SORTPARAM *param,uchar *sort_buffer,
 
47
                       BUFFPEK *buffpek,
 
48
                       uint maxbuffer,IO_CACHE *tempfile,
 
49
                       IO_CACHE *outfile);
 
50
static bool save_index(SORTPARAM *param,uchar **sort_keys, uint count, 
 
51
                       FILESORT_INFO *table_sort);
 
52
static uint suffix_length(ulong string_length);
 
53
static uint sortlength(THD *thd, SORT_FIELD *sortorder, uint s_length,
 
54
                       bool *multi_byte_charset);
 
55
static SORT_ADDON_FIELD *get_addon_fields(THD *thd, Field **ptabfield,
 
56
                                          uint sortlength, uint *plength);
 
57
static void unpack_addon_fields(struct st_sort_addon_field *addon_field,
 
58
                                uchar *buff);
153
59
/**
154
60
  Sort a table.
155
61
  Creates a set of pointers that can be used to read the rows
162
68
  The result set is stored in table->io_cache or
163
69
  table->record_pointers.
164
70
 
 
71
  @param thd           Current thread
165
72
  @param table          Table to sort
166
73
  @param sortorder      How to sort the table
167
74
  @param s_length       Number of elements in sortorder
168
75
  @param select         condition to apply to the rows
169
76
  @param max_rows       Return only this many rows
170
77
  @param sort_positions Set to 1 if we want to force sorting by position
171
 
                        (Needed by UPDATE/INSERT or ALTER Table)
 
78
                        (Needed by UPDATE/INSERT or ALTER TABLE)
172
79
  @param examined_rows  Store number of examined rows here
173
80
 
174
81
  @todo
185
92
    examined_rows       will be set to number of examined rows
186
93
*/
187
94
 
188
 
ha_rows FileSort::run(Table *table, SortField *sortorder, uint32_t s_length,
189
 
                      optimizer::SqlSelect *select, ha_rows max_rows,
190
 
                      bool sort_positions, ha_rows &examined_rows)
 
95
ha_rows filesort(THD *thd, TABLE *table, SORT_FIELD *sortorder, uint s_length,
 
96
                 SQL_SELECT *select, ha_rows max_rows,
 
97
                 bool sort_positions, ha_rows *examined_rows)
191
98
{
192
 
  int error= 1;
193
 
  uint32_t memavl= 0, min_sort_memory;
194
 
  uint32_t maxbuffer;
195
 
  size_t allocated_sort_memory= 0;
196
 
  buffpek *buffpek_inst= 0;
 
99
  int error;
 
100
  ulong memavl, min_sort_memory;
 
101
  uint maxbuffer;
 
102
  BUFFPEK *buffpek;
197
103
  ha_rows records= HA_POS_ERROR;
198
 
  unsigned char **sort_keys= 0;
199
 
  internal::IO_CACHE tempfile;
200
 
  internal::IO_CACHE buffpek_pointers;
201
 
  internal::IO_CACHE *selected_records_file;
202
 
  internal::IO_CACHE *outfile;
203
 
  SortParam param;
 
104
  uchar **sort_keys= 0;
 
105
  IO_CACHE tempfile, buffpek_pointers, *selected_records_file, *outfile; 
 
106
  SORTPARAM param;
204
107
  bool multi_byte_charset;
205
108
 
206
 
  /*
207
 
    Don't use table->sort in filesort as it is also used by
208
 
    QuickIndexMergeSelect. Work with a copy and put it back at the end
209
 
    when index_merge select has finished with it.
210
 
  */
211
 
  filesort_info table_sort(table->sort);
212
 
  table->sort.io_cache= NULL;
213
 
 
214
 
  TableList *tab= table->pos_in_table_list;
 
109
  FILESORT_INFO table_sort;
 
110
  TABLE_LIST *tab= table->pos_in_table_list;
215
111
  Item_subselect *subselect= tab ? tab->containing_subselect() : 0;
216
112
 
217
 
  DRIZZLE_FILESORT_START(table->getShare()->getSchemaName(), table->getShare()->getTableName());
 
113
  MYSQL_FILESORT_START();
218
114
 
219
115
  /*
220
116
   Release InnoDB's adaptive hash index latch (if holding) before
221
117
   running a sort.
222
118
  */
223
 
  plugin::TransactionalStorageEngine::releaseTemporaryLatches(&getSession());
224
 
 
225
 
 
 
119
  ha_release_temporary_latches(thd);
 
120
 
 
121
  /* 
 
122
    Don't use table->sort in filesort as it is also used by 
 
123
    QUICK_INDEX_MERGE_SELECT. Work with a copy and put it back at the end 
 
124
    when index_merge select has finished with it.
 
125
  */
 
126
  memcpy(&table_sort, &table->sort, sizeof(FILESORT_INFO));
 
127
  table->sort.io_cache= NULL;
 
128
  
226
129
  outfile= table_sort.io_cache;
227
 
  assert(tempfile.buffer == 0);
228
 
  assert(buffpek_pointers.buffer == 0);
229
 
 
230
 
  param.sort_length= sortlength(sortorder, s_length, &multi_byte_charset);
231
 
  param.ref_length= table->cursor->ref_length;
232
 
 
233
 
  if (!(table->cursor->getEngine()->check_flag(HTON_BIT_FAST_KEY_READ)) && !sort_positions)
 
130
  my_b_clear(&tempfile);
 
131
  my_b_clear(&buffpek_pointers);
 
132
  buffpek=0;
 
133
  error= 1;
 
134
  bzero((char*) &param,sizeof(param));
 
135
  param.sort_length= sortlength(thd, sortorder, s_length, &multi_byte_charset);
 
136
  param.ref_length= table->file->ref_length;
 
137
  param.addon_field= 0;
 
138
  param.addon_length= 0;
 
139
  if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) && !sort_positions)
234
140
  {
235
 
    /*
236
 
      Get the descriptors of all fields whose values are appended
 
141
    /* 
 
142
      Get the descriptors of all fields whose values are appended 
237
143
      to sorted fields and get its total length in param.spack_length.
238
144
    */
239
 
    param.addon_field= get_addon_fields(table->getFields(),
 
145
    param.addon_field= get_addon_fields(thd, table->field, 
240
146
                                        param.sort_length,
241
147
                                        &param.addon_length);
242
148
  }
248
154
  if (param.addon_field)
249
155
  {
250
156
    param.res_length= param.addon_length;
251
 
    if (!(table_sort.addon_buf= (unsigned char *) malloc(param.addon_length)))
252
 
    {
 
157
    if (!(table_sort.addon_buf= (uchar *) my_malloc(param.addon_length,
 
158
                                                    MYF(MY_WME))))
253
159
      goto err;
254
 
    }
255
160
  }
256
161
  else
257
162
  {
258
163
    param.res_length= param.ref_length;
259
 
    /*
260
 
      The reference to the record is considered
 
164
    /* 
 
165
      The reference to the record is considered 
261
166
      as an additional sorted field
262
167
    */
263
168
    param.sort_length+= param.ref_length;
267
172
 
268
173
  if (select && select->quick)
269
174
  {
270
 
    getSession().status_var.filesort_range_count++;
 
175
    status_var_increment(thd->status_var.filesort_range_count);
271
176
  }
272
177
  else
273
178
  {
274
 
    getSession().status_var.filesort_scan_count++;
 
179
    status_var_increment(thd->status_var.filesort_scan_count);
275
180
  }
276
181
#ifdef CAN_TRUST_RANGE
277
182
  if (select && select->quick && select->quick->records > 0L)
278
183
  {
279
 
    records= min((ha_rows) (select->quick->records*2+EXTRA_RECORDS*2),
280
 
                 table->cursor->stats.records)+EXTRA_RECORDS;
 
184
    records=min((ha_rows) (select->quick->records*2+EXTRA_RECORDS*2),
 
185
                table->file->stats.records)+EXTRA_RECORDS;
281
186
    selected_records_file=0;
282
187
  }
283
188
  else
284
189
#endif
285
190
  {
286
 
    records= table->cursor->estimate_rows_upper_bound();
 
191
    records= table->file->estimate_rows_upper_bound();
287
192
    /*
288
 
      If number of records is not known, use as much of sort buffer
289
 
      as possible.
 
193
      If number of records is not known, use as much of sort buffer 
 
194
      as possible. 
290
195
    */
291
196
    if (records == HA_POS_ERROR)
292
197
      records--;  // we use 'records+1' below.
293
198
    selected_records_file= 0;
294
199
  }
295
200
 
296
 
  if (multi_byte_charset && !(param.tmp_buffer= (char*) malloc(param.sort_length)))
297
 
  {
 
201
  if (multi_byte_charset &&
 
202
      !(param.tmp_buffer= (char*) my_malloc(param.sort_length,MYF(MY_WME))))
298
203
    goto err;
299
 
  }
300
204
 
301
 
  memavl= getSession().variables.sortbuff_size;
302
 
  min_sort_memory= max((uint32_t)MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2);
 
205
  memavl= thd->variables.sortbuff_size;
 
206
  min_sort_memory= max(MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2);
303
207
  while (memavl >= min_sort_memory)
304
208
  {
305
 
    uint32_t old_memavl;
306
 
    uint32_t keys= memavl/(param.rec_length+sizeof(char*));
307
 
    param.keys= (uint32_t) min(records+1, (ha_rows)keys);
308
 
 
309
 
    allocated_sort_memory= param.keys * param.rec_length;
310
 
    if (not global_sort_buffer.add(allocated_sort_memory))
311
 
    {
312
 
      my_error(ER_OUT_OF_GLOBAL_SORTMEMORY, MYF(ME_ERROR+ME_WAITTANG));
313
 
      goto err;
314
 
    }
315
 
 
 
209
    ulong old_memavl;
 
210
    ulong keys= memavl/(param.rec_length+sizeof(char*));
 
211
    param.keys=(uint) min(records+1, keys);
316
212
    if ((table_sort.sort_keys=
317
 
         (unsigned char **) make_char_array((char **) table_sort.sort_keys,
318
 
                                            param.keys, param.rec_length)))
 
213
         (uchar **) make_char_array((char **) table_sort.sort_keys,
 
214
                                    param.keys, param.rec_length, MYF(0))))
319
215
      break;
320
 
 
321
 
    global_sort_buffer.sub(allocated_sort_memory);
322
 
    old_memavl= memavl;
323
 
    if ((memavl= memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
 
216
    old_memavl=memavl;
 
217
    if ((memavl=memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
324
218
      memavl= min_sort_memory;
325
219
  }
326
220
  sort_keys= table_sort.sort_keys;
329
223
    my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR+ME_WAITTANG));
330
224
    goto err;
331
225
  }
332
 
 
333
 
  if (buffpek_pointers.open_cached_file(drizzle_tmpdir.c_str(),TEMP_PREFIX, DISK_BUFFER_SIZE, MYF(MY_WME)))
334
 
  {
 
226
  if (open_cached_file(&buffpek_pointers,mysql_tmpdir,TEMP_PREFIX,
 
227
                       DISK_BUFFER_SIZE, MYF(MY_WME)))
335
228
    goto err;
336
 
  }
337
229
 
338
230
  param.keys--;                         /* TODO: check why we do this */
339
231
  param.sort_form= table;
340
232
  param.end=(param.local_sortorder=sortorder)+s_length;
341
 
  if ((records= find_all_keys(&param,select,sort_keys, &buffpek_pointers,
342
 
                              &tempfile, selected_records_file)) == HA_POS_ERROR)
343
 
  {
 
233
  if ((records=find_all_keys(&param,select,sort_keys, &buffpek_pointers,
 
234
                             &tempfile, selected_records_file)) ==
 
235
      HA_POS_ERROR)
344
236
    goto err;
345
 
  }
346
 
  maxbuffer= (uint32_t) (my_b_tell(&buffpek_pointers)/sizeof(*buffpek_inst));
 
237
  maxbuffer= (uint) (my_b_tell(&buffpek_pointers)/sizeof(*buffpek));
347
238
 
348
239
  if (maxbuffer == 0)                   // The whole set is in memory
349
240
  {
350
 
    if (param.save_index(sort_keys,(uint32_t) records, &table_sort))
351
 
    {
 
241
    if (save_index(&param,sort_keys,(uint) records, &table_sort))
352
242
      goto err;
353
 
    }
354
243
  }
355
244
  else
356
245
  {
357
246
    if (table_sort.buffpek && table_sort.buffpek_len < maxbuffer)
358
247
    {
359
 
      if (table_sort.buffpek)
360
 
        free(table_sort.buffpek);
361
 
      table_sort.buffpek = 0;
 
248
      x_free(table_sort.buffpek);
 
249
      table_sort.buffpek= 0;
362
250
    }
363
251
    if (!(table_sort.buffpek=
364
 
          (unsigned char *) read_buffpek_from_file(&buffpek_pointers, maxbuffer, table_sort.buffpek)))
365
 
    {
 
252
          (uchar *) read_buffpek_from_file(&buffpek_pointers, maxbuffer,
 
253
                                 table_sort.buffpek)))
366
254
      goto err;
367
 
    }
368
 
    buffpek_inst= (buffpek *) table_sort.buffpek;
 
255
    buffpek= (BUFFPEK *) table_sort.buffpek;
369
256
    table_sort.buffpek_len= maxbuffer;
370
 
    buffpek_pointers.close_cached_file();
 
257
    close_cached_file(&buffpek_pointers);
371
258
        /* Open cached file if it isn't open */
372
 
    if (! my_b_inited(outfile) && outfile->open_cached_file(drizzle_tmpdir.c_str(),TEMP_PREFIX,READ_RECORD_BUFFER, MYF(MY_WME)))
373
 
    {
374
 
      goto err;
375
 
    }
376
 
 
377
 
    if (outfile->reinit_io_cache(internal::WRITE_CACHE,0L,0,0))
378
 
    {
379
 
      goto err;
380
 
    }
 
259
    if (! my_b_inited(outfile) &&
 
260
        open_cached_file(outfile,mysql_tmpdir,TEMP_PREFIX,READ_RECORD_BUFFER,
 
261
                          MYF(MY_WME)))
 
262
      goto err;
 
263
    if (reinit_io_cache(outfile,WRITE_CACHE,0L,0,0))
 
264
      goto err;
381
265
 
382
266
    /*
383
267
      Use also the space previously used by string pointers in sort_buffer
384
268
      for temporary key storage.
385
269
    */
386
 
    param.keys=((param.keys*(param.rec_length+sizeof(char*))) / param.rec_length-1);
387
 
 
 
270
    param.keys=((param.keys*(param.rec_length+sizeof(char*))) /
 
271
                param.rec_length-1);
388
272
    maxbuffer--;                                // Offset from 0
389
 
    if (merge_many_buff(&param,(unsigned char*) sort_keys,buffpek_inst,&maxbuffer, &tempfile))
390
 
    {
391
 
      goto err;
392
 
    }
393
 
 
394
 
    if (flush_io_cache(&tempfile) || tempfile.reinit_io_cache(internal::READ_CACHE,0L,0,0))
395
 
    {
396
 
      goto err;
397
 
    }
398
 
 
399
 
    if (merge_index(&param,(unsigned char*) sort_keys,buffpek_inst,maxbuffer,&tempfile, outfile))
400
 
    {
401
 
      goto err;
402
 
    }
 
273
    if (merge_many_buff(&param,(uchar*) sort_keys,buffpek,&maxbuffer,
 
274
                        &tempfile))
 
275
      goto err;
 
276
    if (flush_io_cache(&tempfile) ||
 
277
        reinit_io_cache(&tempfile,READ_CACHE,0L,0,0))
 
278
      goto err;
 
279
    if (merge_index(&param,(uchar*) sort_keys,buffpek,maxbuffer,&tempfile,
 
280
                    outfile))
 
281
      goto err;
403
282
  }
404
 
 
405
283
  if (records > param.max_rows)
406
 
  {
407
 
    records= param.max_rows;
408
 
  }
 
284
    records=param.max_rows;
409
285
  error =0;
410
286
 
411
287
 err:
412
 
  if (not subselect || not subselect->is_uncacheable())
 
288
  if (param.tmp_buffer)
 
289
    x_free(param.tmp_buffer);
 
290
  if (!subselect || !subselect->is_uncacheable())
413
291
  {
414
 
    free(sort_keys);
 
292
    x_free((uchar*) sort_keys);
415
293
    table_sort.sort_keys= 0;
416
 
    free(buffpek_inst);
 
294
    x_free((uchar*) buffpek);
417
295
    table_sort.buffpek= 0;
418
296
    table_sort.buffpek_len= 0;
419
297
  }
420
 
 
421
 
  tempfile.close_cached_file();
422
 
  buffpek_pointers.close_cached_file();
423
 
 
 
298
  close_cached_file(&tempfile);
 
299
  close_cached_file(&buffpek_pointers);
424
300
  if (my_b_inited(outfile))
425
301
  {
426
302
    if (flush_io_cache(outfile))
427
 
    {
428
303
      error=1;
429
 
    }
430
304
    {
431
 
      internal::my_off_t save_pos= outfile->pos_in_file;
 
305
      my_off_t save_pos=outfile->pos_in_file;
432
306
      /* For following reads */
433
 
      if (outfile->reinit_io_cache(internal::READ_CACHE,0L,0,0))
434
 
      {
 
307
      if (reinit_io_cache(outfile,READ_CACHE,0L,0,0))
435
308
        error=1;
436
 
      }
437
309
      outfile->end_of_file=save_pos;
438
310
    }
439
311
  }
440
 
 
441
312
  if (error)
442
 
  {
443
313
    my_message(ER_FILSORT_ABORT, ER(ER_FILSORT_ABORT),
444
314
               MYF(ME_ERROR+ME_WAITTANG));
445
 
  }
446
315
  else
447
 
  {
448
 
    getSession().status_var.filesort_rows+= (uint32_t) records;
449
 
  }
450
 
  examined_rows= param.examined_rows;
451
 
  global_sort_buffer.sub(allocated_sort_memory);
452
 
  table->sort= table_sort;
453
 
  DRIZZLE_FILESORT_DONE(error, records);
454
 
  return (error ? HA_POS_ERROR : records);
 
316
    statistic_add(thd->status_var.filesort_rows,
 
317
                  (ulong) records, &LOCK_status);
 
318
  *examined_rows= param.examined_rows;
 
319
  memcpy(&table->sort, &table_sort, sizeof(FILESORT_INFO));
 
320
  MYSQL_FILESORT_END();
 
321
  return(error ? HA_POS_ERROR : records);
455
322
} /* filesort */
456
323
 
 
324
 
 
325
void filesort_free_buffers(TABLE *table, bool full)
 
326
{
 
327
  if (table->sort.record_pointers)
 
328
  {
 
329
    my_free((uchar*) table->sort.record_pointers,MYF(0));
 
330
    table->sort.record_pointers=0;
 
331
  }
 
332
  if (full)
 
333
  {
 
334
    if (table->sort.sort_keys )
 
335
    {
 
336
      x_free((uchar*) table->sort.sort_keys);
 
337
      table->sort.sort_keys= 0;
 
338
    }
 
339
    if (table->sort.buffpek)
 
340
    {
 
341
      x_free((uchar*) table->sort.buffpek);
 
342
      table->sort.buffpek= 0;
 
343
      table->sort.buffpek_len= 0;
 
344
    }
 
345
  }
 
346
  if (table->sort.addon_buf)
 
347
  {
 
348
    my_free((char *) table->sort.addon_buf, MYF(0));
 
349
    my_free((char *) table->sort.addon_field, MYF(MY_ALLOW_ZERO_PTR));
 
350
    table->sort.addon_buf=0;
 
351
    table->sort.addon_field=0;
 
352
  }
 
353
}
 
354
 
457
355
/** Make a array of string pointers. */
458
356
 
459
 
static char **make_char_array(char **old_pos, uint32_t fields,
460
 
                              uint32_t length)
 
357
static char **make_char_array(char **old_pos, register uint fields,
 
358
                              uint length, myf my_flag)
461
359
{
462
 
  char **pos;
 
360
  register char **pos;
463
361
  char *char_pos;
464
362
 
465
363
  if (old_pos ||
466
 
      (old_pos= (char**) malloc((uint32_t) fields*(length+sizeof(char*)))))
 
364
      (old_pos= (char**) my_malloc((uint) fields*(length+sizeof(char*)),
 
365
                                   my_flag)))
467
366
  {
468
367
    pos=old_pos; char_pos=((char*) (pos+fields)) -length;
469
368
    while (fields--) *(pos++) = (char_pos+= length);
475
374
 
476
375
/** Read 'count' number of buffer pointers into memory. */
477
376
 
478
 
static unsigned char *read_buffpek_from_file(internal::IO_CACHE *buffpek_pointers, uint32_t count,
479
 
                                     unsigned char *buf)
 
377
static uchar *read_buffpek_from_file(IO_CACHE *buffpek_pointers, uint count,
 
378
                                     uchar *buf)
480
379
{
481
 
  uint32_t length= sizeof(buffpek)*count;
482
 
  unsigned char *tmp= buf;
483
 
  if (count > UINT_MAX/sizeof(buffpek))
484
 
    return 0; /* sizeof(buffpek)*count will overflow */
 
380
  ulong length= sizeof(BUFFPEK)*count;
 
381
  uchar *tmp= buf;
 
382
  if (count > UINT_MAX/sizeof(BUFFPEK))
 
383
    return 0; /* sizeof(BUFFPEK)*count will overflow */
485
384
  if (!tmp)
486
 
    tmp= (unsigned char *)malloc(length);
 
385
    tmp= (uchar *)my_malloc(length, MYF(MY_WME));
487
386
  if (tmp)
488
387
  {
489
 
    if (buffpek_pointers->reinit_io_cache(internal::READ_CACHE,0L,0,0) ||
490
 
        my_b_read(buffpek_pointers, (unsigned char*) tmp, length))
 
388
    if (reinit_io_cache(buffpek_pointers,READ_CACHE,0L,0,0) ||
 
389
        my_b_read(buffpek_pointers, (uchar*) tmp, length))
491
390
    {
492
 
      free((char*) tmp);
 
391
      my_free((char*) tmp, MYF(0));
493
392
      tmp=0;
494
393
    }
495
394
  }
504
403
  @param param             Sorting parameter
505
404
  @param select            Use this to get source data
506
405
  @param sort_keys         Array of pointers to sort key + addon buffers.
507
 
  @param buffpek_pointers  File to write buffpeks describing sorted segments
 
406
  @param buffpek_pointers  File to write BUFFPEKs describing sorted segments
508
407
                           in tempfile.
509
408
  @param tempfile          File to write sorted sequences of sortkeys to.
510
409
  @param indexfile         If !NULL, use it for source data (contains rowids)
518
417
       {
519
418
         sort sort_keys buffer;
520
419
         dump sorted sequence to 'tempfile';
521
 
         dump buffpek describing sequence location into 'buffpek_pointers';
 
420
         dump BUFFPEK describing sequence location into 'buffpek_pointers';
522
421
       }
523
422
       put sort key into 'sort_keys';
524
423
     }
534
433
    HA_POS_ERROR on error.
535
434
*/
536
435
 
537
 
ha_rows FileSort::find_all_keys(SortParam *param, 
538
 
                                optimizer::SqlSelect *select,
539
 
                                unsigned char **sort_keys,
540
 
                                internal::IO_CACHE *buffpek_pointers,
541
 
                                internal::IO_CACHE *tempfile, internal::IO_CACHE *indexfile)
 
436
static ha_rows find_all_keys(SORTPARAM *param, SQL_SELECT *select,
 
437
                             uchar **sort_keys,
 
438
                             IO_CACHE *buffpek_pointers,
 
439
                             IO_CACHE *tempfile, IO_CACHE *indexfile)
542
440
{
543
441
  int error,flag,quick_select;
544
 
  uint32_t idx,indexpos,ref_length;
545
 
  unsigned char *ref_pos,*next_pos,ref_buff[MAX_REFLENGTH];
546
 
  internal::my_off_t record;
547
 
  Table *sort_form;
548
 
  volatile Session::killed_state_t *killed= getSession().getKilledPtr();
549
 
  Cursor *file;
550
 
  boost::dynamic_bitset<> *save_read_set= NULL;
551
 
  boost::dynamic_bitset<> *save_write_set= NULL;
 
442
  uint idx,indexpos,ref_length;
 
443
  uchar *ref_pos,*next_pos,ref_buff[MAX_REFLENGTH];
 
444
  my_off_t record;
 
445
  TABLE *sort_form;
 
446
  THD *thd= current_thd;
 
447
  volatile THD::killed_state *killed= &thd->killed;
 
448
  handler *file;
 
449
  MY_BITMAP *save_read_set, *save_write_set;
552
450
 
553
451
  idx=indexpos=0;
554
452
  error=quick_select=0;
555
453
  sort_form=param->sort_form;
556
 
  file= sort_form->cursor;
 
454
  file=sort_form->file;
557
455
  ref_length=param->ref_length;
558
456
  ref_pos= ref_buff;
559
457
  quick_select=select && select->quick;
560
458
  record=0;
561
 
  flag= ((!indexfile && ! file->isOrdered())
 
459
  flag= ((!indexfile && file->ha_table_flags() & HA_REC_NOT_IN_SEQ)
562
460
         || quick_select);
563
461
  if (indexfile || flag)
564
462
    ref_pos= &file->ref[0];
565
463
  next_pos=ref_pos;
566
464
  if (! indexfile && ! quick_select)
567
465
  {
568
 
    next_pos=(unsigned char*) 0;                        /* Find records in sequence */
569
 
    if (file->startTableScan(1))
570
 
      return(HA_POS_ERROR);
571
 
    file->extra_opt(HA_EXTRA_CACHE, getSession().variables.read_buff_size);
 
466
    next_pos=(uchar*) 0;                        /* Find records in sequence */
 
467
    file->ha_rnd_init(1);
 
468
    file->extra_opt(HA_EXTRA_CACHE,
 
469
                    current_thd->variables.read_buff_size);
572
470
  }
573
471
 
574
 
  ReadRecord read_record_info;
 
472
  READ_RECORD read_record_info;
575
473
  if (quick_select)
576
474
  {
577
475
    if (select->quick->reset())
578
476
      return(HA_POS_ERROR);
579
 
 
580
 
    if (read_record_info.init_read_record(&getSession(), select->quick->head, select, 1, 1))
581
 
      return(HA_POS_ERROR);
 
477
    init_read_record(&read_record_info, current_thd, select->quick->head,
 
478
                     select, 1, 1);
582
479
  }
583
480
 
584
481
  /* Remember original bitmaps */
585
482
  save_read_set=  sort_form->read_set;
586
483
  save_write_set= sort_form->write_set;
587
484
  /* Set up temporary column read map for columns used by sort */
588
 
  sort_form->tmp_set.reset();
 
485
  bitmap_clear_all(&sort_form->tmp_set);
589
486
  /* Temporary set for register_used_fields and register_field_in_read_map */
590
487
  sort_form->read_set= &sort_form->tmp_set;
591
 
  param->register_used_fields();
 
488
  register_used_fields(param);
592
489
  if (select && select->cond)
593
490
    select->cond->walk(&Item::register_field_in_read_map, 1,
594
 
                       (unsigned char*) sort_form);
595
 
  sort_form->column_bitmaps_set(sort_form->tmp_set, sort_form->tmp_set);
 
491
                       (uchar*) sort_form);
 
492
  sort_form->column_bitmaps_set(&sort_form->tmp_set, &sort_form->tmp_set);
596
493
 
597
494
  for (;;)
598
495
  {
603
500
        error= HA_ERR_END_OF_FILE;
604
501
        break;
605
502
      }
606
 
      file->position(sort_form->getInsertRecord());
 
503
      file->position(sort_form->record[0]);
607
504
    }
608
505
    else                                        /* Not quick-select */
609
506
    {
610
507
      if (indexfile)
611
508
      {
612
 
        if (my_b_read(indexfile,(unsigned char*) ref_pos,ref_length))
 
509
        if (my_b_read(indexfile,(uchar*) ref_pos,ref_length)) /* purecov: deadcode */
613
510
        {
614
 
          error= errno ? errno : -1;            /* Abort */
 
511
          error= my_errno ? my_errno : -1;              /* Abort */
615
512
          break;
616
513
        }
617
 
        error=file->rnd_pos(sort_form->getInsertRecord(),next_pos);
 
514
        error=file->rnd_pos(sort_form->record[0],next_pos);
618
515
      }
619
516
      else
620
517
      {
621
 
        error=file->rnd_next(sort_form->getInsertRecord());
622
 
 
 
518
        error=file->rnd_next(sort_form->record[0]);
623
519
        if (!flag)
624
520
        {
625
 
          internal::my_store_ptr(ref_pos,ref_length,record); // Position to row
626
 
          record+= sort_form->getShare()->db_record_offset;
 
521
          my_store_ptr(ref_pos,ref_length,record); // Position to row
 
522
          record+= sort_form->s->db_record_offset;
627
523
        }
628
524
        else if (!error)
629
 
          file->position(sort_form->getInsertRecord());
 
525
          file->position(sort_form->record[0]);
630
526
      }
631
527
      if (error && error != HA_ERR_RECORD_DELETED)
632
528
        break;
637
533
      if (!indexfile && !quick_select)
638
534
      {
639
535
        (void) file->extra(HA_EXTRA_NO_CACHE);
640
 
        file->endTableScan();
 
536
        file->ha_rnd_end();
641
537
      }
642
 
      return(HA_POS_ERROR);
 
538
      return(HA_POS_ERROR);             /* purecov: inspected */
643
539
    }
644
540
    if (error == 0)
645
541
      param->examined_rows++;
647
543
    {
648
544
      if (idx == param->keys)
649
545
      {
650
 
        if (param->write_keys(sort_keys, idx, buffpek_pointers, tempfile))
 
546
        if (write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
651
547
          return(HA_POS_ERROR);
652
548
        idx=0;
653
549
        indexpos++;
654
550
      }
655
 
      param->make_sortkey(sort_keys[idx++], ref_pos);
 
551
      make_sortkey(param,sort_keys[idx++],ref_pos);
656
552
    }
657
553
    else
658
 
    {
659
554
      file->unlock_row();
660
 
    }
661
 
 
662
555
    /* It does not make sense to read more keys in case of a fatal error */
663
 
    if (getSession().is_error())
 
556
    if (thd->is_error())
664
557
      break;
665
558
  }
666
559
  if (quick_select)
669
562
      index_merge quick select uses table->sort when retrieving rows, so free
670
563
      resoures it has allocated.
671
564
    */
672
 
    read_record_info.end_read_record();
 
565
    end_read_record(&read_record_info);
673
566
  }
674
567
  else
675
568
  {
676
569
    (void) file->extra(HA_EXTRA_NO_CACHE);      /* End cacheing of records */
677
570
    if (!next_pos)
678
 
      file->endTableScan();
 
571
      file->ha_rnd_end();
679
572
  }
680
573
 
681
 
  if (getSession().is_error())
 
574
  if (thd->is_error())
682
575
    return(HA_POS_ERROR);
683
 
 
 
576
  
684
577
  /* Signal we should use orignal column read and write maps */
685
 
  sort_form->column_bitmaps_set(*save_read_set, *save_write_set);
 
578
  sort_form->column_bitmaps_set(save_read_set, save_write_set);
686
579
 
687
580
  if (error != HA_ERR_END_OF_FILE)
688
581
  {
689
 
    sort_form->print_error(error,MYF(ME_ERROR | ME_WAITTANG));
690
 
    return(HA_POS_ERROR);
691
 
  }
692
 
 
693
 
  if (indexpos && idx && param->write_keys(sort_keys,idx,buffpek_pointers,tempfile))
694
 
  {
695
 
    return(HA_POS_ERROR);
696
 
  }
697
 
 
 
582
    file->print_error(error,MYF(ME_ERROR | ME_WAITTANG)); /* purecov: inspected */
 
583
    return(HA_POS_ERROR);                       /* purecov: inspected */
 
584
  }
 
585
  if (indexpos && idx &&
 
586
      write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
 
587
    return(HA_POS_ERROR);                       /* purecov: inspected */
698
588
  return(my_b_inited(tempfile) ?
699
589
              (ha_rows) (my_b_tell(tempfile)/param->rec_length) :
700
590
              idx);
705
595
  @details
706
596
  Sort the buffer and write:
707
597
  -# the sorted sequence to tempfile
708
 
  -# a buffpek describing the sorted sequence position to buffpek_pointers
 
598
  -# a BUFFPEK describing the sorted sequence position to buffpek_pointers
709
599
 
710
600
    (was: Skriver en buffert med nycklar till filen)
711
601
 
712
602
  @param param             Sort parameters
713
603
  @param sort_keys         Array of pointers to keys to sort
714
604
  @param count             Number of elements in sort_keys array
715
 
  @param buffpek_pointers  One 'buffpek' struct will be written into this file.
716
 
                           The buffpek::{file_pos, count} will indicate where
 
605
  @param buffpek_pointers  One 'BUFFPEK' struct will be written into this file.
 
606
                           The BUFFPEK::{file_pos, count} will indicate where
717
607
                           the sorted data was stored.
718
608
  @param tempfile          The sorted sequence will be written into this file.
719
609
 
723
613
    1 Error
724
614
*/
725
615
 
726
 
int SortParam::write_keys(unsigned char **sort_keys, uint32_t count,
727
 
                          internal::IO_CACHE *buffpek_pointers, internal::IO_CACHE *tempfile)
 
616
static int
 
617
write_keys(SORTPARAM *param, register uchar **sort_keys, uint count,
 
618
           IO_CACHE *buffpek_pointers, IO_CACHE *tempfile)
728
619
{
729
 
  buffpek buffpek;
 
620
  size_t sort_length, rec_length;
 
621
  uchar **end;
 
622
  BUFFPEK buffpek;
730
623
 
731
 
  internal::my_string_ptr_sort((unsigned char*) sort_keys, (uint32_t) count, sort_length);
 
624
  sort_length= param->sort_length;
 
625
  rec_length= param->rec_length;
 
626
  my_string_ptr_sort((uchar*) sort_keys, (uint) count, sort_length);
732
627
  if (!my_b_inited(tempfile) &&
733
 
      tempfile->open_cached_file(drizzle_tmpdir.c_str(), TEMP_PREFIX, DISK_BUFFER_SIZE, MYF(MY_WME)))
734
 
  {
735
 
    return 1;
736
 
  }
 
628
      open_cached_file(tempfile, mysql_tmpdir, TEMP_PREFIX, DISK_BUFFER_SIZE,
 
629
                       MYF(MY_WME)))
 
630
    goto err;                                   /* purecov: inspected */
737
631
  /* check we won't have more buffpeks than we can possibly keep in memory */
738
 
  if (my_b_tell(buffpek_pointers) + sizeof(buffpek) > (uint64_t)UINT_MAX)
739
 
  {
740
 
    return 1;
741
 
  }
742
 
 
 
632
  if (my_b_tell(buffpek_pointers) + sizeof(BUFFPEK) > (uint64_t)UINT_MAX)
 
633
    goto err;
743
634
  buffpek.file_pos= my_b_tell(tempfile);
744
 
  if ((ha_rows) count > max_rows)
745
 
    count=(uint32_t) max_rows;
746
 
 
 
635
  if ((ha_rows) count > param->max_rows)
 
636
    count=(uint) param->max_rows;               /* purecov: inspected */
747
637
  buffpek.count=(ha_rows) count;
748
 
 
749
 
  for (unsigned char **ptr= sort_keys + count ; sort_keys != ptr ; sort_keys++)
750
 
  {
751
 
    if (my_b_write(tempfile, (unsigned char*) *sort_keys, (uint32_t) rec_length))
752
 
    {
753
 
      return 1;
754
 
    }
755
 
  }
756
 
 
757
 
  if (my_b_write(buffpek_pointers, (unsigned char*) &buffpek, sizeof(buffpek)))
758
 
  {
759
 
    return 1;
760
 
  }
761
 
 
762
 
  return 0;
 
638
  for (end=sort_keys+count ; sort_keys != end ; sort_keys++)
 
639
    if (my_b_write(tempfile, (uchar*) *sort_keys, (uint) rec_length))
 
640
      goto err;
 
641
  if (my_b_write(buffpek_pointers, (uchar*) &buffpek, sizeof(buffpek)))
 
642
    goto err;
 
643
  return(0);
 
644
 
 
645
err:
 
646
  return(1);
763
647
} /* write_keys */
764
648
 
765
649
 
767
651
  Store length as suffix in high-byte-first order.
768
652
*/
769
653
 
770
 
static inline void store_length(unsigned char *to, uint32_t length, uint32_t pack_length)
 
654
static inline void store_length(uchar *to, uint length, uint pack_length)
771
655
{
772
656
  switch (pack_length) {
773
657
  case 1:
774
 
    *to= (unsigned char) length;
 
658
    *to= (uchar) length;
775
659
    break;
776
660
  case 2:
777
661
    mi_int2store(to, length);
788
672
 
789
673
/** Make a sort-key from record. */
790
674
 
791
 
void SortParam::make_sortkey(unsigned char *to, unsigned char *ref_pos)
 
675
static void make_sortkey(register SORTPARAM *param,
 
676
                         register uchar *to, uchar *ref_pos)
792
677
{
793
 
  Field *field;
794
 
  SortField *sort_field;
795
 
  size_t length;
 
678
  register Field *field;
 
679
  register SORT_FIELD *sort_field;
 
680
  register uint length;
796
681
 
797
 
  for (sort_field= local_sortorder ;
798
 
       sort_field != end ;
 
682
  for (sort_field=param->local_sortorder ;
 
683
       sort_field != param->end ;
799
684
       sort_field++)
800
685
  {
801
686
    bool maybe_null=0;
806
691
        if (field->is_null())
807
692
        {
808
693
          if (sort_field->reverse)
809
 
            memset(to, 255, sort_field->length+1);
 
694
            bfill(to,sort_field->length+1,(char) 255);
810
695
          else
811
 
            memset(to, 0, sort_field->length+1);
 
696
            bzero((char*) to,sort_field->length+1);
812
697
          to+= sort_field->length+1;
813
698
          continue;
814
699
        }
821
706
    {                                           // Item
822
707
      Item *item=sort_field->item;
823
708
      maybe_null= item->maybe_null;
824
 
 
825
709
      switch (sort_field->result_type) {
826
710
      case STRING_RESULT:
827
 
        {
828
 
          const CHARSET_INFO * const cs=item->collation.collation;
829
 
          char fill_char= ((cs->state & MY_CS_BINSORT) ? (char) 0 : ' ');
830
 
          int diff;
831
 
          uint32_t sort_field_length;
 
711
      {
 
712
        CHARSET_INFO *cs=item->collation.collation;
 
713
        char fill_char= ((cs->state & MY_CS_BINSORT) ? (char) 0 : ' ');
 
714
        int diff;
 
715
        uint sort_field_length;
832
716
 
 
717
        if (maybe_null)
 
718
          *to++=1;
 
719
        /* All item->str() to use some extra byte for end null.. */
 
720
        String tmp((char*) to,sort_field->length+4,cs);
 
721
        String *res= item->str_result(&tmp);
 
722
        if (!res)
 
723
        {
833
724
          if (maybe_null)
834
 
            *to++=1;
835
 
          /* All item->str() to use some extra byte for end null.. */
836
 
          String tmp((char*) to,sort_field->length+4,cs);
837
 
          String *res= item->str_result(&tmp);
838
 
          if (!res)
839
 
          {
840
 
            if (maybe_null)
841
 
              memset(to-1, 0, sort_field->length+1);
842
 
            else
843
 
            {
844
 
              /*
845
 
                This should only happen during extreme conditions if we run out
846
 
                of memory or have an item marked not null when it can be null.
847
 
                This code is here mainly to avoid a hard crash in this case.
848
 
              */
849
 
              assert(0);
850
 
              memset(to, 0, sort_field->length);        // Avoid crash
851
 
            }
852
 
            break;
853
 
          }
854
 
          length= res->length();
855
 
          sort_field_length= sort_field->length - sort_field->suffix_length;
856
 
          diff=(int) (sort_field_length - length);
857
 
          if (diff < 0)
858
 
          {
859
 
            diff=0;
860
 
            length= sort_field_length;
861
 
          }
862
 
          if (sort_field->suffix_length)
863
 
          {
864
 
            /* Store length last in result_string */
865
 
            store_length(to + sort_field_length, length,
866
 
                         sort_field->suffix_length);
867
 
          }
868
 
          if (sort_field->need_strxnfrm)
869
 
          {
870
 
            char *from=(char*) res->ptr();
871
 
            uint32_t tmp_length;
872
 
            if ((unsigned char*) from == to)
873
 
            {
874
 
              set_if_smaller(length,sort_field->length);
875
 
              memcpy(tmp_buffer,from,length);
876
 
              from= tmp_buffer;
877
 
            }
878
 
            tmp_length= my_strnxfrm(cs,to,sort_field->length,
879
 
                                    (unsigned char*) from, length);
880
 
            assert(tmp_length == sort_field->length);
881
 
          }
 
725
            bzero((char*) to-1,sort_field->length+1);
882
726
          else
883
727
          {
884
 
            my_strnxfrm(cs,(unsigned char*)to,length,(const unsigned char*)res->ptr(),length);
885
 
            cs->cset->fill(cs, (char *)to+length,diff,fill_char);
 
728
            /* purecov: begin deadcode */
 
729
            /*
 
730
              This should only happen during extreme conditions if we run out
 
731
              of memory or have an item marked not null when it can be null.
 
732
              This code is here mainly to avoid a hard crash in this case.
 
733
            */
 
734
            assert(0);
 
735
            bzero((char*) to,sort_field->length);       // Avoid crash
 
736
            /* purecov: end */
886
737
          }
887
738
          break;
888
739
        }
 
740
        length= res->length();
 
741
        sort_field_length= sort_field->length - sort_field->suffix_length;
 
742
        diff=(int) (sort_field_length - length);
 
743
        if (diff < 0)
 
744
        {
 
745
          diff=0;
 
746
          length= sort_field_length;
 
747
        }
 
748
        if (sort_field->suffix_length)
 
749
        {
 
750
          /* Store length last in result_string */
 
751
          store_length(to + sort_field_length, length,
 
752
                       sort_field->suffix_length);
 
753
        }
 
754
        if (sort_field->need_strxnfrm)
 
755
        {
 
756
          char *from=(char*) res->ptr();
 
757
          uint tmp_length;
 
758
          if ((uchar*) from == to)
 
759
          {
 
760
            set_if_smaller(length,sort_field->length);
 
761
            memcpy(param->tmp_buffer,from,length);
 
762
            from=param->tmp_buffer;
 
763
          }
 
764
          tmp_length= my_strnxfrm(cs,to,sort_field->length,
 
765
                                  (uchar*) from, length);
 
766
          assert(tmp_length == sort_field->length);
 
767
        }
 
768
        else
 
769
        {
 
770
          my_strnxfrm(cs,(uchar*)to,length,(const uchar*)res->ptr(),length);
 
771
          cs->cset->fill(cs, (char *)to+length,diff,fill_char);
 
772
        }
 
773
        break;
 
774
      }
889
775
      case INT_RESULT:
890
 
        {
 
776
        {
891
777
          int64_t value= item->val_int_result();
892
778
          if (maybe_null)
893
779
          {
894
 
            *to++=1;
 
780
            *to++=1;                            /* purecov: inspected */
895
781
            if (item->null_value)
896
782
            {
897
783
              if (maybe_null)
898
 
                memset(to-1, 0, sort_field->length+1);
 
784
                bzero((char*) to-1,sort_field->length+1);
899
785
              else
900
786
              {
901
 
                memset(to, 0, sort_field->length);
 
787
                bzero((char*) to,sort_field->length);
902
788
              }
903
789
              break;
904
790
            }
905
791
          }
906
 
          to[7]= (unsigned char) value;
907
 
          to[6]= (unsigned char) (value >> 8);
908
 
          to[5]= (unsigned char) (value >> 16);
909
 
          to[4]= (unsigned char) (value >> 24);
910
 
          to[3]= (unsigned char) (value >> 32);
911
 
          to[2]= (unsigned char) (value >> 40);
912
 
          to[1]= (unsigned char) (value >> 48);
913
 
          if (item->unsigned_flag)                    /* Fix sign */
914
 
            to[0]= (unsigned char) (value >> 56);
915
 
          else
916
 
            to[0]= (unsigned char) (value >> 56) ^ 128; /* Reverse signbit */
917
 
          break;
918
 
        }
 
792
#if SIZEOF_LONG_LONG > 4
 
793
          to[7]= (uchar) value;
 
794
          to[6]= (uchar) (value >> 8);
 
795
          to[5]= (uchar) (value >> 16);
 
796
          to[4]= (uchar) (value >> 24);
 
797
          to[3]= (uchar) (value >> 32);
 
798
          to[2]= (uchar) (value >> 40);
 
799
          to[1]= (uchar) (value >> 48);
 
800
          if (item->unsigned_flag)                    /* Fix sign */
 
801
            to[0]= (uchar) (value >> 56);
 
802
          else
 
803
            to[0]= (uchar) (value >> 56) ^ 128; /* Reverse signbit */
 
804
#else
 
805
          to[3]= (uchar) value;
 
806
          to[2]= (uchar) (value >> 8);
 
807
          to[1]= (uchar) (value >> 16);
 
808
          if (item->unsigned_flag)                    /* Fix sign */
 
809
            to[0]= (uchar) (value >> 24);
 
810
          else
 
811
            to[0]= (uchar) (value >> 24) ^ 128; /* Reverse signbit */
 
812
#endif
 
813
          break;
 
814
        }
919
815
      case DECIMAL_RESULT:
920
816
        {
921
 
          type::Decimal dec_buf, *dec_val= item->val_decimal_result(&dec_buf);
 
817
          my_decimal dec_buf, *dec_val= item->val_decimal_result(&dec_buf);
922
818
          if (maybe_null)
923
819
          {
924
820
            if (item->null_value)
925
 
            {
926
 
              memset(to, 0, sort_field->length+1);
 
821
            { 
 
822
              bzero((char*)to, sort_field->length+1);
927
823
              to++;
928
824
              break;
929
825
            }
930
826
            *to++=1;
931
827
          }
932
 
          dec_val->val_binary(E_DEC_FATAL_ERROR, to,
933
 
                              item->max_length - (item->decimals ? 1:0),
934
 
                              item->decimals);
935
 
          break;
 
828
          my_decimal2binary(E_DEC_FATAL_ERROR, dec_val, to,
 
829
                            item->max_length - (item->decimals ? 1:0),
 
830
                            item->decimals);
 
831
         break;
936
832
        }
937
833
      case REAL_RESULT:
938
 
        {
 
834
        {
939
835
          double value= item->val_result();
940
 
          if (maybe_null)
 
836
          if (maybe_null)
941
837
          {
942
838
            if (item->null_value)
943
839
            {
944
 
              memset(to, 0, sort_field->length+1);
 
840
              bzero((char*) to,sort_field->length+1);
945
841
              to++;
946
842
              break;
947
843
            }
948
 
            *to++=1;
 
844
            *to++=1;
949
845
          }
950
 
          change_double_for_sort(value,(unsigned char*) to);
951
 
          break;
952
 
        }
 
846
          change_double_for_sort(value,(uchar*) to);
 
847
          break;
 
848
        }
953
849
      case ROW_RESULT:
954
 
      default:
955
 
        // This case should never be choosen
956
 
        assert(0);
957
 
        break;
 
850
      default: 
 
851
        // This case should never be choosen
 
852
        assert(0);
 
853
        break;
958
854
      }
959
855
    }
960
 
 
961
856
    if (sort_field->reverse)
962
857
    {                                                   /* Revers key */
963
858
      if (maybe_null)
965
860
      length=sort_field->length;
966
861
      while (length--)
967
862
      {
968
 
        *to = (unsigned char) (~ *to);
 
863
        *to = (uchar) (~ *to);
969
864
        to++;
970
865
      }
971
866
    }
972
867
    else
973
 
    {
974
868
      to+= sort_field->length;
975
 
    }
976
869
  }
977
870
 
978
 
  if (addon_field)
 
871
  if (param->addon_field)
979
872
  {
980
 
    /*
 
873
    /* 
981
874
      Save field values appended to sorted fields.
982
875
      First null bit indicators are appended then field values follow.
983
876
      In this implementation we use fixed layout for field values -
984
877
      the same for all records.
985
878
    */
986
 
    sort_addon_field *addonf= addon_field;
987
 
    unsigned char *nulls= to;
 
879
    SORT_ADDON_FIELD *addonf= param->addon_field;
 
880
    uchar *nulls= to;
988
881
    assert(addonf != 0);
989
 
    memset(nulls, 0, addonf->offset);
 
882
    bzero((char *) nulls, addonf->offset);
990
883
    to+= addonf->offset;
991
884
    for ( ; (field= addonf->field) ; addonf++)
992
885
    {
993
886
      if (addonf->null_bit && field->is_null())
994
887
      {
995
888
        nulls[addonf->null_offset]|= addonf->null_bit;
996
 
#ifdef HAVE_VALGRIND
997
 
        memset(to, 0, addonf->length);
 
889
#ifdef HAVE_purify
 
890
        bzero(to, addonf->length);
998
891
#endif
999
892
      }
1000
893
      else
1001
894
      {
1002
 
#ifdef HAVE_VALGRIND
1003
 
        unsigned char *end= field->pack(to, field->ptr);
1004
 
        uint32_t local_length= (uint32_t) ((to + addonf->length) - end);
1005
 
        assert((int) local_length >= 0);
1006
 
        if (local_length)
1007
 
          memset(end, 0, local_length);
 
895
#ifdef HAVE_purify
 
896
        uchar *end= field->pack(to, field->ptr);
 
897
        uint length= (uint) ((to + addonf->length) - end);
 
898
        assert((int) length >= 0);
 
899
        if (length)
 
900
          bzero(end, length);
1008
901
#else
1009
902
        (void) field->pack(to, field->ptr);
1010
903
#endif
1015
908
  else
1016
909
  {
1017
910
    /* Save filepos last */
1018
 
    memcpy(to, ref_pos, (size_t) ref_length);
 
911
    memcpy((uchar*) to, ref_pos, (size_t) param->ref_length);
1019
912
  }
 
913
  return;
1020
914
}
1021
915
 
1022
916
 
1023
917
/*
1024
 
  fields used by sorting in the sorted table's read set
 
918
  Register fields used by sorting in the sorted table's read set
1025
919
*/
1026
920
 
1027
 
void SortParam::register_used_fields()
 
921
static void register_used_fields(SORTPARAM *param)
1028
922
{
1029
 
  SortField *sort_field;
1030
 
  Table *table= sort_form;
 
923
  register SORT_FIELD *sort_field;
 
924
  TABLE *table=param->sort_form;
 
925
  MY_BITMAP *bitmap= table->read_set;
1031
926
 
1032
 
  for (sort_field= local_sortorder ;
1033
 
       sort_field != end ;
 
927
  for (sort_field= param->local_sortorder ;
 
928
       sort_field != param->end ;
1034
929
       sort_field++)
1035
930
  {
1036
931
    Field *field;
1037
932
    if ((field= sort_field->field))
1038
933
    {
1039
 
      if (field->getTable() == table)
1040
 
        table->setReadSet(field->position());
 
934
      if (field->table == table)
 
935
      bitmap_set_bit(bitmap, field->field_index);
1041
936
    }
1042
937
    else
1043
938
    {                                           // Item
1044
939
      sort_field->item->walk(&Item::register_field_in_read_map, 1,
1045
 
                             (unsigned char *) table);
 
940
                             (uchar *) table);
1046
941
    }
1047
942
  }
1048
943
 
1049
 
  if (addon_field)
 
944
  if (param->addon_field)
1050
945
  {
1051
 
    sort_addon_field *addonf= addon_field;
 
946
    SORT_ADDON_FIELD *addonf= param->addon_field;
1052
947
    Field *field;
1053
948
    for ( ; (field= addonf->field) ; addonf++)
1054
 
      table->setReadSet(field->position());
 
949
      bitmap_set_bit(bitmap, field->field_index);
1055
950
  }
1056
951
  else
1057
952
  {
1061
956
}
1062
957
 
1063
958
 
1064
 
bool SortParam::save_index(unsigned char **sort_keys, uint32_t count, filesort_info *table_sort)
 
959
static bool save_index(SORTPARAM *param, uchar **sort_keys, uint count, 
 
960
                       FILESORT_INFO *table_sort)
1065
961
{
1066
 
  uint32_t offset;
1067
 
  unsigned char *to;
1068
 
 
1069
 
  internal::my_string_ptr_sort((unsigned char*) sort_keys, (uint32_t) count, sort_length);
1070
 
  offset= rec_length - res_length;
1071
 
 
1072
 
  if ((ha_rows) count > max_rows)
1073
 
    count=(uint32_t) max_rows;
1074
 
 
1075
 
  if (!(to= table_sort->record_pointers= (unsigned char*) malloc(res_length*count)))
1076
 
    return true;
1077
 
 
1078
 
  for (unsigned char **end_ptr= sort_keys+count ; sort_keys != end_ptr ; sort_keys++)
 
962
  uint offset,res_length;
 
963
  uchar *to;
 
964
 
 
965
  my_string_ptr_sort((uchar*) sort_keys, (uint) count, param->sort_length);
 
966
  res_length= param->res_length;
 
967
  offset= param->rec_length-res_length;
 
968
  if ((ha_rows) count > param->max_rows)
 
969
    count=(uint) param->max_rows;
 
970
  if (!(to= table_sort->record_pointers= 
 
971
        (uchar*) my_malloc(res_length*count, MYF(MY_WME))))
 
972
    return(1);                 /* purecov: inspected */
 
973
  for (uchar **end= sort_keys+count ; sort_keys != end ; sort_keys++)
1079
974
  {
1080
975
    memcpy(to, *sort_keys+offset, res_length);
1081
976
    to+= res_length;
1082
977
  }
1083
 
 
1084
 
  return false;
 
978
  return(0);
1085
979
}
1086
980
 
1087
981
 
1088
982
/** Merge buffers to make < MERGEBUFF2 buffers. */
1089
983
 
1090
 
int FileSort::merge_many_buff(SortParam *param, unsigned char *sort_buffer,
1091
 
                              buffpek *buffpek_inst, uint32_t *maxbuffer, internal::IO_CACHE *t_file)
 
984
int merge_many_buff(SORTPARAM *param, uchar *sort_buffer,
 
985
                    BUFFPEK *buffpek, uint *maxbuffer, IO_CACHE *t_file)
1092
986
{
1093
 
  internal::IO_CACHE t_file2,*from_file,*to_file,*temp;
1094
 
  buffpek *lastbuff;
 
987
  register uint i;
 
988
  IO_CACHE t_file2,*from_file,*to_file,*temp;
 
989
  BUFFPEK *lastbuff;
1095
990
 
1096
991
  if (*maxbuffer < MERGEBUFF2)
1097
 
    return 0;
 
992
    return(0);                          /* purecov: inspected */
1098
993
  if (flush_io_cache(t_file) ||
1099
 
      t_file2.open_cached_file(drizzle_tmpdir.c_str(),TEMP_PREFIX,DISK_BUFFER_SIZE, MYF(MY_WME)))
1100
 
  {
1101
 
    return 1;
1102
 
  }
 
994
      open_cached_file(&t_file2,mysql_tmpdir,TEMP_PREFIX,DISK_BUFFER_SIZE,
 
995
                        MYF(MY_WME)))
 
996
    return(1);                          /* purecov: inspected */
1103
997
 
1104
998
  from_file= t_file ; to_file= &t_file2;
1105
999
  while (*maxbuffer >= MERGEBUFF2)
1106
1000
  {
1107
 
    uint32_t i;
1108
 
 
1109
 
    if (from_file->reinit_io_cache(internal::READ_CACHE,0L,0,0))
1110
 
    {
1111
 
      break;
1112
 
    }
1113
 
 
1114
 
    if (to_file->reinit_io_cache(internal::WRITE_CACHE,0L,0,0))
1115
 
    {
1116
 
      break;
1117
 
    }
1118
 
 
1119
 
    lastbuff=buffpek_inst;
 
1001
    if (reinit_io_cache(from_file,READ_CACHE,0L,0,0))
 
1002
      goto cleanup;
 
1003
    if (reinit_io_cache(to_file,WRITE_CACHE,0L,0,0))
 
1004
      goto cleanup;
 
1005
    lastbuff=buffpek;
1120
1006
    for (i=0 ; i <= *maxbuffer-MERGEBUFF*3/2 ; i+=MERGEBUFF)
1121
1007
    {
1122
1008
      if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
1123
 
                        buffpek_inst+i,buffpek_inst+i+MERGEBUFF-1,0))
1124
 
      {
1125
 
        goto cleanup;
1126
 
      }
 
1009
                        buffpek+i,buffpek+i+MERGEBUFF-1,0))
 
1010
      goto cleanup;
1127
1011
    }
1128
 
 
1129
1012
    if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
1130
 
                      buffpek_inst+i,buffpek_inst+ *maxbuffer,0))
1131
 
    {
1132
 
      break;
1133
 
    }
1134
 
 
 
1013
                      buffpek+i,buffpek+ *maxbuffer,0))
 
1014
      break;                                    /* purecov: inspected */
1135
1015
    if (flush_io_cache(to_file))
1136
 
    {
1137
 
      break;
1138
 
    }
1139
 
 
 
1016
      break;                                    /* purecov: inspected */
1140
1017
    temp=from_file; from_file=to_file; to_file=temp;
1141
 
    from_file->setup_io_cache();
1142
 
    to_file->setup_io_cache();
1143
 
    *maxbuffer= (uint32_t) (lastbuff-buffpek_inst)-1;
 
1018
    setup_io_cache(from_file);
 
1019
    setup_io_cache(to_file);
 
1020
    *maxbuffer= (uint) (lastbuff-buffpek)-1;
1144
1021
  }
1145
 
 
1146
1022
cleanup:
1147
 
  to_file->close_cached_file();                 // This holds old result
 
1023
  close_cached_file(to_file);                   // This holds old result
1148
1024
  if (to_file == t_file)
1149
1025
  {
1150
1026
    *t_file=t_file2;                            // Copy result file
1151
 
    t_file->setup_io_cache();
 
1027
    setup_io_cache(t_file);
1152
1028
  }
1153
1029
 
1154
1030
  return(*maxbuffer >= MERGEBUFF2);     /* Return 1 if interrupted */
1159
1035
  Read data to buffer.
1160
1036
 
1161
1037
  @retval
1162
 
    (uint32_t)-1 if something goes wrong
 
1038
    (uint)-1 if something goes wrong
1163
1039
*/
1164
1040
 
1165
 
uint32_t FileSort::read_to_buffer(internal::IO_CACHE *fromfile, buffpek *buffpek_inst, uint32_t rec_length)
 
1041
uint read_to_buffer(IO_CACHE *fromfile, BUFFPEK *buffpek,
 
1042
                    uint rec_length)
1166
1043
{
1167
 
  uint32_t count;
1168
 
  uint32_t length;
 
1044
  register uint count;
 
1045
  uint length;
1169
1046
 
1170
 
  if ((count= (uint32_t) min((ha_rows) buffpek_inst->max_keys,buffpek_inst->count)))
 
1047
  if ((count=(uint) min((ha_rows) buffpek->max_keys,buffpek->count)))
1171
1048
  {
1172
 
    if (pread(fromfile->file,(unsigned char*) buffpek_inst->base, (length= rec_length*count),buffpek_inst->file_pos) == 0)
1173
 
      return((uint32_t) -1);
1174
 
 
1175
 
    buffpek_inst->key= buffpek_inst->base;
1176
 
    buffpek_inst->file_pos+= length;                    /* New filepos */
1177
 
    buffpek_inst->count-= count;
1178
 
    buffpek_inst->mem_count= count;
 
1049
    if (pread(fromfile->file,(uchar*) buffpek->base, (length= rec_length*count),buffpek->file_pos) == 0)
 
1050
      return((uint) -1);                        /* purecov: inspected */
 
1051
    buffpek->key=buffpek->base;
 
1052
    buffpek->file_pos+= length;                 /* New filepos */
 
1053
    buffpek->count-=    count;
 
1054
    buffpek->mem_count= count;
1179
1055
  }
1180
1056
  return (count*rec_length);
1181
1057
} /* read_to_buffer */
1182
1058
 
1183
1059
 
1184
 
class compare_functor
 
1060
/**
 
1061
  Put all room used by freed buffer to use in adjacent buffer.
 
1062
 
 
1063
  Note, that we can't simply distribute memory evenly between all buffers,
 
1064
  because new areas must not overlap with old ones.
 
1065
 
 
1066
  @param[in] queue      list of non-empty buffers, without freed buffer
 
1067
  @param[in] reuse      empty buffer
 
1068
  @param[in] key_length key length
 
1069
*/
 
1070
 
 
1071
void reuse_freed_buff(QUEUE *queue, BUFFPEK *reuse, uint key_length)
1185
1072
{
1186
 
  qsort2_cmp key_compare;
1187
 
  void *key_compare_arg;
1188
 
 
1189
 
  public:
1190
 
  compare_functor(qsort2_cmp in_key_compare, void *in_compare_arg) :
1191
 
    key_compare(in_key_compare),
1192
 
    key_compare_arg(in_compare_arg)
1193
 
  { }
1194
 
  
1195
 
  inline bool operator()(const buffpek *i, const buffpek *j) const
 
1073
  uchar *reuse_end= reuse->base + reuse->max_keys * key_length;
 
1074
  for (uint i= 0; i < queue->elements; ++i)
1196
1075
  {
1197
 
    int val= key_compare(key_compare_arg, &i->key, &j->key);
1198
 
 
1199
 
    return (val >= 0);
 
1076
    BUFFPEK *bp= (BUFFPEK *) queue_element(queue, i);
 
1077
    if (bp->base + bp->max_keys * key_length == reuse->base)
 
1078
    {
 
1079
      bp->max_keys+= reuse->max_keys;
 
1080
      return;
 
1081
    }
 
1082
    else if (bp->base == reuse_end)
 
1083
    {
 
1084
      bp->base= reuse->base;
 
1085
      bp->max_keys+= reuse->max_keys;
 
1086
      return;
 
1087
    }
1200
1088
  }
1201
 
};
 
1089
  assert(0);
 
1090
}
1202
1091
 
1203
1092
 
1204
1093
/**
1205
1094
  Merge buffers to one buffer.
1206
1095
 
1207
1096
  @param param        Sort parameter
1208
 
  @param from_file    File with source data (buffpeks point to this file)
 
1097
  @param from_file    File with source data (BUFFPEKs point to this file)
1209
1098
  @param to_file      File to write the sorted result data.
1210
1099
  @param sort_buffer  Buffer for data to store up to MERGEBUFF2 sort keys.
1211
 
  @param lastbuff     OUT Store here buffpek describing data written to to_file
1212
 
  @param Fb           First element in source buffpeks array
1213
 
  @param Tb           Last element in source buffpeks array
 
1100
  @param lastbuff     OUT Store here BUFFPEK describing data written to to_file
 
1101
  @param Fb           First element in source BUFFPEKs array
 
1102
  @param Tb           Last element in source BUFFPEKs array
1214
1103
  @param flag
1215
1104
 
1216
1105
  @retval
1219
1108
    other  error
1220
1109
*/
1221
1110
 
1222
 
int FileSort::merge_buffers(SortParam *param, internal::IO_CACHE *from_file,
1223
 
                            internal::IO_CACHE *to_file, unsigned char *sort_buffer,
1224
 
                            buffpek *lastbuff, buffpek *Fb, buffpek *Tb,
1225
 
                            int flag)
 
1111
int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
 
1112
                  IO_CACHE *to_file, uchar *sort_buffer,
 
1113
                  BUFFPEK *lastbuff, BUFFPEK *Fb, BUFFPEK *Tb,
 
1114
                  int flag)
1226
1115
{
1227
1116
  int error;
1228
 
  uint32_t rec_length,res_length,offset;
 
1117
  uint rec_length,res_length,offset;
1229
1118
  size_t sort_length;
1230
 
  uint32_t maxcount;
 
1119
  ulong maxcount;
1231
1120
  ha_rows max_rows,org_max_rows;
1232
 
  internal::my_off_t to_start_filepos;
1233
 
  unsigned char *strpos;
1234
 
  buffpek *buffpek_inst;
 
1121
  my_off_t to_start_filepos;
 
1122
  uchar *strpos;
 
1123
  BUFFPEK *buffpek;
 
1124
  QUEUE queue;
1235
1125
  qsort2_cmp cmp;
1236
1126
  void *first_cmp_arg;
1237
 
  volatile Session::killed_state_t *killed= getSession().getKilledPtr();
1238
 
  Session::killed_state_t not_killable;
 
1127
  volatile THD::killed_state *killed= &current_thd->killed;
 
1128
  THD::killed_state not_killable;
1239
1129
 
1240
 
  getSession().status_var.filesort_merge_passes++;
 
1130
  status_var_increment(current_thd->status_var.filesort_merge_passes);
1241
1131
  if (param->not_killable)
1242
1132
  {
1243
1133
    killed= &not_killable;
1244
 
    not_killable= Session::NOT_KILLED;
 
1134
    not_killable= THD::NOT_KILLED;
1245
1135
  }
1246
1136
 
1247
1137
  error=0;
1249
1139
  res_length= param->res_length;
1250
1140
  sort_length= param->sort_length;
1251
1141
  offset= rec_length-res_length;
1252
 
  maxcount= (uint32_t) (param->keys/((uint32_t) (Tb-Fb) +1));
 
1142
  maxcount= (ulong) (param->keys/((uint) (Tb-Fb) +1));
1253
1143
  to_start_filepos= my_b_tell(to_file);
1254
 
  strpos= (unsigned char*) sort_buffer;
 
1144
  strpos= (uchar*) sort_buffer;
1255
1145
  org_max_rows=max_rows= param->max_rows;
1256
1146
 
1257
1147
  /* The following will fire if there is not enough space in sort_buffer */
1258
1148
  assert(maxcount!=0);
1259
 
 
 
1149
  
1260
1150
  if (param->unique_buff)
1261
1151
  {
1262
1152
    cmp= param->compare;
1264
1154
  }
1265
1155
  else
1266
1156
  {
1267
 
    cmp= internal::get_ptr_compare(sort_length);
 
1157
    cmp= get_ptr_compare(sort_length);
1268
1158
    first_cmp_arg= (void*) &sort_length;
1269
1159
  }
1270
 
  priority_queue<buffpek *, vector<buffpek *>, compare_functor >
1271
 
    queue(compare_functor(cmp, first_cmp_arg));
1272
 
  for (buffpek_inst= Fb ; buffpek_inst <= Tb ; buffpek_inst++)
 
1160
  if (init_queue(&queue, (uint) (Tb-Fb)+1, offsetof(BUFFPEK,key), 0,
 
1161
                 (queue_compare) cmp, first_cmp_arg))
 
1162
    return(1);                                /* purecov: inspected */
 
1163
  for (buffpek= Fb ; buffpek <= Tb ; buffpek++)
1273
1164
  {
1274
 
    buffpek_inst->base= strpos;
1275
 
    buffpek_inst->max_keys= maxcount;
1276
 
    strpos+= (uint32_t) (error= (int) read_to_buffer(from_file, buffpek_inst,
 
1165
    buffpek->base= strpos;
 
1166
    buffpek->max_keys= maxcount;
 
1167
    strpos+= (uint) (error= (int) read_to_buffer(from_file, buffpek,
1277
1168
                                                                         rec_length));
1278
1169
    if (error == -1)
1279
 
      return -1;
1280
 
 
1281
 
    buffpek_inst->max_keys= buffpek_inst->mem_count;    // If less data in buffers than expected
1282
 
    queue.push(buffpek_inst);
 
1170
      goto err;                                 /* purecov: inspected */
 
1171
    buffpek->max_keys= buffpek->mem_count;      // If less data in buffers than expected
 
1172
    queue_insert(&queue, (uchar*) buffpek);
1283
1173
  }
1284
1174
 
1285
1175
  if (param->unique_buff)
1286
1176
  {
1287
 
    /*
 
1177
    /* 
1288
1178
       Called by Unique::get()
1289
1179
       Copy the first argument to param->unique_buff for unique removal.
1290
1180
       Store it also in 'to_file'.
1292
1182
       This is safe as we know that there is always more than one element
1293
1183
       in each block to merge (This is guaranteed by the Unique:: algorithm
1294
1184
    */
1295
 
    buffpek_inst= queue.top();
1296
 
    memcpy(param->unique_buff, buffpek_inst->key, rec_length);
1297
 
    if (my_b_write(to_file, (unsigned char*) buffpek_inst->key, rec_length))
 
1185
    buffpek= (BUFFPEK*) queue_top(&queue);
 
1186
    memcpy(param->unique_buff, buffpek->key, rec_length);
 
1187
    if (my_b_write(to_file, (uchar*) buffpek->key, rec_length))
1298
1188
    {
1299
 
      return 1;
 
1189
      error=1; goto err;                        /* purecov: inspected */
1300
1190
    }
1301
 
    buffpek_inst->key+= rec_length;
1302
 
    buffpek_inst->mem_count--;
 
1191
    buffpek->key+= rec_length;
 
1192
    buffpek->mem_count--;
1303
1193
    if (!--max_rows)
1304
1194
    {
1305
 
      error= 0;
1306
 
      goto end;
 
1195
      error= 0;                                       /* purecov: inspected */
 
1196
      goto end;                                       /* purecov: inspected */
1307
1197
    }
1308
 
    /* Top element has been used */
1309
 
    queue.pop();
1310
 
    queue.push(buffpek_inst);
 
1198
    queue_replaced(&queue);                        // Top element has been used
1311
1199
  }
1312
1200
  else
1313
 
  {
1314
1201
    cmp= 0;                                        // Not unique
1315
 
  }
1316
1202
 
1317
 
  while (queue.size() > 1)
 
1203
  while (queue.elements > 1)
1318
1204
  {
1319
1205
    if (*killed)
1320
1206
    {
1321
 
      return 1;
 
1207
      error= 1; goto err;                        /* purecov: inspected */
1322
1208
    }
1323
1209
    for (;;)
1324
1210
    {
1325
 
      buffpek_inst= queue.top();
 
1211
      buffpek= (BUFFPEK*) queue_top(&queue);
1326
1212
      if (cmp)                                        // Remove duplicates
1327
1213
      {
1328
1214
        if (!(*cmp)(first_cmp_arg, &(param->unique_buff),
1329
 
                    (unsigned char**) &buffpek_inst->key))
 
1215
                    (uchar**) &buffpek->key))
1330
1216
              goto skip_duplicate;
1331
 
            memcpy(param->unique_buff, buffpek_inst->key, rec_length);
 
1217
            memcpy(param->unique_buff, (uchar*) buffpek->key, rec_length);
1332
1218
      }
1333
1219
      if (flag == 0)
1334
1220
      {
1335
 
        if (my_b_write(to_file,(unsigned char*) buffpek_inst->key, rec_length))
 
1221
        if (my_b_write(to_file,(uchar*) buffpek->key, rec_length))
1336
1222
        {
1337
 
          return 1;
 
1223
          error=1; goto err;                        /* purecov: inspected */
1338
1224
        }
1339
1225
      }
1340
1226
      else
1341
1227
      {
1342
 
        if (my_b_write(to_file, (unsigned char*) buffpek_inst->key+offset, res_length))
 
1228
        if (my_b_write(to_file, (uchar*) buffpek->key+offset, res_length))
1343
1229
        {
1344
 
          return 1;
 
1230
          error=1; goto err;                        /* purecov: inspected */
1345
1231
        }
1346
1232
      }
1347
1233
      if (!--max_rows)
1348
1234
      {
1349
 
        error= 0;
1350
 
        goto end;
 
1235
        error= 0;                               /* purecov: inspected */
 
1236
        goto end;                               /* purecov: inspected */
1351
1237
      }
1352
1238
 
1353
1239
    skip_duplicate:
1354
 
      buffpek_inst->key+= rec_length;
1355
 
      if (! --buffpek_inst->mem_count)
 
1240
      buffpek->key+= rec_length;
 
1241
      if (! --buffpek->mem_count)
1356
1242
      {
1357
 
        if (!(error= (int) read_to_buffer(from_file,buffpek_inst,
 
1243
        if (!(error= (int) read_to_buffer(from_file,buffpek,
1358
1244
                                          rec_length)))
1359
1245
        {
1360
 
          queue.pop();
 
1246
          VOID(queue_remove(&queue,0));
 
1247
          reuse_freed_buff(&queue, buffpek, rec_length);
1361
1248
          break;                        /* One buffer have been removed */
1362
1249
        }
1363
1250
        else if (error == -1)
1364
 
        {
1365
 
          return -1;
1366
 
        }
 
1251
          goto err;                        /* purecov: inspected */
1367
1252
      }
1368
 
      /* Top element has been replaced */
1369
 
      queue.pop();
1370
 
      queue.push(buffpek_inst);
 
1253
      queue_replaced(&queue);              /* Top element has been replaced */
1371
1254
    }
1372
1255
  }
1373
 
  buffpek_inst= queue.top();
1374
 
  buffpek_inst->base= sort_buffer;
1375
 
  buffpek_inst->max_keys= param->keys;
 
1256
  buffpek= (BUFFPEK*) queue_top(&queue);
 
1257
  buffpek->base= sort_buffer;
 
1258
  buffpek->max_keys= param->keys;
1376
1259
 
1377
1260
  /*
1378
1261
    As we know all entries in the buffer are unique, we only have to
1380
1263
  */
1381
1264
  if (cmp)
1382
1265
  {
1383
 
    if (!(*cmp)(first_cmp_arg, &(param->unique_buff), (unsigned char**) &buffpek_inst->key))
 
1266
    if (!(*cmp)(first_cmp_arg, &(param->unique_buff), (uchar**) &buffpek->key))
1384
1267
    {
1385
 
      buffpek_inst->key+= rec_length;         // Remove duplicate
1386
 
      --buffpek_inst->mem_count;
 
1268
      buffpek->key+= rec_length;         // Remove duplicate
 
1269
      --buffpek->mem_count;
1387
1270
    }
1388
1271
  }
1389
1272
 
1390
1273
  do
1391
1274
  {
1392
 
    if ((ha_rows) buffpek_inst->mem_count > max_rows)
 
1275
    if ((ha_rows) buffpek->mem_count > max_rows)
1393
1276
    {                                        /* Don't write too many records */
1394
 
      buffpek_inst->mem_count= (uint32_t) max_rows;
1395
 
      buffpek_inst->count= 0;                        /* Don't read more */
 
1277
      buffpek->mem_count= (uint) max_rows;
 
1278
      buffpek->count= 0;                        /* Don't read more */
1396
1279
    }
1397
 
    max_rows-= buffpek_inst->mem_count;
 
1280
    max_rows-= buffpek->mem_count;
1398
1281
    if (flag == 0)
1399
1282
    {
1400
 
      if (my_b_write(to_file,(unsigned char*) buffpek_inst->key,
1401
 
                     (rec_length*buffpek_inst->mem_count)))
 
1283
      if (my_b_write(to_file,(uchar*) buffpek->key,
 
1284
                     (rec_length*buffpek->mem_count)))
1402
1285
      {
1403
 
        return 1;
 
1286
        error= 1; goto err;                        /* purecov: inspected */
1404
1287
      }
1405
1288
    }
1406
1289
    else
1407
1290
    {
1408
 
      unsigned char *end;
1409
 
      strpos= buffpek_inst->key+offset;
1410
 
      for (end= strpos+buffpek_inst->mem_count*rec_length ;
 
1291
      register uchar *end;
 
1292
      strpos= buffpek->key+offset;
 
1293
      for (end= strpos+buffpek->mem_count*rec_length ;
1411
1294
           strpos != end ;
1412
1295
           strpos+= rec_length)
1413
 
      {
1414
 
        if (my_b_write(to_file, (unsigned char *) strpos, res_length))
 
1296
      {     
 
1297
        if (my_b_write(to_file, (uchar *) strpos, res_length))
1415
1298
        {
1416
 
          return 1;
 
1299
          error=1; goto err;                        
1417
1300
        }
1418
1301
      }
1419
1302
    }
1420
1303
  }
1421
 
 
1422
 
  while ((error=(int) read_to_buffer(from_file,buffpek_inst, rec_length))
 
1304
  while ((error=(int) read_to_buffer(from_file,buffpek, rec_length))
1423
1305
         != -1 && error != 0);
1424
1306
 
1425
1307
end:
1426
1308
  lastbuff->count= min(org_max_rows-max_rows, param->max_rows);
1427
1309
  lastbuff->file_pos= to_start_filepos;
1428
 
 
1429
 
  return error;
 
1310
err:
 
1311
  delete_queue(&queue);
 
1312
  return(error);
1430
1313
} /* merge_buffers */
1431
1314
 
1432
1315
 
1433
1316
        /* Do a merge to output-file (save only positions) */
1434
1317
 
1435
 
int FileSort::merge_index(SortParam *param, unsigned char *sort_buffer,
1436
 
                          buffpek *buffpek_inst, uint32_t maxbuffer,
1437
 
                          internal::IO_CACHE *tempfile, internal::IO_CACHE *outfile)
 
1318
static int merge_index(SORTPARAM *param, uchar *sort_buffer,
 
1319
                       BUFFPEK *buffpek, uint maxbuffer,
 
1320
                       IO_CACHE *tempfile, IO_CACHE *outfile)
1438
1321
{
1439
 
  if (merge_buffers(param,tempfile,outfile,sort_buffer,buffpek_inst,buffpek_inst,
1440
 
                    buffpek_inst+maxbuffer,1))
1441
 
    return 1;
1442
 
 
1443
 
  return 0;
 
1322
  if (merge_buffers(param,tempfile,outfile,sort_buffer,buffpek,buffpek,
 
1323
                    buffpek+maxbuffer,1))
 
1324
    return(1);                          /* purecov: inspected */
 
1325
  return(0);
1444
1326
} /* merge_index */
1445
1327
 
1446
1328
 
1447
 
static uint32_t suffix_length(uint32_t string_length)
 
1329
static uint suffix_length(ulong string_length)
1448
1330
{
1449
1331
  if (string_length < 256)
1450
1332
    return 1;
1460
1342
/**
1461
1343
  Calculate length of sort key.
1462
1344
 
 
1345
  @param thd                      Thread handler
1463
1346
  @param sortorder                Order of items to sort
1464
1347
  @param s_length                 Number of items to sort
1465
1348
  @param[out] multi_byte_charset Set to 1 if we are using multi-byte charset
1474
1357
    Total length of sort buffer in bytes
1475
1358
*/
1476
1359
 
1477
 
uint32_t FileSort::sortlength(SortField *sortorder, uint32_t s_length, bool *multi_byte_charset)
 
1360
static uint
 
1361
sortlength(THD *thd, SORT_FIELD *sortorder, uint s_length,
 
1362
           bool *multi_byte_charset)
1478
1363
{
1479
 
  uint32_t length;
1480
 
  const CHARSET_INFO *cs;
 
1364
  register uint length;
 
1365
  CHARSET_INFO *cs;
1481
1366
  *multi_byte_charset= 0;
1482
1367
 
1483
1368
  length=0;
1504
1389
      sortorder->result_type= sortorder->item->result_type();
1505
1390
      if (sortorder->item->result_as_int64_t())
1506
1391
        sortorder->result_type= INT_RESULT;
1507
 
 
1508
1392
      switch (sortorder->result_type) {
1509
1393
      case STRING_RESULT:
1510
 
        sortorder->length=sortorder->item->max_length;
1511
 
        set_if_smaller(sortorder->length,
1512
 
                       getSession().variables.max_sort_length);
1513
 
        if (use_strnxfrm((cs=sortorder->item->collation.collation)))
1514
 
        {
 
1394
        sortorder->length=sortorder->item->max_length;
 
1395
        set_if_smaller(sortorder->length, thd->variables.max_sort_length);
 
1396
        if (use_strnxfrm((cs=sortorder->item->collation.collation)))
 
1397
        { 
1515
1398
          sortorder->length= cs->coll->strnxfrmlen(cs, sortorder->length);
1516
 
          sortorder->need_strxnfrm= 1;
1517
 
          *multi_byte_charset= 1;
1518
 
        }
 
1399
          sortorder->need_strxnfrm= 1;
 
1400
          *multi_byte_charset= 1;
 
1401
        }
1519
1402
        else if (cs == &my_charset_bin)
1520
1403
        {
1521
1404
          /* Store length last to be able to sort blob/varbinary */
1522
1405
          sortorder->suffix_length= suffix_length(sortorder->length);
1523
1406
          sortorder->length+= sortorder->suffix_length;
1524
1407
        }
1525
 
        break;
 
1408
        break;
1526
1409
      case INT_RESULT:
1527
 
        sortorder->length=8;                    // Size of intern int64_t
1528
 
        break;
 
1410
#if SIZEOF_LONG_LONG > 4
 
1411
        sortorder->length=8;                    // Size of intern int64_t
 
1412
#else
 
1413
        sortorder->length=4;
 
1414
#endif
 
1415
        break;
1529
1416
      case DECIMAL_RESULT:
1530
1417
        sortorder->length=
1531
 
          class_decimal_get_binary_size(sortorder->item->max_length -
 
1418
          my_decimal_get_binary_size(sortorder->item->max_length - 
1532
1419
                                     (sortorder->item->decimals ? 1 : 0),
1533
1420
                                     sortorder->item->decimals);
1534
1421
        break;
1535
1422
      case REAL_RESULT:
1536
 
        sortorder->length=sizeof(double);
1537
 
        break;
 
1423
        sortorder->length=sizeof(double);
 
1424
        break;
1538
1425
      case ROW_RESULT:
1539
 
        // This case should never be choosen
1540
 
        assert(0);
1541
 
        break;
 
1426
      default: 
 
1427
        // This case should never be choosen
 
1428
        assert(0);
 
1429
        break;
1542
1430
      }
1543
1431
      if (sortorder->item->maybe_null)
1544
 
        length++;                               // Place for NULL marker
 
1432
        length++;                               // Place for NULL marker
1545
1433
    }
1546
 
    set_if_smaller(sortorder->length, (size_t)getSession().variables.max_sort_length);
 
1434
    set_if_smaller(sortorder->length, thd->variables.max_sort_length);
1547
1435
    length+=sortorder->length;
1548
1436
  }
1549
1437
  sortorder->field= (Field*) 0;                 // end marker
1557
1445
 
1558
1446
  The function first finds out what fields are used in the result set.
1559
1447
  Then it calculates the length of the buffer to store the values of
1560
 
  these fields together with the value of sort values.
 
1448
  these fields together with the value of sort values. 
1561
1449
  If the calculated length is not greater than max_length_for_sort_data
1562
1450
  the function allocates memory for an array of descriptors containing
1563
1451
  layouts for the values of the non-sorted fields in the buffer and
1564
1452
  fills them.
1565
1453
 
 
1454
  @param thd                 Current thread
1566
1455
  @param ptabfield           Array of references to the table fields
1567
1456
  @param sortlength          Total length of sorted fields
1568
1457
  @param[out] plength        Total length of appended fields
1577
1466
    NULL   if we do not store field values with sort data.
1578
1467
*/
1579
1468
 
1580
 
sort_addon_field *FileSort::get_addon_fields(Field **ptabfield, uint32_t sortlength_arg, uint32_t *plength)
 
1469
static SORT_ADDON_FIELD *
 
1470
get_addon_fields(THD *thd, Field **ptabfield, uint sortlength, uint *plength)
1581
1471
{
1582
1472
  Field **pfield;
1583
1473
  Field *field;
1584
 
  sort_addon_field *addonf;
1585
 
  uint32_t length= 0;
1586
 
  uint32_t fields= 0;
1587
 
  uint32_t null_fields= 0;
 
1474
  SORT_ADDON_FIELD *addonf;
 
1475
  uint length= 0;
 
1476
  uint fields= 0;
 
1477
  uint null_fields= 0;
 
1478
  MY_BITMAP *read_set= (*ptabfield)->table->read_set;
1588
1479
 
1589
1480
  /*
1590
1481
    If there is a reference to a field in the query add it
1592
1483
    Note for future refinement:
1593
1484
    This this a too strong condition.
1594
1485
    Actually we need only the fields referred in the
1595
 
    result set. And for some of them it makes sense to use
 
1486
    result set. And for some of them it makes sense to use 
1596
1487
    the values directly from sorted fields.
1597
1488
  */
1598
1489
  *plength= 0;
1599
1490
 
1600
1491
  for (pfield= ptabfield; (field= *pfield) ; pfield++)
1601
1492
  {
1602
 
    if (!(field->isReadSet()))
 
1493
    if (!bitmap_is_set(read_set, field->field_index))
1603
1494
      continue;
1604
1495
    if (field->flags & BLOB_FLAG)
1605
1496
      return 0;
1607
1498
    if (field->maybe_null())
1608
1499
      null_fields++;
1609
1500
    fields++;
1610
 
  }
 
1501
  } 
1611
1502
  if (!fields)
1612
1503
    return 0;
1613
1504
  length+= (null_fields+7)/8;
1614
1505
 
1615
 
  if (length+sortlength_arg > getSession().variables.max_length_for_sort_data ||
1616
 
      !(addonf= (sort_addon_field *) malloc(sizeof(sort_addon_field)*
1617
 
                                            (fields+1))))
 
1506
  if (length+sortlength > thd->variables.max_length_for_sort_data ||
 
1507
      !(addonf= (SORT_ADDON_FIELD *) my_malloc(sizeof(SORT_ADDON_FIELD)*
 
1508
                                               (fields+1), MYF(MY_WME))))
1618
1509
    return 0;
1619
1510
 
1620
1511
  *plength= length;
1622
1513
  null_fields= 0;
1623
1514
  for (pfield= ptabfield; (field= *pfield) ; pfield++)
1624
1515
  {
1625
 
    if (!(field->isReadSet()))
 
1516
    if (!bitmap_is_set(read_set, field->field_index))
1626
1517
      continue;
1627
1518
    addonf->field= field;
1628
1519
    addonf->offset= length;
1642
1533
    addonf++;
1643
1534
  }
1644
1535
  addonf->field= 0;     // Put end marker
1645
 
 
 
1536
  
1646
1537
  return (addonf-fields);
1647
1538
}
1648
1539
 
1662
1553
    void.
1663
1554
*/
1664
1555
 
1665
 
static void
1666
 
unpack_addon_fields(sort_addon_field *addon_field, unsigned char *buff)
 
1556
static void 
 
1557
unpack_addon_fields(struct st_sort_addon_field *addon_field, uchar *buff)
1667
1558
{
1668
1559
  Field *field;
1669
 
  sort_addon_field *addonf= addon_field;
 
1560
  SORT_ADDON_FIELD *addonf= addon_field;
1670
1561
 
1671
1562
  for ( ; (field= addonf->field) ; addonf++)
1672
1563
  {
1687
1578
 
1688
1579
#define DBL_EXP_DIG (sizeof(double)*8-DBL_MANT_DIG)
1689
1580
 
1690
 
void change_double_for_sort(double nr,unsigned char *to)
 
1581
void change_double_for_sort(double nr,uchar *to)
1691
1582
{
1692
 
  unsigned char *tmp=(unsigned char*) to;
 
1583
  uchar *tmp=(uchar*) to;
1693
1584
  if (nr == 0.0)
1694
1585
  {                                             /* Change to zero string */
1695
 
    tmp[0]=(unsigned char) 128;
1696
 
    memset(tmp+1, 0, sizeof(nr)-1);
 
1586
    tmp[0]=(uchar) 128;
 
1587
    bzero((char*) tmp+1,sizeof(nr)-1);
1697
1588
  }
1698
1589
  else
1699
1590
  {
1700
1591
#ifdef WORDS_BIGENDIAN
1701
 
    memcpy(tmp,&nr,sizeof(nr));
 
1592
    memcpy_fixed(tmp,&nr,sizeof(nr));
1702
1593
#else
1703
1594
    {
1704
 
      unsigned char *ptr= (unsigned char*) &nr;
 
1595
      uchar *ptr= (uchar*) &nr;
1705
1596
#if defined(__FLOAT_WORD_ORDER) && (__FLOAT_WORD_ORDER == __BIG_ENDIAN)
1706
1597
      tmp[0]= ptr[3]; tmp[1]=ptr[2]; tmp[2]= ptr[1]; tmp[3]=ptr[0];
1707
1598
      tmp[4]= ptr[7]; tmp[5]=ptr[6]; tmp[6]= ptr[5]; tmp[7]=ptr[4];
1713
1604
#endif
1714
1605
    if (tmp[0] & 128)                           /* Negative */
1715
1606
    {                                           /* make complement */
1716
 
      uint32_t i;
 
1607
      uint i;
1717
1608
      for (i=0 ; i < sizeof(nr); i++)
1718
 
        tmp[i]=tmp[i] ^ (unsigned char) 255;
 
1609
        tmp[i]=tmp[i] ^ (uchar) 255;
1719
1610
    }
1720
1611
    else
1721
1612
    {                                   /* Set high and move exponent one up */
1722
 
      uint16_t exp_part=(((uint16_t) tmp[0] << 8) | (uint16_t) tmp[1] |
1723
 
                       (uint16_t) 32768);
1724
 
      exp_part+= (uint16_t) 1 << (16-1-DBL_EXP_DIG);
1725
 
      tmp[0]= (unsigned char) (exp_part >> 8);
1726
 
      tmp[1]= (unsigned char) exp_part;
 
1613
      ushort exp_part=(((ushort) tmp[0] << 8) | (ushort) tmp[1] |
 
1614
                       (ushort) 32768);
 
1615
      exp_part+= (ushort) 1 << (16-1-DBL_EXP_DIG);
 
1616
      tmp[0]= (uchar) (exp_part >> 8);
 
1617
      tmp[1]= (uchar) exp_part;
1727
1618
    }
1728
1619
  }
1729
1620
}
1730
 
 
1731
 
} /* namespace drizzled */