← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/filesort.cc

  • Committer: Monty Taylor
  • Date: 2008-11-16 23:47:43 UTC
  • mto: (584.1.10 devel)
  • mto: This revision was merged to the branch mainline in revision 589.
  • Revision ID: monty@inaugust.com-20081116234743-c38gmv0pa2kdefaj
Broke out cached_item.

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
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
 
 
32
 
#include "drizzled/sql_sort.h"
33
 
#include "drizzled/error.h"
34
 
#include "drizzled/probes.h"
35
 
#include "drizzled/session.h"
36
 
#include "drizzled/table.h"
37
 
#include "drizzled/table_list.h"
38
 
#include "drizzled/optimizer/range.h"
39
 
#include "drizzled/records.h"
40
 
#include "drizzled/internal/iocache.h"
41
 
#include "drizzled/internal/my_sys.h"
42
 
#include "plugin/myisam/myisam.h"
43
 
#include "drizzled/plugin/transactional_storage_engine.h"
44
 
 
45
 
using namespace std;
46
 
 
47
 
namespace drizzled
48
 
{
 
24
#include <drizzled/server_includes.h>
 
25
#include "sql_sort.h"
 
26
#include <drizzled/error.h>
 
27
#include <drizzled/probes.h>
49
28
 
50
29
/* functions defined in this file */
51
30
 
52
31
static char **make_char_array(char **old_pos, register uint32_t fields,
53
 
                              uint32_t length);
54
 
 
55
 
static unsigned char *read_buffpek_from_file(internal::IO_CACHE *buffer_file,
56
 
                                             uint32_t count,
57
 
                                             unsigned char *buf);
58
 
 
59
 
static ha_rows find_all_keys(SORTPARAM *param,
60
 
                             optimizer::SqlSelect *select,
61
 
                             unsigned char * *sort_keys, 
62
 
                             internal::IO_CACHE *buffer_file,
63
 
                             internal::IO_CACHE *tempfile,
64
 
                             internal::IO_CACHE *indexfile);
65
 
 
66
 
static int write_keys(SORTPARAM *param,
67
 
                      unsigned char * *sort_keys,
68
 
                      uint32_t count,
69
 
                      internal::IO_CACHE *buffer_file,
70
 
                      internal::IO_CACHE *tempfile);
71
 
 
72
 
static void make_sortkey(SORTPARAM *param,
73
 
                         unsigned char *to,
74
 
                         unsigned char *ref_pos);
 
32
                              uint32_t length, myf my_flag);
 
33
static unsigned char *read_buffpek_from_file(IO_CACHE *buffer_file, uint32_t count,
 
34
                                     unsigned char *buf);
 
35
static ha_rows find_all_keys(SORTPARAM *param,SQL_SELECT *select,
 
36
                             unsigned char * *sort_keys, IO_CACHE *buffer_file,
 
37
                             IO_CACHE *tempfile,IO_CACHE *indexfile);
 
38
static int write_keys(SORTPARAM *param,unsigned char * *sort_keys,
 
39
                      uint32_t count, IO_CACHE *buffer_file, IO_CACHE *tempfile);
 
40
static void make_sortkey(SORTPARAM *param,unsigned char *to, unsigned char *ref_pos);
75
41
static void register_used_fields(SORTPARAM *param);
76
 
static int merge_index(SORTPARAM *param,
77
 
                       unsigned char *sort_buffer,
 
42
static int merge_index(SORTPARAM *param,unsigned char *sort_buffer,
78
43
                       BUFFPEK *buffpek,
79
 
                       uint32_t maxbuffer,
80
 
                       internal::IO_CACHE *tempfile,
81
 
                       internal::IO_CACHE *outfile);
82
 
static bool save_index(SORTPARAM *param,
83
 
                       unsigned char **sort_keys,
84
 
                       uint32_t count,
 
44
                       uint32_t maxbuffer,IO_CACHE *tempfile,
 
45
                       IO_CACHE *outfile);
 
46
static bool save_index(SORTPARAM *param,unsigned char **sort_keys, uint32_t count, 
85
47
                       filesort_info_st *table_sort);
86
48
static uint32_t suffix_length(uint32_t string_length);
87
 
static uint32_t sortlength(Session *session,
88
 
                           SORT_FIELD *sortorder,
89
 
                           uint32_t s_length,
90
 
                           bool *multi_byte_charset);
91
 
static SORT_ADDON_FIELD *get_addon_fields(Session *session,
92
 
                                          Field **ptabfield,
93
 
                                          uint32_t sortlength,
94
 
                                          uint32_t *plength);
 
49
static uint32_t sortlength(Session *session, SORT_FIELD *sortorder, uint32_t s_length,
 
50
                       bool *multi_byte_charset);
 
51
static SORT_ADDON_FIELD *get_addon_fields(Session *session, Field **ptabfield,
 
52
                                          uint32_t sortlength, uint32_t *plength);
95
53
static void unpack_addon_fields(struct st_sort_addon_field *addon_field,
96
54
                                unsigned char *buff);
97
55
/**
131
89
*/
132
90
 
133
91
ha_rows filesort(Session *session, Table *table, SORT_FIELD *sortorder, uint32_t s_length,
134
 
                 optimizer::SqlSelect *select, ha_rows max_rows,
 
92
                 SQL_SELECT *select, ha_rows max_rows,
135
93
                 bool sort_positions, ha_rows *examined_rows)
136
94
{
137
95
  int error;
140
98
  BUFFPEK *buffpek;
141
99
  ha_rows records= HA_POS_ERROR;
142
100
  unsigned char **sort_keys= 0;
143
 
  internal::IO_CACHE tempfile, buffpek_pointers, *selected_records_file, *outfile;
 
101
  IO_CACHE tempfile, buffpek_pointers, *selected_records_file, *outfile; 
144
102
  SORTPARAM param;
145
103
  bool multi_byte_charset;
146
104
 
148
106
  TableList *tab= table->pos_in_table_list;
149
107
  Item_subselect *subselect= tab ? tab->containing_subselect() : 0;
150
108
 
151
 
  DRIZZLE_FILESORT_START(table->s->getSchemaName(), table->s->getTableName());
 
109
  DRIZZLE_FILESORT_START();
152
110
 
153
111
  /*
154
112
   Release InnoDB's adaptive hash index latch (if holding) before
155
113
   running a sort.
156
114
  */
157
 
  plugin::TransactionalStorageEngine::releaseTemporaryLatches(session);
 
115
  ha_release_temporary_latches(session);
158
116
 
159
 
  /*
160
 
    Don't use table->sort in filesort as it is also used by
161
 
    QuickIndexMergeSelect. Work with a copy and put it back at the end
 
117
  /* 
 
118
    Don't use table->sort in filesort as it is also used by 
 
119
    QUICK_INDEX_MERGE_SELECT. Work with a copy and put it back at the end 
162
120
    when index_merge select has finished with it.
163
121
  */
164
122
  memcpy(&table_sort, &table->sort, sizeof(filesort_info_st));
165
123
  table->sort.io_cache= NULL;
166
 
 
 
124
  
167
125
  outfile= table_sort.io_cache;
168
126
  my_b_clear(&tempfile);
169
127
  my_b_clear(&buffpek_pointers);
171
129
  error= 1;
172
130
  memset(&param, 0, sizeof(param));
173
131
  param.sort_length= sortlength(session, sortorder, s_length, &multi_byte_charset);
174
 
  param.ref_length= table->cursor->ref_length;
 
132
  param.ref_length= table->file->ref_length;
175
133
  param.addon_field= 0;
176
134
  param.addon_length= 0;
177
 
  if (!(table->cursor->getEngine()->check_flag(HTON_BIT_FAST_KEY_READ)) && !sort_positions)
 
135
  if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) && !sort_positions)
