MySQL  8.0.20
Source Code Documentation
singleton.h
Go to the documentation of this file.
1 #ifndef HISTOGRAMS_SINGLETON_INCLUDED
2 #define HISTOGRAMS_SINGLETON_INCLUDED
3 
4 /* Copyright (c) 2016, 2019, Oracle and/or its affiliates. All rights reserved.
5 
6  This program is free software; you can redistribute it and/or modify
7  it under the terms of the GNU General Public License, version 2.0,
8  as published by the Free Software Foundation.
9 
10  This program is also distributed with certain software (including
11  but not limited to OpenSSL) that is licensed under separate terms,
12  as designated in a particular file or component or in included license
13  documentation. The authors of MySQL hereby grant you an additional
14  permission to link the program and your derivative works with the
15  separately licensed software that they have included with MySQL.
16 
17  This program is distributed in the hope that it will be useful,
18  but WITHOUT ANY WARRANTY; without even the implied warranty of
19  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20  GNU General Public License, version 2.0, for more details.
21 
22  You should have received a copy of the GNU General Public License
23  along with this program; if not, write to the Free Software
24  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
25 
26 /**
27  @file sql/histograms/singleton.h
28  Singleton histogram.
29 
30  This file defines the Singleton histogram. A Singleton histogram is a
31  histogram where only a value and it's frequency is stored. It allows us to
32  use less storage space, as well as estimating selectivity a bit more
33  efficient.
34 
35  A singleton histogram converted to a JSON object, follows the following
36  "schema":
37 
38  {
39  // Last time the histogram was updated. As of now, this means "when the
40  // histogram was created" (incremental updates are not supported). Date/time
41  // is given in UTC.
42  // -- J_DATETIME
43  "last-updated": "2015-11-04 15:19:51.000000",
44 
45  // Histogram type. Always "singleton" for singleton histograms.
46  // -- J_STRING
47  "histogram-type": "singleton",
48 
49  // Fraction of NULL values. This is the total fraction of NULL values in the
50  // original data set.
51  // -- J_DOUBLE
52  "null-values": 0.1,
53 
54  // Histogram buckets. May be an empty array, if for instance the source
55  // only contains NULL values.
56  // -- J_ARRAY
57  "buckets":
58  [
59  [
60  // Value
61  // -- Data type depends on the source column.
62  42,
63 
64  // Cumulative frequency
65  // -- J_DOUBLE
66  0.001978728666831561
67  ]
68  ]
69  }
70 */
71 
72 #include <stddef.h>
73 #include <map> // std::map
74 #include <string> // std::string
75 #include <utility> // std::pair
76 
77 #include "my_inttypes.h"
78 #include "mysql_time.h"
79 #include "sql/histograms/histogram.h" // Histogram, Histogram_comparator,
81 #include "sql/mem_root_allocator.h"
82 #include "sql/my_decimal.h"
83 #include "sql_string.h"
84 
85 class Json_array;
86 class Json_object;
87 struct MEM_ROOT;
88 
89 namespace histograms {
90 
91 /**
92  Singleton histogram.
93 */
94 struct Histogram_comparator;
95 template <class T>
96 class Value_map;
97 
98 template <class T>
99 class Singleton : public Histogram {
100  private:
101  /// String representation of the histogram type SINGLETON.
102  static constexpr const char *singleton_str() { return "singleton"; }
103 
106 
107  using singleton_buckets_type = std::map<const T, double, Histogram_comparator,
109 
110  /// The buckets for this histogram [key, cumulative frequency].
112 
113  public:
114  /**
115  Singleton constructor.
116 
117  This will not build the histogram, but only set its properties.
118 
119  @param mem_root the mem_root where the histogram contents will be allocated
120  @param db_name name of the database this histogram represents
121  @param tbl_name name of the table this histogram represents
122  @param col_name name of the column this histogram represents
123  @param data_type the type of data that this histogram contains
124  */
125  Singleton(MEM_ROOT *mem_root, const std::string &db_name,
126  const std::string &tbl_name, const std::string &col_name,
127  Value_map_type data_type);
128 
129  /**
130  Singleton copy-constructor
131 
132  This will take a copy of the histogram and all of its contents on the
133  provided MEM_ROOT.
134 
135  @param mem_root the MEM_ROOT to allocate the new histogram on.
136  @param other the histogram to take a copy of
137  */
138  Singleton(MEM_ROOT *mem_root, const Singleton<T> &other);
139 
140  Singleton(const Singleton<T> &other) = delete;
141 
142  /**
143  Build the Singleton histogram.
144 
145  @param value_map values to create the histogram for
146  @param num_buckets the number of buckets specified/requested by the user
147 
148  @return true on error, false otherwise
149  */
150  bool build_histogram(const Value_map<T> &value_map, size_t num_buckets);
151 
152  /**
153  Convert this histogram to a JSON object.
154 
155  This function will take the contents of the current histogram and put
156  it in the output parameter "json_object".
157 
158  @param[in,out] json_object output where the histogram is to be stored. The
159  caller is responsible for allocating/deallocating the JSON
160  object
161 
162  @return true on error, false otherwise
163  */
164  bool histogram_to_json(Json_object *json_object) const override;
165 
166  /**
167  @return number of values/buckets in this histogram
168  */
169  size_t get_num_buckets() const override { return m_buckets.size(); }
170 
171  /**
172  Get the estimated number of distinct non-NULL values.
173  @return number of distinct non-NULL values
174  */
175  size_t get_num_distinct_values() const override { return get_num_buckets(); }
176 
177  /**
178  Returns the histogram type as a readable string.
179 
180  @return a readable string representation of the histogram type
181  */
182  std::string histogram_type_to_str() const override;
183 
184  /**
185  Make a clone of this histogram on a MEM_ROOT.
186 
187  @param mem_root the MEM_ROOT to allocate the new histogram contents on.
188 
189  @return a copy of the histogram allocated on the provided MEM_ROOT.
190  */
191  Histogram *clone(MEM_ROOT *mem_root) const override;
192 
193  /**
194  Find the number of values equal to 'value'.
195 
196  This function will estimate the number of values that is equal to the
197  provided value.
198 
199  @param value The value to estimate the selectivity for.
200 
201  @return the selectivity between 0.0 and 1.0 inclusive.
202  */
203  double get_equal_to_selectivity(const T &value) const;
204 
205  /**
206  Find the number of values less than 'value'.
207 
208  This function will estimate the number of values that is less than the
209  provided value.
210 
211  @param value The value to estimate the selectivity for.
212 
213  @return the selectivity between 0.0 and 1.0 inclusive.
214  */
215  double get_less_than_selectivity(const T &value) const;
216 
217  /**
218  Find the number of values greater than 'value'.
219 
220  This function will estimate the number of values that is greater than the
221  provided value.
222 
223  @param value The value to estimate the selectivity for.
224 
225  @return the selectivity between 0.0 and 1.0 inclusive.
226  */
227  double get_greater_than_selectivity(const T &value) const;
228 
229  private:
230  /**
231  Add value to a JSON bucket
232 
233  This function adds the value to the supplied JSON array.
234 
235  @param value the value to add
236  @param[out] json_bucket a JSON array where the bucket data is to be stored
237 
238  @return true on error, false otherwise
239  */
240  static bool add_value_json_bucket(const T &value, Json_array *json_bucket);
241 
242  /**
243  Convert one bucket to a JSON object.
244 
245  @param bucket the histogram bucket to convert
246  @param[out] json_bucket a JSON array where the bucket data is to be stored
247 
248  @return true on error, false otherwise
249  */
250  static bool create_json_bucket(const std::pair<T, double> &bucket,
251  Json_array *json_bucket);
252 
253  protected:
254  /**
255  Populate this histogram with contents from a JSON object.
256 
257  @param json_object a JSON object that represents an Singleton histogram
258 
259  @return true on error, false otherwise.
260  */
261  bool json_to_histogram(const Json_object &json_object) override;
262 };
263 
264 } // namespace histograms
265 
266 #endif
Our own string classes, used pervasively throughout the executor.
Histogram * clone(MEM_ROOT *mem_root) const override
Make a clone of this histogram on a MEM_ROOT.
Definition: singleton.cc:301
Mem_root_allocator is a C++ STL memory allocator based on MEM_ROOT.
Definition: equi_height.h:92
const char * db_name
Definition: rules_table_service.cc:54
Some integer typedefs for easier portability.
double get_equal_to_selectivity(const T &value) const
Find the number of values equal to &#39;value&#39;.
Definition: singleton.cc:312
double get_less_than_selectivity(const T &value) const
Find the number of values less than &#39;value&#39;.
Definition: singleton.cc:334
bool histogram_to_json(Json_object *json_object) const override
Convert this histogram to a JSON object.
Definition: singleton.cc:143
Value_map_type
Datatypes that a Value_map and histogram can hold (including the invalid type).
Definition: value_map_type.h:32
Represents a JSON array container, i.e.
Definition: json_dom.h:518
static constexpr const char * singleton_str()
String representation of the histogram type SINGLETON.
Definition: singleton.h:102
bool json_to_histogram(const Json_object &json_object) override
Populate this histogram with contents from a JSON object.
Definition: singleton.cc:263
size_t get_num_buckets() const override
Definition: singleton.h:169
std::string histogram_type_to_str() const override
Returns the histogram type as a readable string.
Definition: singleton.cc:258
bool build_histogram(const Value_map< T > &value_map, size_t num_buckets)
Build the Singleton histogram.
Definition: singleton.cc:85
It is interface module to fixed precision decimals library.
static bool create_json_bucket(const std::pair< T, double > &bucket, Json_array *json_bucket)
Convert one bucket to a JSON object.
Definition: singleton.cc:171
static MEM_ROOT mem_root
Definition: client_plugin.cc:109
Histogram comparator.
Definition: value_map.h:67
Represents a JSON container value of type "object" (ECMA), type J_OBJECT here.
Definition: json_dom.h:367
Time declarations shared between the server and client API: you should not add anything to this heade...
Histogram base class.
singleton_buckets_type m_buckets
The buckets for this histogram [key, cumulative frequency].
Definition: singleton.h:111
Definition: singleton.h:99
const string value("\alue\)
size_t get_num_distinct_values() const override
Get the estimated number of distinct non-NULL values.
Definition: singleton.h:175
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:77
Definition: column_statistics.h:33
Singleton(MEM_ROOT *mem_root, const std::string &db_name, const std::string &tbl_name, const std::string &col_name, Value_map_type data_type)
Singleton constructor.
Definition: singleton.cc:48
Value_map class.
Definition: histogram.h:68
static bool add_value_json_bucket(const T &value, Json_array *json_bucket)
Add value to a JSON bucket.
std::map< const T, double, Histogram_comparator, singleton_buckets_allocator > singleton_buckets_type
Definition: singleton.h:108
Definition: completion_hash.h:39
Histogram base class.
Definition: histogram.h:136
double get_greater_than_selectivity(const T &value) const
Find the number of values greater than &#39;value&#39;.
Definition: singleton.cc:349