1/* Copyright (c) 2000, 2015, Oracle and/or its affiliates.
2 Copyright (c) 2009, 2015, MariaDB
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA */
16
17
18/**
19 @file
20
21 @brief
22 Sorts a database
23*/
24
25#include "mariadb.h"
26#include "sql_priv.h"
27#include "filesort.h"
28#include <m_ctype.h>
29#include "sql_sort.h"
30#include "probes_mysql.h"
31#include "sql_base.h"
32#include "sql_test.h" // TEST_filesort
33#include "opt_range.h" // SQL_SELECT
34#include "bounded_queue.h"
35#include "filesort_utils.h"
36#include "sql_select.h"
37#include "debug_sync.h"
38
39/// How to write record_ref.
40#define WRITE_REF(file,from) \
41if (my_b_write((file),(uchar*) (from),param->ref_length)) \
42 DBUG_RETURN(1);
43
44 /* functions defined in this file */
45
46static uchar *read_buffpek_from_file(IO_CACHE *buffer_file, uint count,
47 uchar *buf);
48static ha_rows find_all_keys(THD *thd, Sort_param *param, SQL_SELECT *select,
49 SORT_INFO *fs_info,
50 IO_CACHE *buffer_file,
51 IO_CACHE *tempfile,
52 Bounded_queue<uchar, uchar> *pq,
53 ha_rows *found_rows);
54static bool write_keys(Sort_param *param, SORT_INFO *fs_info,
55 uint count, IO_CACHE *buffer_file, IO_CACHE *tempfile);
56static void make_sortkey(Sort_param *param, uchar *to, uchar *ref_pos);
57static void register_used_fields(Sort_param *param);
58static bool save_index(Sort_param *param, uint count,
59 SORT_INFO *table_sort);
60static uint suffix_length(ulong string_length);
61static uint sortlength(THD *thd, SORT_FIELD *sortorder, uint s_length,
62 bool *multi_byte_charset);
63static SORT_ADDON_FIELD *get_addon_fields(ulong max_length_for_sort_data,
64 Field **ptabfield,
65 uint sortlength,
66 LEX_STRING *addon_buf);
67static void unpack_addon_fields(struct st_sort_addon_field *addon_field,
68 uchar *buff, uchar *buff_end);
69static bool check_if_pq_applicable(Sort_param *param, SORT_INFO *info,
70 TABLE *table,
71 ha_rows records, size_t memory_available);
72
73void Sort_param::init_for_filesort(uint sortlen, TABLE *table,
74 ulong max_length_for_sort_data,
75 ha_rows maxrows, bool sort_positions)
76{
77 DBUG_ASSERT(addon_field == 0 && addon_buf.length == 0);
78
79 sort_length= sortlen;
80 ref_length= table->file->ref_length;
81 if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) &&
82 !table->fulltext_searched && !sort_positions)
83 {
84 /*
85 Get the descriptors of all fields whose values are appended
86 to sorted fields and get its total length in addon_buf.length
87 */
88 addon_field= get_addon_fields(max_length_for_sort_data,
89 table->field, sort_length, &addon_buf);
90 }
91 if (addon_field)
92 {
93 DBUG_ASSERT(addon_buf.length < UINT_MAX32);
94 res_length= (uint)addon_buf.length;
95 }
96 else
97 {
98 res_length= ref_length;
99 /*
100 The reference to the record is considered
101 as an additional sorted field
102 */
103 sort_length+= ref_length;
104 }
105 rec_length= sort_length + (uint)addon_buf.length;
106 max_rows= maxrows;
107}
108
109
110/**
111 Sort a table.
112 Creates a set of pointers that can be used to read the rows
113 in sorted order. This should be done with the functions
114 in records.cc.
115
116 Before calling filesort, one must have done
117 table->file->info(HA_STATUS_VARIABLE)
118
119 The result set is stored in
120 filesort_info->io_cache or
121 filesort_info->record_pointers.
122
123 @param thd Current thread
124 @param table Table to sort
125 @param filesort How to sort the table
126 @param[out] found_rows Store the number of found rows here.
127 This is the number of found rows after
128 applying WHERE condition.
129 @note
130 If we sort by position (like if filesort->sort_positions==true)
131 filesort() will call table->prepare_for_position().
132
133 @retval
134 0 Error
135 # SORT_INFO
136*/
137
138SORT_INFO *filesort(THD *thd, TABLE *table, Filesort *filesort,
139 Filesort_tracker* tracker, JOIN *join,
140 table_map first_table_bit)
141{
142 int error;
143 DBUG_ASSERT(thd->variables.sortbuff_size <= SIZE_T_MAX);
144 size_t memory_available= (size_t)thd->variables.sortbuff_size;
145 uint maxbuffer;
146 BUFFPEK *buffpek;
147 ha_rows num_rows= HA_POS_ERROR;
148 IO_CACHE tempfile, buffpek_pointers, *outfile;
149 Sort_param param;
150 bool multi_byte_charset;
151 Bounded_queue<uchar, uchar> pq;
152 SQL_SELECT *const select= filesort->select;
153 ha_rows max_rows= filesort->limit;
154 uint s_length= 0;
155
156 DBUG_ENTER("filesort");
157
158 if (!(s_length= filesort->make_sortorder(thd, join, first_table_bit)))
159 DBUG_RETURN(NULL); /* purecov: inspected */
160
161 DBUG_EXECUTE("info",TEST_filesort(filesort->sortorder,s_length););
162#ifdef SKIP_DBUG_IN_FILESORT
163 DBUG_PUSH(""); /* No DBUG here */
164#endif
165 SORT_INFO *sort;
166 TABLE_LIST *tab= table->pos_in_table_list;
167 Item_subselect *subselect= tab ? tab->containing_subselect() : 0;
168 MYSQL_FILESORT_START(table->s->db.str, table->s->table_name.str);
169 DEBUG_SYNC(thd, "filesort_start");
170
171 if (!(sort= new SORT_INFO))
172 return 0;
173
174 if (subselect && subselect->filesort_buffer.is_allocated())
175 {
176 /* Reuse cache from last call */
177 sort->filesort_buffer= subselect->filesort_buffer;
178 sort->buffpek= subselect->sortbuffer;
179 subselect->filesort_buffer.reset();
180 subselect->sortbuffer.str=0;
181 }
182
183 outfile= &sort->io_cache;
184
185 my_b_clear(&tempfile);
186 my_b_clear(&buffpek_pointers);
187 buffpek=0;
188 error= 1;
189 sort->found_rows= HA_POS_ERROR;
190
191 param.init_for_filesort(sortlength(thd, filesort->sortorder, s_length,
192 &multi_byte_charset),
193 table,
194 thd->variables.max_length_for_sort_data,
195 max_rows, filesort->sort_positions);
196
197 sort->addon_buf= param.addon_buf;
198 sort->addon_field= param.addon_field;
199 sort->unpack= unpack_addon_fields;
200 if (multi_byte_charset &&
201 !(param.tmp_buffer= (char*) my_malloc(param.sort_length,
202 MYF(MY_WME | MY_THREAD_SPECIFIC))))
203 goto err;
204
205 if (select && select->quick)
206 thd->inc_status_sort_range();
207 else
208 thd->inc_status_sort_scan();
209 thd->query_plan_flags|= QPLAN_FILESORT;
210 tracker->report_use(max_rows);
211
212 // If number of rows is not known, use as much of sort buffer as possible.
213 num_rows= table->file->estimate_rows_upper_bound();
214
215 if (check_if_pq_applicable(&param, sort,
216 table, num_rows, memory_available))
217 {
218 DBUG_PRINT("info", ("filesort PQ is applicable"));
219 thd->query_plan_flags|= QPLAN_FILESORT_PRIORITY_QUEUE;
220 status_var_increment(thd->status_var.filesort_pq_sorts_);
221 tracker->incr_pq_used();
222 const size_t compare_length= param.sort_length;
223 if (pq.init(param.max_rows,
224 true, // max_at_top
225 NULL, // compare_function
226 compare_length,
227 &make_sortkey, &param, sort->get_sort_keys()))
228 {
229 /*
230 If we fail to init pq, we have to give up:
231 out of memory means my_malloc() will call my_error().
232 */
233 DBUG_PRINT("info", ("failed to allocate PQ"));
234 DBUG_ASSERT(thd->is_error());
235 goto err;
236 }
237 // For PQ queries (with limit) we initialize all pointers.
238 sort->init_record_pointers();
239 }
240 else
241 {
242 DBUG_PRINT("info", ("filesort PQ is not applicable"));
243
244 size_t min_sort_memory= MY_MAX(MIN_SORT_MEMORY,
245 param.sort_length*MERGEBUFF2);
246 set_if_bigger(min_sort_memory, sizeof(BUFFPEK*)*MERGEBUFF2);
247 while (memory_available >= min_sort_memory)
248 {
249 ulonglong keys= memory_available / (param.rec_length + sizeof(char*));
250 param.max_keys_per_buffer= (uint) MY_MIN(num_rows, keys);
251 if (sort->alloc_sort_buffer(param.max_keys_per_buffer, param.rec_length))
252 break;
253 size_t old_memory_available= memory_available;
254 memory_available= memory_available/4*3;
255 if (memory_available < min_sort_memory &&
256 old_memory_available > min_sort_memory)
257 memory_available= min_sort_memory;
258 }
259 if (memory_available < min_sort_memory)
260 {
261 my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR + ME_FATALERROR));
262 goto err;
263 }
264 tracker->report_sort_buffer_size(sort->sort_buffer_size());
265 }
266
267 if (open_cached_file(&buffpek_pointers,mysql_tmpdir,TEMP_PREFIX,
268 DISK_BUFFER_SIZE, MYF(MY_WME)))
269 goto err;
270
271 param.sort_form= table;
272 param.end=(param.local_sortorder=filesort->sortorder)+s_length;
273 num_rows= find_all_keys(thd, &param, select,
274 sort,
275 &buffpek_pointers,
276 &tempfile,
277 pq.is_initialized() ? &pq : NULL,
278 &sort->found_rows);
279 if (num_rows == HA_POS_ERROR)
280 goto err;
281
282 maxbuffer= (uint) (my_b_tell(&buffpek_pointers)/sizeof(*buffpek));
283 tracker->report_merge_passes_at_start(thd->query_plan_fsort_passes);
284 tracker->report_row_numbers(param.examined_rows, sort->found_rows, num_rows);
285
286 if (maxbuffer == 0) // The whole set is in memory
287 {
288 if (save_index(&param, (uint) num_rows, sort))
289 goto err;
290 }
291 else
292 {
293 /* filesort cannot handle zero-length records during merge. */
294 DBUG_ASSERT(param.sort_length != 0);
295
296 if (sort->buffpek.str && sort->buffpek.length < maxbuffer)
297 {
298 my_free(sort->buffpek.str);
299 sort->buffpek.str= 0;
300 }
301 if (!(sort->buffpek.str=
302 (char *) read_buffpek_from_file(&buffpek_pointers, maxbuffer,
303 (uchar*) sort->buffpek.str)))
304 goto err;
305 sort->buffpek.length= maxbuffer;
306 buffpek= (BUFFPEK *) sort->buffpek.str;
307 close_cached_file(&buffpek_pointers);
308 /* Open cached file if it isn't open */
309 if (! my_b_inited(outfile) &&
310 open_cached_file(outfile,mysql_tmpdir,TEMP_PREFIX,READ_RECORD_BUFFER,
311 MYF(MY_WME)))
312 goto err;
313 if (reinit_io_cache(outfile,WRITE_CACHE,0L,0,0))
314 goto err;
315
316 /*
317 Use also the space previously used by string pointers in sort_buffer
318 for temporary key storage.
319 */
320 param.max_keys_per_buffer=((param.max_keys_per_buffer *
321 (param.rec_length + sizeof(char*))) /
322 param.rec_length - 1);
323 maxbuffer--; // Offset from 0
324 if (merge_many_buff(&param,
325 (uchar*) sort->get_sort_keys(),
326 buffpek,&maxbuffer,
327 &tempfile))
328 goto err;
329 if (flush_io_cache(&tempfile) ||
330 reinit_io_cache(&tempfile,READ_CACHE,0L,0,0))
331 goto err;
332 if (merge_index(&param,
333 (uchar*) sort->get_sort_keys(),
334 buffpek,
335 maxbuffer,
336 &tempfile,
337 outfile))
338 goto err;
339 }
340
341 if (num_rows > param.max_rows)
342 {
343 // If find_all_keys() produced more results than the query LIMIT.
344 num_rows= param.max_rows;
345 }
346 error= 0;
347
348 err:
349 my_free(param.tmp_buffer);
350 if (!subselect || !subselect->is_uncacheable())
351 {
352 sort->free_sort_buffer();
353 my_free(sort->buffpek.str);
354 }
355 else
356 {
357 /* Remember sort buffers for next subquery call */
358 subselect->filesort_buffer= sort->filesort_buffer;
359 subselect->sortbuffer= sort->buffpek;
360 sort->filesort_buffer.reset(); // Don't free this
361 }
362 sort->buffpek.str= 0;
363
364 close_cached_file(&tempfile);
365 close_cached_file(&buffpek_pointers);
366 if (my_b_inited(outfile))
367 {
368 if (flush_io_cache(outfile))
369 error=1;
370 {
371 my_off_t save_pos=outfile->pos_in_file;
372 /* For following reads */
373 if (reinit_io_cache(outfile,READ_CACHE,0L,0,0))
374 error=1;
375 outfile->end_of_file=save_pos;
376 }
377 }
378 tracker->report_merge_passes_at_end(thd->query_plan_fsort_passes);
379 if (unlikely(error))
380 {
381 int kill_errno= thd->killed_errno();
382 DBUG_ASSERT(thd->is_error() || kill_errno || thd->killed == ABORT_QUERY);
383
384 my_printf_error(ER_FILSORT_ABORT,
385 "%s: %s",
386 MYF(0),
387 ER_THD(thd, ER_FILSORT_ABORT),
388 kill_errno ? ER_THD(thd, kill_errno) :
389 thd->killed == ABORT_QUERY ? "" :
390 thd->get_stmt_da()->message());
391
392 if (global_system_variables.log_warnings > 1)
393 {
394 sql_print_warning("%s, host: %s, user: %s, thread: %lu, query: %-.4096s",
395 ER_THD(thd, ER_FILSORT_ABORT),
396 thd->security_ctx->host_or_ip,
397 &thd->security_ctx->priv_user[0],
398 (ulong) thd->thread_id,
399 thd->query());
400 }
401 }
402 else
403 thd->inc_status_sort_rows(num_rows);
404
405 sort->examined_rows= param.examined_rows;
406 sort->return_rows= num_rows;
407#ifdef SKIP_DBUG_IN_FILESORT
408 DBUG_POP(); /* Ok to DBUG */
409#endif
410
411 DBUG_PRINT("exit",
412 ("num_rows: %lld examined_rows: %lld found_rows: %lld",
413 (longlong) sort->return_rows, (longlong) sort->examined_rows,
414 (longlong) sort->found_rows));
415 MYSQL_FILESORT_DONE(error, num_rows);
416
417 if (unlikely(error))
418 {
419 delete sort;
420 sort= 0;
421 }
422 DBUG_RETURN(sort);
423} /* filesort */
424
425
426void Filesort::cleanup()
427{
428 if (select && own_select)
429 {
430 select->cleanup();
431 select= NULL;
432 }
433}
434
435
436uint Filesort::make_sortorder(THD *thd, JOIN *join, table_map first_table_bit)
437{
438 uint count;
439 SORT_FIELD *sort,*pos;
440 ORDER *ord;
441 DBUG_ENTER("make_sortorder");
442
443
444 count=0;
445 for (ord = order; ord; ord= ord->next)
446 count++;
447 if (!sortorder)
448 sortorder= (SORT_FIELD*) thd->alloc(sizeof(SORT_FIELD) * (count + 1));
449 pos= sort= sortorder;
450
451 if (!pos)
452 DBUG_RETURN(0);
453
454 for (ord= order; ord; ord= ord->next, pos++)
455 {
456 Item *first= ord->item[0];
457 /*
458 It is possible that the query plan is to read table t1, while the
459 sort criteria actually has "ORDER BY t2.col" and the WHERE clause has
460 a multi-equality(t1.col, t2.col, ...).
461 The optimizer detects such cases (grep for
462 UseMultipleEqualitiesToRemoveTempTable to see where), but doesn't
463 perform equality substitution in the order->item. We need to do the
464 substitution here ourselves.
465 */
466 table_map item_map= first->used_tables();
467 if (join && (item_map & ~join->const_table_map) &&
468 !(item_map & first_table_bit) && join->cond_equal &&
469 first->get_item_equal())
470 {
471 /*
472 Ok, this is the case descibed just above. Get the first element of the
473 multi-equality.
474 */
475 Item_equal *item_eq= first->get_item_equal();
476 first= item_eq->get_first(NO_PARTICULAR_TAB, NULL);
477 }
478
479 Item *item= first->real_item();
480 pos->field= 0; pos->item= 0;
481 if (item->type() == Item::FIELD_ITEM)
482 pos->field= ((Item_field*) item)->field;
483 else if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item())
484 pos->field= ((Item_sum*) item)->get_tmp_table_field();
485 else if (item->type() == Item::COPY_STR_ITEM)
486 { // Blob patch
487 pos->item= ((Item_copy*) item)->get_item();
488 }
489 else
490 pos->item= *ord->item;
491 pos->reverse= (ord->direction == ORDER::ORDER_DESC);
492 DBUG_ASSERT(pos->field != NULL || pos->item != NULL);
493 }
494 DBUG_RETURN(count);
495}
496
497
498/** Read 'count' number of buffer pointers into memory. */
499
500static uchar *read_buffpek_from_file(IO_CACHE *buffpek_pointers, uint count,
501 uchar *buf)
502{
503 size_t length= sizeof(BUFFPEK)*count;
504 uchar *tmp= buf;
505 DBUG_ENTER("read_buffpek_from_file");
506 if (count > UINT_MAX/sizeof(BUFFPEK))
507 return 0; /* sizeof(BUFFPEK)*count will overflow */
508 if (!tmp)
509 tmp= (uchar *)my_malloc(length, MYF(MY_WME | MY_THREAD_SPECIFIC));
510 if (tmp)
511 {
512 if (reinit_io_cache(buffpek_pointers,READ_CACHE,0L,0,0) ||
513 my_b_read(buffpek_pointers, (uchar*) tmp, length))
514 {
515 my_free(tmp);
516 tmp=0;
517 }
518 }
519 DBUG_RETURN(tmp);
520}
521
522#ifndef DBUG_OFF
523
524/* Buffer where record is returned */
525char dbug_print_row_buff[512];
526
527/* Temporary buffer for printing a column */
528char dbug_print_row_buff_tmp[512];
529
530/*
531 Print table's current row into a buffer and return a pointer to it.
532
533 This is intended to be used from gdb:
534
535 (gdb) p dbug_print_table_row(table)
536 $33 = "SUBQUERY2_t1(col_int_key,col_varchar_nokey)=(7,c)"
537 (gdb)
538
539 Only columns in table->read_set are printed
540*/
541
542const char* dbug_print_table_row(TABLE *table)
543{
544 Field **pfield;
545 String tmp(dbug_print_row_buff_tmp,
546 sizeof(dbug_print_row_buff_tmp),&my_charset_bin);
547
548 String output(dbug_print_row_buff, sizeof(dbug_print_row_buff),
549 &my_charset_bin);
550
551 output.length(0);
552 output.append(table->alias);
553 output.append("(");
554 bool first= true;
555
556 for (pfield= table->field; *pfield ; pfield++)
557 {
558 if (table->read_set && !bitmap_is_set(table->read_set, (*pfield)->field_index))
559 continue;
560
561 if (first)
562 first= false;
563 else
564 output.append(",");
565
566 output.append((*pfield)->field_name.str ?
567 (*pfield)->field_name.str: "NULL");
568 }
569
570 output.append(")=(");
571
572 first= true;
573 for (pfield= table->field; *pfield ; pfield++)
574 {
575 Field *field= *pfield;
576
577 if (table->read_set && !bitmap_is_set(table->read_set, (*pfield)->field_index))
578 continue;
579
580 if (first)
581 first= false;
582 else
583 output.append(",");
584
585 if (field->is_null())
586 output.append("NULL");
587 else
588 {
589 if (field->type() == MYSQL_TYPE_BIT)
590 (void) field->val_int_as_str(&tmp, 1);
591 else
592 field->val_str(&tmp);
593 output.append(tmp.ptr(), tmp.length());
594 }
595 }
596 output.append(")");
597
598 return output.c_ptr_safe();
599}
600
601
602/*
603 Print a text, SQL-like record representation into dbug trace.
604
605 Note: this function is a work in progress: at the moment
606 - column read bitmap is ignored (can print garbage for unused columns)
607 - there is no quoting
608*/
609static void dbug_print_record(TABLE *table, bool print_rowid)
610{
611 char buff[1024];
612 Field **pfield;
613 String tmp(buff,sizeof(buff),&my_charset_bin);
614 DBUG_LOCK_FILE;
615
616 fprintf(DBUG_FILE, "record (");
617 for (pfield= table->field; *pfield ; pfield++)
618 fprintf(DBUG_FILE, "%s%s", (*pfield)->field_name.str,
619 (pfield[1])? ", ":"");
620 fprintf(DBUG_FILE, ") = ");
621
622 fprintf(DBUG_FILE, "(");
623 for (pfield= table->field; *pfield ; pfield++)
624 {
625 Field *field= *pfield;
626
627 if (field->is_null())
628 fwrite("NULL", sizeof(char), 4, DBUG_FILE);
629
630 if (field->type() == MYSQL_TYPE_BIT)
631 (void) field->val_int_as_str(&tmp, 1);
632 else
633 field->val_str(&tmp);
634
635 fwrite(tmp.ptr(),sizeof(char),tmp.length(),DBUG_FILE);
636 if (pfield[1])
637 fwrite(", ", sizeof(char), 2, DBUG_FILE);
638 }
639 fprintf(DBUG_FILE, ")");
640 if (print_rowid)
641 {
642 fprintf(DBUG_FILE, " rowid ");
643 for (uint i=0; i < table->file->ref_length; i++)
644 {
645 fprintf(DBUG_FILE, "%x", (uchar)table->file->ref[i]);
646 }
647 }
648 fprintf(DBUG_FILE, "\n");
649 DBUG_UNLOCK_FILE;
650}
651
652#endif
653
654
655/**
656 Search after sort_keys, and write them into tempfile
657 (if we run out of space in the sort_keys buffer).
658 All produced sequences are guaranteed to be non-empty.
659
660 @param param Sorting parameter
661 @param select Use this to get source data
662 @param sort_keys Array of pointers to sort key + addon buffers.
663 @param buffpek_pointers File to write BUFFPEKs describing sorted segments
664 in tempfile.
665 @param tempfile File to write sorted sequences of sortkeys to.
666 @param pq If !NULL, use it for keeping top N elements
667 @param [out] found_rows The number of FOUND_ROWS().
668 For a query with LIMIT, this value will typically
669 be larger than the function return value.
670
671 @note
672 Basic idea:
673 @verbatim
674 while (get_next_sortkey())
675 {
676 if (using priority queue)
677 push sort key into queue
678 else
679 {
680 if (no free space in sort_keys buffers)
681 {
682 sort sort_keys buffer;
683 dump sorted sequence to 'tempfile';
684 dump BUFFPEK describing sequence location into 'buffpek_pointers';
685 }
686 put sort key into 'sort_keys';
687 }
688 }
689 if (sort_keys has some elements && dumped at least once)
690 sort-dump-dump as above;
691 else
692 don't sort, leave sort_keys array to be sorted by caller.
693 @endverbatim
694
695 @retval
696 Number of records written on success.
697 @retval
698 HA_POS_ERROR on error.
699*/
700
701static ha_rows find_all_keys(THD *thd, Sort_param *param, SQL_SELECT *select,
702 SORT_INFO *fs_info,
703 IO_CACHE *buffpek_pointers,
704 IO_CACHE *tempfile,
705 Bounded_queue<uchar, uchar> *pq,
706 ha_rows *found_rows)
707{
708 int error, quick_select;
709 uint idx, indexpos;
710 uchar *ref_pos, *next_pos, ref_buff[MAX_REFLENGTH];
711 TABLE *sort_form;
712 handler *file;
713 MY_BITMAP *save_read_set, *save_write_set, *save_vcol_set;
714 Item *sort_cond;
715 ha_rows retval;
716 DBUG_ENTER("find_all_keys");
717 DBUG_PRINT("info",("using: %s",
718 (select ? select->quick ? "ranges" : "where":
719 "every row")));
720
721 idx=indexpos=0;
722 error=quick_select=0;
723 sort_form=param->sort_form;
724 file=sort_form->file;
725 ref_pos= ref_buff;
726 quick_select=select && select->quick;
727 *found_rows= 0;
728 ref_pos= &file->ref[0];
729 next_pos=ref_pos;
730
731 DBUG_EXECUTE_IF("show_explain_in_find_all_keys",
732 dbug_serve_apcs(thd, 1);
733 );
734
735 if (!quick_select)
736 {
737 next_pos=(uchar*) 0; /* Find records in sequence */
738 DBUG_EXECUTE_IF("bug14365043_1",
739 DBUG_SET("+d,ha_rnd_init_fail"););
740 if (unlikely(file->ha_rnd_init_with_error(1)))
741 DBUG_RETURN(HA_POS_ERROR);
742 file->extra_opt(HA_EXTRA_CACHE, thd->variables.read_buff_size);
743 }
744
745 /* Remember original bitmaps */
746 save_read_set= sort_form->read_set;
747 save_write_set= sort_form->write_set;
748 save_vcol_set= sort_form->vcol_set;
749
750 /* Set up temporary column read map for columns used by sort */
751 DBUG_ASSERT(save_read_set != &sort_form->tmp_set);
752 bitmap_clear_all(&sort_form->tmp_set);
753 sort_form->column_bitmaps_set(&sort_form->tmp_set, &sort_form->tmp_set,
754 &sort_form->tmp_set);
755 register_used_fields(param);
756 if (quick_select)
757 select->quick->add_used_key_part_to_set();
758
759 sort_cond= (!select ? 0 :
760 (!select->pre_idx_push_select_cond ?
761 select->cond : select->pre_idx_push_select_cond));
762 if (sort_cond)
763 sort_cond->walk(&Item::register_field_in_read_map, 1, sort_form);
764 sort_form->file->column_bitmaps_signal();
765
766 if (quick_select)
767 {
768 if (select->quick->reset())
769 goto err;
770 }
771
772 DEBUG_SYNC(thd, "after_index_merge_phase1");
773 for (;;)
774 {
775 if (quick_select)
776 error= select->quick->get_next();
777 else /* Not quick-select */
778 error= file->ha_rnd_next(sort_form->record[0]);
779 if (unlikely(error))
780 break;
781 file->position(sort_form->record[0]);
782 DBUG_EXECUTE_IF("debug_filesort", dbug_print_record(sort_form, TRUE););
783
784 if (unlikely(thd->check_killed()))
785 {
786 DBUG_PRINT("info",("Sort killed by user"));
787 if (!quick_select)
788 {
789 (void) file->extra(HA_EXTRA_NO_CACHE);
790 file->ha_rnd_end();
791 }
792 goto err; /* purecov: inspected */
793 }
794
795 bool write_record= false;
796 if (likely(error == 0))
797 {
798 param->examined_rows++;
799 if (select && select->cond)
800 {
801 /*
802 If the condition 'select->cond' contains a subquery, restore the
803 original read/write sets of the table 'sort_form' because when
804 SQL_SELECT::skip_record evaluates this condition. it may include a
805 correlated subquery predicate, such that some field in the subquery
806 refers to 'sort_form'.
807
808 PSergey-todo: discuss the above with Timour.
809 */
810 MY_BITMAP *tmp_read_set= sort_form->read_set;
811 MY_BITMAP *tmp_write_set= sort_form->write_set;
812 MY_BITMAP *tmp_vcol_set= sort_form->vcol_set;
813
814 if (select->cond->with_subquery())
815 sort_form->column_bitmaps_set(save_read_set, save_write_set,
816 save_vcol_set);
817 write_record= (select->skip_record(thd) > 0);
818 if (select->cond->with_subquery())
819 sort_form->column_bitmaps_set(tmp_read_set,
820 tmp_write_set,
821 tmp_vcol_set);
822 }
823 else
824 write_record= true;
825 }
826
827 if (write_record)
828 {
829 ++(*found_rows);
830 if (pq)
831 {
832 pq->push(ref_pos);
833 idx= pq->num_elements();
834 }
835 else
836 {
837 if (idx == param->max_keys_per_buffer)
838 {
839 if (write_keys(param, fs_info, idx, buffpek_pointers, tempfile))
840 goto err;
841 idx= 0;
842 indexpos++;
843 }
844 make_sortkey(param, fs_info->get_record_buffer(idx++), ref_pos);
845 }
846 }
847
848 /* It does not make sense to read more keys in case of a fatal error */
849 if (unlikely(thd->is_error()))
850 break;
851
852 /*
853 We need to this after checking the error as the transaction may have
854 rolled back in case of a deadlock
855 */
856 if (!write_record)
857 file->unlock_row();
858 }
859 if (!quick_select)
860 {
861 (void) file->extra(HA_EXTRA_NO_CACHE); /* End cacheing of records */
862 if (!next_pos)
863 file->ha_rnd_end();
864 }
865
866 /* Signal we should use orignal column read and write maps */
867 sort_form->column_bitmaps_set(save_read_set, save_write_set, save_vcol_set);
868
869 if (unlikely(thd->is_error()))
870 DBUG_RETURN(HA_POS_ERROR);
871
872 DBUG_PRINT("test",("error: %d indexpos: %d",error,indexpos));
873 if (unlikely(error != HA_ERR_END_OF_FILE))
874 {
875 file->print_error(error,MYF(ME_ERROR | ME_WAITTANG)); // purecov: inspected
876 DBUG_RETURN(HA_POS_ERROR); /* purecov: inspected */
877 }
878 if (indexpos && idx &&
879 write_keys(param, fs_info, idx, buffpek_pointers, tempfile))
880 DBUG_RETURN(HA_POS_ERROR); /* purecov: inspected */
881 retval= (my_b_inited(tempfile) ?
882 (ha_rows) (my_b_tell(tempfile)/param->rec_length) :
883 idx);
884 DBUG_PRINT("info", ("find_all_keys return %llu", (ulonglong) retval));
885 DBUG_RETURN(retval);
886
887err:
888 sort_form->column_bitmaps_set(save_read_set, save_write_set, save_vcol_set);
889 DBUG_RETURN(HA_POS_ERROR);
890} /* find_all_keys */
891
892
893/**
894 @details
895 Sort the buffer and write:
896 -# the sorted sequence to tempfile
897 -# a BUFFPEK describing the sorted sequence position to buffpek_pointers
898
899 (was: Skriver en buffert med nycklar till filen)
900
901 @param param Sort parameters
902 @param sort_keys Array of pointers to keys to sort
903 @param count Number of elements in sort_keys array
904 @param buffpek_pointers One 'BUFFPEK' struct will be written into this file.
905 The BUFFPEK::{file_pos, count} will indicate where
906 the sorted data was stored.
907 @param tempfile The sorted sequence will be written into this file.
908
909 @retval
910 0 OK
911 @retval
912 1 Error
913*/
914
915static bool
916write_keys(Sort_param *param, SORT_INFO *fs_info, uint count,
917 IO_CACHE *buffpek_pointers, IO_CACHE *tempfile)
918{
919 size_t rec_length;
920 uchar **end;
921 BUFFPEK buffpek;
922 DBUG_ENTER("write_keys");
923
924 rec_length= param->rec_length;
925 uchar **sort_keys= fs_info->get_sort_keys();
926
927 fs_info->sort_buffer(param, count);
928
929 if (!my_b_inited(tempfile) &&
930 open_cached_file(tempfile, mysql_tmpdir, TEMP_PREFIX, DISK_BUFFER_SIZE,
931 MYF(MY_WME)))
932 goto err; /* purecov: inspected */
933 /* check we won't have more buffpeks than we can possibly keep in memory */
934 if (my_b_tell(buffpek_pointers) + sizeof(BUFFPEK) > (ulonglong)UINT_MAX)
935 goto err;
936 bzero(&buffpek, sizeof(buffpek));
937 buffpek.file_pos= my_b_tell(tempfile);
938 if ((ha_rows) count > param->max_rows)
939 count=(uint) param->max_rows; /* purecov: inspected */
940 buffpek.count=(ha_rows) count;
941 for (end=sort_keys+count ; sort_keys != end ; sort_keys++)
942 if (my_b_write(tempfile, (uchar*) *sort_keys, (uint) rec_length))
943 goto err;
944 if (my_b_write(buffpek_pointers, (uchar*) &buffpek, sizeof(buffpek)))
945 goto err;
946 DBUG_RETURN(0);
947
948err:
949 DBUG_RETURN(1);
950} /* write_keys */
951
952
953/**
954 Store length as suffix in high-byte-first order.
955*/
956
957static inline void store_length(uchar *to, uint length, uint pack_length)
958{
959 switch (pack_length) {
960 case 1:
961 *to= (uchar) length;
962 break;
963 case 2:
964 mi_int2store(to, length);
965 break;
966 case 3:
967 mi_int3store(to, length);
968 break;
969 default:
970 mi_int4store(to, length);
971 break;
972 }
973}
974
975
976void
977Type_handler_string_result::make_sort_key(uchar *to, Item *item,
978 const SORT_FIELD_ATTR *sort_field,
979 Sort_param *param) const
980{
981 CHARSET_INFO *cs= item->collation.collation;
982 bool maybe_null= item->maybe_null;
983
984 if (maybe_null)
985 *to++= 1;
986 char *tmp_buffer= param->tmp_buffer ? param->tmp_buffer : (char*) to;
987 String tmp(tmp_buffer, param->tmp_buffer ? param->sort_length :
988 sort_field->length, cs);
989 String *res= item->str_result(&tmp);
990 if (!res)
991 {
992 if (maybe_null)
993 memset(to - 1, 0, sort_field->length + 1);
994 else
995 {
996 /* purecov: begin deadcode */
997 /*
998 This should only happen during extreme conditions if we run out
999 of memory or have an item marked not null when it can be null.
1000 This code is here mainly to avoid a hard crash in this case.
1001 */
1002 DBUG_ASSERT(0);
1003 DBUG_PRINT("warning",
1004 ("Got null on something that shouldn't be null"));
1005 memset(to, 0, sort_field->length); // Avoid crash
1006 /* purecov: end */
1007 }
1008 return;
1009 }
1010
1011 if (use_strnxfrm(cs))
1012 {
1013 IF_DBUG(size_t tmp_length= ,)
1014 cs->coll->strnxfrm(cs, to, sort_field->length,
1015 item->max_char_length() *
1016 cs->strxfrm_multiply,
1017 (uchar*) res->ptr(), res->length(),
1018 MY_STRXFRM_PAD_WITH_SPACE |
1019 MY_STRXFRM_PAD_TO_MAXLEN);
1020 DBUG_ASSERT(tmp_length == sort_field->length);
1021 }
1022 else
1023 {
1024 uint diff;
1025 uint sort_field_length= sort_field->length - sort_field->suffix_length;
1026 uint length= res->length();
1027 if (sort_field_length < length)
1028 {
1029 diff= 0;
1030 length= sort_field_length;
1031 }
1032 else
1033 diff= sort_field_length - length;
1034 if (sort_field->suffix_length)
1035 {
1036 /* Store length last in result_string */
1037 store_length(to + sort_field_length, length, sort_field->suffix_length);
1038 }
1039 /* apply cs->sort_order for case-insensitive comparison if needed */
1040 my_strnxfrm(cs,(uchar*)to,length,(const uchar*)res->ptr(),length);
1041 char fill_char= ((cs->state & MY_CS_BINSORT) ? (char) 0 : ' ');
1042 cs->cset->fill(cs, (char *)to+length,diff,fill_char);
1043 }
1044}
1045
1046
1047void
1048Type_handler_int_result::make_sort_key(uchar *to, Item *item,
1049 const SORT_FIELD_ATTR *sort_field,
1050 Sort_param *param) const
1051{
1052 longlong value= item->val_int_result();
1053 make_sort_key_longlong(to, item->maybe_null, item->null_value,
1054 item->unsigned_flag, value);
1055}
1056
1057
1058void
1059Type_handler_temporal_result::make_sort_key(uchar *to, Item *item,
1060 const SORT_FIELD_ATTR *sort_field,
1061 Sort_param *param) const
1062{
1063 MYSQL_TIME buf;
1064 if (item->get_date_result(&buf, TIME_INVALID_DATES))
1065 {
1066 DBUG_ASSERT(item->maybe_null);
1067 DBUG_ASSERT(item->null_value);
1068 make_sort_key_longlong(to, item->maybe_null, true,
1069 item->unsigned_flag, 0);
1070 }
1071 else
1072 make_sort_key_longlong(to, item->maybe_null, false,
1073 item->unsigned_flag, pack_time(&buf));
1074}
1075
1076
1077void
1078Type_handler::make_sort_key_longlong(uchar *to,
1079 bool maybe_null,
1080 bool null_value,
1081 bool unsigned_flag,
1082 longlong value) const
1083
1084{
1085 if (maybe_null)
1086 {
1087 if (null_value)
1088 {
1089 memset(to, 0, 9);
1090 return;
1091 }
1092 *to++= 1;
1093 }
1094 to[7]= (uchar) value;
1095 to[6]= (uchar) (value >> 8);
1096 to[5]= (uchar) (value >> 16);
1097 to[4]= (uchar) (value >> 24);
1098 to[3]= (uchar) (value >> 32);
1099 to[2]= (uchar) (value >> 40);
1100 to[1]= (uchar) (value >> 48);
1101 if (unsigned_flag) /* Fix sign */
1102 to[0]= (uchar) (value >> 56);
1103 else
1104 to[0]= (uchar) (value >> 56) ^ 128; /* Reverse signbit */
1105}
1106
1107
1108void
1109Type_handler_decimal_result::make_sort_key(uchar *to, Item *item,
1110 const SORT_FIELD_ATTR *sort_field,
1111 Sort_param *param) const
1112{
1113 my_decimal dec_buf, *dec_val= item->val_decimal_result(&dec_buf);
1114 if (item->maybe_null)
1115 {
1116 if (item->null_value)
1117 {
1118 memset(to, 0, sort_field->length + 1);
1119 return;
1120 }
1121 *to++= 1;
1122 }
1123 my_decimal2binary(E_DEC_FATAL_ERROR, dec_val, to,
1124 item->max_length - (item->decimals ? 1 : 0),
1125 item->decimals);
1126}
1127
1128
1129void
1130Type_handler_real_result::make_sort_key(uchar *to, Item *item,
1131 const SORT_FIELD_ATTR *sort_field,
1132 Sort_param *param) const
1133{
1134 double value= item->val_result();
1135 if (item->maybe_null)
1136 {
1137 if (item->null_value)
1138 {
1139 memset(to, 0, sort_field->length + 1);
1140 return;
1141 }
1142 *to++= 1;
1143 }
1144 change_double_for_sort(value, to);
1145}
1146
1147
1148/** Make a sort-key from record. */
1149
1150static void make_sortkey(Sort_param *param, uchar *to, uchar *ref_pos)
1151{
1152 Field *field;
1153 SORT_FIELD *sort_field;
1154 uint length;
1155
1156 for (sort_field=param->local_sortorder ;
1157 sort_field != param->end ;
1158 sort_field++)
1159 {
1160 bool maybe_null=0;
1161 if ((field=sort_field->field))
1162 { // Field
1163 field->make_sort_key(to, sort_field->length);
1164 if ((maybe_null = field->maybe_null()))
1165 to++;
1166 }
1167 else
1168 { // Item
1169 sort_field->item->type_handler()->make_sort_key(to, sort_field->item,
1170 sort_field, param);
1171 if ((maybe_null= sort_field->item->maybe_null))
1172 to++;
1173 }
1174 if (sort_field->reverse)
1175 { /* Revers key */
1176 if (maybe_null && (to[-1]= !to[-1]))
1177 {
1178 to+= sort_field->length; // don't waste the time reversing all 0's
1179 continue;
1180 }
1181 length=sort_field->length;
1182 while (length--)
1183 {
1184 *to = (uchar) (~ *to);
1185 to++;
1186 }
1187 }
1188 else
1189 to+= sort_field->length;
1190 }
1191
1192 if (param->addon_field)
1193 {
1194 /*
1195 Save field values appended to sorted fields.
1196 First null bit indicators are appended then field values follow.
1197 In this implementation we use fixed layout for field values -
1198 the same for all records.
1199 */
1200 SORT_ADDON_FIELD *addonf= param->addon_field;
1201 uchar *nulls= to;
1202 DBUG_ASSERT(addonf != 0);
1203 memset(nulls, 0, addonf->offset);
1204 to+= addonf->offset;
1205 for ( ; (field= addonf->field) ; addonf++)
1206 {
1207 if (addonf->null_bit && field->is_null())
1208 {
1209 nulls[addonf->null_offset]|= addonf->null_bit;
1210#ifdef HAVE_valgrind
1211 bzero(to, addonf->length);
1212#endif
1213 }
1214 else
1215 {
1216#ifdef HAVE_valgrind
1217 uchar *end= field->pack(to, field->ptr);
1218 uint length= (uint) ((to + addonf->length) - end);
1219 DBUG_ASSERT((int) length >= 0);
1220 if (length)
1221 bzero(end, length);
1222#else
1223 (void) field->pack(to, field->ptr);
1224#endif
1225 }
1226 to+= addonf->length;
1227 }
1228 }
1229 else
1230 {
1231 /* Save filepos last */
1232 memcpy((uchar*) to, ref_pos, (size_t) param->ref_length);
1233 }
1234 return;
1235}
1236
1237
1238/*
1239 Register fields used by sorting in the sorted table's read set
1240*/
1241
1242static void register_used_fields(Sort_param *param)
1243{
1244 SORT_FIELD *sort_field;
1245 TABLE *table=param->sort_form;
1246
1247 for (sort_field= param->local_sortorder ;
1248 sort_field != param->end ;
1249 sort_field++)
1250 {
1251 Field *field;
1252 if ((field= sort_field->field))
1253 {
1254 if (field->table == table)
1255 field->register_field_in_read_map();
1256 }
1257 else
1258 { // Item
1259 sort_field->item->walk(&Item::register_field_in_read_map, 1, table);
1260 }
1261 }
1262
1263 if (param->addon_field)
1264 {
1265 SORT_ADDON_FIELD *addonf= param->addon_field;
1266 Field *field;
1267 for ( ; (field= addonf->field) ; addonf++)
1268 field->register_field_in_read_map();
1269 }
1270 else
1271 {
1272 /* Save filepos last */
1273 table->prepare_for_position();
1274 }
1275}
1276
1277
1278static bool save_index(Sort_param *param, uint count,
1279 SORT_INFO *table_sort)
1280{
1281 uint offset,res_length;
1282 uchar *to;
1283 DBUG_ENTER("save_index");
1284 DBUG_ASSERT(table_sort->record_pointers == 0);
1285
1286 table_sort->sort_buffer(param, count);
1287 res_length= param->res_length;
1288 offset= param->rec_length-res_length;
1289 if (!(to= table_sort->record_pointers=
1290 (uchar*) my_malloc(res_length*count,
1291 MYF(MY_WME | MY_THREAD_SPECIFIC))))
1292 DBUG_RETURN(1); /* purecov: inspected */
1293 uchar **sort_keys= table_sort->get_sort_keys();
1294 for (uchar **end= sort_keys+count ; sort_keys != end ; sort_keys++)
1295 {
1296 memcpy(to, *sort_keys+offset, res_length);
1297 to+= res_length;
1298 }
1299 DBUG_RETURN(0);
1300}
1301
1302
1303/**
1304 Test whether priority queue is worth using to get top elements of an
1305 ordered result set. If it is, then allocates buffer for required amount of
1306 records
1307
1308 @param param Sort parameters.
1309 @param filesort_info Filesort information.
1310 @param table Table to sort.
1311 @param num_rows Estimate of number of rows in source record set.
1312 @param memory_available Memory available for sorting.
1313
1314 DESCRIPTION
1315 Given a query like this:
1316 SELECT ... FROM t ORDER BY a1,...,an LIMIT max_rows;
1317 This function tests whether a priority queue should be used to keep
1318 the result. Necessary conditions are:
1319 - estimate that it is actually cheaper than merge-sort
1320 - enough memory to store the <max_rows> records.
1321
1322 If we don't have space for <max_rows> records, but we *do* have
1323 space for <max_rows> keys, we may rewrite 'table' to sort with
1324 references to records instead of additional data.
1325 (again, based on estimates that it will actually be cheaper).
1326
1327 @retval
1328 true - if it's ok to use PQ
1329 false - PQ will be slower than merge-sort, or there is not enough memory.
1330*/
1331
1332static bool check_if_pq_applicable(Sort_param *param,
1333 SORT_INFO *filesort_info,
1334 TABLE *table, ha_rows num_rows,
1335 size_t memory_available)
1336{
1337 DBUG_ENTER("check_if_pq_applicable");
1338
1339 /*
1340 How much Priority Queue sort is slower than qsort.
1341 Measurements (see unit test) indicate that PQ is roughly 3 times slower.
1342 */
1343 const double PQ_slowness= 3.0;
1344
1345 if (param->max_rows == HA_POS_ERROR)
1346 {
1347 DBUG_PRINT("info", ("No LIMIT"));
1348 DBUG_RETURN(false);
1349 }
1350
1351 if (param->max_rows + 2 >= UINT_MAX)
1352 {
1353 DBUG_PRINT("info", ("Too large LIMIT"));
1354 DBUG_RETURN(false);
1355 }
1356
1357 size_t num_available_keys=
1358 memory_available / (param->rec_length + sizeof(char*));
1359 // We need 1 extra record in the buffer, when using PQ.
1360 param->max_keys_per_buffer= (uint) param->max_rows + 1;
1361
1362 if (num_rows < num_available_keys)
1363 {
1364 // The whole source set fits into memory.
1365 if (param->max_rows < num_rows/PQ_slowness )
1366 {
1367 DBUG_RETURN(filesort_info->alloc_sort_buffer(param->max_keys_per_buffer,
1368 param->rec_length) != NULL);
1369 }
1370 else
1371 {
1372 // PQ will be slower.
1373 DBUG_RETURN(false);
1374 }
1375 }
1376
1377 // Do we have space for LIMIT rows in memory?
1378 if (param->max_keys_per_buffer < num_available_keys)
1379 {
1380 DBUG_RETURN(filesort_info->alloc_sort_buffer(param->max_keys_per_buffer,
1381 param->rec_length) != NULL);
1382 }
1383
1384 // Try to strip off addon fields.
1385 if (param->addon_field)
1386 {
1387 const size_t row_length=
1388 param->sort_length + param->ref_length + sizeof(char*);
1389 num_available_keys= memory_available / row_length;
1390
1391 // Can we fit all the keys in memory?
1392 if (param->max_keys_per_buffer < num_available_keys)
1393 {
1394 const double sort_merge_cost=
1395 get_merge_many_buffs_cost_fast(num_rows,
1396 num_available_keys,
1397 (uint)row_length);
1398 /*
1399 PQ has cost:
1400 (insert + qsort) * log(queue size) / TIME_FOR_COMPARE_ROWID +
1401 cost of file lookup afterwards.
1402 The lookup cost is a bit pessimistic: we take scan_time and assume
1403 that on average we find the row after scanning half of the file.
1404 A better estimate would be lookup cost, but note that we are doing
1405 random lookups here, rather than sequential scan.
1406 */
1407 const double pq_cpu_cost=
1408 (PQ_slowness * num_rows + param->max_keys_per_buffer) *
1409 log((double) param->max_keys_per_buffer) / TIME_FOR_COMPARE_ROWID;
1410 const double pq_io_cost=
1411 param->max_rows * table->file->scan_time() / 2.0;
1412 const double pq_cost= pq_cpu_cost + pq_io_cost;
1413
1414 if (sort_merge_cost < pq_cost)
1415 DBUG_RETURN(false);
1416
1417 if (filesort_info->alloc_sort_buffer(param->max_keys_per_buffer,
1418 param->sort_length +
1419 param->ref_length))
1420 {
1421 /* Make attached data to be references instead of fields. */
1422 my_free(filesort_info->addon_field);
1423 filesort_info->addon_field= NULL;
1424 param->addon_field= NULL;
1425
1426 param->res_length= param->ref_length;
1427 param->sort_length+= param->ref_length;
1428 param->rec_length= param->sort_length;
1429
1430 DBUG_RETURN(true);
1431 }
1432 }
1433 }
1434 DBUG_RETURN(false);
1435}
1436
1437
1438/** Merge buffers to make < MERGEBUFF2 buffers. */
1439
1440int merge_many_buff(Sort_param *param, uchar *sort_buffer,
1441 BUFFPEK *buffpek, uint *maxbuffer, IO_CACHE *t_file)
1442{
1443 uint i;
1444 IO_CACHE t_file2,*from_file,*to_file,*temp;
1445 BUFFPEK *lastbuff;
1446 DBUG_ENTER("merge_many_buff");
1447
1448 if (*maxbuffer < MERGEBUFF2)
1449 DBUG_RETURN(0); /* purecov: inspected */
1450 if (flush_io_cache(t_file) ||
1451 open_cached_file(&t_file2,mysql_tmpdir,TEMP_PREFIX,DISK_BUFFER_SIZE,
1452 MYF(MY_WME)))
1453 DBUG_RETURN(1); /* purecov: inspected */
1454
1455 from_file= t_file ; to_file= &t_file2;
1456 while (*maxbuffer >= MERGEBUFF2)
1457 {
1458 if (reinit_io_cache(from_file,READ_CACHE,0L,0,0))
1459 goto cleanup;
1460 if (reinit_io_cache(to_file,WRITE_CACHE,0L,0,0))
1461 goto cleanup;
1462 lastbuff=buffpek;
1463 for (i=0 ; i <= *maxbuffer-MERGEBUFF*3/2 ; i+=MERGEBUFF)
1464 {
1465 if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
1466 buffpek+i,buffpek+i+MERGEBUFF-1,0))
1467 goto cleanup;
1468 }
1469 if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
1470 buffpek+i,buffpek+ *maxbuffer,0))
1471 break; /* purecov: inspected */
1472 if (flush_io_cache(to_file))
1473 break; /* purecov: inspected */
1474 temp=from_file; from_file=to_file; to_file=temp;
1475 *maxbuffer= (uint) (lastbuff-buffpek)-1;
1476 }
1477cleanup:
1478 close_cached_file(to_file); // This holds old result
1479 if (to_file == t_file)
1480 {
1481 *t_file=t_file2; // Copy result file
1482 }
1483
1484 DBUG_RETURN(*maxbuffer >= MERGEBUFF2); /* Return 1 if interrupted */
1485} /* merge_many_buff */
1486
1487
1488/**
1489 Read data to buffer.
1490
1491 @retval Number of bytes read
1492 (ulong)-1 if something goes wrong
1493*/
1494
1495ulong read_to_buffer(IO_CACHE *fromfile, BUFFPEK *buffpek,
1496 uint rec_length)
1497{
1498 ulong count;
1499 ulong length= 0;
1500
1501 if ((count= (ulong) MY_MIN((ha_rows) buffpek->max_keys,buffpek->count)))
1502 {
1503 length= rec_length*count;
1504 if (unlikely(my_b_pread(fromfile, (uchar*) buffpek->base, length,
1505 buffpek->file_pos)))
1506 return ((ulong) -1);
1507 buffpek->key=buffpek->base;
1508 buffpek->file_pos+= length; /* New filepos */
1509 buffpek->count-= count;
1510 buffpek->mem_count= count;
1511 }
1512 return (length);
1513} /* read_to_buffer */
1514
1515
1516/**
1517 Put all room used by freed buffer to use in adjacent buffer.
1518
1519 Note, that we can't simply distribute memory evenly between all buffers,
1520 because new areas must not overlap with old ones.
1521
1522 @param[in] queue list of non-empty buffers, without freed buffer
1523 @param[in] reuse empty buffer
1524 @param[in] key_length key length
1525*/
1526
1527void reuse_freed_buff(QUEUE *queue, BUFFPEK *reuse, uint key_length)
1528{
1529 uchar *reuse_end= reuse->base + reuse->max_keys * key_length;
1530 for (uint i= queue_first_element(queue);
1531 i <= queue_last_element(queue);
1532 i++)
1533 {
1534 BUFFPEK *bp= (BUFFPEK *) queue_element(queue, i);
1535 if (bp->base + bp->max_keys * key_length == reuse->base)
1536 {
1537 bp->max_keys+= reuse->max_keys;
1538 return;
1539 }
1540 else if (bp->base == reuse_end)
1541 {
1542 bp->base= reuse->base;
1543 bp->max_keys+= reuse->max_keys;
1544 return;
1545 }
1546 }
1547 DBUG_ASSERT(0);
1548}
1549
1550
1551/**
1552 Merge buffers to one buffer.
1553
1554 @param param Sort parameter
1555 @param from_file File with source data (BUFFPEKs point to this file)
1556 @param to_file File to write the sorted result data.
1557 @param sort_buffer Buffer for data to store up to MERGEBUFF2 sort keys.
1558 @param lastbuff OUT Store here BUFFPEK describing data written to to_file
1559 @param Fb First element in source BUFFPEKs array
1560 @param Tb Last element in source BUFFPEKs array
1561 @param flag
1562
1563 @retval
1564 0 OK
1565 @retval
1566 1 ERROR
1567*/
1568
1569bool merge_buffers(Sort_param *param, IO_CACHE *from_file,
1570 IO_CACHE *to_file, uchar *sort_buffer,
1571 BUFFPEK *lastbuff, BUFFPEK *Fb, BUFFPEK *Tb,
1572 int flag)
1573{
1574 bool error= 0;
1575 uint rec_length,res_length,offset;
1576 size_t sort_length;
1577 ulong maxcount, bytes_read;
1578 ha_rows max_rows,org_max_rows;
1579 my_off_t to_start_filepos;
1580 uchar *strpos;
1581 BUFFPEK *buffpek;
1582 QUEUE queue;
1583 qsort2_cmp cmp;
1584 void *first_cmp_arg;
1585 element_count dupl_count= 0;
1586 uchar *src;
1587 uchar *unique_buff= param->unique_buff;
1588 const bool killable= !param->not_killable;
1589 THD* const thd=current_thd;
1590 DBUG_ENTER("merge_buffers");
1591
1592 thd->inc_status_sort_merge_passes();
1593 thd->query_plan_fsort_passes++;
1594
1595 rec_length= param->rec_length;
1596 res_length= param->res_length;
1597 sort_length= param->sort_length;
1598 uint dupl_count_ofs= rec_length-sizeof(element_count);
1599 uint min_dupl_count= param->min_dupl_count;
1600 bool check_dupl_count= flag && min_dupl_count;
1601 offset= (rec_length-
1602 (flag && min_dupl_count ? sizeof(dupl_count) : 0)-res_length);
1603 uint wr_len= flag ? res_length : rec_length;
1604 uint wr_offset= flag ? offset : 0;
1605 maxcount= (ulong) (param->max_keys_per_buffer/((uint) (Tb-Fb) +1));
1606 to_start_filepos= my_b_tell(to_file);
1607 strpos= sort_buffer;
1608 org_max_rows=max_rows= param->max_rows;
1609
1610 set_if_bigger(maxcount, 1);
1611
1612 if (unique_buff)
1613 {
1614 cmp= param->compare;
1615 first_cmp_arg= (void *) &param->cmp_context;
1616 }
1617 else
1618 {
1619 cmp= get_ptr_compare(sort_length);
1620 first_cmp_arg= (void*) &sort_length;
1621 }
1622 if (unlikely(init_queue(&queue, (uint) (Tb-Fb)+1, offsetof(BUFFPEK,key), 0,
1623 (queue_compare) cmp, first_cmp_arg, 0, 0)))
1624 DBUG_RETURN(1); /* purecov: inspected */
1625 for (buffpek= Fb ; buffpek <= Tb ; buffpek++)
1626 {
1627 buffpek->base= strpos;
1628 buffpek->max_keys= maxcount;
1629 bytes_read= read_to_buffer(from_file, buffpek, rec_length);
1630 if (unlikely(bytes_read == (ulong) -1))
1631 goto err; /* purecov: inspected */
1632
1633 strpos+= bytes_read;
1634 buffpek->max_keys= buffpek->mem_count; // If less data in buffers than expected
1635 queue_insert(&queue, (uchar*) buffpek);
1636 }
1637
1638 if (unique_buff)
1639 {
1640 /*
1641 Called by Unique::get()
1642 Copy the first argument to unique_buff for unique removal.
1643 Store it also in 'to_file'.
1644 */
1645 buffpek= (BUFFPEK*) queue_top(&queue);
1646 memcpy(unique_buff, buffpek->key, rec_length);
1647 if (min_dupl_count)
1648 memcpy(&dupl_count, unique_buff+dupl_count_ofs,
1649 sizeof(dupl_count));
1650 buffpek->key+= rec_length;
1651 if (! --buffpek->mem_count)
1652 {
1653 if (unlikely(!(bytes_read= read_to_buffer(from_file, buffpek,
1654 rec_length))))
1655 {
1656 (void) queue_remove_top(&queue);
1657 reuse_freed_buff(&queue, buffpek, rec_length);
1658 }
1659 else if (unlikely(bytes_read == (ulong) -1))
1660 goto err; /* purecov: inspected */
1661 }
1662 queue_replace_top(&queue); // Top element has been used
1663 }
1664 else
1665 cmp= 0; // Not unique
1666
1667 while (queue.elements > 1)
1668 {
1669 if (killable && unlikely(thd->check_killed()))
1670 goto err; /* purecov: inspected */
1671
1672 for (;;)
1673 {
1674 buffpek= (BUFFPEK*) queue_top(&queue);
1675 src= buffpek->key;
1676 if (cmp) // Remove duplicates
1677 {
1678 if (!(*cmp)(first_cmp_arg, &unique_buff,
1679 (uchar**) &buffpek->key))
1680 {
1681 if (min_dupl_count)
1682 {
1683 element_count cnt;
1684 memcpy(&cnt, (uchar *) buffpek->key+dupl_count_ofs, sizeof(cnt));
1685 dupl_count+= cnt;
1686 }
1687 goto skip_duplicate;
1688 }
1689 if (min_dupl_count)
1690 {
1691 memcpy(unique_buff+dupl_count_ofs, &dupl_count,
1692 sizeof(dupl_count));
1693 }
1694 src= unique_buff;
1695 }
1696
1697 /*
1698 Do not write into the output file if this is the final merge called
1699 for a Unique object used for intersection and dupl_count is less
1700 than min_dupl_count.
1701 If the Unique object is used to intersect N sets of unique elements
1702 then for any element:
1703 dupl_count >= N <=> the element is occurred in each of these N sets.
1704 */
1705 if (!check_dupl_count || dupl_count >= min_dupl_count)
1706 {
1707 if (my_b_write(to_file, src+wr_offset, wr_len))
1708 goto err; /* purecov: inspected */
1709 }
1710 if (cmp)
1711 {
1712 memcpy(unique_buff, (uchar*) buffpek->key, rec_length);
1713 if (min_dupl_count)
1714 memcpy(&dupl_count, unique_buff+dupl_count_ofs,
1715 sizeof(dupl_count));
1716 }
1717 if (!--max_rows)
1718 {
1719 /* Nothing more to do */
1720 goto end; /* purecov: inspected */
1721 }
1722
1723 skip_duplicate:
1724 buffpek->key+= rec_length;
1725 if (! --buffpek->mem_count)
1726 {
1727 if (unlikely(!(bytes_read= read_to_buffer(from_file, buffpek,
1728 rec_length))))
1729 {
1730 (void) queue_remove_top(&queue);
1731 reuse_freed_buff(&queue, buffpek, rec_length);
1732 break; /* One buffer have been removed */
1733 }
1734 else if (unlikely(bytes_read == (ulong) -1))
1735 goto err; /* purecov: inspected */
1736 }
1737 queue_replace_top(&queue); /* Top element has been replaced */
1738 }
1739 }
1740 buffpek= (BUFFPEK*) queue_top(&queue);
1741 buffpek->base= (uchar*) sort_buffer;
1742 buffpek->max_keys= param->max_keys_per_buffer;
1743
1744 /*
1745 As we know all entries in the buffer are unique, we only have to
1746 check if the first one is the same as the last one we wrote
1747 */
1748 if (cmp)
1749 {
1750 if (!(*cmp)(first_cmp_arg, &unique_buff, (uchar**) &buffpek->key))
1751 {
1752 if (min_dupl_count)
1753 {
1754 element_count cnt;
1755 memcpy(&cnt, (uchar *) buffpek->key+dupl_count_ofs, sizeof(cnt));
1756 dupl_count+= cnt;
1757 }
1758 buffpek->key+= rec_length;
1759 --buffpek->mem_count;
1760 }
1761
1762 if (min_dupl_count)
1763 memcpy(unique_buff+dupl_count_ofs, &dupl_count,
1764 sizeof(dupl_count));
1765
1766 if (!check_dupl_count || dupl_count >= min_dupl_count)
1767 {
1768 src= unique_buff;
1769 if (my_b_write(to_file, src+wr_offset, wr_len))
1770 goto err; /* purecov: inspected */
1771 if (!--max_rows)
1772 goto end;
1773 }
1774 }
1775
1776 do
1777 {
1778 if ((ha_rows) buffpek->mem_count > max_rows)
1779 { /* Don't write too many records */
1780 buffpek->mem_count= (uint) max_rows;
1781 buffpek->count= 0; /* Don't read more */
1782 }
1783 max_rows-= buffpek->mem_count;
1784 if (flag == 0)
1785 {
1786 if (my_b_write(to_file, (uchar*) buffpek->key,
1787 (size_t)(rec_length*buffpek->mem_count)))
1788 goto err; /* purecov: inspected */
1789 }
1790 else
1791 {
1792 uchar *end;
1793 src= buffpek->key+offset;
1794 for (end= src+buffpek->mem_count*rec_length ;
1795 src != end ;
1796 src+= rec_length)
1797 {
1798 if (check_dupl_count)
1799 {
1800 memcpy((uchar *) &dupl_count, src+dupl_count_ofs, sizeof(dupl_count));
1801 if (dupl_count < min_dupl_count)
1802 continue;
1803 }
1804 if (my_b_write(to_file, src, wr_len))
1805 goto err;
1806 }
1807 }
1808 }
1809 while (likely(!(error=
1810 (bytes_read= read_to_buffer(from_file, buffpek,
1811 rec_length)) == (ulong) -1)) &&
1812 bytes_read != 0);
1813
1814end:
1815 lastbuff->count= MY_MIN(org_max_rows-max_rows, param->max_rows);
1816 lastbuff->file_pos= to_start_filepos;
1817cleanup:
1818 delete_queue(&queue);
1819 DBUG_RETURN(error);
1820
1821err:
1822 error= 1;
1823 goto cleanup;
1824
1825} /* merge_buffers */
1826
1827
1828 /* Do a merge to output-file (save only positions) */
1829
1830int merge_index(Sort_param *param, uchar *sort_buffer,
1831 BUFFPEK *buffpek, uint maxbuffer,
1832 IO_CACHE *tempfile, IO_CACHE *outfile)
1833{
1834 DBUG_ENTER("merge_index");
1835 if (merge_buffers(param,tempfile,outfile,sort_buffer,buffpek,buffpek,
1836 buffpek+maxbuffer,1))
1837 DBUG_RETURN(1); /* purecov: inspected */
1838 DBUG_RETURN(0);
1839} /* merge_index */
1840
1841
1842static uint suffix_length(ulong string_length)
1843{
1844 if (string_length < 256)
1845 return 1;
1846 if (string_length < 256L*256L)
1847 return 2;
1848 if (string_length < 256L*256L*256L)
1849 return 3;
1850 return 4; // Can't sort longer than 4G
1851}
1852
1853
1854void
1855Type_handler_string_result::sortlength(THD *thd,
1856 const Type_std_attributes *item,
1857 SORT_FIELD_ATTR *sortorder) const
1858{
1859 CHARSET_INFO *cs;
1860 sortorder->length= item->max_length;
1861 set_if_smaller(sortorder->length, thd->variables.max_sort_length);
1862 if (use_strnxfrm((cs= item->collation.collation)))
1863 {
1864 sortorder->length= (uint)cs->coll->strnxfrmlen(cs, sortorder->length);
1865 }
1866 else if (cs == &my_charset_bin)
1867 {
1868 /* Store length last to be able to sort blob/varbinary */
1869 sortorder->suffix_length= suffix_length(sortorder->length);
1870 sortorder->length+= sortorder->suffix_length;
1871 }
1872}
1873
1874
1875void
1876Type_handler_temporal_result::sortlength(THD *thd,
1877 const Type_std_attributes *item,
1878 SORT_FIELD_ATTR *sortorder) const
1879{
1880 sortorder->length= 8; // Sizof intern longlong
1881}
1882
1883
1884void
1885Type_handler_int_result::sortlength(THD *thd,
1886 const Type_std_attributes *item,
1887 SORT_FIELD_ATTR *sortorder) const
1888{
1889 sortorder->length= 8; // Sizof intern longlong
1890}
1891
1892
1893void
1894Type_handler_real_result::sortlength(THD *thd,
1895 const Type_std_attributes *item,
1896 SORT_FIELD_ATTR *sortorder) const
1897{
1898 sortorder->length= sizeof(double);
1899}
1900
1901
1902void
1903Type_handler_decimal_result::sortlength(THD *thd,
1904 const Type_std_attributes *item,
1905 SORT_FIELD_ATTR *sortorder) const
1906{
1907 sortorder->length=
1908 my_decimal_get_binary_size(item->max_length - (item->decimals ? 1 : 0),
1909 item->decimals);
1910}
1911
1912
1913/**
1914 Calculate length of sort key.
1915
1916 @param thd Thread handler
1917 @param sortorder Order of items to sort
1918 @param s_length Number of items to sort
1919 @param[out] multi_byte_charset Set to 1 if we are using multi-byte charset
1920 (In which case we have to use strxnfrm())
1921
1922 @note
1923 sortorder->length is updated for each sort item.
1924
1925 @return
1926 Total length of sort buffer in bytes
1927*/
1928
1929static uint
1930sortlength(THD *thd, SORT_FIELD *sortorder, uint s_length,
1931 bool *multi_byte_charset)
1932{
1933 uint length;
1934 *multi_byte_charset= 0;
1935
1936 length=0;
1937 for (; s_length-- ; sortorder++)
1938 {
1939 sortorder->suffix_length= 0;
1940 if (sortorder->field)
1941 {
1942 CHARSET_INFO *cs= sortorder->field->sort_charset();
1943 sortorder->length= sortorder->field->sort_length();
1944 if (use_strnxfrm((cs=sortorder->field->sort_charset())))
1945 {
1946 *multi_byte_charset= true;
1947 sortorder->length= (uint)cs->coll->strnxfrmlen(cs, sortorder->length);
1948 }
1949 if (sortorder->field->maybe_null())
1950 length++; // Place for NULL marker
1951 }
1952 else
1953 {
1954 sortorder->item->type_handler()->sortlength(thd, sortorder->item,
1955 sortorder);
1956 if (use_strnxfrm(sortorder->item->collation.collation))
1957 {
1958 *multi_byte_charset= true;
1959 }
1960 if (sortorder->item->maybe_null)
1961 length++; // Place for NULL marker
1962 }
1963 set_if_smaller(sortorder->length, thd->variables.max_sort_length);
1964 length+=sortorder->length;
1965 }
1966 sortorder->field= (Field*) 0; // end marker
1967 DBUG_PRINT("info",("sort_length: %d",length));
1968 return length;
1969}
1970
1971
1972/**
1973 Get descriptors of fields appended to sorted fields and
1974 calculate its total length.
1975
1976 The function first finds out what fields are used in the result set.
1977 Then it calculates the length of the buffer to store the values of
1978 these fields together with the value of sort values.
1979 If the calculated length is not greater than max_length_for_sort_data
1980 the function allocates memory for an array of descriptors containing
1981 layouts for the values of the non-sorted fields in the buffer and
1982 fills them.
1983
1984 @param thd Current thread
1985 @param ptabfield Array of references to the table fields
1986 @param sortlength Total length of sorted fields
1987 @param [out] addon_buf Buffer to us for appended fields
1988
1989 @note
1990 The null bits for the appended values are supposed to be put together
1991 and stored the buffer just ahead of the value of the first field.
1992
1993 @return
1994 Pointer to the layout descriptors for the appended fields, if any
1995 @retval
1996 NULL if we do not store field values with sort data.
1997*/
1998
1999static SORT_ADDON_FIELD *
2000get_addon_fields(ulong max_length_for_sort_data,
2001 Field **ptabfield, uint sortlength, LEX_STRING *addon_buf)
2002{
2003 Field **pfield;
2004 Field *field;
2005 SORT_ADDON_FIELD *addonf;
2006 uint length= 0;
2007 uint fields= 0;
2008 uint null_fields= 0;
2009 MY_BITMAP *read_set= (*ptabfield)->table->read_set;
2010 DBUG_ENTER("get_addon_fields");
2011
2012 /*
2013 If there is a reference to a field in the query add it
2014 to the the set of appended fields.
2015 Note for future refinement:
2016 This this a too strong condition.
2017 Actually we need only the fields referred in the
2018 result set. And for some of them it makes sense to use
2019 the values directly from sorted fields.
2020 But beware the case when item->cmp_type() != item->result_type()
2021 */
2022 addon_buf->str= 0;
2023 addon_buf->length= 0;
2024
2025 for (pfield= ptabfield; (field= *pfield) ; pfield++)
2026 {
2027 if (!bitmap_is_set(read_set, field->field_index))
2028 continue;
2029 if (field->flags & BLOB_FLAG)
2030 DBUG_RETURN(0);
2031 length+= field->max_packed_col_length(field->pack_length());
2032 if (field->maybe_null())
2033 null_fields++;
2034 fields++;
2035 }
2036 if (!fields)
2037 DBUG_RETURN(0);
2038 length+= (null_fields+7)/8;
2039
2040 if (length+sortlength > max_length_for_sort_data ||
2041 !my_multi_malloc(MYF(MY_WME | MY_THREAD_SPECIFIC),
2042 &addonf, sizeof(SORT_ADDON_FIELD) * (fields+1),
2043 &addon_buf->str, length,
2044 NullS))
2045
2046 DBUG_RETURN(0);
2047
2048 addon_buf->length= length;
2049 length= (null_fields+7)/8;
2050 null_fields= 0;
2051 for (pfield= ptabfield; (field= *pfield) ; pfield++)
2052 {
2053 if (!bitmap_is_set(read_set, field->field_index))
2054 continue;
2055 addonf->field= field;
2056 addonf->offset= length;
2057 if (field->maybe_null())
2058 {
2059 addonf->null_offset= null_fields/8;
2060 addonf->null_bit= 1<<(null_fields & 7);
2061 null_fields++;
2062 }
2063 else
2064 {
2065 addonf->null_offset= 0;
2066 addonf->null_bit= 0;
2067 }
2068 addonf->length= field->max_packed_col_length(field->pack_length());
2069 length+= addonf->length;
2070 addonf++;
2071 }
2072 addonf->field= 0; // Put end marker
2073
2074 DBUG_PRINT("info",("addon_length: %d",length));
2075 DBUG_RETURN(addonf-fields);
2076}
2077
2078
2079/**
2080 Copy (unpack) values appended to sorted fields from a buffer back to
2081 their regular positions specified by the Field::ptr pointers.
2082
2083 @param addon_field Array of descriptors for appended fields
2084 @param buff Buffer which to unpack the value from
2085
2086 @note
2087 The function is supposed to be used only as a callback function
2088 when getting field values for the sorted result set.
2089
2090 @return
2091 void.
2092*/
2093
2094static void
2095unpack_addon_fields(struct st_sort_addon_field *addon_field, uchar *buff,
2096 uchar *buff_end)
2097{
2098 Field *field;
2099 SORT_ADDON_FIELD *addonf= addon_field;
2100
2101 for ( ; (field= addonf->field) ; addonf++)
2102 {
2103 if (addonf->null_bit && (addonf->null_bit & buff[addonf->null_offset]))
2104 {
2105 field->set_null();
2106 continue;
2107 }
2108 field->set_notnull();
2109 field->unpack(field->ptr, buff + addonf->offset, buff_end, 0);
2110 }
2111}
2112
2113/*
2114** functions to change a double or float to a sortable string
2115** The following should work for IEEE
2116*/
2117
2118#define DBL_EXP_DIG (sizeof(double)*8-DBL_MANT_DIG)
2119
2120void change_double_for_sort(double nr,uchar *to)
2121{
2122 uchar *tmp=(uchar*) to;
2123 if (nr == 0.0)
2124 { /* Change to zero string */
2125 tmp[0]=(uchar) 128;
2126 memset(tmp+1, 0, sizeof(nr)-1);
2127 }
2128 else
2129 {
2130#ifdef WORDS_BIGENDIAN
2131 memcpy(tmp, &nr, sizeof(nr));
2132#else
2133 {
2134 uchar *ptr= (uchar*) &nr;
2135#if defined(__FLOAT_WORD_ORDER) && (__FLOAT_WORD_ORDER == __BIG_ENDIAN)
2136 tmp[0]= ptr[3]; tmp[1]=ptr[2]; tmp[2]= ptr[1]; tmp[3]=ptr[0];
2137 tmp[4]= ptr[7]; tmp[5]=ptr[6]; tmp[6]= ptr[5]; tmp[7]=ptr[4];
2138#else
2139 tmp[0]= ptr[7]; tmp[1]=ptr[6]; tmp[2]= ptr[5]; tmp[3]=ptr[4];
2140 tmp[4]= ptr[3]; tmp[5]=ptr[2]; tmp[6]= ptr[1]; tmp[7]=ptr[0];
2141#endif
2142 }
2143#endif
2144 if (tmp[0] & 128) /* Negative */
2145 { /* make complement */
2146 uint i;
2147 for (i=0 ; i < sizeof(nr); i++)
2148 tmp[i]=tmp[i] ^ (uchar) 255;
2149 }
2150 else
2151 { /* Set high and move exponent one up */
2152 ushort exp_part=(((ushort) tmp[0] << 8) | (ushort) tmp[1] |
2153 (ushort) 32768);
2154 exp_part+= (ushort) 1 << (16-1-DBL_EXP_DIG);
2155 tmp[0]= (uchar) (exp_part >> 8);
2156 tmp[1]= (uchar) exp_part;
2157 }
2158 }
2159}
2160
2161/**
2162 Free SORT_INFO
2163*/
2164
2165SORT_INFO::~SORT_INFO()
2166{
2167 DBUG_ENTER("~SORT_INFO::SORT_INFO()");
2168 free_data();
2169 DBUG_VOID_RETURN;
2170}
2171