← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to server/uniques.cc

  • Committer: Monty Taylor
  • Date: 2008-07-15 21:40:58 UTC
  • mfrom: (77.1.113 codestyle32)
  • mto: This revision was merged to the branch mainline in revision 176.
  • Revision ID: mordred@camelot-20080715214058-rm3phulldos9xehv
Merged from codestyle.

Show diffs side-by-side

added added

removed removed

Lines of Context:
server/uniques.cc
11
11
 
12
12
   You should have received a copy of the GNU General Public License
13
13
   along with this program; if not, write to the Free Software
14
 
   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA */
 
14
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
15
15
 
16
16
/*
17
17
  Function to handle quick removal of duplicates
21
21
  The basic idea is as follows:
22
22
 
23
23
  Store first all strings in a binary tree, ignoring duplicates.
 
24
  When the tree uses more memory than 'max_heap_table_size',
 
25
  write the tree (in sorted order) out to disk and start with a new tree.
 
26
  When all data has been generated, merge the trees (removing any found
 
27
  duplicates).
24
28
 
25
29
  The unique entries will be returned in sort order, to ensure that we do the
26
30
  deletes in disk order.
27
31
*/
28
32
 
29
 
#include <config.h>
30
 
 
31
 
#include <math.h>
32
 
 
33
 
#include <queue>
34
 
 
35
 
#include <drizzled/sql_sort.h>
36
 
#include <drizzled/session.h>
37
 
#include <drizzled/sql_list.h>
38
 
#include <drizzled/internal/iocache.h>
39
 
#include <drizzled/unique.h>
40
 
 
41
 
#if defined(CMATH_NAMESPACE)
42
 
using namespace CMATH_NAMESPACE;
43
 
#endif
44
 
 
45
 
using namespace std;
46
 
 
47
 
namespace drizzled
 
33
#include "mysql_priv.h"
 
34
#include "sql_sort.h"
 
35
 
 
36
 
 
37
int unique_write_to_file(uchar* key,
 
38
                         element_count count __attribute__((__unused__)),
 
39
                         Unique *unique)
48
40
{
 
41
  /*
 
42
    Use unique->size (size of element stored in the tree) and not
 
43
    unique->tree.size_of_element. The latter is different from unique->size
 
44
    when tree implementation chooses to store pointer to key in TREE_ELEMENT
 
45
    (instead of storing the element itself there)
 
46
  */
 
47
  return my_b_write(&unique->file, key, unique->size) ? 1 : 0;
 
48
}
49
49
 
50
 
int unique_write_to_ptrs(unsigned char* key,
51
 
                         uint32_t, Unique *unique)
 
50
int unique_write_to_ptrs(uchar* key,
 
51
                         element_count count __attribute__((__unused__)),
 
52
                         Unique *unique)
52
53
{
53
54
  memcpy(unique->record_pointers, key, unique->size);
54
55
  unique->record_pointers+=unique->size;
56
57
}
57
58
 
58
59
Unique::Unique(qsort_cmp2 comp_func, void * comp_func_fixed_arg,
59
 
               uint32_t size_arg, size_t max_in_memory_size_arg)
60
 
  : max_in_memory_size(max_in_memory_size_arg),
61
 
    size(size_arg),
62
 
    elements(0)
 
60
               uint size_arg, uint64_t max_in_memory_size_arg)
 
61
  :max_in_memory_size(max_in_memory_size_arg), size(size_arg), elements(0)
