Branch data Line data Source code
1 : : #include "store_manip.hpp"
2 : :
3 : : #include "storage/ColumnStore.hpp"
4 : : #include "util/datagen.hpp"
5 : : #include <algorithm>
6 : : #include <chrono>
7 : : #include <cstring>
8 : : #include <limits>
9 : : #include <mutable/catalog/Schema.hpp>
10 : : #include <mutable/Options.hpp>
11 : : #include <mutable/util/fn.hpp>
12 : : #include <random>
13 : : #include <unordered_set>
14 : :
15 : :
16 : : using namespace m;
17 : :
18 : :
19 : : //======================================================================================================================
20 : : // HELPER FUNCTIONS
21 : : //======================================================================================================================
22 : :
23 : : namespace {
24 : :
25 : : /** Generate `count` many distinct numbers of type `T` in the range of [`min`, `max`). */
26 : : template<typename T>
27 : 4 : std::vector<T> generate_distinct_numbers(const T min, const T max, const std::size_t count)
28 : : {
29 : : using uniform_distibution_t = std::conditional_t<std::is_integral_v<T>,
30 : : std::uniform_int_distribution<T>,
31 : : std::uniform_real_distribution<T>>;
32 : : static_assert(std::is_arithmetic_v<T>, "T must be an arithmetic type");
33 : : if (std::is_integral_v<T>)
34 : 4 : M_insist(T(max - count) > min, "range is too small to provide enough distinct values");
35 : :
36 : 4 : std::vector<T> values;
37 [ + - + - : 4 : values.reserve(count);
+ - + - ]
38 : :
39 : 4 : std::unordered_set<T> taken;
40 : 4 : T counter = max - T(count);
41 : :
42 [ + - + - : 4 : std::mt19937_64 g(0);
+ - + - ]
43 [ + - + - : 4 : uniform_distibution_t dist(min, counter);
+ - + - ]
44 : :
45 [ + + + + : 104 : for (std::size_t i = 0; i != count; ++i) {
+ + + + ]
46 [ + - + - : 100 : T val = dist(g);
+ - + - ]
47 [ + - + - : 100 : auto[_, success] = taken.insert(val);
+ - + - ]
48 [ + + + - : 100 : if (success) {
+ - + - ]
49 [ + - + - : 98 : values.push_back(val);
+ - + - ]
50 : 98 : } else {
51 [ + - # # : 2 : values.push_back(++counter);
# # # # ]
52 : : }
53 : 100 : }
54 : :
55 : 4 : return values;
56 [ + - + - : 4 : }
+ - + - ]
57 : :
58 : : /** Generates data for a numeric column at address `column_ptr` of type `T` and writes it directly to memory. The
59 : : * rows must have been allocated before calling this function. */
60 : : template<typename T>
61 : 6 : void generate_numeric_column(T *column_ptr, std::size_t num_distinct_values, std::size_t begin, std::size_t end)
62 : : {
63 : : static_assert(std::is_arithmetic_v<T>, "T must be an arithmetic type");
64 : 6 : M_insist(begin < end, "must set at least one row");
65 : :
66 : 6 : const auto count = end - begin;
67 : :
68 : : /* Generate distinct values. */
69 : 6 : std::vector<T> values;
70 : : if (std::is_integral_v<T>)
71 [ + - + - : 4 : values = datagen::generate_uniform_distinct_numbers<T>(
+ - + - +
- + - + -
+ - ]
72 : 4 : /* min= */ std::numeric_limits<T>::lowest() + std::is_signed_v<T>,
73 : 4 : /* max= */ std::numeric_limits<T>::max(),
74 : 5 : /* count= */ num_distinct_values
75 : : );
76 : : else
77 [ + - + - : 2 : values = datagen::generate_uniform_distinct_numbers<T>(T(0), T(1), num_distinct_values);
+ - + - ]
78 [ + - + - : 6 : M_insist(values.size() == num_distinct_values);
+ - + - +
- + - ]
79 : :
80 : : /* Write distinct values repeatedly in arbitrary order to column. */
81 : 6 : auto ptr = column_ptr + begin;
82 [ + - + - : 6 : std::mt19937_64 g(0);
+ - + - +
- + - ]
83 [ + - + - : 156 : for (std::size_t i = 0; i != count; ) {
+ - + - +
- + - ]
84 : : /* Shuffle the vector before writing its values to the column. */
85 [ + - + - : 156 : std::shuffle(values.begin(), values.end(), g);
+ - + - +
- + - ]
86 [ + + + + : 1692 : for (auto v : values) {
+ + + + +
+ + + ]
87 : 1542 : *ptr++ = v;
88 : 1542 : ++i;
89 [ + + + + : 1542 : if (i == count)
+ + + + +
+ + + ]
90 : 6 : goto exit;
91 : : }
92 : 0 : }
93 : : exit:
94 [ + - + - : 6 : M_insist(ptr - column_ptr == long(count), "incorrect number of elements written");
+ - + - +
- + - ]
95 : 6 : }
96 : :
97 : : template<typename T>
98 : 4 : void generate_correlated_numeric_columns(T *left_ptr, T *right_ptr, std::size_t num_distinct_values_left,
99 : : std::size_t num_distinct_values_right, std::size_t count_left,
100 : : std::size_t count_right, std::size_t num_distinct_values_matching)
101 : : {
102 : : static_assert(std::is_arithmetic_v<T>, "T must be an arithmetic type");
103 : 4 : M_insist(num_distinct_values_left >= num_distinct_values_matching,
104 : : "num_distinct_values_left must be larger than num_distinct_values_matching");
105 : 4 : M_insist(num_distinct_values_right >= num_distinct_values_matching,
106 : : "num_distinct_values_right must be larger than num_distinct_values_matching");
107 : :
108 : : /* Generate a single set of distinct values to draw from to fill left and right side, with an overlap of exactly
109 : : * `num_distinct_values_matching` values. */
110 : 4 : const std::vector<T> values = generate_distinct_numbers<T>(
111 : 4 : /* min= */ std::numeric_limits<T>::lowest(),
112 : 4 : /* max= */ std::numeric_limits<T>::max(),
113 : 4 : /* count= */ num_distinct_values_left + num_distinct_values_right - num_distinct_values_matching
114 : : );
115 : :
116 [ + - + - : 4 : std::mt19937_64 g(0);
+ - + - ]
117 : :
118 : : /* Fill `store_left`. */
119 : : {
120 : : /* Draw first `num_distinct_values_left` values from `values`. */
121 [ + - + - : 4 : std::vector<T> values_left(values.begin(), values.begin() + num_distinct_values_left);
+ - + - ]
122 : :
123 : : /* Write distinct values repeatedly in arbitrary order to column. */
124 : 4 : auto left = left_ptr;
125 [ + - + - : 104 : for (std::size_t i = 0; i != count_left; ) {
+ - + - ]
126 : : /* Shuffle the vector before writing its values to the column. */
127 [ + - + - : 104 : std::shuffle(values_left.begin(), values_left.end(), g);
+ - + - ]
128 [ + + + + : 1128 : for (auto v : values_left) {
+ + + + ]
129 : 1028 : *left++ = v;
130 : 1028 : ++i;
131 [ + + + + : 1028 : if (i == count_left)
+ + + + ]
132 : 4 : goto exit_left;
133 : : }
134 : 0 : }
135 : : exit_left:
136 [ + - + - : 4 : M_insist(left - left_ptr == long(count_left),
+ - + - ]
137 : : "incorrect number of elements written to left store");
138 : 4 : }
139 : :
140 : : /* Fill `store_right`. */
141 : : {
142 : : /* Draw last `num_distinct_values_right` values from `values`. */
143 [ + - - + : 4 : std::vector<T> values_right(values.rbegin(), values.rbegin() + num_distinct_values_right);
+ - - + +
- - + + -
- + ]
144 : :
145 : : /* Write distinct values repeatedly in arbitrary order to column. */
146 : 4 : auto right = right_ptr;
147 [ + - + - : 104 : for (std::size_t i = 0; i != count_right; ) {
+ - + - ]
148 : : /* Shuffle the vector before writing its values to the column. */
149 [ + - + - : 104 : std::shuffle(values_right.begin(), values_right.end(), g);
+ - + - ]
150 [ + + + + : 2156 : for (auto v : values_right) {
+ + + + ]
151 : 2056 : *right++ = v;
152 : 2056 : ++i;
153 [ + + + + : 2056 : if (i == count_right)
+ + + + ]
154 : 4 : goto exit_right;
155 : : }
156 : 0 : }
157 : : exit_right:
158 [ + - + - : 4 : M_insist(right - right_ptr == long(count_right),
+ - + - ]
159 : : "incorrect number of elements written to right store");
160 : 4 : }
161 : 4 : }
162 : :
163 : : }
164 : :
165 : 1 : void m::set_all_null(uint8_t *column_ptr, std::size_t num_attrs, std::size_t begin, std::size_t end)
166 : : {
167 : 1 : M_insist(begin < end, "must set at least one row");
168 : :
169 : 1 : auto begin_bytes = (num_attrs * begin) / 8U;
170 : 1 : const auto begin_bits = (num_attrs * begin) % 8U;
171 : 1 : const auto end_bytes = (num_attrs * end) / 8U;
172 : 1 : const auto end_bits = (num_attrs * end) % 8U;
173 : :
174 : 1 : M_insist(begin_bytes != end_bytes, "the `begin`-th row and `end`-th row must be in different bytes");
175 : :
176 : : /* Set the `begin_bits` most significant bits to 1. */
177 [ - + ]: 1 : if (begin_bits) {
178 : 0 : *(column_ptr + begin_bytes) |= ~((1U << (8U - begin_bits)) - 1U); // set respective bits to 1
179 : 0 : ++begin_bytes; // advance to first byte which can be written entirely
180 : 0 : }
181 : :
182 : : /* Set the `end_bits` least significant bits to 1. */
183 [ + - ]: 1 : if (end_bits)
184 : 1 : *(column_ptr + end_bytes) |= (1U << end_bits) - 1U; // set respective bits to 1
185 : :
186 : 1 : const auto num_bytes = end_bytes - begin_bytes;
187 : 1 : std::memset(column_ptr + begin_bytes, uint8_t(~0), num_bytes);
188 : 1 : }
189 : :
190 : 1 : void m::set_all_not_null(uint8_t *column_ptr, std::size_t num_attrs, std::size_t begin, std::size_t end)
191 : : {
192 : 1 : M_insist(begin < end, "must set at least one row");
193 : :
194 : 1 : auto begin_bytes = (num_attrs * begin) / 8U;
195 : 1 : const auto begin_bits = (num_attrs * begin) % 8U;
196 : 1 : const auto end_bytes = (num_attrs * end) / 8U;
197 : 1 : const auto end_bits = (num_attrs * end) % 8U;
198 : :
199 : 1 : M_insist(begin_bytes != end_bytes, "the `begin`-th row and `end`-th row must be in different bytes");
200 : :
201 : : /* Set the `begin_bits` most significant bits to 0. */
202 [ - + ]: 1 : if (begin_bits) {
203 : 0 : *(column_ptr + begin_bytes) &= (1U << begin_bits) - 1U; // set respective bits to 0
204 : 0 : ++begin_bytes; // advance to first byte which can be written entirely
205 : 0 : }
206 : :
207 : : /* Set the `end_bits` least significant bits to 0. */
208 [ + - ]: 1 : if (end_bits)
209 : 1 : *(column_ptr + end_bytes) &= ~((1U << (8U - end_bits)) - 1U); // set respective bits to 0
210 : :
211 : 1 : const auto num_bytes = end_bytes - begin_bytes;
212 : 1 : std::memset(column_ptr + begin_bytes, uint8_t(0), num_bytes);
213 : 1 : }
214 : :
215 : :
216 : 3 : void m::generate_primary_keys(void *column_ptr, const Type &type, std::size_t begin, std::size_t end)
217 : : {
218 : 3 : M_insist(begin < end, "must set at least one row");
219 : 3 : M_insist(type.is_integral(), "primary key columns must be of integral type");
220 : :
221 : 3 : auto &n = as<const Numeric>(type);
222 [ - + + ]: 3 : switch (n.size()) {
223 : : default:
224 : 0 : M_unreachable("unsupported size of primary key");
225 : :
226 : : case 32: {
227 : 2 : auto ptr = reinterpret_cast<int32_t*>(column_ptr);
228 : 2 : std::iota<int32_t*, int32_t>(ptr + begin, ptr + end, begin);
229 : 2 : break;
230 : : }
231 : :
232 : : case 64: {
233 : 1 : auto ptr = reinterpret_cast<int64_t*>(column_ptr);
234 : 1 : std::iota<int64_t*, int64_t>(ptr + begin, ptr + end, begin);
235 : 1 : break;
236 : : }
237 : : }
238 : 3 : }
239 : :
240 : 7 : void m::generate_column_data(void *column_ptr, const Attribute &attr, std::size_t num_distinct_values,
241 : : std::size_t begin, std::size_t end)
242 : : {
243 : 7 : M_insist(begin < end, "must set at least one row");
244 : :
245 [ + + ]: 7 : if (streq(*attr.name, "id")) { // generate primary key
246 : 1 : generate_primary_keys(column_ptr, *attr.type, begin, end);
247 [ + - ]: 7 : } else if (auto n = cast<const Numeric>(attr.type)) {
248 [ - - + + ]: 6 : switch (n->kind) {
249 : : case m::Numeric::N_Int:
250 [ - + + + : 4 : switch (n->size()) {
+ ]
251 : : #define CASE(N) case N: \
252 : : ::generate_numeric_column(reinterpret_cast<int##N##_t*>(column_ptr), num_distinct_values, begin, end); \
253 : : break
254 : 1 : CASE(8);
255 : 1 : CASE(16);
256 : 1 : CASE(32);
257 : 1 : CASE(64);
258 : : #undef CASE
259 : : }
260 : 4 : break;
261 : : case m::Numeric::N_Float:
262 [ - + + ]: 2 : switch (n->size()) {
263 : : case 32:
264 : 1 : ::generate_numeric_column(reinterpret_cast<float*>(column_ptr), num_distinct_values, begin, end);
265 : 1 : break;
266 : : case 64:
267 : 1 : ::generate_numeric_column(reinterpret_cast<double*>(column_ptr), num_distinct_values, begin, end);
268 : 1 : break;
269 : : }
270 : 2 : break;
271 : : case m::Numeric::N_Decimal:
272 : 0 : M_unreachable("unsupported type");
273 : : }
274 : :
275 : 6 : } else {
276 : 0 : M_unreachable("unsupported type");
277 : : }
278 : 7 : }
279 : :
280 : 4 : void m::generate_correlated_column_data(void *left_ptr, void *right_ptr, const Attribute &attr,
281 : : std::size_t num_distinct_values_left, std::size_t num_distinct_values_right,
282 : : std::size_t count_left, std::size_t count_right,
283 : : std::size_t num_distinct_values_matching)
284 : : {
285 [ + - ]: 4 : if (streq(*attr.name, "id")) { // primary keys cannot be correlated
286 : 0 : M_unreachable("primary keys unsupported");
287 [ + - ]: 4 : } else if (auto n = cast<const Numeric>(attr.type)) {
288 [ - + + + : 4 : switch (n->size()) {
+ ]
289 : : #define CASE(N) case N: \
290 : : generate_correlated_numeric_columns(reinterpret_cast<int##N##_t*>(left_ptr), \
291 : : reinterpret_cast<int##N##_t*>(right_ptr), \
292 : : num_distinct_values_left, num_distinct_values_right, \
293 : : count_left, count_right, \
294 : : num_distinct_values_matching); \
295 : : break
296 : 1 : CASE(8);
297 : 1 : CASE(16);
298 : 1 : CASE(32);
299 : 1 : CASE(64);
300 : : #undef CASE
301 : : }
302 : 4 : } else {
303 : 0 : M_unreachable("unsupported type");
304 : : }
305 : 4 : }
|
