191 bool sort_positions, ha_rows &examined_rows)
194 uint32_t memavl= 0, min_sort_memory;
196 size_t allocated_sort_memory= 0;
198 ha_rows records= HA_POS_ERROR;
199 unsigned char **sort_keys= 0;
205 bool multi_byte_charset;
213 table->sort.io_cache= NULL;
215 TableList *tab= table->pos_in_table_list;
218 DRIZZLE_FILESORT_START(table->getShare()->getSchemaName(), table->getShare()->getTableName());
227 outfile= table_sort.io_cache;
228 assert(tempfile.buffer == 0);
229 assert(buffpek_pointers.buffer == 0);
231 param.sort_length=
sortlength(sortorder, s_length, &multi_byte_charset);
232 param.ref_length= table->cursor->ref_length;
234 if (!(table->cursor->getEngine()->check_flag(HTON_BIT_FAST_KEY_READ)) && !sort_positions)
242 ¶m.addon_length);
245 table_sort.addon_buf= 0;
246 table_sort.addon_length= param.addon_length;
247 table_sort.addon_field= param.addon_field;
249 if (param.addon_field)
251 param.res_length= param.addon_length;
252 table_sort.addon_buf= (
unsigned char *) malloc(param.addon_length);
256 param.res_length= param.ref_length;
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
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();
289 if (records == HA_POS_ERROR)
291 selected_records_file= 0;
294 if (multi_byte_charset)
295 param.tmp_buffer= (
char*) malloc(param.sort_length);
297 memavl= getSession().variables.sortbuff_size;
298 min_sort_memory= max((uint32_t)MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2);
299 while (memavl >= min_sort_memory)
302 uint32_t keys= memavl/(param.rec_length+
sizeof(
char*));
303 param.keys= (uint32_t) min(records+1, (ha_rows)keys);
305 allocated_sort_memory= param.keys * param.rec_length;
306 if (not global_sort_buffer.add(allocated_sort_memory))
308 my_error(ER_OUT_OF_GLOBAL_SORTMEMORY, MYF(ME_ERROR+ME_WAITTANG));
312 if ((table_sort.sort_keys=
314 param.keys, param.rec_length)))
317 global_sort_buffer.sub(allocated_sort_memory);
319 if ((memavl= memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
320 memavl= min_sort_memory;
322 sort_keys= table_sort.sort_keys;
323 if (memavl < min_sort_memory)
325 my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR+ME_WAITTANG));
329 if (buffpek_pointers.open_cached_file(drizzle_tmpdir.c_str(),TEMP_PREFIX, DISK_BUFFER_SIZE, MYF(MY_WME)))
335 param.sort_form= table;
336 param.end=(param.local_sortorder=sortorder)+s_length;
337 if ((records=
find_all_keys(¶m,select,sort_keys, &buffpek_pointers,
338 &tempfile, selected_records_file)) == HA_POS_ERROR)
342 maxbuffer= (uint32_t)(buffpek_pointers.tell() /
sizeof(*buffpek_inst));
346 param.save_index(sort_keys,(uint32_t) records, &table_sort);
350 if (table_sort.buffpek && table_sort.buffpek_len < maxbuffer)
352 free(table_sort.buffpek);
353 table_sort.buffpek = 0;
355 if (!(table_sort.buffpek=
360 buffpek_inst= (
buffpek *) table_sort.buffpek;
361 table_sort.buffpek_len= maxbuffer;
362 buffpek_pointers.close_cached_file();
364 if (not outfile->inited() && outfile->open_cached_file(drizzle_tmpdir.c_str(),TEMP_PREFIX,READ_RECORD_BUFFER, MYF(MY_WME)))
378 param.keys=((param.keys*(param.rec_length+
sizeof(
char*))) / param.rec_length-1);
381 if (
merge_many_buff(¶m,(
unsigned char*) sort_keys,buffpek_inst,&maxbuffer, &tempfile))
386 if (tempfile.flush() || tempfile.
reinit_io_cache(internal::READ_CACHE,0L,0,0))
391 if (merge_index(¶m,(
unsigned char*) sort_keys,buffpek_inst,maxbuffer,&tempfile, outfile))
397 if (records > param.max_rows)
399 records= param.max_rows;
404 if (not subselect || not subselect->is_uncacheable())
407 table_sort.sort_keys= 0;
409 table_sort.buffpek= 0;
410 table_sort.buffpek_len= 0;
413 tempfile.close_cached_file();
414 buffpek_pointers.close_cached_file();
416 if (outfile->inited())
418 if (outfile->flush())
423 internal::my_off_t save_pos= outfile->pos_in_file;
429 outfile->end_of_file=save_pos;
435 my_message(ER_FILSORT_ABORT, ER(ER_FILSORT_ABORT),
436 MYF(ME_ERROR+ME_WAITTANG));
440 getSession().status_var.filesort_rows+= (uint32_t) records;
442 examined_rows= param.examined_rows;
443 global_sort_buffer.sub(allocated_sort_memory);
444 table->sort= table_sort;
445 DRIZZLE_FILESORT_DONE(error, records);
446 return (error ? HA_POS_ERROR : records);
526 unsigned char **sort_keys,
530 int error,flag,quick_select;
531 uint32_t idx,indexpos,ref_length;
532 unsigned char *ref_pos,*next_pos,ref_buff[MAX_REFLENGTH];
533 internal::my_off_t record;
535 volatile Session::killed_state_t *killed= getSession().getKilledPtr();
537 boost::dynamic_bitset<> *save_read_set= NULL;
538 boost::dynamic_bitset<> *save_write_set= NULL;
541 error=quick_select=0;
542 sort_form=param->sort_form;
544 ref_length=param->ref_length;
546 quick_select=select && select->
quick;
548 flag= ((!indexfile && ! file->isOrdered())
550 if (indexfile || flag)
551 ref_pos= &file->ref[0];
553 if (! indexfile && ! quick_select)
555 next_pos=(
unsigned char*) 0;
556 if (file->startTableScan(1))
557 return(HA_POS_ERROR);
558 file->extra_opt(HA_EXTRA_CACHE, getSession().variables.read_buff_size);
565 return(HA_POS_ERROR);
567 if (read_record_info.init_read_record(&getSession(), select->
quick->head, select, 1, 1))
568 return(HA_POS_ERROR);
572 save_read_set= sort_form->read_set;
573 save_write_set= sort_form->write_set;
575 sort_form->tmp_set.reset();
577 sort_form->read_set= &sort_form->tmp_set;
578 param->register_used_fields();
579 if (select && select->
cond)
580 select->
cond->walk(&Item::register_field_in_read_map, 1,
581 (
unsigned char*) sort_form);
582 sort_form->column_bitmaps_set(sort_form->tmp_set, sort_form->tmp_set);
588 if ((error= read_record_info.read_record(&read_record_info)))
590 error= HA_ERR_END_OF_FILE;
593 file->position(sort_form->getInsertRecord());
599 if (indexfile->read(ref_pos, ref_length))
601 error= errno ? errno : -1;
604 error=file->rnd_pos(sort_form->getInsertRecord(),next_pos);
608 error=file->rnd_next(sort_form->getInsertRecord());
612 internal::my_store_ptr(ref_pos,ref_length,record);
613 record+= sort_form->getShare()->db_record_offset;
616 file->position(sort_form->getInsertRecord());
618 if (error && error != HA_ERR_RECORD_DELETED)
624 if (!indexfile && !quick_select)
626 (void) file->extra(HA_EXTRA_NO_CACHE);
627 file->endTableScan();
629 return(HA_POS_ERROR);
632 param->examined_rows++;
633 if (error == 0 && (!select || select->skip_record() == 0))
635 if (idx == param->keys)
637 if (param->
write_keys(sort_keys, idx, buffpek_pointers, tempfile))
638 return(HA_POS_ERROR);
650 if (getSession().is_error())
659 read_record_info.end_read_record();
663 (void) file->extra(HA_EXTRA_NO_CACHE);
665 file->endTableScan();
668 if (getSession().is_error())
669 return(HA_POS_ERROR);
672 sort_form->column_bitmaps_set(*save_read_set, *save_write_set);
674 if (error != HA_ERR_END_OF_FILE)
676 sort_form->print_error(error,MYF(ME_ERROR | ME_WAITTANG));
677 return(HA_POS_ERROR);
680 if (indexpos && idx && param->
write_keys(sort_keys,idx,buffpek_pointers,tempfile))
682 return(HA_POS_ERROR);
685 return tempfile->inited() ? (ha_rows) (tempfile->tell() / param->rec_length) : idx;
782 for (sort_field= local_sortorder ;
787 if ((field=sort_field->
field))
789 if (field->maybe_null())
791 if (field->is_null())
794 memset(to, 255, sort_field->
length+1);
796 memset(to, 0, sort_field->
length+1);
797 to+= sort_field->
length+1;
803 field->sort_string(to, sort_field->
length);
814 char fill_char= ((cs->state & MY_CS_BINSORT) ? (char) 0 :
' ');
816 uint32_t sort_field_length;
822 String *res= item->str_result(&tmp);
826 memset(to-1, 0, sort_field->
length+1);
835 memset(to, 0, sort_field->
length);
839 length= res->length();
841 diff=(int) (sort_field_length - length);
845 length= sort_field_length;
855 char *from=(
char*) res->ptr();
857 if ((
unsigned char*) from == to)
859 set_if_smaller(length,sort_field->
length);
860 memcpy(tmp_buffer,from,length);
863 tmp_length= cs->strnxfrm(to,sort_field->
length, (
unsigned char*) from, length);
865 assert(tmp_length == sort_field->
length);
869 cs->strnxfrm((
unsigned char*)to,length,(
const unsigned char*)res->ptr(),length);
870 cs->cset->fill(cs, (
char *)to+length,diff,fill_char);
876 int64_t value= item->val_int_result();
880 if (item->null_value)
883 memset(to-1, 0, sort_field->
length+1);
886 memset(to, 0, sort_field->
length);
891 to[7]= (
unsigned char) value;
892 to[6]= (
unsigned char) (value >> 8);
893 to[5]= (
unsigned char) (value >> 16);
894 to[4]= (
unsigned char) (value >> 24);
895 to[3]= (
unsigned char) (value >> 32);
896 to[2]= (
unsigned char) (value >> 40);
897 to[1]= (
unsigned char) (value >> 48);
898 if (item->unsigned_flag)
899 to[0]= (
unsigned char) (value >> 56);
901 to[0]= (
unsigned char) (value >> 56) ^ 128;
906 type::Decimal dec_buf, *dec_val= item->val_decimal_result(&dec_buf);
909 if (item->null_value)
911 memset(to, 0, sort_field->
length+1);
917 dec_val->val_binary(E_DEC_FATAL_ERROR, to,
918 item->max_length - (item->decimals ? 1:0),
924 double value= item->val_result();
927 if (item->null_value)
929 memset(to, 0, sort_field->
length+1);
935 change_double_for_sort(value,(
unsigned char*) to);
950 length=sort_field->
length;
953 *to = (
unsigned char) (~ *to);
972 unsigned char *nulls= to;
974 memset(nulls, 0, addonf->offset);
976 for ( ; (field= addonf->field) ; addonf++)
978 if (addonf->null_bit && field->is_null())
980 nulls[addonf->null_offset]|= addonf->null_bit;
982 memset(to, 0, addonf->length);
988 unsigned char *end= field->pack(to, field->ptr);
989 uint32_t local_length= (uint32_t) ((to + addonf->length) - end);
990 assert((
int) local_length >= 0);
992 memset(end, 0, local_length);
994 (void) field->pack(to, field->ptr);
1003 memcpy(to, ref_pos, (
size_t) ref_length);
1075 if (*maxbuffer < MERGEBUFF2)
1077 if (t_file->flush() ||
1078 t_file2.open_cached_file(drizzle_tmpdir.c_str(),TEMP_PREFIX,DISK_BUFFER_SIZE, MYF(MY_WME)))
1083 from_file= t_file ; to_file= &t_file2;
1084 while (*maxbuffer >= MERGEBUFF2)
1091 lastbuff= buffpek_inst;
1092 for (; i <= *maxbuffer - MERGEBUFF * 3 / 2; i += MERGEBUFF)
1094 if (
merge_buffers(param, from_file, to_file, sort_buffer, lastbuff++, buffpek_inst + i, buffpek_inst + i + MERGEBUFF - 1, 0))
1100 if (
merge_buffers(param, from_file, to_file, sort_buffer, lastbuff++, buffpek_inst + i, buffpek_inst + *maxbuffer, 0)
1101 || to_file->flush())
1104 temp=from_file; from_file=to_file; to_file=temp;
1107 *maxbuffer= (uint32_t) (lastbuff-buffpek_inst)-1;
1111 to_file->close_cached_file();
1112 if (to_file == t_file)
1118 return(*maxbuffer >= MERGEBUFF2);
1192 uint32_t rec_length,res_length,offset;
1195 ha_rows max_rows,org_max_rows;
1196 internal::my_off_t to_start_filepos;
1197 unsigned char *strpos;
1200 void *first_cmp_arg;
1201 volatile Session::killed_state_t *killed= getSession().getKilledPtr();
1202 Session::killed_state_t not_killable;
1204 getSession().status_var.filesort_merge_passes++;
1205 if (param->not_killable)
1207 killed= ¬_killable;
1208 not_killable= Session::NOT_KILLED;
1212 rec_length= param->rec_length;
1213 res_length= param->res_length;
1214 sort_length= param->sort_length;
1215 offset= rec_length-res_length;
1216 maxcount= (uint32_t) (param->keys/((uint32_t) (Tb-Fb) +1));
1217 to_start_filepos= to_file->tell();
1218 strpos= (
unsigned char*) sort_buffer;
1219 org_max_rows=max_rows= param->max_rows;
1222 assert(maxcount!=0);
1224 if (param->unique_buff)
1226 cmp= param->compare;
1227 first_cmp_arg= (
void *) ¶m->cmp_context;
1231 cmp= internal::get_ptr_compare(sort_length);
1232 first_cmp_arg= (
void*) &sort_length;
1236 for (buffpek_inst= Fb ; buffpek_inst <= Tb ; buffpek_inst++)
1238 buffpek_inst->base= strpos;
1239 buffpek_inst->max_keys= maxcount;
1240 strpos+= (uint32_t) (error= (
int)
read_to_buffer(from_file, buffpek_inst,
1245 buffpek_inst->max_keys= buffpek_inst->mem_count;
1246 queue.push(buffpek_inst);
1249 if (param->unique_buff)
1259 buffpek_inst= queue.top();
1260 memcpy(param->unique_buff, buffpek_inst->key, rec_length);
1261 if (to_file->write(buffpek_inst->key, rec_length))
1265 buffpek_inst->key+= rec_length;
1266 buffpek_inst->mem_count--;
1274 queue.push(buffpek_inst);
1281 while (queue.size() > 1)
1289 buffpek_inst= queue.top();
1292 if (!(*cmp)(first_cmp_arg, &(param->unique_buff),
1293 (
unsigned char**) &buffpek_inst->key))
1294 goto skip_duplicate;
1295 memcpy(param->unique_buff, buffpek_inst->key, rec_length);
1299 if (to_file->write(buffpek_inst->key, rec_length))
1306 if (to_file->write(buffpek_inst->key+offset, res_length))
1318 buffpek_inst->key+= rec_length;
1319 if (! --buffpek_inst->mem_count)
1327 else if (error == -1)
1334 queue.push(buffpek_inst);
1337 buffpek_inst= queue.top();
1338 buffpek_inst->base= sort_buffer;
1339 buffpek_inst->max_keys= param->keys;
1347 if (!(*cmp)(first_cmp_arg, &(param->unique_buff), (
unsigned char**) &buffpek_inst->key))
1349 buffpek_inst->key+= rec_length;
1350 --buffpek_inst->mem_count;
1356 if ((ha_rows) buffpek_inst->mem_count > max_rows)
1358 buffpek_inst->mem_count= (uint32_t) max_rows;
1359 buffpek_inst->count= 0;
1361 max_rows-= buffpek_inst->mem_count;
1364 if (to_file->write(buffpek_inst->key, (rec_length*buffpek_inst->mem_count)))
1372 strpos= buffpek_inst->key+offset;
1373 for (end= strpos+buffpek_inst->mem_count*rec_length ;
1375 strpos+= rec_length)
1377 if (to_file->write(strpos, res_length))
1385 while ((error=(
int)
read_to_buffer(from_file,buffpek_inst, rec_length))
1386 != -1 && error != 0);
1389 lastbuff->count= min(org_max_rows-max_rows, param->max_rows);
1390 lastbuff->file_pos= to_start_filepos;