63
62
{
64
 
  // Second element is max size for memory use in unique sort
65
 
  init_tree(&tree, 0, 0, size, comp_func, false,
 
63
  my_b_clear(&file);
 
64
  init_tree(&tree, (ulong) (max_in_memory_size / 16), 0, size, comp_func, 0,
66
65
            NULL, comp_func_fixed_arg);
 
66
  /* If the following fail's the next add will also fail */
 
67
  my_init_dynamic_array(&file_ptrs, sizeof(BUFFPEK), 16, 16);
 
68
  /*
 
69
    If you change the following, change it in get_max_elements function, too.
 
70
  */
 
71
  max_elements= (ulong) (max_in_memory_size /
 
72
                         ALIGN_SIZE(sizeof(TREE_ELEMENT)+size));
 
73
  VOID(open_cached_file(&file, mysql_tmpdir,TEMP_PREFIX, DISK_BUFFER_SIZE,
 
74
                   MYF(MY_WME)));
67
75
}
68
76
 
69
77
 
89
97
 
90
98
 
91
99
/*
 
100
  Calculate cost of merge_buffers function call for given sequence of
 
101
  input stream lengths and store the number of rows in result stream in *last.
 
102
 
 
103
  SYNOPSIS
 
104
    get_merge_buffers_cost()
 
105
      buff_elems  Array of #s of elements in buffers
 
106
      elem_size   Size of element stored in buffer
 
107
      first       Pointer to first merged element size
 
108
      last        Pointer to last merged element size
 
109
 
 
110
  RETURN
 
111
    Cost of merge_buffers operation in disk seeks.
 
112
 
 
113
  NOTES
 
114
    It is assumed that no rows are eliminated during merge.
 
115
    The cost is calculated as
 
116
 
 
117
      cost(read_and_write) + cost(merge_comparisons).
 
118
 
 
119
    All bytes in the sequences is read and written back during merge so cost
 
120
    of disk io is 2*elem_size*total_buf_elems/IO_SIZE (2 is for read + write)
 
121
 
 
122
    For comparisons cost calculations we assume that all merged sequences have
 
123
    the same length, so each of total_buf_size elements will be added to a sort
 
124
    heap with (n_buffers-1) elements. This gives the comparison cost:
 
125
 
 
126
      total_buf_elems* log2(n_buffers) / TIME_FOR_COMPARE_ROWID;
 
127
*/
 
128
 
 
129
static double get_merge_buffers_cost(uint *buff_elems __attribute__((__unused__)),
 
130
                                     uint elem_size,
 
131
                                     uint *first, uint *last)
 
132
{
 
133
  uint total_buf_elems= 0;
 
134
  for (uint *pbuf= first; pbuf <= last; pbuf++)
 
135
    total_buf_elems+= *pbuf;
 
136
  *last= total_buf_elems;
 
137
 
 
138
  int n_buffers= last - first + 1;
 
139
 
 
140
  /* Using log2(n)=log(n)/log(2) formula */
 
141
  return 2*((double)total_buf_elems*elem_size) / IO_SIZE +
 
142
     total_buf_elems*log((double) n_buffers) / (TIME_FOR_COMPARE_ROWID * M_LN2);
 
143
}
 
144
 
 
145
 
 
146
/*
 
147
  Calculate cost of merging buffers into one in Unique::get, i.e. calculate
 
148
  how long (in terms of disk seeks) the two calls
 
149
    merge_many_buffs(...);
 
150
    merge_buffers(...);
 
151
  will take.
 
152
 
 
153
  SYNOPSIS
 
154
    get_merge_many_buffs_cost()
 
155
      buffer        buffer space for temporary data, at least
 
156
                    Unique::get_cost_calc_buff_size bytes
 
157
      maxbuffer     # of full buffers
 
158
      max_n_elems   # of elements in first maxbuffer buffers
 
159
      last_n_elems  # of elements in last buffer
 
160
      elem_size     size of buffer element
 
161
 
 
162
  NOTES
 
163
    maxbuffer+1 buffers are merged, where first maxbuffer buffers contain
 
164
    max_n_elems elements each and last buffer contains last_n_elems elements.
 
165
 
 
166
    The current implementation does a dumb simulation of merge_many_buffs
 
167
    function actions.
 
168
 
 
169
  RETURN
 
170
    Cost of merge in disk seeks.
 
171
*/
 
172
 
 
173
static double get_merge_many_buffs_cost(uint *buffer,
 
174
                                        uint maxbuffer, uint max_n_elems,
 
175
                                        uint last_n_elems, int elem_size)
 
176
{
 
177
  register int i;
 
178
  double total_cost= 0.0;
 
179
  uint *buff_elems= buffer; /* #s of elements in each of merged sequences */
 
180
 
 
181
  /*
 
182
    Set initial state: first maxbuffer sequences contain max_n_elems elements
 
183
    each, last sequence contains last_n_elems elements.
 
184
  */
 
185
  for (i = 0; i < (int)maxbuffer; i++)
 
186
    buff_elems[i]= max_n_elems;
 
187
  buff_elems[maxbuffer]= last_n_elems;
 
188
 
 
189
  /*
 
190
    Do it exactly as merge_many_buff function does, calling
 
191
    get_merge_buffers_cost to get cost of merge_buffers.
 
192
  */
 
193
  if (maxbuffer >= MERGEBUFF2)
 
194
  {
 
195
    while (maxbuffer >= MERGEBUFF2)
 
196
    {
 
197
      uint lastbuff= 0;
 
198
      for (i = 0; i <= (int) maxbuffer - MERGEBUFF*3/2; i += MERGEBUFF)
 
199
      {
 
200
        total_cost+=get_merge_buffers_cost(buff_elems, elem_size,
 
201
                                           buff_elems + i,
 
202
                                           buff_elems + i + MERGEBUFF-1);
 
203
        lastbuff++;
 
204
      }
 
205
      total_cost+=get_merge_buffers_cost(buff_elems, elem_size,
 
206
                                         buff_elems + i,
 
207
                                         buff_elems + maxbuffer);
 
208
      maxbuffer= lastbuff;
 
209
    }
 
210
  }
 
211
 
 
212
  /* Simulate final merge_buff call. */
 
213
  total_cost += get_merge_buffers_cost(buff_elems, elem_size,
 
214
                                       buff_elems, buff_elems + maxbuffer);
 
215
  return total_cost;
 
216
}
 
217
 
 
218
 
 
219
/*
92
220
  Calculate cost of using Unique for processing nkeys elements of size
93
221
  key_size using max_in_memory_size memory.
94
222
 
123
251
 
124
252
      Approximate value of log2(N!) is calculated by log2_n_fact function.
125
253
 
126
 
       
127
 
      (The Next two are historical, we do all unique operations in memory or fail)
128
 
 
129
254
    2. Cost of merging.
130
255
      If only one tree is created by Unique no merging will be necessary.
131
256
      Otherwise, we model execution of merge_many_buff function and count
138
263
      these will be random seeks.
139
264
*/
140
265
 
141
 
double Unique::get_use_cost(uint32_t *, uint32_t nkeys, uint32_t key_size,
142
 
                            size_t max_in_memory_size_arg)
 
266
double Unique::get_use_cost(uint *buffer, uint nkeys, uint key_size,
 
267
                            uint64_t max_in_memory_size)
143
268
{
144
269
  ulong max_elements_in_tree;
145
270
  ulong last_tree_elems;
 
271
  int   n_full_trees; /* number of trees in unique - 1 */
146
272
  double result;
147
273
 
148
 
  max_elements_in_tree= ((ulong) max_in_memory_size_arg /
 
274
  max_elements_in_tree= ((ulong) max_in_memory_size /
149
275
                         ALIGN_SIZE(sizeof(TREE_ELEMENT)+key_size));
150
276
 
 
277
  n_full_trees=    nkeys / max_elements_in_tree;
151
278
  last_tree_elems= nkeys % max_elements_in_tree;
152
279
 
153
280
  /* Calculate cost of creating trees */
154
281
  result= 2*log2_n_fact(last_tree_elems + 1.0);
 
282
  if (n_full_trees)
 
283
    result+= n_full_trees * log2_n_fact(max_elements_in_tree + 1.0);
155
284
  result /= TIME_FOR_COMPARE_ROWID;
156
285
 
 
286
 
 
287
  if (!n_full_trees)
 
288
    return result;
 
289
 
 
290
  /*
 
291
    There is more then one tree and merging is necessary.
 
292
    First, add cost of writing all trees to disk, assuming that all disk
 
293
    writes are sequential.
 
294
  */
 
295
  result += DISK_SEEK_BASE_COST * n_full_trees *
 
296
              ceil(((double) key_size)*max_elements_in_tree / IO_SIZE);
 
297
  result += DISK_SEEK_BASE_COST * ceil(((double) key_size)*last_tree_elems / IO_SIZE);
 
298
 
 
299
  /* Cost of merge */
 
300
  double merge_cost= get_merge_many_buffs_cost(buffer, n_full_trees,
 
301
                                               max_elements_in_tree,
 
302
                                               last_tree_elems, key_size);
 
303
  if (merge_cost < 0.0)
 
304
    return merge_cost;
 
305
 
 
306
  result += merge_cost;
 
307
  /*
 
308
    Add cost of reading the resulting sequence, assuming there were no
 
309
    duplicate elements.
 
310
  */
 
311
  result += ceil((double)key_size*nkeys/IO_SIZE);
 
312
 
157
313
  return result;
158
314
}
159
315
 
160
316
Unique::~Unique()
161
317
{
162
 
  delete_tree(&tree);
 
318
  close_cached_file(&file);
 
319
  delete_tree(&tree);
 
320
  delete_dynamic(&file_ptrs);
 
321
}
 
322
 
 
323
 
 
324
    /* Write tree to disk; clear tree */
 
325
bool Unique::flush()
 
326
{
 
327
  BUFFPEK file_ptr;
 
328
  elements+= tree.elements_in_tree;
 
329
  file_ptr.count=tree.elements_in_tree;
 
330
  file_ptr.file_pos=my_b_tell(&file);
 
331
 
 
332
  if (tree_walk(&tree, (tree_walk_action) unique_write_to_file,
 
333
                (void*) this, left_root_right) ||
 
334
      insert_dynamic(&file_ptrs, (uchar*) &file_ptr))
 
335
    return 1;
 
336
  delete_tree(&tree);
 
337
  return 0;
163
338
}
164
339
 
165
340
 
166
341
/*
167
 
  Clear the tree.
 
342
  Clear the tree and the file.
168
343
  You must call reset() if you want to reuse Unique after walk().
169
344
*/
170
345
 
172
347
Unique::reset()
173
348
{
174
349
  reset_tree(&tree);
175
 
  assert(elements == 0);
 
350
  /*
 
351
    If elements != 0, some trees were stored in the file (see how
 
352
    flush() works). Note, that we can not count on my_b_tell(&file) == 0
 
353
    here, because it can return 0 right after walk(), and walk() does not
 
354
    reset any Unique member.
 
355
  */
 
356
  if (elements)
 
357
  {
 
358
    reset_dynamic(&file_ptrs);
 
359
    reinit_io_cache(&file, WRITE_CACHE, 0L, 0, 1);
 
360
  }
 
361
  elements= 0;
 
362
}
 
363
 
 
364
/*
 
365
  The comparison function, passed to queue_init() in merge_walk() and in
 
366
  merge_buffers() when the latter is called from Uniques::get() must
 
367
  use comparison function of Uniques::tree, but compare members of struct
 
368
  BUFFPEK.
 
369
*/
 
370
 
 
371
C_MODE_START
 
372
 
 
373
static int buffpek_compare(void *arg, uchar *key_ptr1, uchar *key_ptr2)
 
374
{
 
375
  BUFFPEK_COMPARE_CONTEXT *ctx= (BUFFPEK_COMPARE_CONTEXT *) arg;
 
376
  return ctx->key_compare(ctx->key_compare_arg,
 
377
                          *((uchar **) key_ptr1), *((uchar **)key_ptr2));
 
378
}
 
379
 
 
380
C_MODE_END
 
381
 
 
382
 
 
383
/*
 
384
  DESCRIPTION
 
385
 
 
386
    Function is very similar to merge_buffers, but instead of writing sorted
 
387
    unique keys to the output file, it invokes walk_action for each key.
 
388
    This saves I/O if you need to pass through all unique keys only once.
 
389
 
 
390
  SYNOPSIS
 
391
    merge_walk()
 
392
  All params are 'IN' (but see comment for begin, end):
 
393
    merge_buffer       buffer to perform cached piece-by-piece loading
 
394
                       of trees; initially the buffer is empty
 
395
    merge_buffer_size  size of merge_buffer. Must be aligned with
 
396
                       key_length
 
397
    key_length         size of tree element; key_length * (end - begin)
 
398
                       must be less or equal than merge_buffer_size.
 
399
    begin              pointer to BUFFPEK struct for the first tree.
 
400
    end                pointer to BUFFPEK struct for the last tree;
 
401
                       end > begin and [begin, end) form a consecutive
 
402
                       range. BUFFPEKs structs in that range are used and
 
403
                       overwritten in merge_walk().
 
404
    walk_action        element visitor. Action is called for each unique
 
405
                       key.
 
406
    walk_action_arg    argument to walk action. Passed to it on each call.
 
407
    compare            elements comparison function
 
408
    compare_arg        comparison function argument
 
409
    file               file with all trees dumped. Trees in the file
 
410
                       must contain sorted unique values. Cache must be
 
411
                       initialized in read mode.
 
412
  RETURN VALUE
 
413
    0     ok
 
414
    <> 0  error
 
415
*/
 
416
 
 
417
static bool merge_walk(uchar *merge_buffer, ulong merge_buffer_size,
 
418
                       uint key_length, BUFFPEK *begin, BUFFPEK *end,
 
419
                       tree_walk_action walk_action, void *walk_action_arg,
 
420
                       qsort_cmp2 compare, void *compare_arg,
 
421
                       IO_CACHE *file)
 
422
{
 
423
  BUFFPEK_COMPARE_CONTEXT compare_context = { compare, compare_arg };
 
424
  QUEUE queue;
 
425
  if (end <= begin ||
 
426
      merge_buffer_size < (ulong) (key_length * (end - begin + 1)) ||
 
427
      init_queue(&queue, (uint) (end - begin), offsetof(BUFFPEK, key), 0,
 
428
                 buffpek_compare, &compare_context))
 
429
    return 1;
 
430
  /* we need space for one key when a piece of merge buffer is re-read */
 
431
  merge_buffer_size-= key_length;
 
432
  uchar *save_key_buff= merge_buffer + merge_buffer_size;
 
433
  uint max_key_count_per_piece= (uint) (merge_buffer_size/(end-begin) /
 
434
                                        key_length);
 
435
  /* if piece_size is aligned reuse_freed_buffer will always hit */
 
436
  uint piece_size= max_key_count_per_piece * key_length;
 
437
  uint bytes_read;               /* to hold return value of read_to_buffer */
 
438
  BUFFPEK *top;
 
439
  int res= 1;
 
440
  /*
 
441
    Invariant: queue must contain top element from each tree, until a tree
 
442
    is not completely walked through.
 
443
    Here we're forcing the invariant, inserting one element from each tree
 
444
    to the queue.
 
445
  */
 
446
  for (top= begin; top != end; ++top)
 
447
  {
 
448
    top->base= merge_buffer + (top - begin) * piece_size;
 
449
    top->max_keys= max_key_count_per_piece;
 
450
    bytes_read= read_to_buffer(file, top, key_length);
 
451
    if (bytes_read == (uint) (-1))
 
452
      goto end;
 
453
    assert(bytes_read);
 
454
    queue_insert(&queue, (uchar *) top);
 
455
  }
 
456
  top= (BUFFPEK *) queue_top(&queue);
 
457
  while (queue.elements > 1)
 
458
  {
 
459
    /*
 
460
      Every iteration one element is removed from the queue, and one is
 
461
      inserted by the rules of the invariant. If two adjacent elements on
 
462
      the top of the queue are not equal, biggest one is unique, because all
 
463
      elements in each tree are unique. Action is applied only to unique
 
464
      elements.
 
465
    */
 
466
    void *old_key= top->key;
 
467
    /*
 
468
      read next key from the cache or from the file and push it to the
 
469
      queue; this gives new top.
 
470
    */
 
471
    top->key+= key_length;
 
472
    if (--top->mem_count)
 
473
      queue_replaced(&queue);
 
474
    else /* next piece should be read */
 
475
    {
 
476
      /* save old_key not to overwrite it in read_to_buffer */
 
477
      memcpy(save_key_buff, old_key, key_length);
 
478
      old_key= save_key_buff;
 
479
      bytes_read= read_to_buffer(file, top, key_length);
 
480
      if (bytes_read == (uint) (-1))
 
481
        goto end;
 
482
      else if (bytes_read > 0)      /* top->key, top->mem_count are reset */
 
483
        queue_replaced(&queue);     /* in read_to_buffer */
 
484
      else
 
485
      {
 
486
        /*
 
487
          Tree for old 'top' element is empty: remove it from the queue and
 
488
          give all its memory to the nearest tree.
 
489
        */
 
490
        queue_remove(&queue, 0);
 
491
        reuse_freed_buff(&queue, top, key_length);
 
492
      }
 
493
    }
 
494
    top= (BUFFPEK *) queue_top(&queue);
 
495
    /* new top has been obtained; if old top is unique, apply the action */
 
496
    if (compare(compare_arg, old_key, top->key))
 
497
    {
 
498
      if (walk_action(old_key, 1, walk_action_arg))
 
499
        goto end;
 
500
    }
 
501
  }
 
502
  /*
 
503
    Applying walk_action to the tail of the last tree: this is safe because
 
504
    either we had only one tree in the beginning, either we work with the
 
505
    last tree in the queue.
 
506
  */
 
507
  do
 
508
  {
 
509
    do
 
510
    {
 
511
      if (walk_action(top->key, 1, walk_action_arg))
 
512
        goto end;
 
513
      top->key+= key_length;
 
514
    }
 
515
    while (--top->mem_count);
 
516
    bytes_read= read_to_buffer(file, top, key_length);
 
517
    if (bytes_read == (uint) (-1))
 
518
      goto end;
 
519
  }
 
520
  while (bytes_read);
 
521
  res= 0;
 
522
end:
 
523
  delete_queue(&queue);
 
524
  return res;
176
525
}
177
526
 
178
527
 
188
537
  SYNOPSIS
189
538
    Unique:walk()
190
539
  All params are 'IN':
191
 
    action  function-visitor, typed in include/tree.h
 
540
    action  function-visitor, typed in include/my_tree.h
192
541
            function is called for each unique element
193
542
    arg     argument for visitor, which is passed to it on each call
194
543
  RETURN VALUE
198
547
 
199
548
bool Unique::walk(tree_walk_action action, void *walk_action_arg)
200
549
{
201
 
  return tree_walk(&tree, action, walk_action_arg, left_root_right);
 
550
  int res;
 
551
  uchar *merge_buffer;
 
552
 
 
553
  if (elements == 0)                       /* the whole tree is in memory */
 
554
    return tree_walk(&tree, action, walk_action_arg, left_root_right);
 
555
 
 
556
  /* flush current tree to the file to have some memory for merge buffer */
 
557
  if (flush())
 
558
    return 1;
 
559
  if (flush_io_cache(&file) || reinit_io_cache(&file, READ_CACHE, 0L, 0, 0))
 
560
    return 1;
 
561
  if (!(merge_buffer= (uchar *) my_malloc((ulong) max_in_memory_size, MYF(0))))
 
562
    return 1;
 
563
  res= merge_walk(merge_buffer, (ulong) max_in_memory_size, size,
 
564
                  (BUFFPEK *) file_ptrs.buffer,
 
565
                  (BUFFPEK *) file_ptrs.buffer + file_ptrs.elements,
 
566
                  action, walk_action_arg,
 
567
                  tree.compare, tree.custom_arg, &file);
 
568
  my_free((char*) merge_buffer, MYF(0));
 
569
  return res;
202
570
}
203
571
 
204
572
/*
205
 
  Modify the Table element so that when one calls init_records()
 
573
  Modify the TABLE element so that when one calls init_records()
206
574
  the rows will be read in priority order.
207
575
*/
208
576
 
209
 
bool Unique::get(Table *table)
 
577
bool Unique::get(TABLE *table)
210
578
{
211
 
  table->sort.found_records= elements+tree.elements_in_tree;
 
579
  SORTPARAM sort_param;
 
580
  table->sort.found_records=elements+tree.elements_in_tree;
212
581
 
213
 
  if ((record_pointers=table->sort.record_pointers= (unsigned char*)
214
 
       malloc(size * tree.elements_in_tree)))
 
582
  if (my_b_tell(&file) == 0)
215
583
  {
216
 
    (void) tree_walk(&tree, (tree_walk_action) unique_write_to_ptrs,
217
 
                     this, left_root_right);
218
 
    return 0;
 
584
    /* Whole tree is in memory;  Don't use disk if you don't need to */
 
585
    if ((record_pointers=table->sort.record_pointers= (uchar*)
 
586
         my_malloc(size * tree.elements_in_tree, MYF(0))))
 
587
    {
 
588
      (void) tree_walk(&tree, (tree_walk_action) unique_write_to_ptrs,
 
589
                       this, left_root_right);
 
590
      return 0;
 
591
    }
219
592
  }
220
 
  /* Not enough memory */
221
 
  return 1;
 
593
  /* Not enough memory; Save the result to file && free memory used by tree */
 
594
  if (flush())
 
595
    return 1;
 
596
 
 
597
  IO_CACHE *outfile=table->sort.io_cache;
 
598
  BUFFPEK *file_ptr= (BUFFPEK*) file_ptrs.buffer;
 
599
  uint maxbuffer= file_ptrs.elements - 1;
 
600
  uchar *sort_buffer;
 
601
  my_off_t save_pos;
 
602
  bool error=1;
 
603
 
 
604
      /* Open cached file if it isn't open */
 
605
  outfile=table->sort.io_cache=(IO_CACHE*) my_malloc(sizeof(IO_CACHE),
 
606
                                MYF(MY_ZEROFILL));
 
607
 
 
608
  if (!outfile || (! my_b_inited(outfile) && open_cached_file(outfile,mysql_tmpdir,TEMP_PREFIX,READ_RECORD_BUFFER, MYF(MY_WME))))
 
609
    return 1;
 
610
  reinit_io_cache(outfile,WRITE_CACHE,0L,0,0);
 
611
 
 
612
  bzero((char*) &sort_param,sizeof(sort_param));
 
613
  sort_param.max_rows= elements;
 
614
  sort_param.sort_form=table;
 
615
  sort_param.rec_length= sort_param.sort_length= sort_param.ref_length=
 
616
    size;
 
617
  sort_param.keys= (uint) (max_in_memory_size / sort_param.sort_length);
 
618
  sort_param.not_killable=1;
 
619
 
 
620
  if (!(sort_buffer=(uchar*) my_malloc((sort_param.keys+1) *
 
621
                                       sort_param.sort_length,
 
622
                                       MYF(0))))
 
623
    return 1;
 
624
  sort_param.unique_buff= sort_buffer+(sort_param.keys*
 
625
                                       sort_param.sort_length);
 
626
 
 
627
  sort_param.compare= (qsort2_cmp) buffpek_compare;
 
628
  sort_param.cmp_context.key_compare= tree.compare;
 
629
  sort_param.cmp_context.key_compare_arg= tree.custom_arg;
 
630
 
 
631
  /* Merge the buffers to one file, removing duplicates */
 
632
  if (merge_many_buff(&sort_param,sort_buffer,file_ptr,&maxbuffer,&file))
 
633
    goto err;
 
634
  if (flush_io_cache(&file) ||
 
635
      reinit_io_cache(&file,READ_CACHE,0L,0,0))
 
636
    goto err;
 
637
  if (merge_buffers(&sort_param, &file, outfile, sort_buffer, file_ptr,
 
638
                    file_ptr, file_ptr+maxbuffer,0))
 
639
    goto err;
 
640
  error=0;
 
641
err:
 
642
  x_free(sort_buffer);
 
643
  if (flush_io_cache(outfile))
 
644
    error=1;
 
645
 
 
646
  /* Setup io_cache for reading */
 
647
  save_pos=outfile->pos_in_file;
 
648
  if (reinit_io_cache(outfile,READ_CACHE,0L,0,0))
 
649
    error=1;
 
650
  outfile->end_of_file=save_pos;
 
651
  return error;
222
652
}
223
 
 
224
 
} /* namespace drizzled */