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 uint make_sortkey(Sort_param *param, uchar *to, uchar *ref_pos,
52 bool using_packed_sortkeys= false);
53 static uint make_sortkey(Sort_param *param, uchar *to);
54 static uint make_packed_sortkey(Sort_param *param, uchar *to);
55
56 static void register_used_fields(Sort_param *param);
57 static bool save_index(Sort_param *param, uint count,
58 SORT_INFO *table_sort);
59 static uint suffix_length(ulong string_length);
60 static uint sortlength(THD *thd, Sort_keys *sortorder,
61 bool *allow_packing_for_sortkeys);
62 static Addon_fields *get_addon_fields(TABLE *table, uint sortlength,
63 uint *addon_length,
64 uint *m_packable_length);
65
66 static bool check_if_pq_applicable(Sort_param *param, SORT_INFO *info,
67 TABLE *table,
68 ha_rows records, size_t memory_available);
69
store_key_part_length(uint32 num,uchar * to,uint bytes)70 static void store_key_part_length(uint32 num, uchar *to, uint bytes)
71 {
72 switch(bytes) {
73 case 1: *to= (uchar)num; break;
74 case 2: int2store(to, num); break;
75 case 3: int3store(to, num); break;
76 case 4: int4store(to, num); break;
77 default: DBUG_ASSERT(0);
78 }
79 }
80
81
read_keypart_length(const uchar * from,uint bytes)82 static uint32 read_keypart_length(const uchar *from, uint bytes)
83 {
84 switch(bytes) {
85 case 1: return from[0];
86 case 2: return uint2korr(from);
87 case 3: return uint3korr(from);
88 case 4: return uint4korr(from);
89 default: DBUG_ASSERT(0); return 0;
90 }
91 }
92
93
94 // @param sortlen [Maximum] length of the sort key
init_for_filesort(uint sortlen,TABLE * table,ha_rows maxrows,bool sort_positions)95 void Sort_param::init_for_filesort(uint sortlen, TABLE *table,
96 ha_rows maxrows, bool sort_positions)
97 {
98 DBUG_ASSERT(addon_fields == NULL);
99
100 sort_length= sortlen;
101 ref_length= table->file->ref_length;
102 if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) &&
103 !table->fulltext_searched && !sort_positions)
104 {
105 /*
106 Get the descriptors of all fields whose values are appended
107 to sorted fields and get its total length in addon_buf.length
108 */
109 addon_fields= get_addon_fields(table, sort_length, &addon_length,
110 &m_packable_length);
111 }
112 if (using_addon_fields())
113 {
114 DBUG_ASSERT(addon_length < UINT_MAX32);
115 res_length= addon_length;
116 }
117 else
118 {
119 res_length= ref_length;
120 /*
121 The reference to the record is considered
122 as an additional sorted field
123 */
124 sort_length+= ref_length;
125 }
126 rec_length= sort_length + addon_length;
127 max_rows= maxrows;
128 }
129
130
try_to_pack_addons(ulong max_length_for_sort_data)131 void Sort_param::try_to_pack_addons(ulong max_length_for_sort_data)
132 {
133 if (!using_addon_fields() || // no addons, or
134 using_packed_addons()) // already packed
135 return;
136
137 if (!Addon_fields::can_pack_addon_fields(res_length))
138 return;
139
140 const uint sz= Addon_fields::size_of_length_field;
141
142 // Heuristic: skip packing if potential savings are less than 10 bytes.
143 if (m_packable_length < (10 + sz))
144 return;
145
146 SORT_ADDON_FIELD *addonf= addon_fields->begin();
147 for (;addonf != addon_fields->end(); ++addonf)
148 {
149 addonf->offset+= sz;
150 addonf->null_offset+= sz;
151 }
152
153 addon_fields->set_using_packed_addons(true);
154 m_using_packed_addons= true;
155 m_packed_format= true;
156
157 addon_length+= sz;
158 res_length+= sz;
159 rec_length+= sz;
160 }
161
162 /**
163 Sort a table.
164 Creates a set of pointers that can be used to read the rows
165 in sorted order. This should be done with the functions
166 in records.cc.
167
168 Before calling filesort, one must have done
169 table->file->info(HA_STATUS_VARIABLE)
170
171 The result set is stored in
172 filesort_info->io_cache or
173 filesort_info->record_pointers.
174
175 @param thd Current thread
176 @param table Table to sort
177 @param filesort How to sort the table
178 @param[out] found_rows Store the number of found rows here.
179 This is the number of found rows after
180 applying WHERE condition.
181 @note
182 If we sort by position (like if filesort->sort_positions==true)
183 filesort() will call table->prepare_for_position().
184
185 @retval
186 0 Error
187 # SORT_INFO
188 */
189
filesort(THD * thd,TABLE * table,Filesort * filesort,Filesort_tracker * tracker,JOIN * join,table_map first_table_bit)190 SORT_INFO *filesort(THD *thd, TABLE *table, Filesort *filesort,
191 Filesort_tracker* tracker, JOIN *join,
192 table_map first_table_bit)
193 {
194 int error;
195 DBUG_ASSERT(thd->variables.sortbuff_size <= SIZE_T_MAX);
196 size_t memory_available= (size_t)thd->variables.sortbuff_size;
197 uint maxbuffer;
198 Merge_chunk *buffpek;
199 ha_rows num_rows= HA_POS_ERROR;
200 IO_CACHE tempfile, buffpek_pointers, *outfile;
201 Sort_param param;
202 bool allow_packing_for_sortkeys;
203 Bounded_queue<uchar, uchar> pq;
204 SQL_SELECT *const select= filesort->select;
205 ha_rows max_rows= filesort->limit;
206 uint s_length= 0;
207 Sort_keys *sort_keys;
208
209 DBUG_ENTER("filesort");
210
211 if (!(sort_keys= filesort->make_sortorder(thd, join, first_table_bit)))
212 DBUG_RETURN(NULL); /* purecov: inspected */
213
214 s_length= static_cast<uint>(sort_keys->size());
215
216 DBUG_EXECUTE("info",TEST_filesort(filesort->sortorder, s_length););
217 #ifdef SKIP_DBUG_IN_FILESORT
218 DBUG_PUSH_EMPTY; /* No DBUG here */
219 #endif
220 SORT_INFO *sort;
221 TABLE_LIST *tab= table->pos_in_table_list;
222 Item_subselect *subselect= tab ? tab->containing_subselect() : 0;
223 MYSQL_FILESORT_START(table->s->db.str, table->s->table_name.str);
224 DEBUG_SYNC(thd, "filesort_start");
225
226 if (!(sort= new SORT_INFO))
227 return 0;
228
229 if (subselect && subselect->filesort_buffer.is_allocated())
230 {
231 // Reuse cache from last call
232 sort->filesort_buffer= subselect->filesort_buffer;
233 sort->buffpek= subselect->sortbuffer;
234 subselect->filesort_buffer.reset();
235 subselect->sortbuffer.str=0;
236 }
237
238 DBUG_ASSERT(sort->sorted_result_in_fsbuf == FALSE ||
239 sort->record_pointers == NULL);
240
241 outfile= &sort->io_cache;
242
243 my_b_clear(&tempfile);
244 my_b_clear(&buffpek_pointers);
245 buffpek=0;
246 error= 1;
247 sort->found_rows= HA_POS_ERROR;
248
249 param.sort_keys= sort_keys;
250 uint sort_len= sortlength(thd, sort_keys, &allow_packing_for_sortkeys);
251
252 param.init_for_filesort(sort_len, table, max_rows, filesort->sort_positions);
253
254 sort->addon_fields= param.addon_fields;
255 sort->sort_keys= param.sort_keys;
256
257 if (select && select->quick)
258 thd->inc_status_sort_range();
259 else
260 thd->inc_status_sort_scan();
261 thd->query_plan_flags|= QPLAN_FILESORT;
262 tracker->report_use(thd, max_rows);
263
264 // If number of rows is not known, use as much of sort buffer as possible.
265 num_rows= table->file->estimate_rows_upper_bound();
266
267 if (check_if_pq_applicable(¶m, sort,
268 table, num_rows, memory_available))
269 {
270 DBUG_PRINT("info", ("filesort PQ is applicable"));
271 thd->query_plan_flags|= QPLAN_FILESORT_PRIORITY_QUEUE;
272 status_var_increment(thd->status_var.filesort_pq_sorts_);
273 tracker->incr_pq_used();
274 param.using_pq= true;
275 const size_t compare_length= param.sort_length;
276 DBUG_ASSERT(param.using_packed_sortkeys() == false);
277 /*
278 For PQ queries (with limit) we know exactly how many pointers/records
279 we have in the buffer, so to simplify things, we initialize
280 all pointers here. (We cannot pack fields anyways, so there is no
281 point in doing lazy initialization).
282 */
283 sort->init_record_pointers();
284 if (pq.init(param.max_rows,
285 true, // max_at_top
286 NULL, // compare_function
287 compare_length,
288 &make_sortkey, ¶m, sort->get_sort_keys()))
289 {
290 /*
291 If we fail to init pq, we have to give up:
292 out of memory means my_malloc() will call my_error().
293 */
294 DBUG_PRINT("info", ("failed to allocate PQ"));
295 DBUG_ASSERT(thd->is_error());
296 goto err;
297 }
298 }
299 else
300 {
301 DBUG_PRINT("info", ("filesort PQ is not applicable"));
302
303 if (allow_packing_for_sortkeys)
304 param.try_to_pack_sortkeys();
305
306 param.try_to_pack_addons(thd->variables.max_length_for_sort_data);
307 tracker->report_sort_keys_format(param.using_packed_sortkeys());
308 param.using_pq= false;
309
310 size_t min_sort_memory= MY_MAX(MIN_SORT_MEMORY,
311 param.sort_length*MERGEBUFF2);
312 set_if_bigger(min_sort_memory, sizeof(Merge_chunk*)*MERGEBUFF2);
313 while (memory_available >= min_sort_memory)
314 {
315 ulonglong keys= memory_available / (param.rec_length + sizeof(char*));
316 param.max_keys_per_buffer= (uint) MY_MAX(MERGEBUFF2,
317 MY_MIN(num_rows, keys));
318 sort->alloc_sort_buffer(param.max_keys_per_buffer, param.rec_length);
319 if (sort->sort_buffer_size() > 0)
320 break;
321 size_t old_memory_available= memory_available;
322 memory_available= memory_available/4*3;
323 if (memory_available < min_sort_memory &&
324 old_memory_available > min_sort_memory)
325 memory_available= min_sort_memory;
326 }
327 if (memory_available < min_sort_memory)
328 {
329 my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR_LOG + ME_FATAL));
330 goto err;
331 }
332 tracker->report_sort_buffer_size(sort->sort_buffer_size());
333 }
334
335 if (param.using_addon_fields())
336 {
337 // report information whether addon fields are packed or not
338 tracker->report_addon_fields_format(param.using_packed_addons());
339 }
340
341 if (param.tmp_buffer.alloc(param.sort_length))
342 goto err;
343
344 if (open_cached_file(&buffpek_pointers,mysql_tmpdir,TEMP_PREFIX,
345 DISK_BUFFER_SIZE, MYF(MY_WME)))
346 goto err;
347
348 param.sort_form= table;
349 param.local_sortorder=
350 Bounds_checked_array<SORT_FIELD>(filesort->sortorder, s_length);
351
352 num_rows= find_all_keys(thd, ¶m, select,
353 sort,
354 &buffpek_pointers,
355 &tempfile,
356 pq.is_initialized() ? &pq : NULL,
357 &sort->found_rows);
358 if (num_rows == HA_POS_ERROR)
359 goto err;
360
361 maxbuffer= (uint) (my_b_tell(&buffpek_pointers)/sizeof(*buffpek));
362 tracker->report_merge_passes_at_start(thd->query_plan_fsort_passes);
363 tracker->report_row_numbers(param.examined_rows, sort->found_rows, num_rows);
364
365 if (maxbuffer == 0) // The whole set is in memory
366 {
367 if (save_index(¶m, (uint) num_rows, sort))
368 goto err;
369 }
370 else
371 {
372 /* filesort cannot handle zero-length records during merge. */
373 DBUG_ASSERT(param.sort_length != 0);
374
375 if (sort->buffpek.str && sort->buffpek.length < maxbuffer)
376 {
377 my_free(sort->buffpek.str);
378 sort->buffpek.str= 0;
379 }
380
381 if (param.using_addon_fields())
382 {
383 DBUG_ASSERT(sort->addon_fields);
384 if (!sort->addon_fields->allocate_addon_buf(param.addon_length))
385 goto err;
386 }
387
388 if (!(sort->buffpek.str=
389 (char *) read_buffpek_from_file(&buffpek_pointers, maxbuffer,
390 (uchar*) sort->buffpek.str)))
391 goto err;
392 sort->buffpek.length= maxbuffer;
393 buffpek= (Merge_chunk *) sort->buffpek.str;
394 close_cached_file(&buffpek_pointers);
395 /* Open cached file if it isn't open */
396 if (! my_b_inited(outfile) &&
397 open_cached_file(outfile,mysql_tmpdir,TEMP_PREFIX,READ_RECORD_BUFFER,
398 MYF(MY_WME)))
399 goto err;
400 if (reinit_io_cache(outfile,WRITE_CACHE,0L,0,0))
401 goto err;
402
403 /*
404 Use also the space previously used by string pointers in sort_buffer
405 for temporary key storage.
406 */
407
408 param.max_keys_per_buffer= static_cast<uint>(sort->sort_buffer_size()) /
409 param.rec_length;
410 set_if_bigger(param.max_keys_per_buffer, 1);
411 maxbuffer--; // Offset from 0
412
413 if (merge_many_buff(¶m, sort->get_raw_buf(),
414 buffpek,&maxbuffer,
415 &tempfile))
416 goto err;
417 if (flush_io_cache(&tempfile) ||
418 reinit_io_cache(&tempfile,READ_CACHE,0L,0,0))
419 goto err;
420 if (merge_index(¶m,
421 sort->get_raw_buf(),
422 buffpek,
423 maxbuffer,
424 &tempfile,
425 outfile))
426 goto err;
427 }
428
429 if (num_rows > param.max_rows)
430 {
431 // If find_all_keys() produced more results than the query LIMIT.
432 num_rows= param.max_rows;
433 }
434 error= 0;
435
436 err:
437 if (!subselect || !subselect->is_uncacheable())
438 {
439 if (!param.using_addon_fields())
440 sort->free_sort_buffer();
441 my_free(sort->buffpek.str);
442 }
443 else
444 {
445 /* Remember sort buffers for next subquery call */
446 subselect->filesort_buffer= sort->filesort_buffer;
447 subselect->sortbuffer= sort->buffpek;
448 sort->filesort_buffer.reset(); // Don't free this*/
449 }
450 sort->buffpek.str= 0;
451
452 close_cached_file(&tempfile);
453 close_cached_file(&buffpek_pointers);
454 if (my_b_inited(outfile))
455 {
456 if (flush_io_cache(outfile))
457 error=1;
458 {
459 my_off_t save_pos=outfile->pos_in_file;
460 /* For following reads */
461 if (reinit_io_cache(outfile,READ_CACHE,0L,0,0))
462 error=1;
463 outfile->end_of_file=save_pos;
464 }
465 }
466 tracker->report_merge_passes_at_end(thd, thd->query_plan_fsort_passes);
467 if (unlikely(error))
468 {
469 int kill_errno= thd->killed_errno();
470 DBUG_ASSERT(thd->is_error() || kill_errno || thd->killed == ABORT_QUERY);
471
472 my_printf_error(ER_FILSORT_ABORT,
473 "%s: %s",
474 MYF(0),
475 ER_THD(thd, ER_FILSORT_ABORT),
476 kill_errno ? ER_THD(thd, kill_errno) :
477 thd->killed == ABORT_QUERY ? "" :
478 thd->get_stmt_da()->message());
479
480 if (global_system_variables.log_warnings > 1)
481 {
482 sql_print_warning("%s, host: %s, user: %s, thread: %lu, query: %-.4096s",
483 ER_THD(thd, ER_FILSORT_ABORT),
484 thd->security_ctx->host_or_ip,
485 &thd->security_ctx->priv_user[0],
486 (ulong) thd->thread_id,
487 thd->query());
488 }
489 }
490 else
491 thd->inc_status_sort_rows(num_rows);
492
493 sort->examined_rows= param.examined_rows;
494 sort->return_rows= num_rows;
495 #ifdef SKIP_DBUG_IN_FILESORT
496 DBUG_POP_EMPTY; /* Ok to DBUG */
497 #endif
498
499 DBUG_PRINT("exit",
500 ("num_rows: %lld examined_rows: %lld found_rows: %lld",
501 (longlong) sort->return_rows, (longlong) sort->examined_rows,
502 (longlong) sort->found_rows));
503 MYSQL_FILESORT_DONE(error, num_rows);
504
505 if (unlikely(error))
506 {
507 delete sort;
508 sort= 0;
509 }
510 DBUG_RETURN(sort);
511 } /* filesort */
512
513
cleanup()514 void Filesort::cleanup()
515 {
516 if (select && own_select)
517 {
518 select->cleanup();
519 select= NULL;
520 }
521 }
522
523
524 /*
525 Create the Sort_keys array and fill the sort_keys[i]->{item|field}.
526
527 This indicates which field/item values will be used as sort keys.
528 Attributes like lengths are not filled yet.
529 */
530
531 Sort_keys*
make_sortorder(THD * thd,JOIN * join,table_map first_table_bit)532 Filesort::make_sortorder(THD *thd, JOIN *join, table_map first_table_bit)
533 {
534 uint count;
535 SORT_FIELD *sort,*pos;
536 ORDER *ord;
537 DBUG_ENTER("make_sortorder");
538
539 count=0;
540 for (ord = order; ord; ord= ord->next)
541 count++;
542
543 if (sortorder)
544 DBUG_RETURN(sort_keys);
545
546 DBUG_ASSERT(sort_keys == NULL);
547
548 sortorder= (SORT_FIELD*) thd->alloc(sizeof(SORT_FIELD) * count);
549 pos= sort= sortorder;
550
551 if (!pos)
552 DBUG_RETURN(0);
553
554 sort_keys= new Sort_keys(sortorder, count);
555
556 if (!sort_keys)
557 DBUG_RETURN(0);
558
559 pos= sort_keys->begin();
560 for (ord= order; ord; ord= ord->next, pos++)
561 {
562 Item *first= ord->item[0];
563 /*
564 It is possible that the query plan is to read table t1, while the
565 sort criteria actually has "ORDER BY t2.col" and the WHERE clause has
566 a multi-equality(t1.col, t2.col, ...).
567 The optimizer detects such cases (grep for
568 UseMultipleEqualitiesToRemoveTempTable to see where), but doesn't
569 perform equality substitution in the order->item. We need to do the
570 substitution here ourselves.
571 */
572 table_map item_map= first->used_tables();
573 if (join && (item_map & ~join->const_table_map) &&
574 !(item_map & first_table_bit) && join->cond_equal &&
575 first->get_item_equal())
576 {
577 /*
578 Ok, this is the case descibed just above. Get the first element of the
579 multi-equality.
580 */
581 Item_equal *item_eq= first->get_item_equal();
582 first= item_eq->get_first(NO_PARTICULAR_TAB, NULL);
583 }
584
585 Item *item= first->real_item();
586 pos->field= 0; pos->item= 0;
587 if (item->type() == Item::FIELD_ITEM)
588 pos->field= ((Item_field*) item)->field;
589 else if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item())
590 {
591 // Aggregate, or Item_aggregate_ref
592 DBUG_ASSERT(first->type() == Item::SUM_FUNC_ITEM ||
593 (first->type() == Item::REF_ITEM &&
594 static_cast<Item_ref*>(first)->ref_type() ==
595 Item_ref::AGGREGATE_REF));
596 pos->field= first->get_tmp_table_field();
597 }
598 else if (item->type() == Item::COPY_STR_ITEM)
599 { // Blob patch
600 pos->item= ((Item_copy*) item)->get_item();
601 }
602 else
603 pos->item= *ord->item;
604 pos->reverse= (ord->direction == ORDER::ORDER_DESC);
605 DBUG_ASSERT(pos->field != NULL || pos->item != NULL);
606 }
607 DBUG_RETURN(sort_keys);
608 }
609
610
611 /** Read 'count' number of buffer pointers into memory. */
612
read_buffpek_from_file(IO_CACHE * buffpek_pointers,uint count,uchar * buf)613 static uchar *read_buffpek_from_file(IO_CACHE *buffpek_pointers, uint count,
614 uchar *buf)
615 {
616 size_t length= sizeof(Merge_chunk)*count;
617 uchar *tmp= buf;
618 DBUG_ENTER("read_buffpek_from_file");
619 if (count > UINT_MAX/sizeof(Merge_chunk))
620 return 0; /* sizeof(BUFFPEK)*count will overflow */
621 if (!tmp)
622 tmp= (uchar *)my_malloc(key_memory_Filesort_info_merge, length,
623 MYF(MY_WME | MY_THREAD_SPECIFIC));
624 if (tmp)
625 {
626 if (reinit_io_cache(buffpek_pointers,READ_CACHE,0L,0,0) ||
627 my_b_read(buffpek_pointers, (uchar*) tmp, length))
628 {
629 my_free(tmp);
630 tmp=0;
631 }
632 }
633 DBUG_RETURN(tmp);
634 }
635
636 #ifndef DBUG_OFF
637
638 /* Buffer where record is returned */
639 char dbug_print_row_buff[512];
640
641 /* Temporary buffer for printing a column */
642 char dbug_print_row_buff_tmp[512];
643
644 /*
645 Print table's current row into a buffer and return a pointer to it.
646
647 This is intended to be used from gdb:
648
649 (gdb) p dbug_print_table_row(table)
650 $33 = "SUBQUERY2_t1(col_int_key,col_varchar_nokey)=(7,c)"
651 (gdb)
652
653 Only columns in table->read_set are printed
654 */
655
dbug_print_table_row(TABLE * table)656 const char* dbug_print_table_row(TABLE *table)
657 {
658 Field **pfield;
659 String tmp(dbug_print_row_buff_tmp,
660 sizeof(dbug_print_row_buff_tmp),&my_charset_bin);
661
662 String output(dbug_print_row_buff, sizeof(dbug_print_row_buff),
663 &my_charset_bin);
664
665 output.length(0);
666 output.append(table->alias);
667 output.append("(");
668 bool first= true;
669
670 for (pfield= table->field; *pfield ; pfield++)
671 {
672 if (table->read_set && !bitmap_is_set(table->read_set, (*pfield)->field_index))
673 continue;
674
675 if (first)
676 first= false;
677 else
678 output.append(",");
679
680 output.append((*pfield)->field_name.str ?
681 (*pfield)->field_name.str: "NULL");
682 }
683
684 output.append(")=(");
685
686 first= true;
687 for (pfield= table->field; *pfield ; pfield++)
688 {
689 Field *field= *pfield;
690
691 if (table->read_set && !bitmap_is_set(table->read_set, (*pfield)->field_index))
692 continue;
693
694 if (first)
695 first= false;
696 else
697 output.append(",");
698
699 if (field->is_null())
700 output.append("NULL");
701 else
702 {
703 if (field->type() == MYSQL_TYPE_BIT)
704 (void) field->val_int_as_str(&tmp, 1);
705 else
706 field->val_str(&tmp);
707 output.append(tmp.ptr(), tmp.length());
708 }
709 }
710 output.append(")");
711
712 return output.c_ptr_safe();
713 }
714
715
dbug_print_row(TABLE * table,uchar * rec)716 const char* dbug_print_row(TABLE *table, uchar *rec)
717 {
718 table->move_fields(table->field, rec, table->record[0]);
719 const char* ret= dbug_print_table_row(table);
720 table->move_fields(table->field, table->record[0], rec);
721 return ret;
722 }
723
724
725 /*
726 Print a text, SQL-like record representation into dbug trace.
727
728 Note: this function is a work in progress: at the moment
729 - column read bitmap is ignored (can print garbage for unused columns)
730 - there is no quoting
731 */
dbug_print_record(TABLE * table,bool print_rowid)732 static void dbug_print_record(TABLE *table, bool print_rowid)
733 {
734 char buff[1024];
735 Field **pfield;
736 String tmp(buff,sizeof(buff),&my_charset_bin);
737 DBUG_LOCK_FILE;
738
739 fprintf(DBUG_FILE, "record (");
740 for (pfield= table->field; *pfield ; pfield++)
741 fprintf(DBUG_FILE, "%s%s", (*pfield)->field_name.str,
742 (pfield[1])? ", ":"");
743 fprintf(DBUG_FILE, ") = ");
744
745 fprintf(DBUG_FILE, "(");
746 for (pfield= table->field; *pfield ; pfield++)
747 {
748 Field *field= *pfield;
749
750 if (field->is_null())
751 fwrite("NULL", sizeof(char), 4, DBUG_FILE);
752
753 if (field->type() == MYSQL_TYPE_BIT)
754 (void) field->val_int_as_str(&tmp, 1);
755 else
756 field->val_str(&tmp);
757
758 fwrite(tmp.ptr(),sizeof(char),tmp.length(),DBUG_FILE);
759 if (pfield[1])
760 fwrite(", ", sizeof(char), 2, DBUG_FILE);
761 }
762 fprintf(DBUG_FILE, ")");
763 if (print_rowid)
764 {
765 fprintf(DBUG_FILE, " rowid ");
766 for (uint i=0; i < table->file->ref_length; i++)
767 {
768 fprintf(DBUG_FILE, "%x", (uchar)table->file->ref[i]);
769 }
770 }
771 fprintf(DBUG_FILE, "\n");
772 DBUG_UNLOCK_FILE;
773 }
774
775 #endif
776
777
778 /**
779 Search after sort_keys, and write them into tempfile
780 (if we run out of space in the sort_keys buffer).
781 All produced sequences are guaranteed to be non-empty.
782
783 @param param Sorting parameter
784 @param select Use this to get source data
785 @param sort_keys Array of pointers to sort key + addon buffers.
786 @param buffpek_pointers File to write BUFFPEKs describing sorted segments
787 in tempfile.
788 @param tempfile File to write sorted sequences of sortkeys to.
789 @param pq If !NULL, use it for keeping top N elements
790 @param [out] found_rows The number of FOUND_ROWS().
791 For a query with LIMIT, this value will typically
792 be larger than the function return value.
793
794 @note
795 Basic idea:
796 @verbatim
797 while (get_next_sortkey())
798 {
799 if (using priority queue)
800 push sort key into queue
801 else
802 {
803 if (no free space in sort_keys buffers)
804 {
805 sort sort_keys buffer;
806 dump sorted sequence to 'tempfile';
807 dump BUFFPEK describing sequence location into 'buffpek_pointers';
808 }
809 put sort key into 'sort_keys';
810 }
811 }
812 if (sort_keys has some elements && dumped at least once)
813 sort-dump-dump as above;
814 else
815 don't sort, leave sort_keys array to be sorted by caller.
816 @endverbatim
817
818 @retval
819 Number of records written on success.
820 @retval
821 HA_POS_ERROR on error.
822 */
823
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)824 static ha_rows find_all_keys(THD *thd, Sort_param *param, SQL_SELECT *select,
825 SORT_INFO *fs_info,
826 IO_CACHE *buffpek_pointers,
827 IO_CACHE *tempfile,
828 Bounded_queue<uchar, uchar> *pq,
829 ha_rows *found_rows)
830 {
831 int error, quick_select;
832 uint idx, indexpos;
833 uchar *ref_pos, *next_pos, ref_buff[MAX_REFLENGTH];
834 TABLE *sort_form;
835 handler *file;
836 MY_BITMAP *save_read_set, *save_write_set;
837 Item *sort_cond;
838 ha_rows num_records= 0;
839 const bool packed_format= param->is_packed_format();
840 const bool using_packed_sortkeys= param->using_packed_sortkeys();
841
842 DBUG_ENTER("find_all_keys");
843 DBUG_PRINT("info",("using: %s",
844 (select ? select->quick ? "ranges" : "where":
845 "every row")));
846
847 idx=indexpos=0;
848 error=quick_select=0;
849 sort_form=param->sort_form;
850 file=sort_form->file;
851 ref_pos= ref_buff;
852 quick_select=select && select->quick;
853 *found_rows= 0;
854 ref_pos= &file->ref[0];
855 next_pos=ref_pos;
856
857 DBUG_EXECUTE_IF("show_explain_in_find_all_keys",
858 dbug_serve_apcs(thd, 1);
859 );
860
861 if (!quick_select)
862 {
863 next_pos=(uchar*) 0; /* Find records in sequence */
864 DBUG_EXECUTE_IF("bug14365043_1",
865 DBUG_SET("+d,ha_rnd_init_fail"););
866 if (unlikely(file->ha_rnd_init_with_error(1)))
867 DBUG_RETURN(HA_POS_ERROR);
868 file->extra_opt(HA_EXTRA_CACHE, thd->variables.read_buff_size);
869 }
870
871 /* Remember original bitmaps */
872 save_read_set= sort_form->read_set;
873 save_write_set= sort_form->write_set;
874
875 /* Set up temporary column read map for columns used by sort */
876 DBUG_ASSERT(save_read_set != &sort_form->tmp_set);
877 bitmap_clear_all(&sort_form->tmp_set);
878 sort_form->column_bitmaps_set(&sort_form->tmp_set, &sort_form->tmp_set);
879 register_used_fields(param);
880 if (quick_select)
881 select->quick->add_used_key_part_to_set();
882
883 sort_cond= (!select ? 0 :
884 (!select->pre_idx_push_select_cond ?
885 select->cond : select->pre_idx_push_select_cond));
886 if (sort_cond)
887 sort_cond->walk(&Item::register_field_in_read_map, 1, sort_form);
888 sort_form->file->column_bitmaps_signal();
889
890 if (quick_select)
891 {
892 if (select->quick->reset())
893 goto err;
894 }
895
896 DEBUG_SYNC(thd, "after_index_merge_phase1");
897
898 for (;;)
899 {
900 if (quick_select)
901 error= select->quick->get_next();
902 else /* Not quick-select */
903 error= file->ha_rnd_next(sort_form->record[0]);
904 if (unlikely(error))
905 break;
906 file->position(sort_form->record[0]);
907 DBUG_EXECUTE_IF("debug_filesort", dbug_print_record(sort_form, TRUE););
908
909 if (unlikely(thd->check_killed()))
910 {
911 DBUG_PRINT("info",("Sort killed by user"));
912 if (!quick_select)
913 {
914 (void) file->extra(HA_EXTRA_NO_CACHE);
915 file->ha_rnd_end();
916 }
917 goto err; /* purecov: inspected */
918 }
919
920 bool write_record= false;
921 if (likely(error == 0))
922 {
923 param->examined_rows++;
924 if (select && select->cond)
925 {
926 /*
927 If the condition 'select->cond' contains a subquery, restore the
928 original read/write sets of the table 'sort_form' because when
929 SQL_SELECT::skip_record evaluates this condition. it may include a
930 correlated subquery predicate, such that some field in the subquery
931 refers to 'sort_form'.
932
933 PSergey-todo: discuss the above with Timour.
934 */
935 MY_BITMAP *tmp_read_set= sort_form->read_set;
936 MY_BITMAP *tmp_write_set= sort_form->write_set;
937
938 if (select->cond->with_subquery())
939 sort_form->column_bitmaps_set(save_read_set, save_write_set);
940 write_record= (select->skip_record(thd) > 0);
941 if (select->cond->with_subquery())
942 sort_form->column_bitmaps_set(tmp_read_set, tmp_write_set);
943 }
944 else
945 write_record= true;
946 }
947
948 if (write_record)
949 {
950 if (pq)
951 pq->push(ref_pos);
952 else
953 {
954 if (fs_info->isfull())
955 {
956 if (write_keys(param, fs_info, idx, buffpek_pointers, tempfile))
957 goto err;
958 idx= 0;
959 indexpos++;
960 }
961 if (idx == 0)
962 fs_info->init_next_record_pointer();
963 uchar *start_of_rec= fs_info->get_next_record_pointer();
964
965 const uint rec_sz= make_sortkey(param, start_of_rec,
966 ref_pos, using_packed_sortkeys);
967 if (packed_format && rec_sz != param->rec_length)
968 fs_info->adjust_next_record_pointer(rec_sz);
969 idx++;
970 }
971 num_records++;
972 }
973
974 /* It does not make sense to read more keys in case of a fatal error */
975 if (unlikely(thd->is_error()))
976 break;
977
978 /*
979 We need to this after checking the error as the transaction may have
980 rolled back in case of a deadlock
981 */
982 if (!write_record)
983 file->unlock_row();
984 }
985 if (!quick_select)
986 {
987 (void) file->extra(HA_EXTRA_NO_CACHE); /* End caching of records */
988 if (!next_pos)
989 file->ha_rnd_end();
990 }
991
992 /* Signal we should use original column read and write maps */
993 sort_form->column_bitmaps_set(save_read_set, save_write_set);
994
995 if (unlikely(thd->is_error()))
996 DBUG_RETURN(HA_POS_ERROR);
997
998 DBUG_PRINT("test",("error: %d indexpos: %d",error,indexpos));
999 if (unlikely(error != HA_ERR_END_OF_FILE))
1000 {
1001 file->print_error(error,MYF(ME_ERROR_LOG));
1002 DBUG_RETURN(HA_POS_ERROR);
1003 }
1004 if (indexpos && idx &&
1005 write_keys(param, fs_info, idx, buffpek_pointers, tempfile))
1006 DBUG_RETURN(HA_POS_ERROR); /* purecov: inspected */
1007
1008 (*found_rows)= num_records;
1009 if (pq)
1010 num_records= pq->num_elements();
1011
1012
1013 DBUG_PRINT("info", ("find_all_keys return %llu", (ulonglong) num_records));
1014 DBUG_RETURN(num_records);
1015
1016 err:
1017 sort_form->column_bitmaps_set(save_read_set, save_write_set);
1018 DBUG_RETURN(HA_POS_ERROR);
1019 } /* find_all_keys */
1020
1021
1022 /**
1023 @details
1024 Sort the buffer and write:
1025 -# the sorted sequence to tempfile
1026 -# a BUFFPEK describing the sorted sequence position to buffpek_pointers
1027
1028 (was: Skriver en buffert med nycklar till filen)
1029
1030 @param param Sort parameters
1031 @param sort_keys Array of pointers to keys to sort
1032 @param count Number of elements in sort_keys array
1033 @param buffpek_pointers One 'BUFFPEK' struct will be written into this file.
1034 The BUFFPEK::{file_pos, count} will indicate where
1035 the sorted data was stored.
1036 @param tempfile The sorted sequence will be written into this file.
1037
1038 @retval
1039 0 OK
1040 @retval
1041 1 Error
1042 */
1043
1044 static bool
write_keys(Sort_param * param,SORT_INFO * fs_info,uint count,IO_CACHE * buffpek_pointers,IO_CACHE * tempfile)1045 write_keys(Sort_param *param, SORT_INFO *fs_info, uint count,
1046 IO_CACHE *buffpek_pointers, IO_CACHE *tempfile)
1047 {
1048 Merge_chunk buffpek;
1049 DBUG_ENTER("write_keys");
1050
1051 fs_info->sort_buffer(param, count);
1052
1053 if (!my_b_inited(tempfile) &&
1054 open_cached_file(tempfile, mysql_tmpdir, TEMP_PREFIX, DISK_BUFFER_SIZE,
1055 MYF(MY_WME)))
1056 DBUG_RETURN(1); /* purecov: inspected */
1057 /* check we won't have more buffpeks than we can possibly keep in memory */
1058 if (my_b_tell(buffpek_pointers) + sizeof(Merge_chunk) > (ulonglong)UINT_MAX)
1059 DBUG_RETURN(1);
1060
1061 buffpek.set_file_position(my_b_tell(tempfile));
1062 if ((ha_rows) count > param->max_rows)
1063 count=(uint) param->max_rows; /* purecov: inspected */
1064 buffpek.set_rowcount(static_cast<ha_rows>(count));
1065
1066 for (uint ix= 0; ix < count; ++ix)
1067 {
1068 uchar *record= fs_info->get_sorted_record(ix);
1069
1070
1071 if (my_b_write(tempfile, record, param->get_record_length(record)))
1072 DBUG_RETURN(1); /* purecov: inspected */
1073 }
1074
1075 if (my_b_write(buffpek_pointers, (uchar*) &buffpek, sizeof(buffpek)))
1076 DBUG_RETURN(1);
1077
1078 DBUG_RETURN(0);
1079
1080 } /* write_keys */
1081
1082
1083 /**
1084 Store length in high-byte-first order.
1085 */
store_length(uchar * to,uint length,uint pack_length)1086 void store_length(uchar *to, uint length, uint pack_length)
1087 {
1088 switch (pack_length) {
1089 case 1:
1090 *to= (uchar) length;
1091 break;
1092 case 2:
1093 mi_int2store(to, length);
1094 break;
1095 case 3:
1096 mi_int3store(to, length);
1097 break;
1098 default:
1099 mi_int4store(to, length);
1100 break;
1101 }
1102 }
1103
1104
1105 void
make_sort_key_part(uchar * to,Item * item,const SORT_FIELD_ATTR * sort_field,Sort_param * param) const1106 Type_handler_string_result::make_sort_key_part(uchar *to, Item *item,
1107 const SORT_FIELD_ATTR *sort_field,
1108 Sort_param *param) const
1109 {
1110 CHARSET_INFO *cs= item->collation.collation;
1111 bool maybe_null= item->maybe_null;
1112
1113 if (maybe_null)
1114 *to++= 1;
1115
1116 String *res= item->str_result(¶m->tmp_buffer);
1117 if (!res)
1118 {
1119 if (maybe_null)
1120 memset(to - 1, 0, sort_field->length + 1);
1121 else
1122 {
1123 /* purecov: begin deadcode */
1124 /*
1125 This should only happen during extreme conditions if we run out
1126 of memory or have an item marked not null when it can be null.
1127 This code is here mainly to avoid a hard crash in this case.
1128 */
1129 DBUG_ASSERT(0);
1130 DBUG_PRINT("warning",
1131 ("Got null on something that shouldn't be null"));
1132 memset(to, 0, sort_field->length); // Avoid crash
1133 /* purecov: end */
1134 }
1135 return;
1136 }
1137
1138 if (use_strnxfrm(cs))
1139 {
1140 #ifdef DBUG_ASSERT_EXISTS
1141 size_t tmp_length=
1142 #endif
1143 cs->strnxfrm(to, sort_field->length,
1144 item->max_char_length() * cs->strxfrm_multiply,
1145 (uchar*) res->ptr(), res->length(),
1146 MY_STRXFRM_PAD_WITH_SPACE |
1147 MY_STRXFRM_PAD_TO_MAXLEN);
1148 DBUG_ASSERT(tmp_length == sort_field->length);
1149 }
1150 else
1151 {
1152 uint diff;
1153 uint sort_field_length= sort_field->length - sort_field->suffix_length;
1154 uint length= res->length();
1155 if (sort_field_length < length)
1156 {
1157 diff= 0;
1158 length= sort_field_length;
1159 }
1160 else
1161 diff= sort_field_length - length;
1162 if (sort_field->suffix_length)
1163 {
1164 /* Store length last in result_string */
1165 store_length(to + sort_field_length, length, sort_field->suffix_length);
1166 }
1167 /* apply cs->sort_order for case-insensitive comparison if needed */
1168 cs->strnxfrm((uchar*)to, length, (const uchar*) res->ptr(), length);
1169 char fill_char= ((cs->state & MY_CS_BINSORT) ? (char) 0 : ' ');
1170 cs->fill((char *) to + length, diff, fill_char);
1171 }
1172 }
1173
1174
1175 void
make_sort_key_part(uchar * to,Item * item,const SORT_FIELD_ATTR * sort_field,Sort_param * param) const1176 Type_handler_int_result::make_sort_key_part(uchar *to, Item *item,
1177 const SORT_FIELD_ATTR *sort_field,
1178 Sort_param *param) const
1179 {
1180 longlong value= item->val_int_result();
1181 make_sort_key_longlong(to, item->maybe_null, item->null_value,
1182 item->unsigned_flag, value);
1183 }
1184
1185
1186 void
make_sort_key_part(uchar * to,Item * item,const SORT_FIELD_ATTR * sort_field,Sort_param * param) const1187 Type_handler_temporal_result::make_sort_key_part(uchar *to, Item *item,
1188 const SORT_FIELD_ATTR *sort_field,
1189 Sort_param *param) const
1190 {
1191 MYSQL_TIME buf;
1192 // This is a temporal type. No nanoseconds. Rounding mode is not important.
1193 DBUG_ASSERT(item->cmp_type() == TIME_RESULT);
1194 static const Temporal::Options opt(TIME_INVALID_DATES, TIME_FRAC_NONE);
1195 if (item->get_date_result(current_thd, &buf, opt))
1196 {
1197 DBUG_ASSERT(item->maybe_null);
1198 DBUG_ASSERT(item->null_value);
1199 make_sort_key_longlong(to, item->maybe_null, true,
1200 item->unsigned_flag, 0);
1201 }
1202 else
1203 make_sort_key_longlong(to, item->maybe_null, false,
1204 item->unsigned_flag, pack_time(&buf));
1205 }
1206
1207
1208 void
make_sort_key_part(uchar * to,Item * item,const SORT_FIELD_ATTR * sort_field,Sort_param * param) const1209 Type_handler_timestamp_common::make_sort_key_part(uchar *to, Item *item,
1210 const SORT_FIELD_ATTR *sort_field,
1211 Sort_param *param) const
1212 {
1213 THD *thd= current_thd;
1214 uint binlen= my_timestamp_binary_length(item->decimals);
1215 Timestamp_or_zero_datetime_native_null native(thd, item);
1216 if (native.is_null() || native.is_zero_datetime())
1217 {
1218 // NULL or '0000-00-00 00:00:00'
1219 bzero(to, item->maybe_null ? binlen + 1 : binlen);
1220 }
1221 else
1222 {
1223 if (item->maybe_null)
1224 *to++= 1;
1225 if (native.length() != binlen)
1226 {
1227 /*
1228 Some items can return native representation with a different
1229 number of fractional digits, e.g.: GREATEST(ts_3, ts_4) can
1230 return a value with 3 fractional digits, although its fractional
1231 precision is 4. Re-pack with a proper precision now.
1232 */
1233 Timestamp(native).to_native(&native, item->datetime_precision(thd));
1234 }
1235 DBUG_ASSERT(native.length() == binlen);
1236 memcpy((char *) to, native.ptr(), binlen);
1237 }
1238 }
1239
1240
1241 void
store_sort_key_longlong(uchar * to,bool unsigned_flag,longlong value) const1242 Type_handler::store_sort_key_longlong(uchar *to, bool unsigned_flag,
1243 longlong value) const
1244 {
1245 to[7]= (uchar) value;
1246 to[6]= (uchar) (value >> 8);
1247 to[5]= (uchar) (value >> 16);
1248 to[4]= (uchar) (value >> 24);
1249 to[3]= (uchar) (value >> 32);
1250 to[2]= (uchar) (value >> 40);
1251 to[1]= (uchar) (value >> 48);
1252 if (unsigned_flag) /* Fix sign */
1253 to[0]= (uchar) (value >> 56);
1254 else
1255 to[0]= (uchar) (value >> 56) ^ 128; /* Reverse signbit */
1256 }
1257
1258
1259 void
make_sort_key_longlong(uchar * to,bool maybe_null,bool null_value,bool unsigned_flag,longlong value) const1260 Type_handler::make_sort_key_longlong(uchar *to,
1261 bool maybe_null,
1262 bool null_value,
1263 bool unsigned_flag,
1264 longlong value) const
1265
1266 {
1267 if (maybe_null)
1268 {
1269 if (null_value)
1270 {
1271 memset(to, 0, 9);
1272 return;
1273 }
1274 *to++= 1;
1275 }
1276 store_sort_key_longlong(to, unsigned_flag, value);
1277 }
1278
1279
1280 uint
make_packed_sort_key_longlong(uchar * to,bool maybe_null,bool null_value,bool unsigned_flag,longlong value,const SORT_FIELD_ATTR * sort_field) const1281 Type_handler::make_packed_sort_key_longlong(uchar *to, bool maybe_null,
1282 bool null_value, bool unsigned_flag,
1283 longlong value,
1284 const SORT_FIELD_ATTR *sort_field) const
1285 {
1286 if (maybe_null)
1287 {
1288 if (null_value)
1289 {
1290 *to++= 0;
1291 return 0;
1292 }
1293 *to++= 1;
1294 }
1295 store_sort_key_longlong(to, unsigned_flag, value);
1296 DBUG_ASSERT(sort_field->original_length == sort_field->length);
1297 return sort_field->original_length;
1298 }
1299
1300
1301 void
make_sort_key_part(uchar * to,Item * item,const SORT_FIELD_ATTR * sort_field,Sort_param * param) const1302 Type_handler_decimal_result::make_sort_key_part(uchar *to, Item *item,
1303 const SORT_FIELD_ATTR *sort_field,
1304 Sort_param *param) const
1305 {
1306 my_decimal dec_buf, *dec_val= item->val_decimal_result(&dec_buf);
1307 if (item->maybe_null)
1308 {
1309 if (item->null_value)
1310 {
1311 memset(to, 0, sort_field->length + 1);
1312 return;
1313 }
1314 *to++= 1;
1315 }
1316 dec_val->to_binary(to, item->max_length - (item->decimals ? 1 : 0),
1317 item->decimals);
1318 }
1319
1320
1321 void
make_sort_key_part(uchar * to,Item * item,const SORT_FIELD_ATTR * sort_field,Sort_param * param) const1322 Type_handler_real_result::make_sort_key_part(uchar *to, Item *item,
1323 const SORT_FIELD_ATTR *sort_field,
1324 Sort_param *param) const
1325 {
1326 double value= item->val_result();
1327 if (item->maybe_null)
1328 {
1329 if (item->null_value)
1330 {
1331 memset(to, 0, sort_field->length + 1);
1332 return;
1333 }
1334 *to++= 1;
1335 }
1336 change_double_for_sort(value, to);
1337 }
1338
1339
1340 /** Make a sort-key from record. */
1341
make_sortkey(Sort_param * param,uchar * to,uchar * ref_pos,bool using_packed_sortkeys)1342 static uint make_sortkey(Sort_param *param, uchar *to, uchar *ref_pos,
1343 bool using_packed_sortkeys)
1344 {
1345 uchar *orig_to= to;
1346
1347 to+= using_packed_sortkeys ?
1348 make_packed_sortkey(param, to) :
1349 make_sortkey(param, to);
1350
1351 if (param->using_addon_fields())
1352 {
1353 /*
1354 Save field values appended to sorted fields.
1355 First null bit indicators are appended then field values follow.
1356 In this implementation we use fixed layout for field values -
1357 the same for all records.
1358 */
1359 SORT_ADDON_FIELD *addonf= param->addon_fields->begin();
1360 uchar *nulls= to;
1361 uchar *p_len= to;
1362 DBUG_ASSERT(addonf != 0);
1363 const bool packed_addon_fields= param->addon_fields->using_packed_addons();
1364 uint32 res_len= addonf->offset;
1365 memset(nulls, 0, addonf->offset);
1366 to+= addonf->offset;
1367 for ( ; addonf != param->addon_fields->end() ; addonf++)
1368 {
1369 Field *field= addonf->field;
1370 if (addonf->null_bit && field->is_null())
1371 {
1372 nulls[addonf->null_offset]|= addonf->null_bit;
1373 if (!packed_addon_fields)
1374 to+= addonf->length;
1375 }
1376 else
1377 {
1378 uchar *end= field->pack(to, field->ptr);
1379 DBUG_ASSERT(end >= to);
1380 uint sz= static_cast<uint>(end - to);
1381 res_len += sz;
1382 if (packed_addon_fields)
1383 to+= sz;
1384 else
1385 {
1386 if (addonf->length > sz)
1387 bzero(end, addonf->length - sz); // Make Valgrind/MSAN happy
1388 to+= addonf->length;
1389 }
1390 }
1391 }
1392 if (packed_addon_fields)
1393 Addon_fields::store_addon_length(p_len, res_len);
1394 }
1395 else
1396 {
1397 /* Save filepos last */
1398 memcpy((uchar*) to, ref_pos, (size_t) param->ref_length);
1399 to+= param->ref_length;
1400 }
1401 return static_cast<uint>(to - orig_to);
1402 }
1403
1404
1405 /*
1406 Register fields used by sorting in the sorted table's read set
1407 */
1408
register_used_fields(Sort_param * param)1409 static void register_used_fields(Sort_param *param)
1410 {
1411 SORT_FIELD *sort_field;
1412 TABLE *table=param->sort_form;
1413
1414 for (sort_field= param->local_sortorder.begin() ;
1415 sort_field != param->local_sortorder.end() ;
1416 sort_field++)
1417 {
1418 Field *field;
1419 if ((field= sort_field->field))
1420 {
1421 if (field->table == table)
1422 field->register_field_in_read_map();
1423 }
1424 else
1425 { // Item
1426 sort_field->item->walk(&Item::register_field_in_read_map, 1, table);
1427 }
1428 }
1429
1430 if (param->using_addon_fields())
1431 {
1432 SORT_ADDON_FIELD *addonf= param->addon_fields->begin();
1433 for ( ; (addonf != param->addon_fields->end()) ; addonf++)
1434 {
1435 Field *field= addonf->field;
1436 field->register_field_in_read_map();
1437 }
1438 }
1439 else
1440 {
1441 /* Save filepos last */
1442 table->prepare_for_position();
1443 }
1444 }
1445
1446
save_index(Sort_param * param,uint count,SORT_INFO * table_sort)1447 static bool save_index(Sort_param *param, uint count,
1448 SORT_INFO *table_sort)
1449 {
1450 uint offset,res_length, length;
1451 uchar *to;
1452 DBUG_ENTER("save_index");
1453 DBUG_ASSERT(table_sort->record_pointers == 0);
1454
1455 table_sort->sort_buffer(param, count);
1456
1457 if (param->using_addon_fields())
1458 {
1459 table_sort->sorted_result_in_fsbuf= TRUE;
1460 table_sort->set_sort_length(param->sort_length);
1461 DBUG_RETURN(0);
1462 }
1463
1464 bool using_packed_sortkeys= param->using_packed_sortkeys();
1465 res_length= param->res_length;
1466 offset= param->rec_length-res_length;
1467 if (!(to= table_sort->record_pointers=
1468 (uchar*) my_malloc(key_memory_Filesort_info_record_pointers,
1469 res_length*count, MYF(MY_WME | MY_THREAD_SPECIFIC))))
1470 DBUG_RETURN(1); /* purecov: inspected */
1471 for (uint ix= 0; ix < count; ++ix)
1472 {
1473 uchar *record= table_sort->get_sorted_record(ix);
1474
1475 length= using_packed_sortkeys ?
1476 Sort_keys::read_sortkey_length(record) : offset;
1477
1478 memcpy(to, record + length, res_length);
1479 to+= res_length;
1480 }
1481 DBUG_RETURN(0);
1482 }
1483
1484
1485 /**
1486 Test whether priority queue is worth using to get top elements of an
1487 ordered result set. If it is, then allocates buffer for required amount of
1488 records
1489
1490 @param param Sort parameters.
1491 @param filesort_info Filesort information.
1492 @param table Table to sort.
1493 @param num_rows Estimate of number of rows in source record set.
1494 @param memory_available Memory available for sorting.
1495
1496 DESCRIPTION
1497 Given a query like this:
1498 SELECT ... FROM t ORDER BY a1,...,an LIMIT max_rows;
1499 This function tests whether a priority queue should be used to keep
1500 the result. Necessary conditions are:
1501 - estimate that it is actually cheaper than merge-sort
1502 - enough memory to store the <max_rows> records.
1503
1504 If we don't have space for <max_rows> records, but we *do* have
1505 space for <max_rows> keys, we may rewrite 'table' to sort with
1506 references to records instead of additional data.
1507 (again, based on estimates that it will actually be cheaper).
1508
1509 @retval
1510 true - if it's ok to use PQ
1511 false - PQ will be slower than merge-sort, or there is not enough memory.
1512 */
1513
check_if_pq_applicable(Sort_param * param,SORT_INFO * filesort_info,TABLE * table,ha_rows num_rows,size_t memory_available)1514 static bool check_if_pq_applicable(Sort_param *param,
1515 SORT_INFO *filesort_info,
1516 TABLE *table, ha_rows num_rows,
1517 size_t memory_available)
1518 {
1519 DBUG_ENTER("check_if_pq_applicable");
1520
1521 /*
1522 How much Priority Queue sort is slower than qsort.
1523 Measurements (see unit test) indicate that PQ is roughly 3 times slower.
1524 */
1525 const double PQ_slowness= 3.0;
1526
1527 if (param->max_rows == HA_POS_ERROR)
1528 {
1529 DBUG_PRINT("info", ("No LIMIT"));
1530 DBUG_RETURN(false);
1531 }
1532
1533 if (param->max_rows + 2 >= UINT_MAX)
1534 {
1535 DBUG_PRINT("info", ("Too large LIMIT"));
1536 DBUG_RETURN(false);
1537 }
1538
1539 size_t num_available_keys=
1540 memory_available / (param->rec_length + sizeof(char*));
1541 // We need 1 extra record in the buffer, when using PQ.
1542 param->max_keys_per_buffer= (uint) param->max_rows + 1;
1543
1544 if (num_rows < num_available_keys)
1545 {
1546 // The whole source set fits into memory.
1547 if (param->max_rows < num_rows/PQ_slowness )
1548 {
1549 filesort_info->alloc_sort_buffer(param->max_keys_per_buffer,
1550 param->rec_length);
1551 DBUG_RETURN(filesort_info->sort_buffer_size() != 0);
1552 }
1553 else
1554 {
1555 // PQ will be slower.
1556 DBUG_RETURN(false);
1557 }
1558 }
1559
1560 // Do we have space for LIMIT rows in memory?
1561 if (param->max_keys_per_buffer < num_available_keys)
1562 {
1563 filesort_info->alloc_sort_buffer(param->max_keys_per_buffer,
1564 param->rec_length);
1565 DBUG_RETURN(filesort_info->sort_buffer_size() != 0);
1566 }
1567
1568 // Try to strip off addon fields.
1569 if (param->addon_fields)
1570 {
1571 const size_t row_length=
1572 param->sort_length + param->ref_length + sizeof(char*);
1573 num_available_keys= memory_available / row_length;
1574
1575 // Can we fit all the keys in memory?
1576 if (param->max_keys_per_buffer < num_available_keys)
1577 {
1578 const double sort_merge_cost=
1579 get_merge_many_buffs_cost_fast(num_rows,
1580 num_available_keys,
1581 (uint)row_length);
1582 /*
1583 PQ has cost:
1584 (insert + qsort) * log(queue size) / TIME_FOR_COMPARE_ROWID +
1585 cost of file lookup afterwards.
1586 The lookup cost is a bit pessimistic: we take scan_time and assume
1587 that on average we find the row after scanning half of the file.
1588 A better estimate would be lookup cost, but note that we are doing
1589 random lookups here, rather than sequential scan.
1590 */
1591 const double pq_cpu_cost=
1592 (PQ_slowness * num_rows + param->max_keys_per_buffer) *
1593 log((double) param->max_keys_per_buffer) / TIME_FOR_COMPARE_ROWID;
1594 const double pq_io_cost=
1595 param->max_rows * table->file->scan_time() / 2.0;
1596 const double pq_cost= pq_cpu_cost + pq_io_cost;
1597
1598 if (sort_merge_cost < pq_cost)
1599 DBUG_RETURN(false);
1600
1601 filesort_info->alloc_sort_buffer(param->max_keys_per_buffer,
1602 param->sort_length + param->ref_length);
1603
1604 if (filesort_info->sort_buffer_size() > 0)
1605 {
1606 /* Make attached data to be references instead of fields. */
1607 my_free(filesort_info->addon_fields);
1608 filesort_info->addon_fields= NULL;
1609 param->addon_fields= NULL;
1610
1611 param->res_length= param->ref_length;
1612 param->sort_length+= param->ref_length;
1613 param->rec_length= param->sort_length;
1614
1615 DBUG_RETURN(true);
1616 }
1617 }
1618 }
1619 DBUG_RETURN(false);
1620 }
1621
1622
1623 /** Merge buffers to make < MERGEBUFF2 buffers. */
1624
merge_many_buff(Sort_param * param,Sort_buffer sort_buffer,Merge_chunk * buffpek,uint * maxbuffer,IO_CACHE * t_file)1625 int merge_many_buff(Sort_param *param, Sort_buffer sort_buffer,
1626 Merge_chunk *buffpek, uint *maxbuffer, IO_CACHE *t_file)
1627 {
1628 uint i;
1629 IO_CACHE t_file2,*from_file,*to_file,*temp;
1630 Merge_chunk *lastbuff;
1631 DBUG_ENTER("merge_many_buff");
1632
1633 if (*maxbuffer < MERGEBUFF2)
1634 DBUG_RETURN(0); /* purecov: inspected */
1635 if (flush_io_cache(t_file) ||
1636 open_cached_file(&t_file2,mysql_tmpdir,TEMP_PREFIX,DISK_BUFFER_SIZE,
1637 MYF(MY_WME)))
1638 DBUG_RETURN(1); /* purecov: inspected */
1639
1640 from_file= t_file ; to_file= &t_file2;
1641 while (*maxbuffer >= MERGEBUFF2)
1642 {
1643 if (reinit_io_cache(from_file,READ_CACHE,0L,0,0))
1644 goto cleanup;
1645 if (reinit_io_cache(to_file,WRITE_CACHE,0L,0,0))
1646 goto cleanup;
1647 lastbuff=buffpek;
1648 for (i=0 ; i <= *maxbuffer-MERGEBUFF*3/2 ; i+=MERGEBUFF)
1649 {
1650 if (merge_buffers(param,from_file,to_file,sort_buffer, lastbuff++,
1651 buffpek+i,buffpek+i+MERGEBUFF-1,0))
1652 goto cleanup;
1653 }
1654 if (merge_buffers(param,from_file,to_file,sort_buffer, lastbuff++,
1655 buffpek+i,buffpek+ *maxbuffer,0))
1656 break; /* purecov: inspected */
1657 if (flush_io_cache(to_file))
1658 break; /* purecov: inspected */
1659 temp=from_file; from_file=to_file; to_file=temp;
1660 *maxbuffer= (uint) (lastbuff-buffpek)-1;
1661 }
1662 cleanup:
1663 close_cached_file(to_file); // This holds old result
1664 if (to_file == t_file)
1665 {
1666 *t_file=t_file2; // Copy result file
1667 }
1668
1669 DBUG_RETURN(*maxbuffer >= MERGEBUFF2); /* Return 1 if interrupted */
1670 } /* merge_many_buff */
1671
1672
1673 /**
1674 Read data to buffer.
1675
1676 @retval Number of bytes read
1677 (ulong)-1 if something goes wrong
1678 */
1679
read_to_buffer(IO_CACHE * fromfile,Merge_chunk * buffpek,Sort_param * param,bool packed_format)1680 ulong read_to_buffer(IO_CACHE *fromfile, Merge_chunk *buffpek,
1681 Sort_param *param, bool packed_format)
1682 {
1683 ha_rows count;
1684 uint rec_length= param->rec_length;
1685
1686 if ((count= MY_MIN(buffpek->max_keys(),buffpek->rowcount())))
1687 {
1688 size_t bytes_to_read;
1689 if (packed_format)
1690 {
1691 count= buffpek->rowcount();
1692 bytes_to_read= MY_MIN(buffpek->buffer_size(),
1693 static_cast<size_t>(fromfile->end_of_file -
1694 buffpek->file_position()));
1695 }
1696 else
1697 bytes_to_read= rec_length * static_cast<size_t>(count);
1698
1699 if (unlikely(my_b_pread(fromfile, buffpek->buffer_start(),
1700 bytes_to_read, buffpek->file_position())))
1701 return ((ulong) -1);
1702
1703 size_t num_bytes_read;
1704
1705 if (packed_format)
1706 {
1707 /*
1708 The last record read is most likely not complete here.
1709 We need to loop through all the records, reading the length fields,
1710 and then "chop off" the final incomplete record.
1711 */
1712 uchar *record= buffpek->buffer_start();
1713 uint ix= 0;
1714 uint size_of_addon_length= param->using_packed_addons() ?
1715 Addon_fields::size_of_length_field : 0;
1716
1717 uint size_of_sort_length= param->using_packed_sortkeys() ?
1718 Sort_keys::size_of_length_field : 0;
1719
1720 for (; ix < count; ++ix)
1721 {
1722 if (record + size_of_sort_length > buffpek->buffer_end())
1723 break;
1724 uint sort_length= param->using_packed_sortkeys() ?
1725 Sort_keys::read_sortkey_length(record) :
1726 param->sort_length;
1727
1728 DBUG_ASSERT(sort_length <= param->sort_length);
1729
1730 if (record + sort_length + size_of_addon_length >
1731 buffpek->buffer_end())
1732 break; // Incomplete record.
1733
1734 uchar *plen= record + sort_length;
1735 uint res_length= param->get_result_length(plen);
1736 if (plen + res_length > buffpek->buffer_end())
1737 break; // Incomplete record.
1738 DBUG_ASSERT(res_length > 0);
1739 DBUG_ASSERT(sort_length + res_length <= param->rec_length);
1740 record+= sort_length;
1741 record+= res_length;
1742 }
1743 DBUG_ASSERT(ix > 0);
1744 count= ix;
1745 num_bytes_read= record - buffpek->buffer_start();
1746 DBUG_PRINT("info", ("read %llu bytes of complete records",
1747 static_cast<ulonglong>(bytes_to_read)));
1748 }
1749 else
1750 num_bytes_read= bytes_to_read;
1751
1752 buffpek->init_current_key();
1753 buffpek->advance_file_position(num_bytes_read); /* New filepos */
1754 buffpek->decrement_rowcount(count);
1755 buffpek->set_mem_count(count);
1756 return (ulong) num_bytes_read;
1757 }
1758 return 0;
1759 } /* read_to_buffer */
1760
1761
1762 /**
1763 Put all room used by freed buffer to use in adjacent buffer.
1764
1765 Note, that we can't simply distribute memory evenly between all buffers,
1766 because new areas must not overlap with old ones.
1767
1768 @param[in] queue list of non-empty buffers, without freed buffer
1769 @param[in] reuse empty buffer
1770 @param[in] key_length key length
1771 */
1772
reuse_freed_buff(QUEUE * queue,Merge_chunk * reuse,uint key_length)1773 void reuse_freed_buff(QUEUE *queue, Merge_chunk *reuse, uint key_length)
1774 {
1775 for (uint i= queue_first_element(queue);
1776 i <= queue_last_element(queue);
1777 i++)
1778 {
1779 Merge_chunk *bp= (Merge_chunk *) queue_element(queue, i);
1780 if (reuse->merge_freed_buff(bp))
1781 return;
1782 }
1783 DBUG_ASSERT(0);
1784 }
1785
1786
1787 /**
1788 Merge buffers to one buffer.
1789
1790 @param param Sort parameter
1791 @param from_file File with source data (BUFFPEKs point to this file)
1792 @param to_file File to write the sorted result data.
1793 @param sort_buffer Buffer for data to store up to MERGEBUFF2 sort keys.
1794 @param lastbuff OUT Store here BUFFPEK describing data written to to_file
1795 @param Fb First element in source BUFFPEKs array
1796 @param Tb Last element in source BUFFPEKs array
1797 @param flag 0 <=> write {sort_key, addon_fields} pairs as further
1798 sorting will be performed
1799 1 <=> write just addon_fields as this is the final
1800 merge pass
1801
1802 @retval
1803 0 OK
1804 @retval
1805 1 ERROR
1806 */
1807
merge_buffers(Sort_param * param,IO_CACHE * from_file,IO_CACHE * to_file,Sort_buffer sort_buffer,Merge_chunk * lastbuff,Merge_chunk * Fb,Merge_chunk * Tb,int flag)1808 bool merge_buffers(Sort_param *param, IO_CACHE *from_file,
1809 IO_CACHE *to_file, Sort_buffer sort_buffer,
1810 Merge_chunk *lastbuff, Merge_chunk *Fb, Merge_chunk *Tb,
1811 int flag)
1812 {
1813 bool error= 0;
1814 uint rec_length,res_length,offset;
1815 size_t sort_length;
1816 ulong maxcount, bytes_read;
1817 ha_rows max_rows,org_max_rows;
1818 my_off_t to_start_filepos;
1819 uchar *strpos;
1820 Merge_chunk *buffpek;
1821 QUEUE queue;
1822 qsort2_cmp cmp;
1823 void *first_cmp_arg;
1824 element_count dupl_count= 0;
1825 uchar *src;
1826 uchar *unique_buff= param->unique_buff;
1827 const bool killable= !param->not_killable;
1828 THD* const thd=current_thd;
1829 DBUG_ENTER("merge_buffers");
1830
1831 thd->inc_status_sort_merge_passes();
1832 thd->query_plan_fsort_passes++;
1833
1834 rec_length= param->rec_length;
1835 res_length= param->res_length;
1836 sort_length= param->sort_length;
1837 uint dupl_count_ofs= rec_length-sizeof(element_count);
1838 uint min_dupl_count= param->min_dupl_count;
1839 bool check_dupl_count= flag && min_dupl_count;
1840 offset= (rec_length-
1841 (flag && min_dupl_count ? sizeof(dupl_count) : 0)-res_length);
1842 uint wr_len= flag ? res_length : rec_length;
1843 uint wr_offset= flag ? offset : 0;
1844
1845 const bool using_packed_sortkeys= param->using_packed_sortkeys();
1846 bool offset_for_packing= (flag == 1 && using_packed_sortkeys);
1847 const bool packed_format= param->is_packed_format();
1848
1849 maxcount= (ulong) (param->max_keys_per_buffer/((uint) (Tb-Fb) +1));
1850 to_start_filepos= my_b_tell(to_file);
1851 strpos= sort_buffer.array();
1852 org_max_rows=max_rows= param->max_rows;
1853
1854 set_if_bigger(maxcount, 1);
1855
1856 if (unique_buff)
1857 {
1858 cmp= param->compare;
1859 first_cmp_arg= (void *) ¶m->cmp_context;
1860 }
1861 else
1862 {
1863 cmp= param->get_compare_function();
1864 first_cmp_arg= param->get_compare_argument(&sort_length);
1865 }
1866 if (unlikely(init_queue(&queue, (uint) (Tb-Fb)+1,
1867 offsetof(Merge_chunk,m_current_key), 0,
1868 (queue_compare) cmp, first_cmp_arg, 0, 0)))
1869 DBUG_RETURN(1); /* purecov: inspected */
1870 const size_t chunk_sz = (sort_buffer.size()/((uint) (Tb-Fb) +1));
1871 for (buffpek= Fb ; buffpek <= Tb ; buffpek++)
1872 {
1873 buffpek->set_buffer(strpos, strpos + chunk_sz);
1874 buffpek->set_max_keys(maxcount);
1875 bytes_read= read_to_buffer(from_file, buffpek, param, packed_format);
1876 if (unlikely(bytes_read == (ulong) -1))
1877 goto err; /* purecov: inspected */
1878 strpos+= chunk_sz;
1879 // If less data in buffers than expected
1880 buffpek->set_max_keys(buffpek->mem_count());
1881 queue_insert(&queue, (uchar*) buffpek);
1882 }
1883
1884 if (unique_buff)
1885 {
1886 /*
1887 Called by Unique::get()
1888 Copy the first argument to unique_buff for unique removal.
1889 Store it also in 'to_file'.
1890 */
1891 buffpek= (Merge_chunk*) queue_top(&queue);
1892 memcpy(unique_buff, buffpek->current_key(), rec_length);
1893 if (min_dupl_count)
1894 memcpy(&dupl_count, unique_buff+dupl_count_ofs,
1895 sizeof(dupl_count));
1896 buffpek->advance_current_key(rec_length);
1897 buffpek->decrement_mem_count();
1898 if (buffpek->mem_count() == 0)
1899 {
1900 if (unlikely(!(bytes_read= read_to_buffer(from_file, buffpek,
1901 param, packed_format))))
1902 {
1903 (void) queue_remove_top(&queue);
1904 reuse_freed_buff(&queue, buffpek, rec_length);
1905 }
1906 else if (unlikely(bytes_read == (ulong) -1))
1907 goto err; /* purecov: inspected */
1908 }
1909 queue_replace_top(&queue); // Top element has been used
1910 }
1911 else
1912 cmp= 0; // Not unique
1913
1914 while (queue.elements > 1)
1915 {
1916 if (killable && unlikely(thd->check_killed()))
1917 goto err; /* purecov: inspected */
1918
1919 for (;;)
1920 {
1921 buffpek= (Merge_chunk*) queue_top(&queue);
1922 src= buffpek->current_key();
1923 if (cmp) // Remove duplicates
1924 {
1925 uchar *current_key= buffpek->current_key();
1926 if (!(*cmp)(first_cmp_arg, &unique_buff, ¤t_key))
1927 {
1928 if (min_dupl_count)
1929 {
1930 element_count cnt;
1931 memcpy(&cnt, buffpek->current_key() + dupl_count_ofs, sizeof(cnt));
1932 dupl_count+= cnt;
1933 }
1934 goto skip_duplicate;
1935 }
1936 if (min_dupl_count)
1937 {
1938 memcpy(unique_buff+dupl_count_ofs, &dupl_count,
1939 sizeof(dupl_count));
1940 }
1941 src= unique_buff;
1942 }
1943
1944 {
1945 param->get_rec_and_res_len(buffpek->current_key(),
1946 &rec_length, &res_length);
1947 const uint bytes_to_write= (flag == 0) ? rec_length : res_length;
1948
1949 /*
1950 Do not write into the output file if this is the final merge called
1951 for a Unique object used for intersection and dupl_count is less
1952 than min_dupl_count.
1953 If the Unique object is used to intersect N sets of unique elements
1954 then for any element:
1955 dupl_count >= N <=> the element is occurred in each of these N sets.
1956 */
1957 if (!check_dupl_count || dupl_count >= min_dupl_count)
1958 {
1959 if(my_b_write(to_file,
1960 src + (offset_for_packing ?
1961 rec_length - res_length : // sort length
1962 wr_offset),
1963 bytes_to_write))
1964 goto err; /* purecov: inspected */
1965 }
1966 if (cmp)
1967 {
1968 memcpy(unique_buff, buffpek->current_key(), rec_length);
1969 if (min_dupl_count)
1970 memcpy(&dupl_count, unique_buff+dupl_count_ofs,
1971 sizeof(dupl_count));
1972 }
1973 if (!--max_rows)
1974 {
1975 /* Nothing more to do */
1976 goto end; /* purecov: inspected */
1977 }
1978 }
1979 skip_duplicate:
1980 buffpek->advance_current_key(rec_length);
1981 buffpek->decrement_mem_count();
1982
1983 if (buffpek->mem_count() == 0)
1984 {
1985 if (unlikely(!(bytes_read= read_to_buffer(from_file, buffpek,
1986 param, packed_format))))
1987 {
1988 (void) queue_remove_top(&queue);
1989 reuse_freed_buff(&queue, buffpek, rec_length);
1990 break; /* One buffer have been removed */
1991 }
1992 else if (unlikely(bytes_read == (ulong) -1))
1993 goto err; /* purecov: inspected */
1994 }
1995 queue_replace_top(&queue); /* Top element has been replaced */
1996 }
1997 }
1998 buffpek= (Merge_chunk*) queue_top(&queue);
1999 buffpek->set_buffer(sort_buffer.array(),
2000 sort_buffer.array() + sort_buffer.size());
2001 buffpek->set_max_keys(param->max_keys_per_buffer);
2002
2003 /*
2004 As we know all entries in the buffer are unique, we only have to
2005 check if the first one is the same as the last one we wrote
2006 */
2007 if (cmp)
2008 {
2009 uchar *current_key= buffpek->current_key();
2010 if (!(*cmp)(first_cmp_arg, &unique_buff, ¤t_key))
2011 {
2012 if (min_dupl_count)
2013 {
2014 element_count cnt;
2015 memcpy(&cnt, buffpek->current_key() + dupl_count_ofs, sizeof(cnt));
2016 dupl_count+= cnt;
2017 }
2018 buffpek->advance_current_key(rec_length);
2019 buffpek->decrement_mem_count();
2020 }
2021
2022 if (min_dupl_count)
2023 memcpy(unique_buff+dupl_count_ofs, &dupl_count,
2024 sizeof(dupl_count));
2025
2026 if (!check_dupl_count || dupl_count >= min_dupl_count)
2027 {
2028 src= unique_buff;
2029 if (my_b_write(to_file, src+wr_offset, wr_len))
2030 goto err; /* purecov: inspected */
2031 if (!--max_rows)
2032 goto end;
2033 }
2034 }
2035
2036 do
2037 {
2038 if (buffpek->mem_count() > max_rows)
2039 { /* Don't write too many records */
2040 buffpek->set_mem_count(max_rows);
2041 buffpek->set_rowcount(0); /* Don't read more */
2042 }
2043 max_rows-= buffpek->mem_count();
2044 for (uint ix= 0; ix < buffpek->mem_count(); ++ix)
2045 {
2046 uchar *src= buffpek->current_key();
2047 param->get_rec_and_res_len(src,
2048 &rec_length, &res_length);
2049 const uint bytes_to_write= (flag == 0) ? rec_length : res_length;
2050 if (check_dupl_count)
2051 {
2052 memcpy((uchar *) &dupl_count,
2053 buffpek->current_key() + offset + dupl_count_ofs,
2054 sizeof(dupl_count));
2055 if (dupl_count < min_dupl_count)
2056 continue;
2057 }
2058 if(my_b_write(to_file,
2059 src + (offset_for_packing ?
2060 rec_length - res_length : // sort length
2061 wr_offset),
2062 bytes_to_write))
2063 goto err;
2064 buffpek->advance_current_key(rec_length);
2065 }
2066 }
2067 while (likely(!(error=
2068 (bytes_read= read_to_buffer(from_file, buffpek, param,
2069 packed_format)) == (ulong) -1)) &&
2070 bytes_read != 0);
2071
2072 end:
2073 lastbuff->set_rowcount(MY_MIN(org_max_rows-max_rows, param->max_rows));
2074 lastbuff->set_file_position(to_start_filepos);
2075
2076 cleanup:
2077 delete_queue(&queue);
2078 DBUG_RETURN(error);
2079
2080 err:
2081 error= 1;
2082 goto cleanup;
2083
2084 } /* merge_buffers */
2085
2086
2087 /* Do a merge to output-file (save only positions) */
2088
merge_index(Sort_param * param,Sort_buffer sort_buffer,Merge_chunk * buffpek,uint maxbuffer,IO_CACHE * tempfile,IO_CACHE * outfile)2089 int merge_index(Sort_param *param, Sort_buffer sort_buffer,
2090 Merge_chunk *buffpek, uint maxbuffer,
2091 IO_CACHE *tempfile, IO_CACHE *outfile)
2092 {
2093 DBUG_ENTER("merge_index");
2094 if (merge_buffers(param, tempfile, outfile, sort_buffer, buffpek, buffpek,
2095 buffpek + maxbuffer, 1))
2096 DBUG_RETURN(1); /* purecov: inspected */
2097 DBUG_RETURN(0);
2098 } /* merge_index */
2099
2100
suffix_length(ulong string_length)2101 static uint suffix_length(ulong string_length)
2102 {
2103 if (string_length < 256)
2104 return 1;
2105 if (string_length < 256L*256L)
2106 return 2;
2107 if (string_length < 256L*256L*256L)
2108 return 3;
2109 return 4; // Can't sort longer than 4G
2110 }
2111
2112
2113 void
sort_length(THD * thd,const Type_std_attributes * item,SORT_FIELD_ATTR * sortorder) const2114 Type_handler_string_result::sort_length(THD *thd,
2115 const Type_std_attributes *item,
2116 SORT_FIELD_ATTR *sortorder) const
2117 {
2118 CHARSET_INFO *cs;
2119 sortorder->set_length_and_original_length(thd, item->max_length);
2120
2121 if (use_strnxfrm((cs= item->collation.collation)))
2122 {
2123 sortorder->length= (uint) cs->strnxfrmlen(sortorder->length);
2124 }
2125 else if (cs == &my_charset_bin)
2126 {
2127 /* Store length last to be able to sort blob/varbinary */
2128 sortorder->suffix_length= suffix_length(item->max_length);
2129 DBUG_ASSERT(sortorder->length <= UINT_MAX32 - sortorder->suffix_length);
2130 sortorder->length+= sortorder->suffix_length;
2131 if (sortorder->original_length >= UINT_MAX32 - sortorder->suffix_length)
2132 sortorder->original_length= UINT_MAX32;
2133 else
2134 sortorder->original_length+= sortorder->suffix_length;
2135 }
2136 }
2137
2138
2139 void
sort_length(THD * thd,const Type_std_attributes * item,SORT_FIELD_ATTR * sortorder) const2140 Type_handler_temporal_result::sort_length(THD *thd,
2141 const Type_std_attributes *item,
2142 SORT_FIELD_ATTR *sortorder) const
2143 {
2144 sortorder->original_length= sortorder->length= 8; // Sizof intern longlong
2145 }
2146
2147
2148 void
sort_length(THD * thd,const Type_std_attributes * item,SORT_FIELD_ATTR * sortorder) const2149 Type_handler_timestamp_common::sort_length(THD *thd,
2150 const Type_std_attributes *item,
2151 SORT_FIELD_ATTR *sortorder) const
2152 {
2153 sortorder->length= my_timestamp_binary_length(item->decimals);
2154 sortorder->original_length= sortorder->length;
2155 }
2156
2157
2158 void
sort_length(THD * thd,const Type_std_attributes * item,SORT_FIELD_ATTR * sortorder) const2159 Type_handler_int_result::sort_length(THD *thd,
2160 const Type_std_attributes *item,
2161 SORT_FIELD_ATTR *sortorder) const
2162 {
2163 sortorder->original_length= sortorder->length= 8; // Sizof intern longlong
2164 }
2165
2166
2167 void
sort_length(THD * thd,const Type_std_attributes * item,SORT_FIELD_ATTR * sortorder) const2168 Type_handler_real_result::sort_length(THD *thd,
2169 const Type_std_attributes *item,
2170 SORT_FIELD_ATTR *sortorder) const
2171 {
2172 sortorder->original_length= sortorder->length= sizeof(double);
2173 }
2174
2175
2176 void
sort_length(THD * thd,const Type_std_attributes * item,SORT_FIELD_ATTR * sortorder) const2177 Type_handler_decimal_result::sort_length(THD *thd,
2178 const Type_std_attributes *item,
2179 SORT_FIELD_ATTR *sortorder) const
2180 {
2181 sortorder->length=
2182 my_decimal_get_binary_size(item->max_length - (item->decimals ? 1 : 0),
2183 item->decimals);
2184 sortorder->original_length= sortorder->length;
2185 }
2186
2187
2188 /**
2189 Calculate length of sort key.
2190
2191 @param thd Thread handler
2192 @param sortorder Order of items to sort
2193 @param s_length Number of items to sort
2194 @param allow_packing_for_sortkeys [out] set to false if packing sort keys is not
2195 allowed
2196
2197 @note
2198 * sortorder->length and other members are updated for each sort item.
2199 * TODO what is the meaning of this value if some fields are using packing while
2200 others are not?
2201
2202 @return
2203 Total length of sort buffer in bytes
2204 */
2205
2206 static uint
sortlength(THD * thd,Sort_keys * sort_keys,bool * allow_packing_for_sortkeys)2207 sortlength(THD *thd, Sort_keys *sort_keys, bool *allow_packing_for_sortkeys)
2208 {
2209 uint length;
2210 *allow_packing_for_sortkeys= true;
2211 bool allow_packing_for_keys= true;
2212
2213 length=0;
2214 uint nullable_cols=0;
2215
2216 if (sort_keys->is_parameters_computed())
2217 {
2218 *allow_packing_for_sortkeys= sort_keys->using_packed_sortkeys();
2219 return sort_keys->get_sort_length_with_memcmp_values();
2220 }
2221
2222 for (SORT_FIELD *sortorder= sort_keys->begin();
2223 sortorder != sort_keys->end();
2224 sortorder++)
2225 {
2226 sortorder->suffix_length= 0;
2227 sortorder->length_bytes= 0;
2228 if (sortorder->field)
2229 {
2230 Field *field= sortorder->field;
2231 CHARSET_INFO *cs= sortorder->field->sort_charset();
2232 sortorder->type= field->is_packable() ?
2233 SORT_FIELD_ATTR::VARIABLE_SIZE :
2234 SORT_FIELD_ATTR::FIXED_SIZE;
2235 sortorder->set_length_and_original_length(thd, field->sort_length());
2236 sortorder->suffix_length= sortorder->field->sort_suffix_length();
2237 sortorder->cs= cs;
2238
2239 if (use_strnxfrm((cs=sortorder->field->sort_charset())))
2240 sortorder->length= (uint) cs->strnxfrmlen(sortorder->length);
2241
2242 if (sortorder->is_variable_sized() && allow_packing_for_keys)
2243 {
2244 allow_packing_for_keys= sortorder->check_if_packing_possible(thd);
2245 sortorder->length_bytes=
2246 number_storage_requirement(MY_MIN(sortorder->original_length,
2247 thd->variables.max_sort_length));
2248 }
2249
2250 if ((sortorder->maybe_null= sortorder->field->maybe_null()))
2251 nullable_cols++; // Place for NULL marker
2252 }
2253 else
2254 {
2255 sortorder->type= sortorder->item->type_handler()->is_packable() ?
2256 SORT_FIELD_ATTR::VARIABLE_SIZE :
2257 SORT_FIELD_ATTR::FIXED_SIZE;
2258 sortorder->item->type_handler()->sort_length(thd, sortorder->item,
2259 sortorder);
2260 sortorder->cs= sortorder->item->collation.collation;
2261 if (sortorder->is_variable_sized() && allow_packing_for_keys)
2262 {
2263 allow_packing_for_keys= sortorder->check_if_packing_possible(thd);
2264 sortorder->length_bytes=
2265 number_storage_requirement(MY_MIN(sortorder->original_length,
2266 thd->variables.max_sort_length));
2267 }
2268
2269 if ((sortorder->maybe_null= sortorder->item->maybe_null))
2270 nullable_cols++; // Place for NULL marker
2271 }
2272 if (sortorder->is_variable_sized())
2273 {
2274 set_if_smaller(sortorder->length, thd->variables.max_sort_length);
2275 set_if_smaller(sortorder->original_length, thd->variables.max_sort_length);
2276 }
2277 length+=sortorder->length;
2278
2279 sort_keys->increment_size_of_packable_fields(sortorder->length_bytes);
2280 sort_keys->increment_original_sort_length(sortorder->original_length);
2281 }
2282 // add bytes for nullable_cols
2283 sort_keys->increment_original_sort_length(nullable_cols);
2284 *allow_packing_for_sortkeys= allow_packing_for_keys;
2285 sort_keys->set_sort_length_with_memcmp_values(length + nullable_cols);
2286 sort_keys->set_parameters_computed(true);
2287 DBUG_PRINT("info",("sort_length: %d",length));
2288 return length + nullable_cols;
2289 }
2290
2291
2292 /*
2293 Check whether addon fields can be used or not.
2294
2295 @param table Table structure
2296 @param sortlength Length of sort key [strxfrm form]
2297 @param length [OUT] Max length of addon fields
2298 @param fields [OUT] Number of addon fields
2299 @param null_fields [OUT] Number of nullable addon fields
2300 @param packable_length [OUT] Max length of addon fields that can be
2301 packed
2302
2303 @retval
2304 TRUE Addon fields can be used
2305 FALSE Otherwise
2306 */
2307
filesort_use_addons(TABLE * table,uint sortlength,uint * length,uint * fields,uint * null_fields,uint * packable_length)2308 bool filesort_use_addons(TABLE *table, uint sortlength,
2309 uint *length, uint *fields, uint *null_fields,
2310 uint *packable_length)
2311 {
2312 Field **pfield, *field;
2313 *length= *fields= *null_fields= *packable_length= 0;
2314 uint field_length=0;
2315
2316 for (pfield= table->field; (field= *pfield) ; pfield++)
2317 {
2318 if (!bitmap_is_set(table->read_set, field->field_index))
2319 continue;
2320 if (field->flags & BLOB_FLAG)
2321 return false;
2322 field_length= field->max_packed_col_length(field->pack_length());
2323 (*length)+= field_length;
2324
2325 if (field->maybe_null() || field->is_packable())
2326 (*packable_length)+= field_length;
2327
2328 if (field->maybe_null())
2329 (*null_fields)++;
2330 (*fields)++;
2331 }
2332 if (!*fields)
2333 return false;
2334 (*length)+= (*null_fields+7)/8;
2335
2336 /*
2337 sortlength used here is unpacked key length (the strxfrm form). This is
2338 done because unpacked key length is a good upper bound for packed sort
2339 key length.
2340 But for some collations the max packed length may be greater than the
2341 length obtained from the strxfrm form.
2342 Example: for utf8_general_ci, the original string form can be longer than
2343 its mem-comparable form (note that this is rarely achieved in practice).
2344 */
2345 return *length + sortlength <
2346 table->in_use->variables.max_length_for_sort_data;
2347 }
2348
2349 /**
2350 Get descriptors of fields appended to sorted fields and
2351 calculate its total length.
2352
2353 The function first finds out what fields are used in the result set.
2354 Then it calculates the length of the buffer to store the values of
2355 these fields together with the value of sort values.
2356 If the calculated length is not greater than max_length_for_sort_data
2357 the function allocates memory for an array of descriptors containing
2358 layouts for the values of the non-sorted fields in the buffer and
2359 fills them.
2360
2361 @param table Table structure
2362 @param sortlength Total length of sorted fields
2363 @param addon_length [OUT] Length of addon fields
2364 @param m_packable_length [OUT] Length of the addon fields that can be
2365 packed
2366 @note
2367 The null bits for the appended values are supposed to be put together
2368 and stored the buffer just ahead of the value of the first field.
2369
2370 @return
2371 Pointer to the layout descriptors for the appended fields, if any
2372 @retval
2373 NULL if we do not store field values with sort data.
2374 */
2375
2376 static Addon_fields*
get_addon_fields(TABLE * table,uint sortlength,uint * addon_length,uint * m_packable_length)2377 get_addon_fields(TABLE *table, uint sortlength,
2378 uint *addon_length, uint *m_packable_length)
2379 {
2380 Field **pfield;
2381 Field *field;
2382 uint length, fields, null_fields, packable_length;
2383 MY_BITMAP *read_set= table->read_set;
2384 DBUG_ENTER("get_addon_fields");
2385
2386 /*
2387 If there is a reference to a field in the query add it
2388 to the the set of appended fields.
2389 Note for future refinement:
2390 This this a too strong condition.
2391 Actually we need only the fields referred in the
2392 result set. And for some of them it makes sense to use
2393 the values directly from sorted fields.
2394 But beware the case when item->cmp_type() != item->result_type()
2395 */
2396
2397 // see remove_const() for HA_SLOW_RND_POS explanation
2398 if (table->file->ha_table_flags() & HA_SLOW_RND_POS)
2399 sortlength= 0;
2400
2401 void *raw_mem_addon_field, *raw_mem;
2402
2403 if (!filesort_use_addons(table, sortlength, &length, &fields, &null_fields,
2404 &packable_length) ||
2405 !(my_multi_malloc(PSI_INSTRUMENT_ME, MYF(MY_WME | MY_THREAD_SPECIFIC),
2406 &raw_mem, sizeof(Addon_fields),
2407 &raw_mem_addon_field,
2408 sizeof(SORT_ADDON_FIELD) * fields,
2409 NullS)))
2410 DBUG_RETURN(0);
2411
2412 Addon_fields_array
2413 addon_array(static_cast<SORT_ADDON_FIELD*>(raw_mem_addon_field), fields);
2414 Addon_fields *addon_fields= new (raw_mem) Addon_fields(addon_array);
2415
2416 DBUG_ASSERT(addon_fields);
2417
2418 (*addon_length)= length;
2419 (*m_packable_length)= packable_length;
2420
2421 length= (null_fields+7)/8;
2422 null_fields= 0;
2423 SORT_ADDON_FIELD* addonf= addon_fields->begin();
2424 for (pfield= table->field; (field= *pfield) ; pfield++)
2425 {
2426 if (!bitmap_is_set(read_set, field->field_index))
2427 continue;
2428 addonf->field= field;
2429 addonf->offset= length;
2430 if (field->maybe_null())
2431 {
2432 addonf->null_offset= null_fields/8;
2433 addonf->null_bit= 1<<(null_fields & 7);
2434 null_fields++;
2435 }
2436 else
2437 {
2438 addonf->null_offset= 0;
2439 addonf->null_bit= 0;
2440 }
2441 addonf->length= field->max_packed_col_length(field->pack_length());
2442 length+= addonf->length;
2443 addonf++;
2444 }
2445
2446 DBUG_PRINT("info",("addon_length: %d",length));
2447 DBUG_RETURN(addon_fields);
2448 }
2449
2450
2451 /*
2452 ** functions to change a double or float to a sortable string
2453 ** The following should work for IEEE
2454 */
2455
2456 #define DBL_EXP_DIG (sizeof(double)*8-DBL_MANT_DIG)
2457
change_double_for_sort(double nr,uchar * to)2458 void change_double_for_sort(double nr,uchar *to)
2459 {
2460 uchar *tmp=(uchar*) to;
2461 if (nr == 0.0)
2462 { /* Change to zero string */
2463 tmp[0]=(uchar) 128;
2464 memset(tmp+1, 0, sizeof(nr)-1);
2465 }
2466 else
2467 {
2468 #ifdef WORDS_BIGENDIAN
2469 memcpy(tmp, &nr, sizeof(nr));
2470 #else
2471 {
2472 uchar *ptr= (uchar*) &nr;
2473 #if defined(__FLOAT_WORD_ORDER) && (__FLOAT_WORD_ORDER == __BIG_ENDIAN)
2474 tmp[0]= ptr[3]; tmp[1]=ptr[2]; tmp[2]= ptr[1]; tmp[3]=ptr[0];
2475 tmp[4]= ptr[7]; tmp[5]=ptr[6]; tmp[6]= ptr[5]; tmp[7]=ptr[4];
2476 #else
2477 tmp[0]= ptr[7]; tmp[1]=ptr[6]; tmp[2]= ptr[5]; tmp[3]=ptr[4];
2478 tmp[4]= ptr[3]; tmp[5]=ptr[2]; tmp[6]= ptr[1]; tmp[7]=ptr[0];
2479 #endif
2480 }
2481 #endif
2482 if (tmp[0] & 128) /* Negative */
2483 { /* make complement */
2484 uint i;
2485 for (i=0 ; i < sizeof(nr); i++)
2486 tmp[i]=tmp[i] ^ (uchar) 255;
2487 }
2488 else
2489 { /* Set high and move exponent one up */
2490 ushort exp_part=(((ushort) tmp[0] << 8) | (ushort) tmp[1] |
2491 (ushort) 32768);
2492 exp_part+= (ushort) 1 << (16-1-DBL_EXP_DIG);
2493 tmp[0]= (uchar) (exp_part >> 8);
2494 tmp[1]= (uchar) exp_part;
2495 }
2496 }
2497 }
2498
using_packed_addons()2499 bool SORT_INFO::using_packed_addons()
2500 {
2501 return addon_fields != NULL && addon_fields->using_packed_addons();
2502 }
2503
free_addon_buff()2504 void SORT_INFO::free_addon_buff()
2505 {
2506 if (addon_fields)
2507 addon_fields->free_addon_buff();
2508 }
2509
2510 /*
2511 Check if packed sortkeys are used or not
2512 */
using_packed_sortkeys()2513 bool SORT_INFO::using_packed_sortkeys()
2514 {
2515 return sort_keys != NULL && sort_keys->using_packed_sortkeys();
2516 }
2517
2518 /**
2519 Free SORT_INFO
2520 */
2521
~SORT_INFO()2522 SORT_INFO::~SORT_INFO()
2523 {
2524 DBUG_ENTER("~SORT_INFO::SORT_INFO()");
2525 free_data();
2526 DBUG_VOID_RETURN;
2527 }
2528
2529
try_to_pack_sortkeys()2530 void Sort_param::try_to_pack_sortkeys()
2531 {
2532 #ifdef WITHOUT_PACKED_SORT_KEYS
2533 return;
2534 #endif
2535
2536 uint size_of_packable_fields= sort_keys->get_size_of_packable_fields();
2537
2538 /*
2539 Disable packing when all fields are fixed-size fields.
2540 */
2541 if (size_of_packable_fields == 0)
2542 return;
2543
2544 const uint sz= Sort_keys::size_of_length_field;
2545 uint sort_len= sort_keys->get_sort_length_with_original_values();
2546
2547 /*
2548 Heuristic introduced, skip packing sort keys if saving less than 128 bytes
2549 */
2550
2551 if (sort_len < 128 + sz + size_of_packable_fields)
2552 return;
2553
2554 sort_keys->set_using_packed_sortkeys(true);
2555 m_packed_format= true;
2556 m_using_packed_sortkeys= true;
2557 sort_length= sort_len + sz + size_of_packable_fields +
2558 (using_addon_fields() ? 0 : res_length);
2559 /* Only the record length needs to be updated, the res_length does not need
2560 to be updated
2561 */
2562 rec_length= sort_length + addon_length;
2563 }
2564
2565
2566 uint
make_packed_sort_key_part(uchar * to,Item * item,const SORT_FIELD_ATTR * sort_field,Sort_param * param) const2567 Type_handler_string_result::make_packed_sort_key_part(uchar *to, Item *item,
2568 const SORT_FIELD_ATTR *sort_field,
2569 Sort_param *param) const
2570 {
2571 CHARSET_INFO *cs= item->collation.collation;
2572 bool maybe_null= item->maybe_null;
2573
2574 if (maybe_null)
2575 *to++= 1;
2576
2577 Binary_string *res= item->str_result(¶m->tmp_buffer);
2578 if (!res)
2579 {
2580 if (maybe_null)
2581 {
2582 *(to-1)= 0;
2583 return 0;
2584 }
2585 else
2586 {
2587 /* purecov: begin deadcode */
2588 /*
2589 This should only happen during extreme conditions if we run out
2590 of memory or have an item marked not null when it can be null.
2591 This code is here mainly to avoid a hard crash in this case.
2592 */
2593 DBUG_ASSERT(0);
2594 DBUG_PRINT("warning",
2595 ("Got null on something that shouldn't be null"));
2596 memset(to, 0, sort_field->length); // Avoid crash
2597 /* purecov: end */
2598 return sort_field->original_length;
2599 }
2600 }
2601 return sort_field->pack_sort_string(to, res, cs);
2602 }
2603
2604
2605 uint
make_packed_sort_key_part(uchar * to,Item * item,const SORT_FIELD_ATTR * sort_field,Sort_param * param) const2606 Type_handler_int_result::make_packed_sort_key_part(uchar *to, Item *item,
2607 const SORT_FIELD_ATTR *sort_field,
2608 Sort_param *param) const
2609 {
2610 longlong value= item->val_int_result();
2611 return make_packed_sort_key_longlong(to, item->maybe_null,
2612 item->null_value, item->unsigned_flag,
2613 value, sort_field);
2614 }
2615
2616
2617 uint
make_packed_sort_key_part(uchar * to,Item * item,const SORT_FIELD_ATTR * sort_field,Sort_param * param) const2618 Type_handler_decimal_result::make_packed_sort_key_part(uchar *to, Item *item,
2619 const SORT_FIELD_ATTR *sort_field,
2620 Sort_param *param) const
2621 {
2622 my_decimal dec_buf, *dec_val= item->val_decimal_result(&dec_buf);
2623 if (item->maybe_null)
2624 {
2625 if (item->null_value)
2626 {
2627 *to++=0;
2628 return 0;
2629 }
2630 *to++= 1;
2631 }
2632 dec_val->to_binary(to, item->max_length - (item->decimals ? 1 : 0),
2633 item->decimals);
2634 DBUG_ASSERT(sort_field->original_length == sort_field->length);
2635 return sort_field->original_length;
2636 }
2637
2638
2639 uint
make_packed_sort_key_part(uchar * to,Item * item,const SORT_FIELD_ATTR * sort_field,Sort_param * param) const2640 Type_handler_real_result::make_packed_sort_key_part(uchar *to, Item *item,
2641 const SORT_FIELD_ATTR *sort_field,
2642 Sort_param *param) const
2643 {
2644 double value= item->val_result();
2645 if (item->maybe_null)
2646 {
2647 if (item->null_value)
2648 {
2649 *to++=0;
2650 return 0;
2651 }
2652 *to++= 1;
2653 }
2654 change_double_for_sort(value, to);
2655 DBUG_ASSERT(sort_field->original_length == sort_field->length);
2656 return sort_field->original_length;
2657 }
2658
2659
2660 uint
make_packed_sort_key_part(uchar * to,Item * item,const SORT_FIELD_ATTR * sort_field,Sort_param * param) const2661 Type_handler_temporal_result::make_packed_sort_key_part(uchar *to, Item *item,
2662 const SORT_FIELD_ATTR *sort_field,
2663 Sort_param *param) const
2664 {
2665 MYSQL_TIME buf;
2666 // This is a temporal type. No nanoseconds. Rounding mode is not important.
2667 DBUG_ASSERT(item->cmp_type() == TIME_RESULT);
2668 static const Temporal::Options opt(TIME_INVALID_DATES, TIME_FRAC_NONE);
2669 if (item->get_date_result(current_thd, &buf, opt))
2670 {
2671 DBUG_ASSERT(item->maybe_null);
2672 DBUG_ASSERT(item->null_value);
2673 return make_packed_sort_key_longlong(to, item->maybe_null, true,
2674 item->unsigned_flag, 0, sort_field);
2675 }
2676 return make_packed_sort_key_longlong(to, item->maybe_null, false,
2677 item->unsigned_flag, pack_time(&buf),
2678 sort_field);
2679 }
2680
2681
2682 uint
make_packed_sort_key_part(uchar * to,Item * item,const SORT_FIELD_ATTR * sort_field,Sort_param * param) const2683 Type_handler_timestamp_common::make_packed_sort_key_part(uchar *to, Item *item,
2684 const SORT_FIELD_ATTR *sort_field,
2685 Sort_param *param) const
2686 {
2687 THD *thd= current_thd;
2688 uint binlen= my_timestamp_binary_length(item->decimals);
2689 Timestamp_or_zero_datetime_native_null native(thd, item);
2690 if (native.is_null() || native.is_zero_datetime())
2691 {
2692 // NULL or '0000-00-00 00:00:00'
2693 if (item->maybe_null)
2694 {
2695 *to++=0;
2696 return 0;
2697 }
2698 else
2699 {
2700 bzero(to, binlen);
2701 return binlen;
2702 }
2703 }
2704 else
2705 {
2706 if (item->maybe_null)
2707 *to++= 1;
2708 if (native.length() != binlen)
2709 {
2710 /*
2711 Some items can return native representation with a different
2712 number of fractional digits, e.g.: GREATEST(ts_3, ts_4) can
2713 return a value with 3 fractional digits, although its fractional
2714 precision is 4. Re-pack with a proper precision now.
2715 */
2716 Timestamp(native).to_native(&native, item->datetime_precision(thd));
2717 }
2718 DBUG_ASSERT(native.length() == binlen);
2719 memcpy((char *) to, native.ptr(), binlen);
2720 return binlen;
2721 }
2722 }
2723
2724
2725 /*
2726 @brief
2727 Reverse the key for DESC clause
2728 @param to buffer where values are written
2729 @param maybe_null nullability of a column
2730 @param sort_field Sort field structure
2731 @details
2732 used for mem-comparable sort keys
2733 */
2734
reverse_key(uchar * to,const SORT_FIELD_ATTR * sort_field)2735 void reverse_key(uchar *to, const SORT_FIELD_ATTR *sort_field)
2736 {
2737 uint length;
2738 if (sort_field->maybe_null && (to[-1]= !to[-1]))
2739 {
2740 to+= sort_field->length; // don't waste the time reversing all 0's
2741 return;
2742 }
2743 length=sort_field->length;
2744 while (length--)
2745 {
2746 *to = (uchar) (~ *to);
2747 to++;
2748 }
2749 }
2750
2751
2752 /*
2753 @brief
2754 Check if packing sort keys is allowed
2755 @param THD thread structure
2756 @retval
2757 TRUE packing allowed
2758 FALSE packing not allowed
2759 */
check_if_packing_possible(THD * thd) const2760 bool SORT_FIELD_ATTR::check_if_packing_possible(THD *thd) const
2761 {
2762 /*
2763 Packing not allowed when original length is greater than max_sort_length
2764 and we have a complex collation because cutting a prefix is not safe in
2765 such a case
2766 */
2767 if (original_length > thd->variables.max_sort_length &&
2768 cs->state & MY_CS_NON1TO1)
2769 return false;
2770 return true;
2771 }
2772
2773
set_length_and_original_length(THD * thd,uint length_arg)2774 void SORT_FIELD_ATTR::set_length_and_original_length(THD *thd, uint length_arg)
2775 {
2776 length= length_arg;
2777 if (is_variable_sized())
2778 set_if_smaller(length, thd->variables.max_sort_length);
2779 original_length= length_arg;
2780 }
2781
2782
2783 /*
2784 Compare function used for packing sort keys
2785 */
2786
get_packed_keys_compare_ptr()2787 qsort2_cmp get_packed_keys_compare_ptr()
2788 {
2789 return (qsort2_cmp) compare_packed_sort_keys;
2790 }
2791
2792
2793 /*
2794 Compare two varstrings.
2795
2796 The strings are in this data format:
2797
2798 [null_byte] [length of string + suffix_bytes] [the string] [suffix_bytes]
2799
2800 suffix_bytes are used only for binary columns.
2801 */
2802
compare_packed_varstrings(uchar * a,size_t * a_len,uchar * b,size_t * b_len)2803 int SORT_FIELD_ATTR::compare_packed_varstrings(uchar *a, size_t *a_len,
2804 uchar *b, size_t *b_len)
2805 {
2806 int retval;
2807 size_t a_length, b_length;
2808 if (maybe_null)
2809 {
2810 *a_len= *b_len= 1; // NULL bytes are always stored
2811 if (*a != *b)
2812 {
2813 // Note we don't return a proper value in *{a|b}_len for the non-NULL
2814 // value but that's ok
2815 if (*a == 0)
2816 return -1;
2817 else
2818 return 1;
2819 }
2820 else
2821 {
2822 if (*a == 0)
2823 return 0;
2824 }
2825 a++;
2826 b++;
2827 }
2828 else
2829 *a_len= *b_len= 0;
2830
2831 a_length= read_keypart_length(a, length_bytes);
2832 b_length= read_keypart_length(b, length_bytes);
2833
2834 *a_len+= length_bytes + a_length;
2835 *b_len+= length_bytes + b_length;
2836
2837 retval= cs->strnncollsp(a + length_bytes,
2838 a_length - suffix_length,
2839 b + length_bytes,
2840 b_length - suffix_length);
2841
2842 if (!retval && suffix_length)
2843 {
2844 DBUG_ASSERT(cs == &my_charset_bin);
2845 // comparing the length stored in suffix bytes for binary strings
2846 a= a + length_bytes + a_length - suffix_length;
2847 b= b + length_bytes + b_length - suffix_length;
2848 retval= memcmp(a, b, suffix_length);
2849 }
2850
2851 return retval;
2852 }
2853
2854
2855 /*
2856 A value comparison function that has a signature that's suitable for
2857 comparing packed values, but actually compares fixed-size values with memcmp.
2858
2859 This is used for ordering fixed-size columns when the sorting procedure used
2860 packed-value format.
2861 */
2862
compare_packed_fixed_size_vals(uchar * a,size_t * a_len,uchar * b,size_t * b_len)2863 int SORT_FIELD_ATTR::compare_packed_fixed_size_vals(uchar *a, size_t *a_len,
2864 uchar *b, size_t *b_len)
2865 {
2866 if (maybe_null)
2867 {
2868 *a_len=1;
2869 *b_len=1;
2870 if (*a != *b)
2871 {
2872 if (*a == 0)
2873 return -1;
2874 else
2875 return 1;
2876 }
2877 else
2878 {
2879 if (*a == 0)
2880 return 0;
2881 }
2882 a++;
2883 b++;
2884 }
2885 else
2886 *a_len= *b_len= 0;
2887
2888 *a_len+= length;
2889 *b_len+= length;
2890 return memcmp(a,b, length);
2891 }
2892
2893
2894 /*
2895 @brief
2896 Comparison function to compare two packed sort keys
2897
2898 @param sort_param cmp argument
2899 @param a_ptr packed sort key
2900 @param b_ptr packed sort key
2901
2902 @retval
2903 >0 key a_ptr greater than b_ptr
2904 =0 key a_ptr equal to b_ptr
2905 <0 key a_ptr less than b_ptr
2906
2907 */
2908
compare_packed_sort_keys(void * sort_param,unsigned char ** a_ptr,unsigned char ** b_ptr)2909 int compare_packed_sort_keys(void *sort_param,
2910 unsigned char **a_ptr, unsigned char **b_ptr)
2911 {
2912 int retval= 0;
2913 size_t a_len, b_len;
2914 Sort_param *param= (Sort_param*)sort_param;
2915 Sort_keys *sort_keys= param->sort_keys;
2916 uchar *a= *a_ptr;
2917 uchar *b= *b_ptr;
2918
2919 a+= Sort_keys::size_of_length_field;
2920 b+= Sort_keys::size_of_length_field;
2921 for (SORT_FIELD *sort_field= sort_keys->begin();
2922 sort_field != sort_keys->end(); sort_field++)
2923 {
2924 retval= sort_field->is_variable_sized() ?
2925 sort_field->compare_packed_varstrings(a, &a_len, b, &b_len) :
2926 sort_field->compare_packed_fixed_size_vals(a, &a_len, b, &b_len);
2927
2928 if (retval)
2929 return sort_field->reverse ? -retval : retval;
2930
2931 a+= a_len;
2932 b+= b_len;
2933
2934 }
2935 /*
2936 this comparison is done for the case when the sort keys is appended with
2937 the ROW_ID pointer. For such cases we don't have addon fields
2938 so we can make a memcmp check over both the sort keys
2939 */
2940 if (!param->using_addon_fields())
2941 retval= memcmp(a, b, param->res_length);
2942 return retval;
2943 }
2944
2945
2946 /*
2947 @brief
2948 Store a packed string in the buffer
2949
2950 @param to buffer
2951 @param str packed string value
2952 @param cs character set
2953
2954 @details
2955 This function writes to the buffer the packed value of a key_part
2956 of the sort key.
2957
2958 The values written to the buffer are in this order
2959 - value for null byte
2960 - length of the string
2961 - value of the string
2962 - suffix length (for binary character set)
2963 */
2964
2965 uint
pack_sort_string(uchar * to,const Binary_string * str,CHARSET_INFO * cs) const2966 SORT_FIELD_ATTR::pack_sort_string(uchar *to, const Binary_string *str,
2967 CHARSET_INFO *cs) const
2968 {
2969 uchar *orig_to= to;
2970 uint32 length, data_length;
2971 DBUG_ASSERT(str->length() <= UINT32_MAX);
2972 length= (uint32) str->length();
2973
2974 if (length + suffix_length <= original_length)
2975 data_length= length;
2976 else
2977 data_length= original_length - suffix_length;
2978
2979 // length stored in lowendian form
2980 store_key_part_length(data_length + suffix_length, to, length_bytes);
2981 to+= length_bytes;
2982 // copying data length bytes to the buffer
2983 memcpy(to, (uchar*)str->ptr(), data_length);
2984 to+= data_length;
2985
2986 if (cs == &my_charset_bin && suffix_length)
2987 {
2988 // suffix length stored in bigendian form
2989 store_bigendian(length, to, suffix_length);
2990 to+= suffix_length;
2991 }
2992 return static_cast<uint>(to - orig_to);
2993 }
2994
2995
2996 /*
2997 @brief
2998 Create a mem-comparable sort key
2999
3000 @param param sort param structure
3001 @param to buffer where values are written
3002
3003 @retval
3004 length of the bytes written including the NULL bytes
3005 */
3006
make_sortkey(Sort_param * param,uchar * to)3007 static uint make_sortkey(Sort_param *param, uchar *to)
3008 {
3009 Field *field;
3010 SORT_FIELD *sort_field;
3011 uchar *orig_to= to;
3012
3013 for (sort_field=param->local_sortorder.begin() ;
3014 sort_field != param->local_sortorder.end() ;
3015 sort_field++)
3016 {
3017 bool maybe_null=0;
3018 if ((field=sort_field->field))
3019 {
3020 // Field
3021 field->make_sort_key_part(to, sort_field->length);
3022 if ((maybe_null= field->maybe_null()))
3023 to++;
3024 }
3025 else
3026 { // Item
3027 sort_field->item->type_handler()->make_sort_key_part(to,
3028 sort_field->item,
3029 sort_field, param);
3030 if ((maybe_null= sort_field->item->maybe_null))
3031 to++;
3032 }
3033
3034 if (sort_field->reverse)
3035 reverse_key(to, sort_field);
3036 to+= sort_field->length;
3037 }
3038
3039 DBUG_ASSERT(static_cast<uint>(to - orig_to) <= param->sort_length);
3040 return static_cast<uint>(to - orig_to);
3041 }
3042
3043
3044 /*
3045 @brief
3046 create a compact sort key which can be compared with a comparison
3047 function. They are called packed sort keys
3048
3049 @param param sort param structure
3050 @param to buffer where values are written
3051
3052 @retval
3053 length of the bytes written including the NULL bytes
3054 */
3055
make_packed_sortkey(Sort_param * param,uchar * to)3056 static uint make_packed_sortkey(Sort_param *param, uchar *to)
3057 {
3058 Field *field;
3059 SORT_FIELD *sort_field;
3060 uint length;
3061 uchar *orig_to= to;
3062
3063 to+= Sort_keys::size_of_length_field;
3064
3065 for (sort_field=param->local_sortorder.begin() ;
3066 sort_field != param->local_sortorder.end() ;
3067 sort_field++)
3068 {
3069 bool maybe_null=0;
3070 if ((field=sort_field->field))
3071 {
3072 // Field
3073 length= field->make_packed_sort_key_part(to, sort_field);
3074 if ((maybe_null= field->maybe_null()))
3075 to++;
3076 }
3077 else
3078 { // Item
3079 Item *item= sort_field->item;
3080 length= item->type_handler()->make_packed_sort_key_part(to, item,
3081 sort_field,
3082 param);
3083 if ((maybe_null= sort_field->item->maybe_null))
3084 to++;
3085 }
3086 to+= length;
3087 }
3088
3089 length= static_cast<int>(to - orig_to);
3090 DBUG_ASSERT(length <= param->sort_length);
3091 Sort_keys::store_sortkey_length(orig_to, length);
3092 return length;
3093 }
3094