178
136
  {
179
 
    /*
180
 
      Get the descriptors of all fields whose values are appended
 
137
    /* 
 
138
      Get the descriptors of all fields whose values are appended 
181
139
      to sorted fields and get its total length in param.spack_length.
182
140
    */
183
 
    param.addon_field= get_addon_fields(session, table->field,
 
141
    param.addon_field= get_addon_fields(session, table->field, 
184
142
                                        param.sort_length,
185
143
                                        &param.addon_length);
186
144
  }
192
150
  if (param.addon_field)
193
151
  {
194
152
    param.res_length= param.addon_length;
195
 
    if (!(table_sort.addon_buf= (unsigned char *) malloc(param.addon_length)))
 
153
    if (!(table_sort.addon_buf= (unsigned char *) my_malloc(param.addon_length,
 
154
                                                    MYF(MY_WME))))
196
155
      goto err;
197
156
  }
198
157
  else
199
158
  {
200
159
    param.res_length= param.ref_length;
201
 
    /*
202
 
      The reference to the record is considered
 
160
    /* 
 
161
      The reference to the record is considered 
203
162
      as an additional sorted field
204
163
    */
205
164
    param.sort_length+= param.ref_length;
218
177
#ifdef CAN_TRUST_RANGE
219
178
  if (select && select->quick && select->quick->records > 0L)
220
179
  {
221
 
    records= min((ha_rows) (select->quick->records*2+EXTRA_RECORDS*2),
222
 
                 table->cursor->stats.records)+EXTRA_RECORDS;
 
180
    records=cmin((ha_rows) (select->quick->records*2+EXTRA_RECORDS*2),
 
181
                table->file->stats.records)+EXTRA_RECORDS;
223
182
    selected_records_file=0;
224
183
  }
225
184
  else
226
185
#endif
227
186
  {
228
 
    records= table->cursor->estimate_rows_upper_bound();
 
187
    records= table->file->estimate_rows_upper_bound();
229
188
    /*
230
 
      If number of records is not known, use as much of sort buffer
231
 
      as possible.
 
189
      If number of records is not known, use as much of sort buffer 
 
190
      as possible. 
232
191
    */
233
192
    if (records == HA_POS_ERROR)
234
193
      records--;  // we use 'records+1' below.
236
195
  }
237
196
 
238
197
  if (multi_byte_charset &&
239
 
      !(param.tmp_buffer= (char*) malloc(param.sort_length)))
 
198
      !(param.tmp_buffer= (char*) my_malloc(param.sort_length,MYF(MY_WME))))
240
199
    goto err;
241
200
 
242
201
  memavl= session->variables.sortbuff_size;
243
 
  min_sort_memory= max((uint32_t)MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2);
 
202
  min_sort_memory= cmax((uint32_t)MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2);
244
203
  while (memavl >= min_sort_memory)
245
204
  {
246
205
    uint32_t old_memavl;
247
206
    uint32_t keys= memavl/(param.rec_length+sizeof(char*));
248
 
    param.keys= (uint32_t) min(records+1, (ha_rows)keys);
 
207
    param.keys=(uint32_t) cmin(records+1, keys);
249
208
    if ((table_sort.sort_keys=
250
209
         (unsigned char **) make_char_array((char **) table_sort.sort_keys,
251
 
                                            param.keys, param.rec_length)))
 
210
                                    param.keys, param.rec_length, MYF(0))))
252
211
      break;
253
 
    old_memavl= memavl;
254
 
    if ((memavl= memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
 
212
    old_memavl=memavl;
 
213
    if ((memavl=memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
255
214
      memavl= min_sort_memory;
256
215
  }
257
216
  sort_keys= table_sort.sort_keys;
298
257
        open_cached_file(outfile,drizzle_tmpdir,TEMP_PREFIX,READ_RECORD_BUFFER,
299
258
                          MYF(MY_WME)))
300
259
      goto err;
301
 
    if (reinit_io_cache(outfile,internal::WRITE_CACHE,0L,0,0))
 
260
    if (reinit_io_cache(outfile,WRITE_CACHE,0L,0,0))
302
261
      goto err;
303
262
 
304
263
    /*
312
271
                        &tempfile))
313
272
      goto err;
314
273
    if (flush_io_cache(&tempfile) ||
315
 
        reinit_io_cache(&tempfile,internal::READ_CACHE,0L,0,0))
 
274
        reinit_io_cache(&tempfile,READ_CACHE,0L,0,0))
316
275
      goto err;
317
276
    if (merge_index(&param,(unsigned char*) sort_keys,buffpek,maxbuffer,&tempfile,
318
277
                    outfile))
343
302
    if (flush_io_cache(outfile))
344
303
      error=1;
345
304
    {
346
 
      internal::my_off_t save_pos=outfile->pos_in_file;
 
305
      my_off_t save_pos=outfile->pos_in_file;
347
306
      /* For following reads */
348
 
      if (reinit_io_cache(outfile,internal::READ_CACHE,0L,0,0))
 
307
      if (reinit_io_cache(outfile,READ_CACHE,0L,0,0))
349
308
        error=1;
350
309
      outfile->end_of_file=save_pos;
351
310
    }
358
317
                  (uint32_t) records, &LOCK_status);
