1 /* Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
2 
3    This program is free software; you can redistribute it and/or modify
4    it under the terms of the GNU General Public License, version 2.0,
5    as published by the Free Software Foundation.
6 
7    This program is also distributed with certain software (including
8    but not limited to OpenSSL) that is licensed under separate terms,
9    as designated in a particular file or component or in included license
10    documentation.  The authors of MySQL hereby grant you an additional
11    permission to link the program and your derivative works with the
12    separately licensed software that they have included with MySQL.
13 
14    This program is distributed in the hope that it will be useful,
15    but WITHOUT ANY WARRANTY; without even the implied warranty of
16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17    GNU General Public License, version 2.0, for more details.
18 
19    You should have received a copy of the GNU General Public License
20    along with this program; if not, write to the Free Software
21    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA */
22 
23 #ifndef FILESORT_UTILS_INCLUDED
24 #define FILESORT_UTILS_INCLUDED
25 
26 #include "my_global.h"
27 #include "my_base.h"
28 #include "sql_array.h"
29 
30 #include <utility>
31 
32 class Sort_param;
33 /*
34   Calculate cost of merge sort
35 
36     @param num_rows            Total number of rows.
37     @param num_keys_per_buffer Number of keys per buffer.
38     @param elem_size           Size of each element.
39 
40     Calculates cost of merge sort by simulating call to merge_many_buff().
41 
42   @retval
43     Computed cost of merge sort in disk seeks.
44 
45   @note
46     Declared here in order to be able to unit test it,
47     since library dependencies have not been sorted out yet.
48 
49     See also comments get_merge_many_buffs_cost().
50 */
51 
52 double get_merge_many_buffs_cost_fast(ha_rows num_rows,
53                                       ha_rows num_keys_per_buffer,
54                                       uint    elem_size);
55 
56 
57 /**
58   A wrapper class around the buffer used by filesort().
59   The buffer is a contiguous chunk of memory,
60   where the first part is <num_records> pointers to the actual data.
61 
62   We wrap the buffer in order to be able to do lazy initialization of the
63   pointers: the buffer is often much larger than what we actually need.
64 
65   The buffer must be kept available for multiple executions of the
66   same sort operation, so we have explicit allocate and free functions,
67   rather than doing alloc/free in CTOR/DTOR.
68  */
69 class Filesort_buffer
70 {
71 public:
Filesort_buffer()72   Filesort_buffer() :
73     m_idx_array(), m_record_length(0), m_start_of_data(NULL)
74   {}
75 
76   /** Sort me... */
77   void sort_buffer(const Sort_param *param, uint count);
78 
79   /// Initializes a record pointer.
get_record_buffer(uint idx)80   uchar *get_record_buffer(uint idx)
81   {
82     m_idx_array[idx]= m_start_of_data + (idx * m_record_length);
83     return m_idx_array[idx];
84   }
85 
86   /// Initializes all the record pointers.
init_record_pointers()87   void init_record_pointers()
88   {
89     for (uint ix= 0; ix < m_idx_array.size(); ++ix)
90       (void) get_record_buffer(ix);
91   }
92 
93   /// Returns total size: pointer array + record buffers.
sort_buffer_size()94   size_t sort_buffer_size() const
95   {
96     return m_idx_array.size() * (m_record_length + sizeof(uchar*));
97   }
98 
99   /// Allocates the buffer, but does *not* initialize pointers.
100   uchar **alloc_sort_buffer(uint num_records, uint record_length);
101 
102   /// Frees the buffer.
103   void free_sort_buffer();
104 
105   /// Getter, for calling routines which still use the uchar** interface.
get_sort_keys()106   uchar **get_sort_keys() { return m_idx_array.array(); }
107 
108   /**
109     We need an assignment operator, see filesort().
110     This happens to have the same semantics as the one that would be
111     generated by the compiler. We still implement it here, to show shallow
112     assignment explicitly: we have two objects sharing the same array.
113   */
114   Filesort_buffer &operator=(const Filesort_buffer &rhs)
115   {
116     m_idx_array= rhs.m_idx_array;
117     m_record_length= rhs.m_record_length;
118     m_start_of_data= rhs.m_start_of_data;
119     return *this;
120   }
121 
122 private:
123   typedef Bounds_checked_array<uchar*> Idx_array;
124 
125   Idx_array  m_idx_array;
126   uint       m_record_length;
127   uchar     *m_start_of_data;
128 };
129 
130 #endif  // FILESORT_UTILS_INCLUDED
131