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