359
318
  *examined_rows= param.examined_rows;
360
319
  memcpy(&table->sort, &table_sort, sizeof(filesort_info_st));
361
 
  DRIZZLE_FILESORT_DONE(error, records);
362
 
  return (error ? HA_POS_ERROR : records);
 
320
  DRIZZLE_FILESORT_END();
 
321
  return(error ? HA_POS_ERROR : records);
363
322
} /* filesort */
364
323
 
365
324
 
366
 
void Table::filesort_free_buffers(bool full)
 
325
void filesort_free_buffers(Table *table, bool full)
367
326
{
368
 
  if (sort.record_pointers)
 
327
  if (table->sort.record_pointers)
369
328
  {
370
 
    free((unsigned char*) sort.record_pointers);
371
 
    sort.record_pointers=0;
 
329
    free((unsigned char*) table->sort.record_pointers);
 
330
    table->sort.record_pointers=0;
372
331
  }
373
332
  if (full)
374
333
  {
375
 
    if (sort.sort_keys )
 
334
    if (table->sort.sort_keys )
376
335
    {
377
 
      if ((unsigned char*) sort.sort_keys)
378
 
        free((unsigned char*) sort.sort_keys);
379
 
      sort.sort_keys= 0;
 
336
      if ((unsigned char*) table->sort.sort_keys)
 
337
        free((unsigned char*) table->sort.sort_keys);
 
338
      table->sort.sort_keys= 0;
380
339
    }
381
 
    if (sort.buffpek)
 
340
    if (table->sort.buffpek)
382
341
    {
383
 
      if ((unsigned char*) sort.buffpek)
384
 
        free((unsigned char*) sort.buffpek);
385
 
      sort.buffpek= 0;
386
 
      sort.buffpek_len= 0;
 
342
      if ((unsigned char*) table->sort.buffpek)
 
343
        free((unsigned char*) table->sort.buffpek);
 
344
      table->sort.buffpek= 0;
 
345
      table->sort.buffpek_len= 0;
387
346
    }
388
347
  }
389
 
  if (sort.addon_buf)
 
348
  if (table->sort.addon_buf)
390
349
  {
391
 
    free((char *) sort.addon_buf);
392
 
    free((char *) sort.addon_field);
393
 
    sort.addon_buf=0;
394
 
    sort.addon_field=0;
 
350
    free((char *) table->sort.addon_buf);
 
351
    free((char *) table->sort.addon_field);
 
352
    table->sort.addon_buf=0;
 
353
    table->sort.addon_field=0;
395
354
  }
396
355
}
397
356
 
398
357
/** Make a array of string pointers. */
399
358
 
400
359
static char **make_char_array(char **old_pos, register uint32_t fields,
401
 
                              uint32_t length)
 
360
                              uint32_t length, myf my_flag)
402
361
{
403
362
  register char **pos;
404
363
  char *char_pos;
405
364
 
406
365
  if (old_pos ||
407
 
      (old_pos= (char**) malloc((uint32_t) fields*(length+sizeof(char*)))))
 
366
      (old_pos= (char**) my_malloc((uint32_t) fields*(length+sizeof(char*)),
 
367
                                   my_flag)))
