1 /* Copyright (c) 2001, 2021, Oracle and/or its affiliates.
2 Copyright (c) 2018, Percona and/or its affiliates. All rights reserved.
3 Copyright (c) 2010, 2015, MariaDB
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License, version 2.0,
7 as published by the Free Software Foundation.
8
9 This program is also distributed with certain software (including
10 but not limited to OpenSSL) that is licensed under separate terms,
11 as designated in a particular file or component or in included license
12 documentation. The authors of MySQL hereby grant you an additional
13 permission to link the program and your derivative works with the
14 separately licensed software that they have included with MySQL.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License, version 2.0, for more details.
20
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
24
25 /*
26 Function to handle quick removal of duplicates
27 This code is used when doing multi-table deletes to find the rows in
28 reference tables that needs to be deleted.
29
30 The basic idea is as follows:
31
32 Store first all strings in a binary tree, ignoring duplicates.
33 When the tree uses more memory than 'max_heap_table_size',
34 write the tree (in sorted order) out to disk and start with a new tree.
35 When all data has been generated, merge the trees (removing any found
36 duplicates).
37
38 The unique entries will be returned in sort order, to ensure that we do the
39 deletes in disk order.
40 */
41
42 #include "sql_sort.h"
43 #include "my_tree.h" // element_count
44 #include "opt_costmodel.h"
45 #include "uniques.h" // Unique
46 #include "sql_base.h" // TEMP_PREFIX
47 #include "priority_queue.h"
48 #include "malloc_allocator.h"
49
50 #include <algorithm>
51
unique_write_to_file(uchar * key,element_count count,Unique * unique)52 int unique_write_to_file(uchar* key, element_count count, Unique *unique)
53 {
54 /*
55 Use unique->size (size of element stored in the tree) and not
56 unique->tree.size_of_element. The latter is different from unique->size
57 when tree implementation chooses to store pointer to key in TREE_ELEMENT
58 (instead of storing the element itself there)
59 */
60 return my_b_write(&unique->file, key, unique->size) ? 1 : 0;
61 }
62
unique_write_to_ptrs(uchar * key,element_count count,Unique * unique)63 int unique_write_to_ptrs(uchar* key, element_count count, Unique *unique)
64 {
65 memcpy(unique->record_pointers, key, unique->size);
66 unique->record_pointers+=unique->size;
67 return 0;
68 }
69
Unique(qsort_cmp2 comp_func,void * comp_func_fixed_arg,uint size_arg,ulonglong max_in_memory_size_arg)70 Unique::Unique(qsort_cmp2 comp_func, void * comp_func_fixed_arg,
71 uint size_arg, ulonglong max_in_memory_size_arg)
72 :file_ptrs(PSI_INSTRUMENT_ME),
73 max_in_memory_size(max_in_memory_size_arg),
74 record_pointers(NULL),
75 size(size_arg),
76 elements(0)
77 {
78 my_b_clear(&file);
79 init_tree(&tree, (ulong) (max_in_memory_size / 16), 0, size, comp_func, 0,
80 NULL, comp_func_fixed_arg);
81
82 /*
83 If you change the following, change it in get_max_elements function, too.
84 */
85 max_elements= (ulong) (max_in_memory_size /
86 ALIGN_SIZE(sizeof(TREE_ELEMENT)+size));
87 (void) open_cached_file(&file, mysql_tmpdir,TEMP_PREFIX, DISK_BUFFER_SIZE,
88 MYF(MY_WME));
89 }
90
91
92 /**
93 Calculate log2(n!)
94
95 Stirling's approximate formula is used:
96
97 n! ~= sqrt(2*M_PI*n) * (n/M_E)^n
98
99 Derivation of formula used for calculations is as follows:
100
101 log2(n!) = log(n!)/log(2) = log(sqrt(2*M_PI*n)*(n/M_E)^n) / log(2) =
102
103 = (log(2*M_PI*n)/2 + n*log(n/M_E)) / log(2).
104
105 @param n the number to calculate log2(n!) for
106
107 @return log2(n!) for the function argument
108 */
109
log2_n_fact(ulong n)110 static inline double log2_n_fact(ulong n)
111 {
112 /*
113 Stirling's approximation produces a small negative value when n is
114 1 so we handle this as a special case in order to avoid negative
115 numbers in estimates. For n equal to 0, the formula below will
116 produce NaN. Since 0! by definition is 1, we return 0 for this
117 case too.
118 */
119 if (n <= 1)
120 return 0.0;
121
122 return (log(2*M_PI*n)/2 + n*log(n/M_E)) / M_LN2;
123 }
124
125
126 /*
127 Calculate cost of merge_buffers function call for given sequence of
128 input stream lengths and store the number of rows in result stream in *last.
129
130 SYNOPSIS
131 get_merge_buffers_cost()
132 buff_elems Array of #s of elements in buffers
133 elem_size Size of element stored in buffer
134 first Pointer to first merged element size
135 last Pointer to last merged element size
136
137 RETURN
138 Cost of merge_buffers operation in disk seeks.
139
140 NOTES
141 It is assumed that no rows are eliminated during merge.
142 The cost is calculated as
143
144 cost(read_and_write) + cost(merge_comparisons).
145
146 All bytes in the sequences is read and written back during merge so cost
147 of disk io is 2*elem_size*total_buf_elems/IO_SIZE (2 is for read + write)
148
149 For comparisons cost calculations we assume that all merged sequences have
150 the same length, so each of total_buf_size elements will be added to a sort
151 heap with (n_buffers-1) elements. This gives the comparison cost:
152
153 key_compare_cost(total_buf_elems * log2(n_buffers));
154 */
155
get_merge_buffers_cost(Unique::Imerge_cost_buf_type buff_elems,uint elem_size,uint first,uint last,const Cost_model_table * cost_model)156 static double get_merge_buffers_cost(Unique::Imerge_cost_buf_type buff_elems,
157 uint elem_size,
158 uint first, uint last,
159 const Cost_model_table *cost_model)
160 {
161 uint total_buf_elems= 0;
162 for (uint pbuf= first; pbuf <= last; pbuf++)
163 total_buf_elems+= buff_elems[pbuf];
164 buff_elems[last]= total_buf_elems;
165
166 const size_t n_buffers= last - first + 1;
167
168 const double io_ops= static_cast<double>(total_buf_elems * elem_size) /
169 IO_SIZE;
170 const double io_cost= cost_model->io_block_read_cost(io_ops);
171 /* Using log2(n)=log(n)/log(2) formula */
172 const double cpu_cost=
173 cost_model->key_compare_cost(total_buf_elems * log((double) n_buffers) /
174 M_LN2);
175
176 return 2 * io_cost + cpu_cost;
177 }
178
179
180 /*
181 Calculate cost of merging buffers into one in Unique::get, i.e. calculate
182 how long (in terms of disk seeks) the two calls
183 merge_many_buffs(...);
184 merge_buffers(...);
185 will take.
186
187 SYNOPSIS
188 get_merge_many_buffs_cost()
189 buffer buffer space for temporary data, at least
190 Unique::get_cost_calc_buff_size bytes
191 maxbuffer # of full buffers
192 max_n_elems # of elements in first maxbuffer buffers
193 last_n_elems # of elements in last buffer
194 elem_size size of buffer element
195
196 NOTES
197 maxbuffer+1 buffers are merged, where first maxbuffer buffers contain
198 max_n_elems elements each and last buffer contains last_n_elems elements.
199
200 The current implementation does a dumb simulation of merge_many_buffs
201 function actions.
202
203 RETURN
204 Cost of merge in disk seeks.
205 */
206
get_merge_many_buffs_cost(Unique::Imerge_cost_buf_type buffer,uint maxbuffer,uint max_n_elems,uint last_n_elems,int elem_size,const Cost_model_table * cost_model)207 static double get_merge_many_buffs_cost(Unique::Imerge_cost_buf_type buffer,
208 uint maxbuffer, uint max_n_elems,
209 uint last_n_elems, int elem_size,
210 const Cost_model_table *cost_model)
211 {
212 int i;
213 double total_cost= 0.0;
214 Unique::Imerge_cost_buf_type buff_elems=
215 buffer; /* #s of elements in each of merged sequences */
216
217 /*
218 Set initial state: first maxbuffer sequences contain max_n_elems elements
219 each, last sequence contains last_n_elems elements.
220 */
221 for (i = 0; i < (int)maxbuffer; i++)
222 buff_elems[i]= max_n_elems;
223 buff_elems[maxbuffer]= last_n_elems;
224
225 /*
226 Do it exactly as merge_many_buff function does, calling
227 get_merge_buffers_cost to get cost of merge_buffers.
228 */
229 if (maxbuffer >= MERGEBUFF2)
230 {
231 while (maxbuffer >= MERGEBUFF2)
232 {
233 uint lastbuff= 0;
234 for (i = 0; i <= (int) maxbuffer - MERGEBUFF*3/2; i += MERGEBUFF)
235 {
236 total_cost+=get_merge_buffers_cost(buff_elems, elem_size,
237 i,
238 i + MERGEBUFF-1,
239 cost_model);
240 lastbuff++;
241 }
242 total_cost+=get_merge_buffers_cost(buff_elems, elem_size,
243 i,
244 maxbuffer,
245 cost_model);
246 maxbuffer= lastbuff;
247 }
248 }
249
250 /* Simulate final merge_buff call. */
251 total_cost += get_merge_buffers_cost(buff_elems, elem_size,
252 0, maxbuffer, cost_model);
253 return total_cost;
254 }
255
256
257 /*
258 Calculate cost of using Unique for processing nkeys elements of size
259 key_size using max_in_memory_size memory.
260
261 SYNOPSIS
262 Unique::get_use_cost()
263 buffer space for temporary data, use Unique::get_cost_calc_buff_size
264 to get # bytes needed.
265 nkeys #of elements in Unique
266 key_size size of each elements in bytes
267 max_in_memory_size amount of memory Unique will be allowed to use
268
269 RETURN
270 Cost in disk seeks.
271
272 NOTES
273 cost(using_unqiue) =
274 cost(create_trees) + (see #1)
275 cost(merge) + (see #2)
276 cost(read_result) (see #3)
277
278 1. Cost of trees creation
279 For each Unique::put operation there will be 2*log2(n+1) elements
280 comparisons, where n runs from 1 tree_size (we assume that all added
281 elements are different). Together this gives:
282
283 n_compares = 2*(log2(2) + log2(3) + ... + log2(N+1)) = 2*log2((N+1)!)
284
285 then cost(tree_creation) = key_compare_cost(n_compares);
286
287 Total cost of creating trees:
288 (n_trees - 1)*max_size_tree_cost + non_max_size_tree_cost.
289
290 Approximate value of log2(N!) is calculated by log2_n_fact function.
291
292 2. Cost of merging.
293 If only one tree is created by Unique no merging will be necessary.
294 Otherwise, we model execution of merge_many_buff function and count
295 #of merges. (The reason behind this is that number of buffers is small,
296 while size of buffers is big and we don't want to loose precision with
297 O(x)-style formula)
298
299 3. If only one tree is created by Unique no disk io will happen.
300 Otherwise, ceil(key_len*n_keys) disk seeks are necessary. We assume
301 these will be random seeks.
302 */
303
get_use_cost(Imerge_cost_buf_type buffer,uint nkeys,uint key_size,ulonglong max_in_memory_size,const Cost_model_table * cost_model)304 double Unique::get_use_cost(Imerge_cost_buf_type buffer,
305 uint nkeys, uint key_size,
306 ulonglong max_in_memory_size,
307 const Cost_model_table *cost_model)
308 {
309 ulong max_elements_in_tree;
310 ulong last_tree_elems;
311 int n_full_trees; /* number of trees in unique - 1 */
312
313 max_elements_in_tree= ((ulong) max_in_memory_size /
314 ALIGN_SIZE(sizeof(TREE_ELEMENT)+key_size));
315
316 n_full_trees= nkeys / max_elements_in_tree;
317 last_tree_elems= nkeys % max_elements_in_tree;
318
319 /* Calculate cost of creating trees */
320 double n_compares= 2 * log2_n_fact(last_tree_elems + 1);
321 if (n_full_trees)
322 n_compares+= n_full_trees * log2_n_fact(max_elements_in_tree + 1);
323 double result= cost_model->key_compare_cost(n_compares);
324
325 DBUG_PRINT("info",("unique trees sizes: %u=%u*%lu + %lu", nkeys,
326 n_full_trees, n_full_trees?max_elements_in_tree:0,
327 last_tree_elems));
328
329 if (!n_full_trees)
330 return result;
331
332 /*
333 There is more then one tree and merging is necessary.
334 First, add cost of writing all trees to disk, assuming that all disk
335 writes are sequential.
336 */
337 result+= cost_model->disk_seek_base_cost() * n_full_trees *
338 ceil(((double) key_size) * max_elements_in_tree / IO_SIZE);
339 result+= cost_model->disk_seek_base_cost() *
340 ceil(((double) key_size) * last_tree_elems / IO_SIZE);
341
342 /* Cost of merge */
343 double merge_cost= get_merge_many_buffs_cost(buffer, n_full_trees,
344 max_elements_in_tree,
345 last_tree_elems, key_size,
346 cost_model);
347 if (merge_cost < 0.0)
348 return merge_cost;
349
350 result += merge_cost;
351 /*
352 Add cost of reading the resulting sequence, assuming there were no
353 duplicate elements.
354 */
355 const double n_blocks= ceil((double)key_size * nkeys / IO_SIZE);
356 result += cost_model->io_block_read_cost(n_blocks);
357
358 return result;
359 }
360
~Unique()361 Unique::~Unique()
362 {
363 close_cached_file(&file);
364 delete_tree(&tree);
365 }
366
367
368 /* Write tree to disk; clear tree */
flush()369 bool Unique::flush()
370 {
371 Merge_chunk file_ptr;
372 elements+= tree.elements_in_tree;
373 file_ptr.set_rowcount(tree.elements_in_tree);
374 file_ptr.set_file_position(my_b_tell(&file));
375
376 if (tree_walk(&tree, (tree_walk_action) unique_write_to_file,
377 (void*) this, left_root_right) ||
378 file_ptrs.push_back(file_ptr))
379 return 1;
380 delete_tree(&tree);
381 return 0;
382 }
383
384
385 /*
386 Clear the tree and the file.
387 You must call reset() if you want to reuse Unique after walk().
388 */
389
390 void
reset()391 Unique::reset()
392 {
393 reset_tree(&tree);
394 /*
395 If elements != 0, some trees were stored in the file (see how
396 flush() works). Note, that we can not count on my_b_tell(&file) == 0
397 here, because it can return 0 right after walk(), and walk() does not
398 reset any Unique member.
399 */
400 if (elements)
401 {
402 file_ptrs.clear();
403 MY_ATTRIBUTE((unused)) int reinit_res=
404 reinit_io_cache(&file, WRITE_CACHE, 0L, 0, 1);
405 assert(reinit_res == 0);
406 }
407 elements= 0;
408 }
409
410 /*
411 The comparison function, used by the Priority_queue in merge_buffers()
412 When the called from Uniques::get() must use comparison function of
413 Uniques::tree, but compare members of struct Merge_chunk.
414 */
415
merge_chunk_compare(Merge_chunk_compare_context * ctx,uchar * key_ptr1,uchar * key_ptr2)416 static int merge_chunk_compare(Merge_chunk_compare_context *ctx,
417 uchar *key_ptr1, uchar *key_ptr2)
418 {
419 return ctx->key_compare(ctx->key_compare_arg, key_ptr1, key_ptr2);
420 }
421
422 namespace {
423
424 struct Merge_chunk_less
425 {
Merge_chunk_less__anonb39c07150111::Merge_chunk_less426 Merge_chunk_less(const Merge_chunk_compare_context context)
427 : m_context(context)
428 {}
operator ()__anonb39c07150111::Merge_chunk_less429 bool operator()(Merge_chunk *a, Merge_chunk *b)
430 {
431 return m_context.key_compare(m_context.key_compare_arg,
432 a->current_key(), b->current_key()) > 0;
433 }
434 Merge_chunk_compare_context m_context;
435 };
436
437 } // namespace
438
439 /*
440 DESCRIPTION
441
442 Function is very similar to merge_buffers, but instead of writing sorted
443 unique keys to the output file, it invokes walk_action for each key.
444 This saves I/O if you need to pass through all unique keys only once.
445
446 SYNOPSIS
447 merge_walk()
448 All params are 'IN' (but see comment for begin, end):
449 merge_buffer buffer to perform cached piece-by-piece loading
450 of trees; initially the buffer is empty
451 merge_buffer_size size of merge_buffer. Must be aligned with
452 key_length
453 key_length size of tree element; key_length * (end - begin)
454 must be less or equal than merge_buffer_size.
455 begin pointer to Merge_chunk struct for the first tree.
456 end pointer to Merge_chunk struct for the last tree;
457 end > begin and [begin, end) form a consecutive
458 range. Merge_chunks structs in that range are used and
459 overwritten in merge_walk().
460 walk_action element visitor. Action is called for each unique
461 key.
462 walk_action_arg argument to walk action. Passed to it on each call.
463 compare elements comparison function
464 compare_arg comparison function argument
465 file file with all trees dumped. Trees in the file
466 must contain sorted unique values. Cache must be
467 initialized in read mode.
468 RETURN VALUE
469 0 ok
470 <> 0 error
471 */
472
merge_walk(uchar * merge_buffer,size_t merge_buffer_size,size_t key_length,Merge_chunk * begin,Merge_chunk * end,tree_walk_action walk_action,void * walk_action_arg,qsort_cmp2 compare,const void * compare_arg,IO_CACHE * file)473 static bool merge_walk(uchar *merge_buffer, size_t merge_buffer_size,
474 size_t key_length, Merge_chunk *begin, Merge_chunk *end,
475 tree_walk_action walk_action, void *walk_action_arg,
476 qsort_cmp2 compare, const void *compare_arg,
477 IO_CACHE *file)
478 {
479 if (end <= begin ||
480 merge_buffer_size < (ulong) (key_length * (end - begin + 1)))
481 return 1;
482
483 Merge_chunk_compare_context compare_context = { compare, compare_arg };
484 Priority_queue<Merge_chunk*,
485 std::vector<Merge_chunk*, Malloc_allocator<Merge_chunk*> >,
486 Merge_chunk_less>
487 queue((Merge_chunk_less(compare_context)),
488 (Malloc_allocator<Merge_chunk*>(key_memory_Unique_merge_buffer)));
489 if (queue.reserve(end - begin))
490 return 1;
491
492 /* we need space for one key when a piece of merge buffer is re-read */
493 merge_buffer_size-= key_length;
494 uchar *save_key_buff= merge_buffer + merge_buffer_size;
495 uint max_key_count_per_piece= (uint) (merge_buffer_size/(end-begin) /
496 key_length);
497 /* if piece_size is aligned reuse_freed_buffer will always hit */
498 size_t piece_size= max_key_count_per_piece * key_length;
499 uint bytes_read; /* to hold return value of read_to_buffer */
500 Merge_chunk *top;
501 int res= 1;
502
503 // read_to_buffer() needs only rec_length.
504 Sort_param sort_param;
505 sort_param.rec_length= key_length;
506 assert(!sort_param.using_addon_fields());
507
508 /*
509 Invariant: queue must contain top element from each tree, until a tree
510 is not completely walked through.
511 Here we're forcing the invariant, inserting one element from each tree
512 to the queue.
513 */
514 for (top= begin; top != end; ++top)
515 {
516 top->set_buffer_start(merge_buffer + (top - begin) * piece_size);
517 top->set_buffer_end(top->buffer_start() + piece_size);
518 top->set_max_keys(max_key_count_per_piece);
519 bytes_read= read_to_buffer(file, top, &sort_param);
520 if (bytes_read == (uint) (-1))
521 goto end;
522 assert(bytes_read);
523 queue.push(top);
524 }
525 top= queue.top();
526 while (queue.size() > 1)
527 {
528 /*
529 Every iteration one element is removed from the queue, and one is
530 inserted by the rules of the invariant. If two adjacent elements on
531 the top of the queue are not equal, biggest one is unique, because all
532 elements in each tree are unique. Action is applied only to unique
533 elements.
534 */
535 void *old_key= top->current_key();
536 /*
537 read next key from the cache or from the file and push it to the
538 queue; this gives new top.
539 */
540 top->advance_current_key(key_length);
541 top->decrement_mem_count();
542 if (top->mem_count())
543 queue.update_top();
544 else /* next piece should be read */
545 {
546 /* save old_key not to overwrite it in read_to_buffer */
547 memcpy(save_key_buff, old_key, key_length);
548 old_key= save_key_buff;
549 bytes_read= read_to_buffer(file, top, &sort_param);
550 if (bytes_read == (uint) (-1))
551 goto end;
552 else if (bytes_read > 0) /* top->key, top->mem_count are reset */
553 queue.update_top(); /* in read_to_buffer */
554 else
555 {
556 /*
557 Tree for old 'top' element is empty: remove it from the queue and
558 give all its memory to the nearest tree.
559 */
560 queue.pop();
561 reuse_freed_buff(top, &queue);
562 }
563 }
564 top= queue.top();
565 /* new top has been obtained; if old top is unique, apply the action */
566 if (compare(compare_arg, old_key, top->current_key()))
567 {
568 if (walk_action(old_key, 1, walk_action_arg))
569 goto end;
570 }
571 }
572 /*
573 Applying walk_action to the tail of the last tree: this is safe because
574 either we had only one tree in the beginning, either we work with the
575 last tree in the queue.
576 */
577 do
578 {
579 do
580 {
581 if (walk_action(top->current_key(), 1, walk_action_arg))
582 goto end;
583 top->advance_current_key(key_length);
584 }
585 while (top->decrement_mem_count());
586 bytes_read= read_to_buffer(file, top, &sort_param);
587 if (bytes_read == (uint) (-1))
588 goto end;
589 }
590 while (bytes_read);
591 res= 0;
592 end:
593 return res;
594 }
595
596
597 /*
598 DESCRIPTION
599 Walks consecutively through all unique elements:
600 if all elements are in memory, then it simply invokes 'tree_walk', else
601 all flushed trees are loaded to memory piece-by-piece, pieces are
602 sorted, and action is called for each unique value.
603 Note: so as merging resets file_ptrs state, this method can change
604 internal Unique state to undefined: if you want to reuse Unique after
605 walk() you must call reset() first!
606 SYNOPSIS
607 Unique:walk()
608 All params are 'IN':
609 action function-visitor, typed in include/my_tree.h
610 function is called for each unique element
611 arg argument for visitor, which is passed to it on each call
612 RETURN VALUE
613 0 OK
614 <> 0 error
615 */
616
walk(tree_walk_action action,void * walk_action_arg)617 bool Unique::walk(tree_walk_action action, void *walk_action_arg)
618 {
619 int res;
620 uchar *merge_buffer;
621
622 if (elements == 0) /* the whole tree is in memory */
623 return tree_walk(&tree, action, walk_action_arg, left_root_right);
624
625 /* flush current tree to the file to have some memory for merge buffer */
626 if (flush())
627 return 1;
628 if (flush_io_cache(&file) || reinit_io_cache(&file, READ_CACHE, 0L, 0, 0))
629 return 1;
630
631 /*
632 Compute the size of the merge buffer used by merge_walk(). This buffer
633 must at least be able to store one element from each file pointer plus
634 one extra.
635 */
636 const size_t min_merge_buffer_size= (file_ptrs.size() + 1) * size;
637 const size_t merge_buffer_size=
638 std::max(min_merge_buffer_size, static_cast<size_t>(max_in_memory_size));
639
640 if (!(merge_buffer= (uchar *) my_malloc(key_memory_Unique_merge_buffer,
641 merge_buffer_size, MYF(0))))
642 return 1;
643 res= merge_walk(merge_buffer, merge_buffer_size, size,
644 file_ptrs.begin(), file_ptrs.end(),
645 action, walk_action_arg,
646 tree.compare, tree.custom_arg, &file);
647 my_free(merge_buffer);
648 return res;
649 }
650
651 /*
652 Modify the TABLE element so that when one calls init_records()
653 the rows will be read in priority order.
654 */
655
get(TABLE * table)656 bool Unique::get(TABLE *table)
657 {
658 table->sort.found_records=elements+tree.elements_in_tree;
659
660 if (my_b_tell(&file) == 0)
661 {
662 /* Whole tree is in memory; Don't use disk if you don't need to */
663 assert(table->sort.sorted_result == NULL);
664 if ((record_pointers= table->sort.sorted_result= (uchar*)
665 my_malloc(key_memory_Filesort_info_record_pointers,
666 size * tree.elements_in_tree, MYF(0))))
667 {
668 (void) tree_walk(&tree, (tree_walk_action) unique_write_to_ptrs,
669 this, left_root_right);
670 return 0;
671 }
672 }
673 /* Not enough memory; Save the result to file && free memory used by tree */
674 if (flush())
675 return 1;
676
677 IO_CACHE *outfile=table->sort.io_cache;
678 Merge_chunk *file_ptr= file_ptrs.begin();
679 size_t num_chunks= file_ptrs.size();
680 uchar *sort_memory;
681 my_off_t save_pos;
682 bool error=1;
683
684 /*
685 Open cached file if it isn't open. Reuse the existing io_cache if it is
686 already present.
687 */
688 if (!table->sort.io_cache)
689 outfile=table->sort.io_cache=(IO_CACHE*) my_malloc(key_memory_TABLE_sort_io_cache,
690 sizeof(IO_CACHE),
691 MYF(MY_ZEROFILL));
692
693 if (!outfile || (! my_b_inited(outfile) &&
694 open_cached_file(outfile,mysql_tmpdir,TEMP_PREFIX,READ_RECORD_BUFFER,
695 MYF(MY_WME))))
696 return 1;
697 if (reinit_io_cache(outfile, WRITE_CACHE, 0L, 0, 0) != 0)
698 return 1;
699
700 Sort_param sort_param;
701 sort_param.max_rows= elements;
702 sort_param.sort_form=table;
703 sort_param.rec_length= sort_param.sort_length= sort_param.ref_length= size;
704 sort_param.max_keys_per_buffer=
705 (uint) (max_in_memory_size / sort_param.sort_length);
706 sort_param.not_killable=1;
707
708 const size_t num_bytes=
709 (sort_param.max_keys_per_buffer + 1) * sort_param.sort_length;
710 if (!(sort_memory=(uchar*) my_malloc(key_memory_Unique_sort_buffer,
711 num_bytes, MYF(0))))
712 return 1;
713 sort_param.unique_buff= sort_memory+(sort_param.max_keys_per_buffer *
714 sort_param.sort_length);
715
716 sort_param.compare= merge_chunk_compare;
717 sort_param.cmp_context.key_compare= tree.compare;
718 sort_param.cmp_context.key_compare_arg= tree.custom_arg;
719
720 /* Merge the buffers to one file, removing duplicates */
721 if (merge_many_buff(&sort_param, Sort_buffer(sort_memory, num_bytes),
722 Merge_chunk_array(file_ptrs.begin(), file_ptrs.size()),
723 &num_chunks, &file))
724 goto err;
725 if (flush_io_cache(&file) ||
726 reinit_io_cache(&file,READ_CACHE,0L,0,0))
727 goto err;
728 if (merge_buffers(&sort_param, &file, outfile,
729 Sort_buffer(sort_memory, num_bytes),
730 file_ptr,
731 Merge_chunk_array(file_ptr, num_chunks), 0))
732 goto err;
733 error=0;
734 err:
735 my_free(sort_memory);
736 if (flush_io_cache(outfile))
737 error=1;
738
739 /* Setup io_cache for reading */
740 save_pos=outfile->pos_in_file;
741 if (reinit_io_cache(outfile,READ_CACHE,0L,0,0))
742 error=1;
743 outfile->end_of_file=save_pos;
744 return error;
745 }
746