1
/* Copyright (C) 2000-2006 MySQL AB
3
This program is free software; you can redistribute it and/or modify
4
it under the terms of the GNU General Public License as published by
5
the Free Software Foundation; version 2 of the License.
7
This program is distributed in the hope that it will be useful,
8
but WITHOUT ANY WARRANTY; without even the implied warranty of
9
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10
GNU General Public License for more details.
12
You should have received a copy of the GNU General Public License
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 */
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"
56
/* Defines used by filesort and uniques */
60
class BufferCompareContext
63
qsort_cmp2 key_compare;
64
void *key_compare_arg;
66
BufferCompareContext() :
75
uint32_t rec_length; /* Length of sorted records */
76
uint32_t sort_length; /* Length of sorted columns */
77
uint32_t ref_length; /* Length of record ref. */
78
uint32_t addon_length; /* Length of added packed fields */
79
uint32_t res_length; /* Length of records in final sorted file/buffer */
80
uint32_t keys; /* Max keys / buffer */
81
ha_rows max_rows,examined_rows;
82
Table *sort_form; /* For quicker make_sortkey */
83
SortField *local_sortorder;
85
sort_addon_field *addon_field; /* Descriptors for companion fields */
86
unsigned char *unique_buff;
89
/* The fields below are used only by Unique class */
91
BufferCompareContext cmp_context;
119
int write_keys(unsigned char * *sort_keys,
121
internal::IO_CACHE *buffer_file,
122
internal::IO_CACHE *tempfile);
124
void make_sortkey(unsigned char *to,
125
unsigned char *ref_pos);
126
void register_used_fields();
127
bool save_index(unsigned char **sort_keys,
129
filesort_info *table_sort);
133
/* functions defined in this file */
135
static char **make_char_array(char **old_pos, register uint32_t fields,
138
static unsigned char *read_buffpek_from_file(internal::IO_CACHE *buffer_file,
142
static uint32_t suffix_length(uint32_t string_length);
143
static void unpack_addon_fields(sort_addon_field *addon_field,
144
unsigned char *buff);
146
FileSort::FileSort(Session &arg) :
153
Creates a set of pointers that can be used to read the rows
154
in sorted order. This should be done with the functions
157
Before calling filesort, one must have done
158
table->file->info(HA_STATUS_VARIABLE)
160
The result set is stored in table->io_cache or
161
table->record_pointers.
163
@param table Table to sort
164
@param sortorder How to sort the table
165
@param s_length Number of elements in sortorder
166
@param select condition to apply to the rows
167
@param max_rows Return only this many rows
168
@param sort_positions Set to 1 if we want to force sorting by position
169
(Needed by UPDATE/INSERT or ALTER Table)
170
@param examined_rows Store number of examined rows here
173
check why we do this (param.keys--)
175
If we sort by position (like if sort_positions is 1) filesort() will
176
call table->prepare_for_position().
183
examined_rows will be set to number of examined rows
186
ha_rows FileSort::run(Table *table, SortField *sortorder, uint32_t s_length,
187
optimizer::SqlSelect *select, ha_rows max_rows,
188
bool sort_positions, ha_rows &examined_rows)
191
uint32_t memavl= 0, min_sort_memory;
193
size_t allocated_sort_memory= 0;
194
buffpek *buffpek_inst= 0;
195
ha_rows records= HA_POS_ERROR;
196
unsigned char **sort_keys= 0;
197
internal::IO_CACHE tempfile;
198
internal::IO_CACHE buffpek_pointers;
199
internal::IO_CACHE *selected_records_file;
200
internal::IO_CACHE *outfile;
202
bool multi_byte_charset;
205
Don't use table->sort in filesort as it is also used by
206
QuickIndexMergeSelect. Work with a copy and put it back at the end
207
when index_merge select has finished with it.
209
filesort_info table_sort(table->sort);
210
table->sort.io_cache= NULL;
212
TableList *tab= table->pos_in_table_list;
213
Item_subselect *subselect= tab ? tab->containing_subselect() : 0;
215
DRIZZLE_FILESORT_START(table->getShare()->getSchemaName(), table->getShare()->getTableName());
218
Release InnoDB's adaptive hash index latch (if holding) before
221
plugin::TransactionalStorageEngine::releaseTemporaryLatches(&getSession());
224
outfile= table_sort.io_cache;
225
assert(tempfile.buffer == 0);
226
assert(buffpek_pointers.buffer == 0);
228
param.sort_length= sortlength(sortorder, s_length, &multi_byte_charset);
229
param.ref_length= table->cursor->ref_length;
231
if (!(table->cursor->getEngine()->check_flag(HTON_BIT_FAST_KEY_READ)) && !sort_positions)
234
Get the descriptors of all fields whose values are appended
235
to sorted fields and get its total length in param.spack_length.
237
param.addon_field= get_addon_fields(table->getFields(),
239
¶m.addon_length);
242
table_sort.addon_buf= 0;
243
table_sort.addon_length= param.addon_length;
244
table_sort.addon_field= param.addon_field;
245
table_sort.unpack= unpack_addon_fields;
246
if (param.addon_field)
248
param.res_length= param.addon_length;
249
if (!(table_sort.addon_buf= (unsigned char *) malloc(param.addon_length)))
256
param.res_length= param.ref_length;
258
The reference to the record is considered
259
as an additional sorted field
261
param.sort_length+= param.ref_length;
263
param.rec_length= param.sort_length+param.addon_length;
264
param.max_rows= max_rows;
266
if (select && select->quick)
268
getSession().status_var.filesort_range_count++;
272
getSession().status_var.filesort_scan_count++;
274
#ifdef CAN_TRUST_RANGE
275
if (select && select->quick && select->quick->records > 0L)
277
records= min((ha_rows) (select->quick->records*2+EXTRA_RECORDS*2),
278
table->cursor->stats.records)+EXTRA_RECORDS;
279
selected_records_file=0;
284
records= table->cursor->estimate_rows_upper_bound();
286
If number of records is not known, use as much of sort buffer
289
if (records == HA_POS_ERROR)
290
records--; // we use 'records+1' below.
291
selected_records_file= 0;
294
if (multi_byte_charset && !(param.tmp_buffer= (char*) malloc(param.sort_length)))
299
memavl= getSession().variables.sortbuff_size;
300
min_sort_memory= max((uint32_t)MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2);
301
while (memavl >= min_sort_memory)
304
uint32_t keys= memavl/(param.rec_length+sizeof(char*));
305
param.keys= (uint32_t) min(records+1, (ha_rows)keys);
307
allocated_sort_memory= param.keys * param.rec_length;
308
if (not global_sort_buffer.add(allocated_sort_memory))
310
my_error(ER_OUT_OF_GLOBAL_SORTMEMORY, MYF(ME_ERROR+ME_WAITTANG));
314
if ((table_sort.sort_keys=
315
(unsigned char **) make_char_array((char **) table_sort.sort_keys,
316
param.keys, param.rec_length)))
319
global_sort_buffer.sub(allocated_sort_memory);
321
if ((memavl= memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
322
memavl= min_sort_memory;
324
sort_keys= table_sort.sort_keys;
325
if (memavl < min_sort_memory)
327
my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR+ME_WAITTANG));
331
if (buffpek_pointers.open_cached_file(drizzle_tmpdir.c_str(),TEMP_PREFIX, DISK_BUFFER_SIZE, MYF(MY_WME)))
336
param.keys--; /* TODO: check why we do this */
337
param.sort_form= table;
338
param.end=(param.local_sortorder=sortorder)+s_length;
339
if ((records= find_all_keys(¶m,select,sort_keys, &buffpek_pointers,
340
&tempfile, selected_records_file)) == HA_POS_ERROR)
344
maxbuffer= (uint32_t) (my_b_tell(&buffpek_pointers)/sizeof(*buffpek_inst));
346
if (maxbuffer == 0) // The whole set is in memory
348
if (param.save_index(sort_keys,(uint32_t) records, &table_sort))
355
if (table_sort.buffpek && table_sort.buffpek_len < maxbuffer)
357
if (table_sort.buffpek)
358
free(table_sort.buffpek);
359
table_sort.buffpek = 0;
361
if (!(table_sort.buffpek=
362
(unsigned char *) read_buffpek_from_file(&buffpek_pointers, maxbuffer, table_sort.buffpek)))
366
buffpek_inst= (buffpek *) table_sort.buffpek;
367
table_sort.buffpek_len= maxbuffer;
368
buffpek_pointers.close_cached_file();
369
/* Open cached file if it isn't open */
370
if (! my_b_inited(outfile) && outfile->open_cached_file(drizzle_tmpdir.c_str(),TEMP_PREFIX,READ_RECORD_BUFFER, MYF(MY_WME)))
375
if (outfile->reinit_io_cache(internal::WRITE_CACHE,0L,0,0))
381
Use also the space previously used by string pointers in sort_buffer
382
for temporary key storage.
384
param.keys=((param.keys*(param.rec_length+sizeof(char*))) / param.rec_length-1);
386
maxbuffer--; // Offset from 0
387
if (merge_many_buff(¶m,(unsigned char*) sort_keys,buffpek_inst,&maxbuffer, &tempfile))
392
if (flush_io_cache(&tempfile) || tempfile.reinit_io_cache(internal::READ_CACHE,0L,0,0))
397
if (merge_index(¶m,(unsigned char*) sort_keys,buffpek_inst,maxbuffer,&tempfile, outfile))
403
if (records > param.max_rows)
405
records= param.max_rows;
410
if (not subselect || not subselect->is_uncacheable())
413
table_sort.sort_keys= 0;
415
table_sort.buffpek= 0;
416
table_sort.buffpek_len= 0;
419
tempfile.close_cached_file();
420
buffpek_pointers.close_cached_file();
422
if (my_b_inited(outfile))
424
if (flush_io_cache(outfile))
429
internal::my_off_t save_pos= outfile->pos_in_file;
430
/* For following reads */
431
if (outfile->reinit_io_cache(internal::READ_CACHE,0L,0,0))
435
outfile->end_of_file=save_pos;
441
my_message(ER_FILSORT_ABORT, ER(ER_FILSORT_ABORT),
442
MYF(ME_ERROR+ME_WAITTANG));
446
getSession().status_var.filesort_rows+= (uint32_t) records;
448
examined_rows= param.examined_rows;
449
global_sort_buffer.sub(allocated_sort_memory);
450
table->sort= table_sort;
451
DRIZZLE_FILESORT_DONE(error, records);
452
return (error ? HA_POS_ERROR : records);
455
/** Make a array of string pointers. */
457
static char **make_char_array(char **old_pos, register uint32_t fields,
464
(old_pos= (char**) malloc((uint32_t) fields*(length+sizeof(char*)))))
466
pos=old_pos; char_pos=((char*) (pos+fields)) -length;
467
while (fields--) *(pos++) = (char_pos+= length);
471
} /* make_char_array */
474
/** Read 'count' number of buffer pointers into memory. */
476
static unsigned char *read_buffpek_from_file(internal::IO_CACHE *buffpek_pointers, uint32_t count,
479
uint32_t length= sizeof(buffpek)*count;
480
unsigned char *tmp= buf;
481
if (count > UINT_MAX/sizeof(buffpek))
482
return 0; /* sizeof(buffpek)*count will overflow */
484
tmp= (unsigned char *)malloc(length);
487
if (buffpek_pointers->reinit_io_cache(internal::READ_CACHE,0L,0,0) ||
488
my_b_read(buffpek_pointers, (unsigned char*) tmp, length))
499
Search after sort_keys and write them into tempfile.
500
All produced sequences are guaranteed to be non-empty.
502
@param param Sorting parameter
503
@param select Use this to get source data
504
@param sort_keys Array of pointers to sort key + addon buffers.
505
@param buffpek_pointers File to write buffpeks describing sorted segments
507
@param tempfile File to write sorted sequences of sortkeys to.
508
@param indexfile If !NULL, use it for source data (contains rowids)
513
while (get_next_sortkey())
515
if (no free space in sort_keys buffers)
517
sort sort_keys buffer;
518
dump sorted sequence to 'tempfile';
519
dump buffpek describing sequence location into 'buffpek_pointers';
521
put sort key into 'sort_keys';
523
if (sort_keys has some elements && dumped at least once)
524
sort-dump-dump as above;
526
don't sort, leave sort_keys array to be sorted by caller.
530
Number of records written on success.
532
HA_POS_ERROR on error.
535
ha_rows FileSort::find_all_keys(SortParam *param,
536
optimizer::SqlSelect *select,
537
unsigned char **sort_keys,
538
internal::IO_CACHE *buffpek_pointers,
539
internal::IO_CACHE *tempfile, internal::IO_CACHE *indexfile)
541
int error,flag,quick_select;
542
uint32_t idx,indexpos,ref_length;
543
unsigned char *ref_pos,*next_pos,ref_buff[MAX_REFLENGTH];
544
internal::my_off_t record;
546
volatile Session::killed_state_t *killed= getSession().getKilledPtr();
548
boost::dynamic_bitset<> *save_read_set= NULL;
549
boost::dynamic_bitset<> *save_write_set= NULL;
552
error=quick_select=0;
553
sort_form=param->sort_form;
554
file= sort_form->cursor;
555
ref_length=param->ref_length;
557
quick_select=select && select->quick;
559
flag= ((!indexfile && ! file->isOrdered())
561
if (indexfile || flag)
562
ref_pos= &file->ref[0];
564
if (! indexfile && ! quick_select)
566
next_pos=(unsigned char*) 0; /* Find records in sequence */
567
file->startTableScan(1);
568
file->extra_opt(HA_EXTRA_CACHE, getSession().variables.read_buff_size);
571
ReadRecord read_record_info;
574
if (select->quick->reset())
575
return(HA_POS_ERROR);
577
read_record_info.init_read_record(&getSession(), select->quick->head, select, 1, 1);
580
/* Remember original bitmaps */
581
save_read_set= sort_form->read_set;
582
save_write_set= sort_form->write_set;
583
/* Set up temporary column read map for columns used by sort */
584
sort_form->tmp_set.reset();
585
/* Temporary set for register_used_fields and register_field_in_read_map */
586
sort_form->read_set= &sort_form->tmp_set;
587
param->register_used_fields();
588
if (select && select->cond)
589
select->cond->walk(&Item::register_field_in_read_map, 1,
590
(unsigned char*) sort_form);
591
sort_form->column_bitmaps_set(sort_form->tmp_set, sort_form->tmp_set);
597
if ((error= read_record_info.read_record(&read_record_info)))
599
error= HA_ERR_END_OF_FILE;
602
file->position(sort_form->getInsertRecord());
604
else /* Not quick-select */
608
if (my_b_read(indexfile,(unsigned char*) ref_pos,ref_length))
610
error= errno ? errno : -1; /* Abort */
613
error=file->rnd_pos(sort_form->getInsertRecord(),next_pos);
617
error=file->rnd_next(sort_form->getInsertRecord());
621
internal::my_store_ptr(ref_pos,ref_length,record); // Position to row
622
record+= sort_form->getShare()->db_record_offset;
625
file->position(sort_form->getInsertRecord());
627
if (error && error != HA_ERR_RECORD_DELETED)
633
if (!indexfile && !quick_select)
635
(void) file->extra(HA_EXTRA_NO_CACHE);
636
file->endTableScan();
638
return(HA_POS_ERROR);
641
param->examined_rows++;
642
if (error == 0 && (!select || select->skip_record() == 0))
644
if (idx == param->keys)
646
if (param->write_keys(sort_keys, idx, buffpek_pointers, tempfile))
647
return(HA_POS_ERROR);
651
param->make_sortkey(sort_keys[idx++], ref_pos);
658
/* It does not make sense to read more keys in case of a fatal error */
659
if (getSession().is_error())
665
index_merge quick select uses table->sort when retrieving rows, so free
666
resoures it has allocated.
668
read_record_info.end_read_record();
672
(void) file->extra(HA_EXTRA_NO_CACHE); /* End cacheing of records */
674
file->endTableScan();
677
if (getSession().is_error())
678
return(HA_POS_ERROR);
680
/* Signal we should use orignal column read and write maps */
681
sort_form->column_bitmaps_set(*save_read_set, *save_write_set);
683
if (error != HA_ERR_END_OF_FILE)
685
sort_form->print_error(error,MYF(ME_ERROR | ME_WAITTANG));
686
return(HA_POS_ERROR);
689
if (indexpos && idx && param->write_keys(sort_keys,idx,buffpek_pointers,tempfile))
691
return(HA_POS_ERROR);
694
return(my_b_inited(tempfile) ?
695
(ha_rows) (my_b_tell(tempfile)/param->rec_length) :
697
} /* find_all_keys */
702
Sort the buffer and write:
703
-# the sorted sequence to tempfile
704
-# a buffpek describing the sorted sequence position to buffpek_pointers
706
(was: Skriver en buffert med nycklar till filen)
708
@param param Sort parameters
709
@param sort_keys Array of pointers to keys to sort
710
@param count Number of elements in sort_keys array
711
@param buffpek_pointers One 'buffpek' struct will be written into this file.
712
The buffpek::{file_pos, count} will indicate where
713
the sorted data was stored.
714
@param tempfile The sorted sequence will be written into this file.
722
int SortParam::write_keys(register unsigned char **sort_keys, uint32_t count,
723
internal::IO_CACHE *buffpek_pointers, internal::IO_CACHE *tempfile)
727
internal::my_string_ptr_sort((unsigned char*) sort_keys, (uint32_t) count, sort_length);
728
if (!my_b_inited(tempfile) &&
729
tempfile->open_cached_file(drizzle_tmpdir.c_str(), TEMP_PREFIX, DISK_BUFFER_SIZE, MYF(MY_WME)))
733
/* check we won't have more buffpeks than we can possibly keep in memory */
734
if (my_b_tell(buffpek_pointers) + sizeof(buffpek) > (uint64_t)UINT_MAX)
739
buffpek.file_pos= my_b_tell(tempfile);
740
if ((ha_rows) count > max_rows)
741
count=(uint32_t) max_rows;
743
buffpek.count=(ha_rows) count;
745
for (unsigned char **ptr= sort_keys + count ; sort_keys != ptr ; sort_keys++)
747
if (my_b_write(tempfile, (unsigned char*) *sort_keys, (uint32_t) rec_length))
753
if (my_b_write(buffpek_pointers, (unsigned char*) &buffpek, sizeof(buffpek)))
763
Store length as suffix in high-byte-first order.
766
static inline void store_length(unsigned char *to, uint32_t length, uint32_t pack_length)
768
switch (pack_length) {
770
*to= (unsigned char) length;
773
mi_int2store(to, length);
776
mi_int3store(to, length);
779
mi_int4store(to, length);
785
/** Make a sort-key from record. */
787
void SortParam::make_sortkey(register unsigned char *to, unsigned char *ref_pos)
790
SortField *sort_field;
793
for (sort_field= local_sortorder ;
798
if ((field=sort_field->field))
800
if (field->maybe_null())
802
if (field->is_null())
804
if (sort_field->reverse)
805
memset(to, 255, sort_field->length+1);
807
memset(to, 0, sort_field->length+1);
808
to+= sort_field->length+1;
814
field->sort_string(to, sort_field->length);
818
Item *item=sort_field->item;
819
maybe_null= item->maybe_null;
821
switch (sort_field->result_type) {
824
const CHARSET_INFO * const cs=item->collation.collation;
825
char fill_char= ((cs->state & MY_CS_BINSORT) ? (char) 0 : ' ');
827
uint32_t sort_field_length;
831
/* All item->str() to use some extra byte for end null.. */
832
String tmp((char*) to,sort_field->length+4,cs);
833
String *res= item->str_result(&tmp);
837
memset(to-1, 0, sort_field->length+1);
841
This should only happen during extreme conditions if we run out
842
of memory or have an item marked not null when it can be null.
843
This code is here mainly to avoid a hard crash in this case.
846
memset(to, 0, sort_field->length); // Avoid crash
850
length= res->length();
851
sort_field_length= sort_field->length - sort_field->suffix_length;
852
diff=(int) (sort_field_length - length);
856
length= sort_field_length;
858
if (sort_field->suffix_length)
860
/* Store length last in result_string */
861
store_length(to + sort_field_length, length,
862
sort_field->suffix_length);
864
if (sort_field->need_strxnfrm)
866
char *from=(char*) res->ptr();
868
if ((unsigned char*) from == to)
870
set_if_smaller(length,sort_field->length);
871
memcpy(tmp_buffer,from,length);
874
tmp_length= my_strnxfrm(cs,to,sort_field->length,
875
(unsigned char*) from, length);
876
assert(tmp_length == sort_field->length);
880
my_strnxfrm(cs,(unsigned char*)to,length,(const unsigned char*)res->ptr(),length);
881
cs->cset->fill(cs, (char *)to+length,diff,fill_char);
887
int64_t value= item->val_int_result();
891
if (item->null_value)
894
memset(to-1, 0, sort_field->length+1);
897
memset(to, 0, sort_field->length);
902
to[7]= (unsigned char) value;
903
to[6]= (unsigned char) (value >> 8);
904
to[5]= (unsigned char) (value >> 16);
905
to[4]= (unsigned char) (value >> 24);
906
to[3]= (unsigned char) (value >> 32);
907
to[2]= (unsigned char) (value >> 40);
908
to[1]= (unsigned char) (value >> 48);
909
if (item->unsigned_flag) /* Fix sign */
910
to[0]= (unsigned char) (value >> 56);
912
to[0]= (unsigned char) (value >> 56) ^ 128; /* Reverse signbit */
917
my_decimal dec_buf, *dec_val= item->val_decimal_result(&dec_buf);
920
if (item->null_value)
922
memset(to, 0, sort_field->length+1);
928
my_decimal2binary(E_DEC_FATAL_ERROR, dec_val, to,
929
item->max_length - (item->decimals ? 1:0),
935
double value= item->val_result();
938
if (item->null_value)
940
memset(to, 0, sort_field->length+1);
946
change_double_for_sort(value,(unsigned char*) to);
951
// This case should never be choosen
957
if (sort_field->reverse)
961
length=sort_field->length;
964
*to = (unsigned char) (~ *to);
970
to+= sort_field->length;
977
Save field values appended to sorted fields.
978
First null bit indicators are appended then field values follow.
979
In this implementation we use fixed layout for field values -
980
the same for all records.
982
sort_addon_field *addonf= addon_field;
983
unsigned char *nulls= to;
985
memset(nulls, 0, addonf->offset);
987
for ( ; (field= addonf->field) ; addonf++)
989
if (addonf->null_bit && field->is_null())
991
nulls[addonf->null_offset]|= addonf->null_bit;
993
memset(to, 0, addonf->length);
999
unsigned char *end= field->pack(to, field->ptr);
1000
uint32_t local_length= (uint32_t) ((to + addonf->length) - end);
1001
assert((int) local_length >= 0);
1003
memset(end, 0, local_length);
1005
(void) field->pack(to, field->ptr);
1008
to+= addonf->length;
1013
/* Save filepos last */
1014
memcpy(to, ref_pos, (size_t) ref_length);
1020
Register fields used by sorting in the sorted table's read set
1023
void SortParam::register_used_fields()
1025
SortField *sort_field;
1026
Table *table= sort_form;
1028
for (sort_field= local_sortorder ;
1033
if ((field= sort_field->field))
1035
if (field->getTable() == table)
1036
table->setReadSet(field->position());
1040
sort_field->item->walk(&Item::register_field_in_read_map, 1,
1041
(unsigned char *) table);
1047
sort_addon_field *addonf= addon_field;
1049
for ( ; (field= addonf->field) ; addonf++)
1050
table->setReadSet(field->position());
1054
/* Save filepos last */
1055
table->prepare_for_position();
1060
bool SortParam::save_index(unsigned char **sort_keys, uint32_t count, filesort_info *table_sort)
1065
internal::my_string_ptr_sort((unsigned char*) sort_keys, (uint32_t) count, sort_length);
1066
offset= rec_length - res_length;
1068
if ((ha_rows) count > max_rows)
1069
count=(uint32_t) max_rows;
1071
if (!(to= table_sort->record_pointers= (unsigned char*) malloc(res_length*count)))
1074
for (unsigned char **end_ptr= sort_keys+count ; sort_keys != end_ptr ; sort_keys++)
1076
memcpy(to, *sort_keys+offset, res_length);
1084
/** Merge buffers to make < MERGEBUFF2 buffers. */
1086
int FileSort::merge_many_buff(SortParam *param, unsigned char *sort_buffer,
1087
buffpek *buffpek_inst, uint32_t *maxbuffer, internal::IO_CACHE *t_file)
1089
internal::IO_CACHE t_file2,*from_file,*to_file,*temp;
1092
if (*maxbuffer < MERGEBUFF2)
1094
if (flush_io_cache(t_file) ||
1095
t_file2.open_cached_file(drizzle_tmpdir.c_str(),TEMP_PREFIX,DISK_BUFFER_SIZE, MYF(MY_WME)))
1100
from_file= t_file ; to_file= &t_file2;
1101
while (*maxbuffer >= MERGEBUFF2)
1103
register uint32_t i;
1105
if (from_file->reinit_io_cache(internal::READ_CACHE,0L,0,0))
1110
if (to_file->reinit_io_cache(internal::WRITE_CACHE,0L,0,0))
1115
lastbuff=buffpek_inst;
1116
for (i=0 ; i <= *maxbuffer-MERGEBUFF*3/2 ; i+=MERGEBUFF)
1118
if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
1119
buffpek_inst+i,buffpek_inst+i+MERGEBUFF-1,0))
1125
if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
1126
buffpek_inst+i,buffpek_inst+ *maxbuffer,0))
1131
if (flush_io_cache(to_file))
1136
temp=from_file; from_file=to_file; to_file=temp;
1137
from_file->setup_io_cache();
1138
to_file->setup_io_cache();
1139
*maxbuffer= (uint32_t) (lastbuff-buffpek_inst)-1;
1143
to_file->close_cached_file(); // This holds old result
1144
if (to_file == t_file)
1146
*t_file=t_file2; // Copy result file
1147
t_file->setup_io_cache();
1150
return(*maxbuffer >= MERGEBUFF2); /* Return 1 if interrupted */
1151
} /* merge_many_buff */
1155
Read data to buffer.
1158
(uint32_t)-1 if something goes wrong
1161
uint32_t FileSort::read_to_buffer(internal::IO_CACHE *fromfile, buffpek *buffpek_inst, uint32_t rec_length)
1163
register uint32_t count;
1166
if ((count= (uint32_t) min((ha_rows) buffpek_inst->max_keys,buffpek_inst->count)))
1168
if (pread(fromfile->file,(unsigned char*) buffpek_inst->base, (length= rec_length*count),buffpek_inst->file_pos) == 0)
1169
return((uint32_t) -1);
1171
buffpek_inst->key= buffpek_inst->base;
1172
buffpek_inst->file_pos+= length; /* New filepos */
1173
buffpek_inst->count-= count;
1174
buffpek_inst->mem_count= count;
1176
return (count*rec_length);
1177
} /* read_to_buffer */
1180
class compare_functor
1182
qsort2_cmp key_compare;
1183
void *key_compare_arg;
1186
compare_functor(qsort2_cmp in_key_compare, void *in_compare_arg) :
1187
key_compare(in_key_compare),
1188
key_compare_arg(in_compare_arg)
1191
inline bool operator()(const buffpek *i, const buffpek *j) const
1193
int val= key_compare(key_compare_arg, &i->key, &j->key);
1201
Merge buffers to one buffer.
1203
@param param Sort parameter
1204
@param from_file File with source data (buffpeks point to this file)
1205
@param to_file File to write the sorted result data.
1206
@param sort_buffer Buffer for data to store up to MERGEBUFF2 sort keys.
1207
@param lastbuff OUT Store here buffpek describing data written to to_file
1208
@param Fb First element in source buffpeks array
1209
@param Tb Last element in source buffpeks array
1218
int FileSort::merge_buffers(SortParam *param, internal::IO_CACHE *from_file,
1219
internal::IO_CACHE *to_file, unsigned char *sort_buffer,
1220
buffpek *lastbuff, buffpek *Fb, buffpek *Tb,
1224
uint32_t rec_length,res_length,offset;
1227
ha_rows max_rows,org_max_rows;
1228
internal::my_off_t to_start_filepos;
1229
unsigned char *strpos;
1230
buffpek *buffpek_inst;
1232
void *first_cmp_arg;
1233
volatile Session::killed_state_t *killed= getSession().getKilledPtr();
1234
Session::killed_state_t not_killable;
1236
getSession().status_var.filesort_merge_passes++;
1237
if (param->not_killable)
1239
killed= ¬_killable;
1240
not_killable= Session::NOT_KILLED;
1244
rec_length= param->rec_length;
1245
res_length= param->res_length;
1246
sort_length= param->sort_length;
1247
offset= rec_length-res_length;
1248
maxcount= (uint32_t) (param->keys/((uint32_t) (Tb-Fb) +1));
1249
to_start_filepos= my_b_tell(to_file);
1250
strpos= (unsigned char*) sort_buffer;
1251
org_max_rows=max_rows= param->max_rows;
1253
/* The following will fire if there is not enough space in sort_buffer */
1254
assert(maxcount!=0);
1256
if (param->unique_buff)
1258
cmp= param->compare;
1259
first_cmp_arg= (void *) ¶m->cmp_context;
1263
cmp= internal::get_ptr_compare(sort_length);
1264
first_cmp_arg= (void*) &sort_length;
1266
priority_queue<buffpek *, vector<buffpek *>, compare_functor >
1267
queue(compare_functor(cmp, first_cmp_arg));
1268
for (buffpek_inst= Fb ; buffpek_inst <= Tb ; buffpek_inst++)
1270
buffpek_inst->base= strpos;
1271
buffpek_inst->max_keys= maxcount;
1272
strpos+= (uint32_t) (error= (int) read_to_buffer(from_file, buffpek_inst,
1277
buffpek_inst->max_keys= buffpek_inst->mem_count; // If less data in buffers than expected
1278
queue.push(buffpek_inst);
1281
if (param->unique_buff)
1284
Called by Unique::get()
1285
Copy the first argument to param->unique_buff for unique removal.
1286
Store it also in 'to_file'.
1288
This is safe as we know that there is always more than one element
1289
in each block to merge (This is guaranteed by the Unique:: algorithm
1291
buffpek_inst= queue.top();
1292
memcpy(param->unique_buff, buffpek_inst->key, rec_length);
1293
if (my_b_write(to_file, (unsigned char*) buffpek_inst->key, rec_length))
1297
buffpek_inst->key+= rec_length;
1298
buffpek_inst->mem_count--;
1304
/* Top element has been used */
1306
queue.push(buffpek_inst);
1310
cmp= 0; // Not unique
1313
while (queue.size() > 1)
1321
buffpek_inst= queue.top();
1322
if (cmp) // Remove duplicates
1324
if (!(*cmp)(first_cmp_arg, &(param->unique_buff),
1325
(unsigned char**) &buffpek_inst->key))
1326
goto skip_duplicate;
1327
memcpy(param->unique_buff, buffpek_inst->key, rec_length);
1331
if (my_b_write(to_file,(unsigned char*) buffpek_inst->key, rec_length))
1338
if (my_b_write(to_file, (unsigned char*) buffpek_inst->key+offset, res_length))
1350
buffpek_inst->key+= rec_length;
1351
if (! --buffpek_inst->mem_count)
1353
if (!(error= (int) read_to_buffer(from_file,buffpek_inst,
1357
break; /* One buffer have been removed */
1359
else if (error == -1)
1364
/* Top element has been replaced */
1366
queue.push(buffpek_inst);
1369
buffpek_inst= queue.top();
1370
buffpek_inst->base= sort_buffer;
1371
buffpek_inst->max_keys= param->keys;
1374
As we know all entries in the buffer are unique, we only have to
1375
check if the first one is the same as the last one we wrote
1379
if (!(*cmp)(first_cmp_arg, &(param->unique_buff), (unsigned char**) &buffpek_inst->key))
1381
buffpek_inst->key+= rec_length; // Remove duplicate
1382
--buffpek_inst->mem_count;
1388
if ((ha_rows) buffpek_inst->mem_count > max_rows)
1389
{ /* Don't write too many records */
1390
buffpek_inst->mem_count= (uint32_t) max_rows;
1391
buffpek_inst->count= 0; /* Don't read more */
1393
max_rows-= buffpek_inst->mem_count;
1396
if (my_b_write(to_file,(unsigned char*) buffpek_inst->key,
1397
(rec_length*buffpek_inst->mem_count)))
1404
register unsigned char *end;
1405
strpos= buffpek_inst->key+offset;
1406
for (end= strpos+buffpek_inst->mem_count*rec_length ;
1408
strpos+= rec_length)
1410
if (my_b_write(to_file, (unsigned char *) strpos, res_length))
1418
while ((error=(int) read_to_buffer(from_file,buffpek_inst, rec_length))
1419
!= -1 && error != 0);
1422
lastbuff->count= min(org_max_rows-max_rows, param->max_rows);
1423
lastbuff->file_pos= to_start_filepos;
1426
} /* merge_buffers */
1429
/* Do a merge to output-file (save only positions) */
1431
int FileSort::merge_index(SortParam *param, unsigned char *sort_buffer,
1432
buffpek *buffpek_inst, uint32_t maxbuffer,
1433
internal::IO_CACHE *tempfile, internal::IO_CACHE *outfile)
1435
if (merge_buffers(param,tempfile,outfile,sort_buffer,buffpek_inst,buffpek_inst,
1436
buffpek_inst+maxbuffer,1))
1443
static uint32_t suffix_length(uint32_t string_length)
1445
if (string_length < 256)
1447
if (string_length < 256L*256L)
1449
if (string_length < 256L*256L*256L)
1451
return 4; // Can't sort longer than 4G
1457
Calculate length of sort key.
1459
@param sortorder Order of items to sort
1460
@param s_length Number of items to sort
1461
@param[out] multi_byte_charset Set to 1 if we are using multi-byte charset
1462
(In which case we have to use strxnfrm())
1465
sortorder->length is updated for each sort item.
1467
sortorder->need_strxnfrm is set 1 if we have to use strxnfrm
1470
Total length of sort buffer in bytes
1473
uint32_t FileSort::sortlength(SortField *sortorder, uint32_t s_length, bool *multi_byte_charset)
1475
register uint32_t length;
1476
const CHARSET_INFO *cs;
1477
*multi_byte_charset= 0;
1480
for (; s_length-- ; sortorder++)
1482
sortorder->need_strxnfrm= 0;
1483
sortorder->suffix_length= 0;
1484
if (sortorder->field)
1486
cs= sortorder->field->sort_charset();
1487
sortorder->length= sortorder->field->sort_length();
1489
if (use_strnxfrm((cs=sortorder->field->sort_charset())))
1491
sortorder->need_strxnfrm= 1;
1492
*multi_byte_charset= 1;
1493
sortorder->length= cs->coll->strnxfrmlen(cs, sortorder->length);
1495
if (sortorder->field->maybe_null())
1496
length++; // Place for NULL marker
1500
sortorder->result_type= sortorder->item->result_type();
1501
if (sortorder->item->result_as_int64_t())
1502
sortorder->result_type= INT_RESULT;
1504
switch (sortorder->result_type) {
1506
sortorder->length=sortorder->item->max_length;
1507
set_if_smaller(sortorder->length,
1508
getSession().variables.max_sort_length);
1509
if (use_strnxfrm((cs=sortorder->item->collation.collation)))
1511
sortorder->length= cs->coll->strnxfrmlen(cs, sortorder->length);
1512
sortorder->need_strxnfrm= 1;
1513
*multi_byte_charset= 1;
1515
else if (cs == &my_charset_bin)
1517
/* Store length last to be able to sort blob/varbinary */
1518
sortorder->suffix_length= suffix_length(sortorder->length);
1519
sortorder->length+= sortorder->suffix_length;
1523
sortorder->length=8; // Size of intern int64_t
1525
case DECIMAL_RESULT:
1527
my_decimal_get_binary_size(sortorder->item->max_length -
1528
(sortorder->item->decimals ? 1 : 0),
1529
sortorder->item->decimals);
1532
sortorder->length=sizeof(double);
1535
// This case should never be choosen
1539
if (sortorder->item->maybe_null)
1540
length++; // Place for NULL marker
1542
set_if_smaller(sortorder->length, (size_t)getSession().variables.max_sort_length);
1543
length+=sortorder->length;
1545
sortorder->field= (Field*) 0; // end marker
1551
Get descriptors of fields appended to sorted fields and
1552
calculate its total length.
1554
The function first finds out what fields are used in the result set.
1555
Then it calculates the length of the buffer to store the values of
1556
these fields together with the value of sort values.
1557
If the calculated length is not greater than max_length_for_sort_data
1558
the function allocates memory for an array of descriptors containing
1559
layouts for the values of the non-sorted fields in the buffer and
1562
@param ptabfield Array of references to the table fields
1563
@param sortlength Total length of sorted fields
1564
@param[out] plength Total length of appended fields
1567
The null bits for the appended values are supposed to be put together
1568
and stored the buffer just ahead of the value of the first field.
1571
Pointer to the layout descriptors for the appended fields, if any
1573
NULL if we do not store field values with sort data.
1576
sort_addon_field *FileSort::get_addon_fields(Field **ptabfield, uint32_t sortlength_arg, uint32_t *plength)
1580
sort_addon_field *addonf;
1583
uint32_t null_fields= 0;
1586
If there is a reference to a field in the query add it
1587
to the the set of appended fields.
1588
Note for future refinement:
1589
This this a too strong condition.
1590
Actually we need only the fields referred in the
1591
result set. And for some of them it makes sense to use
1592
the values directly from sorted fields.
1596
for (pfield= ptabfield; (field= *pfield) ; pfield++)
1598
if (!(field->isReadSet()))
1600
if (field->flags & BLOB_FLAG)
1602
length+= field->max_packed_col_length(field->pack_length());
1603
if (field->maybe_null())
1609
length+= (null_fields+7)/8;
1611
if (length+sortlength_arg > getSession().variables.max_length_for_sort_data ||
1612
!(addonf= (sort_addon_field *) malloc(sizeof(sort_addon_field)*
1617
length= (null_fields+7)/8;
1619
for (pfield= ptabfield; (field= *pfield) ; pfield++)
1621
if (!(field->isReadSet()))
1623
addonf->field= field;
1624
addonf->offset= length;
1625
if (field->maybe_null())
1627
addonf->null_offset= null_fields/8;
1628
addonf->null_bit= 1<<(null_fields & 7);
1633
addonf->null_offset= 0;
1634
addonf->null_bit= 0;
1636
addonf->length= field->max_packed_col_length(field->pack_length());
1637
length+= addonf->length;
1640
addonf->field= 0; // Put end marker
1642
return (addonf-fields);
1647
Copy (unpack) values appended to sorted fields from a buffer back to
1648
their regular positions specified by the Field::ptr pointers.
1650
@param addon_field Array of descriptors for appended fields
1651
@param buff Buffer which to unpack the value from
1654
The function is supposed to be used only as a callback function
1655
when getting field values for the sorted result set.
1662
unpack_addon_fields(sort_addon_field *addon_field, unsigned char *buff)
1665
sort_addon_field *addonf= addon_field;
1667
for ( ; (field= addonf->field) ; addonf++)
1669
if (addonf->null_bit && (addonf->null_bit & buff[addonf->null_offset]))
1674
field->set_notnull();
1675
field->unpack(field->ptr, buff + addonf->offset);
1680
** functions to change a double or float to a sortable string
1681
** The following should work for IEEE
1684
#define DBL_EXP_DIG (sizeof(double)*8-DBL_MANT_DIG)
1686
void change_double_for_sort(double nr,unsigned char *to)
1688
unsigned char *tmp=(unsigned char*) to;
1690
{ /* Change to zero string */
1691
tmp[0]=(unsigned char) 128;
1692
memset(tmp+1, 0, sizeof(nr)-1);
1696
#ifdef WORDS_BIGENDIAN
1697
memcpy(tmp,&nr,sizeof(nr));
1700
unsigned char *ptr= (unsigned char*) &nr;
1701
#if defined(__FLOAT_WORD_ORDER) && (__FLOAT_WORD_ORDER == __BIG_ENDIAN)
1702
tmp[0]= ptr[3]; tmp[1]=ptr[2]; tmp[2]= ptr[1]; tmp[3]=ptr[0];
1703
tmp[4]= ptr[7]; tmp[5]=ptr[6]; tmp[6]= ptr[5]; tmp[7]=ptr[4];
1705
tmp[0]= ptr[7]; tmp[1]=ptr[6]; tmp[2]= ptr[5]; tmp[3]=ptr[4];
1706
tmp[4]= ptr[3]; tmp[5]=ptr[2]; tmp[6]= ptr[1]; tmp[7]=ptr[0];
1710
if (tmp[0] & 128) /* Negative */
1711
{ /* make complement */
1713
for (i=0 ; i < sizeof(nr); i++)
1714
tmp[i]=tmp[i] ^ (unsigned char) 255;
1717
{ /* Set high and move exponent one up */
1718
uint16_t exp_part=(((uint16_t) tmp[0] << 8) | (uint16_t) tmp[1] |
1720
exp_part+= (uint16_t) 1 << (16-1-DBL_EXP_DIG);
1721
tmp[0]= (unsigned char) (exp_part >> 8);
1722
tmp[1]= (unsigned char) exp_part;
1727
} /* namespace drizzled */
added
removed
.pc/debian-changes-2010.12.06-0ubuntu4/drizzled/filesort.cc