408
368
  {
409
369
    pos=old_pos; char_pos=((char*) (pos+fields)) -length;
410
370
    while (fields--) *(pos++) = (char_pos+= length);
416
376
 
417
377
/** Read 'count' number of buffer pointers into memory. */
418
378
 
419
 
static unsigned char *read_buffpek_from_file(internal::IO_CACHE *buffpek_pointers, uint32_t count,
 
379
static unsigned char *read_buffpek_from_file(IO_CACHE *buffpek_pointers, uint32_t count,
420
380
                                     unsigned char *buf)
421
381
{
422
382
  uint32_t length= sizeof(BUFFPEK)*count;
424
384
  if (count > UINT_MAX/sizeof(BUFFPEK))
425
385
    return 0; /* sizeof(BUFFPEK)*count will overflow */
426
386
  if (!tmp)
427
 
    tmp= (unsigned char *)malloc(length);
 
387
    tmp= (unsigned char *)my_malloc(length, MYF(MY_WME));
428
388
  if (tmp)
429
389
  {
430
 
    if (reinit_io_cache(buffpek_pointers,internal::READ_CACHE,0L,0,0) ||
 
390
    if (reinit_io_cache(buffpek_pointers,READ_CACHE,0L,0,0) ||
431
391
        my_b_read(buffpek_pointers, (unsigned char*) tmp, length))
432
392
    {
433
393
      free((char*) tmp);
475
435
    HA_POS_ERROR on error.
476
436
*/
477
437
 
478
 
static ha_rows find_all_keys(SORTPARAM *param, 
479
 
                             optimizer::SqlSelect *select,
 
438
static ha_rows find_all_keys(SORTPARAM *param, SQL_SELECT *select,
480
439
                             unsigned char **sort_keys,
481
 
                             internal::IO_CACHE *buffpek_pointers,
482
 
                             internal::IO_CACHE *tempfile, internal::IO_CACHE *indexfile)
 
440
                             IO_CACHE *buffpek_pointers,
 
441
                             IO_CACHE *tempfile, IO_CACHE *indexfile)
483
442
{
484
443
  int error,flag,quick_select;
485
444
  uint32_t idx,indexpos,ref_length;
486
445
  unsigned char *ref_pos,*next_pos,ref_buff[MAX_REFLENGTH];
487
 
  internal::my_off_t record;
 
446
  my_off_t record;
488
447
  Table *sort_form;
489
448
  Session *session= current_session;
490
449
  volatile Session::killed_state *killed= &session->killed;
491
 
  Cursor *file;
492
 
  MyBitmap *save_read_set, *save_write_set;
 
450
  handler *file;
 
451
  MY_BITMAP *save_read_set, *save_write_set;
493
452
 
494
453
  idx=indexpos=0;
495
454
  error=quick_select=0;
496
455
  sort_form=param->sort_form;
497
 
  file= sort_form->cursor;
 
456
  file=sort_form->file;
498
457
  ref_length=param->ref_length;
499
458
  ref_pos= ref_buff;
500
459
  quick_select=select && select->quick;
501
460
  record=0;
502
 
  flag= ((!indexfile && ! file->isOrdered())
 
461
  flag= ((!indexfile && file->ha_table_flags() & HA_REC_NOT_IN_SEQ)
503
462
         || quick_select);
504
463
  if (indexfile || flag)
505
464
    ref_pos= &file->ref[0];
525
484
  save_read_set=  sort_form->read_set;
526
485
  save_write_set= sort_form->write_set;
527
486
  /* Set up temporary column read map for columns used by sort */
528
 
  sort_form->tmp_set.clearAll();
 
487
  bitmap_clear_all(&sort_form->tmp_set);
529
488
  /* Temporary set for register_used_fields and register_field_in_read_map */
530
489
  sort_form->read_set= &sort_form->tmp_set;
531
490
  register_used_fields(param);
549
508
    {
550
509
      if (indexfile)
551
510
      {
552
 
        if (my_b_read(indexfile,(unsigned char*) ref_pos,ref_length))
 
511
        if (my_b_read(indexfile,(unsigned char*) ref_pos,ref_length)) /* purecov: deadcode */
553
512
        {
554
 
          error= errno ? errno : -1;            /* Abort */
 
513
          error= my_errno ? my_errno : -1;              /* Abort */
555
514
          break;
556
515
        }
557
516
        error=file->rnd_pos(sort_form->record[0],next_pos);
559
518
      else
560
519
      {
561
520
        error=file->rnd_next(sort_form->record[0]);
 
521
        if (!error)
 
522
          update_virtual_fields_marked_for_write(sort_form);
562
523
 
563
524
        if (!flag)
564
525
        {
565
 
          internal::my_store_ptr(ref_pos,ref_length,record); // Position to row
 
526
          my_store_ptr(ref_pos,ref_length,record); // Position to row
566
527
          record+= sort_form->s->db_record_offset;
567
528
        }
568
529
        else if (!error)
579
540
        (void) file->extra(HA_EXTRA_NO_CACHE);
580
541
        file->ha_rnd_end();
581
542
      }
582
 
      return(HA_POS_ERROR);
 
543
      return(HA_POS_ERROR);             /* purecov: inspected */
583
544
    }
584
545
    if (error == 0)
585
546
      param->examined_rows++;
617
578
 
618
579
  if (session->is_error())
619
580
    return(HA_POS_ERROR);
620
 
 
 
581
  
621
582
  /* Signal we should use orignal column read and write maps */
622
583
  sort_form->column_bitmaps_set(save_read_set, save_write_set);
623
584
 
624
585
  if (error != HA_ERR_END_OF_FILE)
625
586
  {
626
 
    sort_form->print_error(error,MYF(ME_ERROR | ME_WAITTANG));
627
 
    return(HA_POS_ERROR);
 
587
    file->print_error(error,MYF(ME_ERROR | ME_WAITTANG)); /* purecov: inspected */
 
588
    return(HA_POS_ERROR);                       /* purecov: inspected */
628
589
  }
629
590
  if (indexpos && idx &&
630
591
      write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
631
 
    return(HA_POS_ERROR);
 
592
    return(HA_POS_ERROR);                       /* purecov: inspected */
632
593
  return(my_b_inited(tempfile) ?
633
594
              (ha_rows) (my_b_tell(tempfile)/param->rec_length) :
634
595
              idx);
659
620
 
660
621
static int
661
622
write_keys(SORTPARAM *param, register unsigned char **sort_keys, uint32_t count,
662
 
           internal::IO_CACHE *buffpek_pointers, internal::IO_CACHE *tempfile)
 
623
           IO_CACHE *buffpek_pointers, IO_CACHE *tempfile)
663
624
{
664
625
  size_t sort_length, rec_length;
665
626
  unsigned char **end;
667
628
 
668
629
  sort_length= param->sort_length;
669
630
  rec_length= param->rec_length;
670
 
  internal::my_string_ptr_sort((unsigned char*) sort_keys, (uint32_t) count, sort_length);
 
631
  my_string_ptr_sort((unsigned char*) sort_keys, (uint32_t) count, sort_length);
671
632
  if (!my_b_inited(tempfile) &&
672
633
      open_cached_file(tempfile, drizzle_tmpdir, TEMP_PREFIX, DISK_BUFFER_SIZE,
673
634
                       MYF(MY_WME)))
674
 
    goto err;
 
635
    goto err;                                   /* purecov: inspected */
675
636
  /* check we won't have more buffpeks than we can possibly keep in memory */
676
637
  if (my_b_tell(buffpek_pointers) + sizeof(BUFFPEK) > (uint64_t)UINT_MAX)
677
638
    goto err;
678
639
  buffpek.file_pos= my_b_tell(tempfile);
679
640
  if ((ha_rows) count > param->max_rows)
680
 
    count=(uint32_t) param->max_rows;
 
641
    count=(uint32_t) param->max_rows;               /* purecov: inspected */
681
642
  buffpek.count=(ha_rows) count;
682
643
  for (end=sort_keys+count ; sort_keys != end ; sort_keys++)
683
644
    if (my_b_write(tempfile, (unsigned char*) *sort_keys, (uint32_t) rec_length))
721
682
{
722
683
  register Field *field;
723
684
  register SORT_FIELD *sort_field;
724
 
  size_t length;
 
685
  register uint32_t length;
725
686
 
726
687
  for (sort_field=param->local_sortorder ;
727
688
       sort_field != param->end ;
769
730
            memset(to-1, 0, sort_field->length+1);
770
731
          else
771
732
          {
 
733
            /* purecov: begin deadcode */
772
734
            /*
773
735
              This should only happen during extreme conditions if we run out
774
736
              of memory or have an item marked not null when it can be null.
776
738
            */
777
739
            assert(0);
778
740
            memset(to, 0, sort_field->length);  // Avoid crash
 
741
            /* purecov: end */
779
742
          }
780
743
          break;
781
744
        }
819
782
          int64_t value= item->val_int_result();
820
783
          if (maybe_null)
821
784
          {
822
 
            *to++=1;
 
785
            *to++=1;                            /* purecov: inspected */
823
786
            if (item->null_value)
824
787
            {
825
788
              if (maybe_null)
850
813
          if (maybe_null)
851
814
          {
852
815
            if (item->null_value)
853
 
            {
 
816
            { 
854
817
              memset(to, 0, sort_field->length+1);
855
818
              to++;
856
819
              break;
879
842
          break;
880
843
        }
881
844
      case ROW_RESULT:
882
 
      default:
 
845
      default: 
883
846
        // This case should never be choosen
884
847
        assert(0);
885
848
        break;
902
865
 
903
866
  if (param->addon_field)
904
867
  {
905
 
    /*
 
868
    /* 
906
869
      Save field values appended to sorted fields.
907
870
      First null bit indicators are appended then field values follow.
908
871
      In this implementation we use fixed layout for field values -
954
917
{
955
918
  register SORT_FIELD *sort_field;
956
919
  Table *table=param->sort_form;
 
920
  MY_BITMAP *bitmap= table->read_set;
957
921
 
958
922
  for (sort_field= param->local_sortorder ;
959
923
       sort_field != param->end ;
963
927
    if ((field= sort_field->field))
964
928
    {
965
929
      if (field->table == table)
966
 
        table->setReadSet(field->field_index);
 
930
      bitmap_set_bit(bitmap, field->field_index);
967
931
    }
968
932
    else
969
933
    {                                           // Item
977
941
    SORT_ADDON_FIELD *addonf= param->addon_field;
978
942
    Field *field;
979
943
    for ( ; (field= addonf->field) ; addonf++)
980
 
      table->setReadSet(field->field_index);
 
944
      bitmap_set_bit(bitmap, field->field_index);
981
945
  }
982
946
  else
983
947
  {
987
951
}
988
952
 
989
953
 
990
 
static bool save_index(SORTPARAM *param, unsigned char **sort_keys, uint32_t count,
 
954
static bool save_index(SORTPARAM *param, unsigned char **sort_keys, uint32_t count, 
991
955
                       filesort_info_st *table_sort)
992
956
{
993
957
  uint32_t offset,res_length;
994
958
  unsigned char *to;
995
959
 
996
 
  internal::my_string_ptr_sort((unsigned char*) sort_keys, (uint32_t) count, param->sort_length);
 
960
  my_string_ptr_sort((unsigned char*) sort_keys, (uint32_t) count, param->sort_length);
997
961
  res_length= param->res_length;
998
962
  offset= param->rec_length-res_length;
999
963
  if ((ha_rows) count > param->max_rows)
1000
964
    count=(uint32_t) param->max_rows;
1001
 
  if (!(to= table_sort->record_pointers=
1002
 
        (unsigned char*) malloc(res_length*count)))
1003
 
    return(1);
 
965
  if (!(to= table_sort->record_pointers= 
 
966
        (unsigned char*) my_malloc(res_length*count, MYF(MY_WME))))
 
967
    return(1);                 /* purecov: inspected */
1004
968
  for (unsigned char **end= sort_keys+count ; sort_keys != end ; sort_keys++)
1005
969
  {
1006
970
    memcpy(to, *sort_keys+offset, res_length);
1013
977
/** Merge buffers to make < MERGEBUFF2 buffers. */
1014
978
 
1015
979
int merge_many_buff(SORTPARAM *param, unsigned char *sort_buffer,
1016
 
                    BUFFPEK *buffpek, uint32_t *maxbuffer, internal::IO_CACHE *t_file)
 
980
                    BUFFPEK *buffpek, uint32_t *maxbuffer, IO_CACHE *t_file)
1017
981
{
1018
982
  register uint32_t i;
1019
 
  internal::IO_CACHE t_file2,*from_file,*to_file,*temp;
 
983
  IO_CACHE t_file2,*from_file,*to_file,*temp;
1020
984
  BUFFPEK *lastbuff;
1021
985
 
1022
986
  if (*maxbuffer < MERGEBUFF2)
1023
 
    return(0);
 
987
    return(0);                          /* purecov: inspected */
1024
988
  if (flush_io_cache(t_file) ||
1025
989
      open_cached_file(&t_file2,drizzle_tmpdir,TEMP_PREFIX,DISK_BUFFER_SIZE,
1026
990
                        MYF(MY_WME)))
1027
 
    return(1);
 
991
    return(1);                          /* purecov: inspected */
1028
992
 
1029
993
  from_file= t_file ; to_file= &t_file2;
1030
994
  while (*maxbuffer >= MERGEBUFF2)
1031
995
  {
1032
 
    if (reinit_io_cache(from_file,internal::READ_CACHE,0L,0,0))
 
996
    if (reinit_io_cache(from_file,READ_CACHE,0L,0,0))
1033
997
      goto cleanup;
1034
 
    if (reinit_io_cache(to_file,internal::WRITE_CACHE,0L,0,0))
 
998
    if (reinit_io_cache(to_file,WRITE_CACHE,0L,0,0))
1035
999
      goto cleanup;
1036
1000
    lastbuff=buffpek;
1037
1001
    for (i=0 ; i <= *maxbuffer-MERGEBUFF*3/2 ; i+=MERGEBUFF)
1042
1006
    }
1043
1007
    if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
1044
1008
                      buffpek+i,buffpek+ *maxbuffer,0))
1045
 
      break;
 
1009
      break;                                    /* purecov: inspected */
1046
1010
    if (flush_io_cache(to_file))
1047
 
      break;
 
1011
      break;                                    /* purecov: inspected */
1048
1012
    temp=from_file; from_file=to_file; to_file=temp;
1049
1013
    setup_io_cache(from_file);
1050
1014
    setup_io_cache(to_file);
1069
1033
    (uint32_t)-1 if something goes wrong
1070
1034
*/
1071
1035
 
1072
 
uint32_t read_to_buffer(internal::IO_CACHE *fromfile, BUFFPEK *buffpek,
1073
 
                        uint32_t rec_length)
 
1036
uint32_t read_to_buffer(IO_CACHE *fromfile, BUFFPEK *buffpek,
 
1037
                    uint32_t rec_length)
1074
1038
{
1075
1039
  register uint32_t count;
1076
1040
  uint32_t length;
1077
1041
 
1078
 
  if ((count= (uint32_t) min((ha_rows) buffpek->max_keys,buffpek->count)))
 
1042
  if ((count=(uint32_t) cmin((ha_rows) buffpek->max_keys,buffpek->count)))
1079
1043
  {
1080
1044
    if (pread(fromfile->file,(unsigned char*) buffpek->base, (length= rec_length*count),buffpek->file_pos) == 0)
1081
 
      return((uint32_t) -1);
1082
 
 
1083
 
    buffpek->key= buffpek->base;
 
1045
      return((uint32_t) -1);                    /* purecov: inspected */
 
1046
    buffpek->key=buffpek->base;
1084
1047
    buffpek->file_pos+= length;                 /* New filepos */
1085
 
    buffpek->count-= count;
 
1048
    buffpek->count-=    count;
1086
1049
    buffpek->mem_count= count;
1087
1050
  }
1088
1051
  return (count*rec_length);
1089
1052
} /* read_to_buffer */
1090
1053
 
1091
1054
 
1092
 
class compare_functor
 
1055
/**
 
1056
  Put all room used by freed buffer to use in adjacent buffer.
 
1057
 
 
1058
  Note, that we can't simply distribute memory evenly between all buffers,
 
1059
  because new areas must not overlap with old ones.
 
1060
 
 
1061
  @param[in] queue      list of non-empty buffers, without freed buffer
 
1062
  @param[in] reuse      empty buffer
 
1063
  @param[in] key_length key length
 
1064
*/
 
1065
 
 
1066
void reuse_freed_buff(QUEUE *queue, BUFFPEK *reuse, uint32_t key_length)
1093
1067
{
1094
 
  qsort2_cmp key_compare;
1095
 
  void *key_compare_arg;
1096
 
  public:
1097
 
  compare_functor(qsort2_cmp in_key_compare, void *in_compare_arg)
1098
 
    : key_compare(in_key_compare), key_compare_arg(in_compare_arg) { }
1099
 
  inline bool operator()(const BUFFPEK *i, const BUFFPEK *j) const
 
1068
  unsigned char *reuse_end= reuse->base + reuse->max_keys * key_length;
 
1069
  for (uint32_t i= 0; i < queue->elements; ++i)
1100
1070
  {
1101
 
    int val= key_compare(key_compare_arg,
1102
 
                      &i->key, &j->key);
1103
 
    return (val >= 0);
 
1071
    BUFFPEK *bp= (BUFFPEK *) queue_element(queue, i);
 
1072
    if (bp->base + bp->max_keys * key_length == reuse->base)
 
1073
    {
 
1074
      bp->max_keys+= reuse->max_keys;
 
1075
      return;
 
1076
    }
 
1077
    else if (bp->base == reuse_end)
 
1078
    {
 
1079
      bp->base= reuse->base;
 
1080
      bp->max_keys+= reuse->max_keys;
 
1081
      return;
 
1082
    }
1104
1083
  }
1105
 
};
 
1084
  assert(0);
 
1085
}
1106
1086
 
1107
1087
 
1108
1088
/**
1123
1103
    other  error
1124
1104
*/
1125
1105
 
1126
 
int merge_buffers(SORTPARAM *param, internal::IO_CACHE *from_file,
1127
 
                  internal::IO_CACHE *to_file, unsigned char *sort_buffer,
 
1106
int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
 
1107
                  IO_CACHE *to_file, unsigned char *sort_buffer,
1128
1108
                  BUFFPEK *lastbuff, BUFFPEK *Fb, BUFFPEK *Tb,
1129
1109
                  int flag)
1130
1110
{
1133
1113
  size_t sort_length;
1134
1114
  uint32_t maxcount;
1135
1115
  ha_rows max_rows,org_max_rows;
1136
 
  internal::my_off_t to_start_filepos;
 
1116
  my_off_t to_start_filepos;
1137
1117
  unsigned char *strpos;
1138
1118
  BUFFPEK *buffpek;
 
1119
  QUEUE queue;
1139
1120
  qsort2_cmp cmp;
1140
1121
  void *first_cmp_arg;
1141
1122
  volatile Session::killed_state *killed= &current_session->killed;
1160
1141
 
1161
1142
  /* The following will fire if there is not enough space in sort_buffer */
1162
1143
  assert(maxcount!=0);
1163
 
 
 
1144
  
1164
1145
  if (param->unique_buff)
1165
1146
  {
1166
1147
    cmp= param->compare;
1168
1149
  }
1169
1150
  else
1170
1151
  {
1171
 
    cmp= internal::get_ptr_compare(sort_length);
 
1152
    cmp= get_ptr_compare(sort_length);
1172
1153
    first_cmp_arg= (void*) &sort_length;
1173
1154
  }
1174
 
  priority_queue<BUFFPEK *, vector<BUFFPEK *>, compare_functor > 
1175
 
    queue(compare_functor(cmp, first_cmp_arg));
 
1155
  if (init_queue(&queue, (uint32_t) (Tb-Fb)+1, offsetof(BUFFPEK,key), 0,
 
1156
                 (queue_compare) cmp, first_cmp_arg))
 
1157
    return(1);                                /* purecov: inspected */
1176
1158
  for (buffpek= Fb ; buffpek <= Tb ; buffpek++)
1177
1159
  {
1178
1160
    buffpek->base= strpos;
1180
1162
    strpos+= (uint32_t) (error= (int) read_to_buffer(from_file, buffpek,
1181
1163
                                                                         rec_length));
1182
1164
    if (error == -1)
1183
 
      goto err;
 
1165
      goto err;                                 /* purecov: inspected */
1184
1166
    buffpek->max_keys= buffpek->mem_count;      // If less data in buffers than expected
1185
 
    queue.push(buffpek);
 
1167
    queue_insert(&queue, (unsigned char*) buffpek);
1186
1168
  }
1187
1169
 
1188
1170
  if (param->unique_buff)
1189
1171
  {
1190
 
    /*
 
1172
    /* 
1191
1173
       Called by Unique::get()
1192
1174
       Copy the first argument to param->unique_buff for unique removal.
1193
1175
       Store it also in 'to_file'.
1195
1177
       This is safe as we know that there is always more than one element
1196
1178
       in each block to merge (This is guaranteed by the Unique:: algorithm
1197
1179
    */
1198
 
    buffpek= queue.top();
 
1180
    buffpek= (BUFFPEK*) queue_top(&queue);
1199
1181
    memcpy(param->unique_buff, buffpek->key, rec_length);
1200
1182
    if (my_b_write(to_file, (unsigned char*) buffpek->key, rec_length))
1201
1183
    {
1202
 
      error=1; goto err;
 
1184
      error=1; goto err;                        /* purecov: inspected */
1203
1185
    }
1204
1186
    buffpek->key+= rec_length;
1205
1187
    buffpek->mem_count--;
1206
1188
    if (!--max_rows)
1207
1189
    {
1208
 
      error= 0;
1209
 
      goto end;
 
1190
      error= 0;                                       /* purecov: inspected */
 
1191
      goto end;                                       /* purecov: inspected */
1210
1192
    }
1211
 
    /* Top element has been used */
1212
 
    queue.pop();
1213
 
    queue.push(buffpek);
 
1193
    queue_replaced(&queue);                        // Top element has been used
1214
1194
  }
1215
1195
  else
1216
1196
    cmp= 0;                                        // Not unique
1217
1197
 
1218
 
  while (queue.size() > 1)
 
1198
  while (queue.elements > 1)
1219
1199
  {
1220
1200
    if (*killed)
1221
1201
    {
1222
 
      error= 1; goto err;
 
1202
      error= 1; goto err;                        /* purecov: inspected */
1223
1203
    }
1224
1204
    for (;;)
1225
1205
    {
1226
 
      buffpek= queue.top();
 
1206
      buffpek= (BUFFPEK*) queue_top(&queue);
1227
1207
      if (cmp)                                        // Remove duplicates
1228
1208
      {
1229
1209
        if (!(*cmp)(first_cmp_arg, &(param->unique_buff),
1235
1215
      {
1236
1216
        if (my_b_write(to_file,(unsigned char*) buffpek->key, rec_length))
1237
1217
        {
1238
 
          error=1; goto err;
 
1218
          error=1; goto err;                        /* purecov: inspected */
1239
1219
        }
1240
1220
      }
1241
1221
      else
1242
1222
      {
1243
1223
        if (my_b_write(to_file, (unsigned char*) buffpek->key+offset, res_length))
1244
1224
        {
1245
 
          error=1; goto err;
 
1225
          error=1; goto err;                        /* purecov: inspected */
1246
1226
        }
1247
1227
      }
1248
1228
      if (!--max_rows)
1249
1229
      {
1250
 
        error= 0;
1251
 
        goto end;
 
1230
        error= 0;                               /* purecov: inspected */
 
1231
        goto end;                               /* purecov: inspected */
1252
1232
      }
1253
1233
 
1254
1234
    skip_duplicate:
1258
1238
        if (!(error= (int) read_to_buffer(from_file,buffpek,
1259
1239
                                          rec_length)))
1260
1240
        {
1261
 
          queue.pop();
 
1241
          queue_remove(&queue,0);
 
1242
          reuse_freed_buff(&queue, buffpek, rec_length);
1262
1243
          break;                        /* One buffer have been removed */
1263
1244
        }
1264
1245
        else if (error == -1)
1265
 
          goto err;
 
1246
          goto err;                        /* purecov: inspected */
1266
1247
      }
1267
 
      /* Top element has been replaced */
1268
 
      queue.pop();
1269
 
      queue.push(buffpek);
 
1248
      queue_replaced(&queue);              /* Top element has been replaced */
1270
1249
    }
1271
1250
  }
1272
 
  buffpek= queue.top();
 
1251
  buffpek= (BUFFPEK*) queue_top(&queue);
1273
1252
  buffpek->base= sort_buffer;
1274
1253
  buffpek->max_keys= param->keys;
1275
1254
 
1299
1278
      if (my_b_write(to_file,(unsigned char*) buffpek->key,
1300
1279
                     (rec_length*buffpek->mem_count)))
1301
1280
      {
1302
 
        error= 1; goto err;
 
1281
        error= 1; goto err;                        /* purecov: inspected */
1303
1282
      }
1304
1283
    }
1305
1284
    else
1309
1288
      for (end= strpos+buffpek->mem_count*rec_length ;
1310
1289
           strpos != end ;
1311
1290
           strpos+= rec_length)
1312
 
      {
 
1291
      {     
1313
1292
        if (my_b_write(to_file, (unsigned char *) strpos, res_length))
1314
1293
        {
1315
 
          error=1; goto err;
 
1294
          error=1; goto err;                        
1316
1295
        }
1317
1296
      }
1318
1297
    }
1321
1300
         != -1 && error != 0);
1322
1301
 
1323
1302
end:
1324
 
  lastbuff->count= min(org_max_rows-max_rows, param->max_rows);
 
1303
  lastbuff->count= cmin(org_max_rows-max_rows, param->max_rows);
1325
1304
  lastbuff->file_pos= to_start_filepos;
1326
1305
err:
 
1306
  delete_queue(&queue);
1327
1307
  return(error);
1328
1308
} /* merge_buffers */
1329
1309
 
1332
1312
 
1333
1313
static int merge_index(SORTPARAM *param, unsigned char *sort_buffer,
1334
1314
                       BUFFPEK *buffpek, uint32_t maxbuffer,
1335
 
                       internal::IO_CACHE *tempfile, internal::IO_CACHE *outfile)
 
1315
                       IO_CACHE *tempfile, IO_CACHE *outfile)
1336
1316
{
1337
1317
  if (merge_buffers(param,tempfile,outfile,sort_buffer,buffpek,buffpek,
1338
1318
                    buffpek+maxbuffer,1))
1339
 
    return(1);
 
1319
    return(1);                          /* purecov: inspected */
1340
1320
  return(0);
1341
1321
} /* merge_index */
1342
1322
 
1357
1337
/**
1358
1338
  Calculate length of sort key.
1359
1339
 
1360
 
  @param session                          Thread Cursor
 
1340
  @param session                          Thread handler
1361
1341
  @param sortorder                Order of items to sort
1362
1342
  @param s_length                 Number of items to sort
1363
1343
  @param[out] multi_byte_charset Set to 1 if we are using multi-byte charset
1407
1387
      switch (sortorder->result_type) {
1408
1388
      case STRING_RESULT:
1409
1389
        sortorder->length=sortorder->item->max_length;
1410
 
        set_if_smaller(sortorder->length,
1411
 
                       session->variables.max_sort_length);
 
1390
        set_if_smaller(sortorder->length, session->variables.max_sort_length);
1412
1391
        if (use_strnxfrm((cs=sortorder->item->collation.collation)))
1413
 
        {
 
1392
        { 
1414
1393
          sortorder->length= cs->coll->strnxfrmlen(cs, sortorder->length);
1415
1394
          sortorder->need_strxnfrm= 1;
1416
1395
          *multi_byte_charset= 1;
1427
1406
        break;
1428
1407
      case DECIMAL_RESULT:
1429
1408
        sortorder->length=
1430
 
          my_decimal_get_binary_size(sortorder->item->max_length -
 
1409
          my_decimal_get_binary_size(sortorder->item->max_length - 
1431
1410
                                     (sortorder->item->decimals ? 1 : 0),
1432
1411
                                     sortorder->item->decimals);
1433
1412
        break;
1435
1414
        sortorder->length=sizeof(double);
1436
1415
        break;
1437
1416
      case ROW_RESULT:
1438
 
      default:
 
1417
      default: 
1439
1418
        // This case should never be choosen
1440
1419
        assert(0);
1441
1420
        break;
1443
1422
      if (sortorder->item->maybe_null)
1444
1423
        length++;                               // Place for NULL marker
1445
1424
    }
1446
 
    set_if_smaller(sortorder->length,
1447
 
                   (size_t)session->variables.max_sort_length);
 
1425
    set_if_smaller(sortorder->length, session->variables.max_sort_length);
1448
1426
    length+=sortorder->length;
1449
1427
  }
1450
1428
  sortorder->field= (Field*) 0;                 // end marker
1458
1436
 
1459
1437
  The function first finds out what fields are used in the result set.
1460
1438
  Then it calculates the length of the buffer to store the values of
1461
 
  these fields together with the value of sort values.
 
1439
  these fields together with the value of sort values. 
1462
1440
  If the calculated length is not greater than max_length_for_sort_data
1463
1441
  the function allocates memory for an array of descriptors containing
1464
1442
  layouts for the values of the non-sorted fields in the buffer and
1488
1466
  uint32_t length= 0;
1489
1467
  uint32_t fields= 0;
1490
1468
  uint32_t null_fields= 0;
 
1469
  MY_BITMAP *read_set= (*ptabfield)->table->read_set;
1491
1470
 
1492
1471
  /*
1493
1472
    If there is a reference to a field in the query add it
1495
1474
    Note for future refinement:
1496
1475
    This this a too strong condition.
1497
1476
    Actually we need only the fields referred in the
1498
 
    result set. And for some of them it makes sense to use
 
1477
    result set. And for some of them it makes sense to use 
1499
1478
    the values directly from sorted fields.
1500
1479
  */
1501
1480
  *plength= 0;
1502
1481
 
1503
1482
  for (pfield= ptabfield; (field= *pfield) ; pfield++)
1504
1483
  {
1505
 
    if (!(field->isReadSet()))
 
1484
    if (!bitmap_is_set(read_set, field->field_index))
1506
1485
      continue;
1507
1486
    if (field->flags & BLOB_FLAG)
1508
1487
      return 0;
1510
1489
    if (field->maybe_null())
1511
1490
      null_fields++;
1512
1491
    fields++;
1513
 
  }
 
1492
  } 
1514
1493
  if (!fields)
1515
1494
    return 0;
1516
1495
  length+= (null_fields+7)/8;
1517
1496
 
1518
1497
  if (length+sortlength > session->variables.max_length_for_sort_data ||
1519
 
      !(addonf= (SORT_ADDON_FIELD *) malloc(sizeof(SORT_ADDON_FIELD)*
1520
 
                                            (fields+1))))
 
1498
      !(addonf= (SORT_ADDON_FIELD *) my_malloc(sizeof(SORT_ADDON_FIELD)*
 
1499
                                               (fields+1), MYF(MY_WME))))
1521
1500
    return 0;
1522
1501
 
1523
1502
  *plength= length;
1525
1504
  null_fields= 0;
1526
1505
  for (pfield= ptabfield; (field= *pfield) ; pfield++)
1527
1506
  {
1528
 
    if (!(field->isReadSet()))
 
1507
    if (!bitmap_is_set(read_set, field->field_index))
1529
1508
      continue;
1530
1509
    addonf->field= field;
1531
1510
    addonf->offset= length;
1545
1524
    addonf++;
1546
1525
  }
1547
1526
  addonf->field= 0;     // Put end marker
1548
 
 
 
1527
  
1549
1528
  return (addonf-fields);
1550
1529
}
1551
1530
 
1565
1544
    void.
1566
1545
*/
1567
1546
 
1568
 
static void
 
1547
static void 
1569
1548
unpack_addon_fields(struct st_sort_addon_field *addon_field, unsigned char *buff)
1570
1549
{
1571
1550
  Field *field;
1630
1609
    }
1631
1610
  }
1632
1611
}
1633
 
 
1634
 
} /* namespace drizzled */