1#include "duckdb/storage/segment/uncompressed.hpp"
2#include "duckdb/storage/buffer_manager.hpp"
3#include "duckdb/common/types/vector.hpp"
4#include "duckdb/storage/table/append_state.hpp"
5
6#include "duckdb/common/types/null_value.hpp"
7#include "duckdb/storage/table/column_segment.hpp"
8#include "duckdb/function/compression_function.hpp"
9#include "duckdb/storage/table/scan_state.hpp"
10
11namespace duckdb {
12
13//===--------------------------------------------------------------------===//
14// Mask constants
15//===--------------------------------------------------------------------===//
16// LOWER_MASKS contains masks with all the lower bits set until a specific value
17// LOWER_MASKS[0] has the 0 lowest bits set, i.e.:
18// 0b0000000000000000000000000000000000000000000000000000000000000000,
19// LOWER_MASKS[10] has the 10 lowest bits set, i.e.:
20// 0b0000000000000000000000000000000000000000000000000000000111111111,
21// etc...
22// 0b0000000000000000000000000000000000000001111111111111111111111111,
23// ...
24// 0b0000000000000000000001111111111111111111111111111111111111111111,
25// until LOWER_MASKS[64], which has all bits set:
26// 0b1111111111111111111111111111111111111111111111111111111111111111
27// generated with this python snippet:
28// for i in range(65):
29// print(hex(int((64 - i) * '0' + i * '1', 2)) + ",")
30const validity_t ValidityUncompressed::LOWER_MASKS[] = {0x0,
31 0x1,
32 0x3,
33 0x7,
34 0xf,
35 0x1f,
36 0x3f,
37 0x7f,
38 0xff,
39 0x1ff,
40 0x3ff,
41 0x7ff,
42 0xfff,
43 0x1fff,
44 0x3fff,
45 0x7fff,
46 0xffff,
47 0x1ffff,
48 0x3ffff,
49 0x7ffff,
50 0xfffff,
51 0x1fffff,
52 0x3fffff,
53 0x7fffff,
54 0xffffff,
55 0x1ffffff,
56 0x3ffffff,
57 0x7ffffff,
58 0xfffffff,
59 0x1fffffff,
60 0x3fffffff,
61 0x7fffffff,
62 0xffffffff,
63 0x1ffffffff,
64 0x3ffffffff,
65 0x7ffffffff,
66 0xfffffffff,
67 0x1fffffffff,
68 0x3fffffffff,
69 0x7fffffffff,
70 0xffffffffff,
71 0x1ffffffffff,
72 0x3ffffffffff,
73 0x7ffffffffff,
74 0xfffffffffff,
75 0x1fffffffffff,
76 0x3fffffffffff,
77 0x7fffffffffff,
78 0xffffffffffff,
79 0x1ffffffffffff,
80 0x3ffffffffffff,
81 0x7ffffffffffff,
82 0xfffffffffffff,
83 0x1fffffffffffff,
84 0x3fffffffffffff,
85 0x7fffffffffffff,
86 0xffffffffffffff,
87 0x1ffffffffffffff,
88 0x3ffffffffffffff,
89 0x7ffffffffffffff,
90 0xfffffffffffffff,
91 0x1fffffffffffffff,
92 0x3fffffffffffffff,
93 0x7fffffffffffffff,
94 0xffffffffffffffff};
95
96// UPPER_MASKS contains masks with all the highest bits set until a specific value
97// UPPER_MASKS[0] has the 0 highest bits set, i.e.:
98// 0b0000000000000000000000000000000000000000000000000000000000000000,
99// UPPER_MASKS[10] has the 10 highest bits set, i.e.:
100// 0b1111111111110000000000000000000000000000000000000000000000000000,
101// etc...
102// 0b1111111111111111111111110000000000000000000000000000000000000000,
103// ...
104// 0b1111111111111111111111111111111111111110000000000000000000000000,
105// until UPPER_MASKS[64], which has all bits set:
106// 0b1111111111111111111111111111111111111111111111111111111111111111
107// generated with this python snippet:
108// for i in range(65):
109// print(hex(int(i * '1' + (64 - i) * '0', 2)) + ",")
110const validity_t ValidityUncompressed::UPPER_MASKS[] = {0x0,
111 0x8000000000000000,
112 0xc000000000000000,
113 0xe000000000000000,
114 0xf000000000000000,
115 0xf800000000000000,
116 0xfc00000000000000,
117 0xfe00000000000000,
118 0xff00000000000000,
119 0xff80000000000000,
120 0xffc0000000000000,
121 0xffe0000000000000,
122 0xfff0000000000000,
123 0xfff8000000000000,
124 0xfffc000000000000,
125 0xfffe000000000000,
126 0xffff000000000000,
127 0xffff800000000000,
128 0xffffc00000000000,
129 0xffffe00000000000,
130 0xfffff00000000000,
131 0xfffff80000000000,
132 0xfffffc0000000000,
133 0xfffffe0000000000,
134 0xffffff0000000000,
135 0xffffff8000000000,
136 0xffffffc000000000,
137 0xffffffe000000000,
138 0xfffffff000000000,
139 0xfffffff800000000,
140 0xfffffffc00000000,
141 0xfffffffe00000000,
142 0xffffffff00000000,
143 0xffffffff80000000,
144 0xffffffffc0000000,
145 0xffffffffe0000000,
146 0xfffffffff0000000,
147 0xfffffffff8000000,
148 0xfffffffffc000000,
149 0xfffffffffe000000,
150 0xffffffffff000000,
151 0xffffffffff800000,
152 0xffffffffffc00000,
153 0xffffffffffe00000,
154 0xfffffffffff00000,
155 0xfffffffffff80000,
156 0xfffffffffffc0000,
157 0xfffffffffffe0000,
158 0xffffffffffff0000,
159 0xffffffffffff8000,
160 0xffffffffffffc000,
161 0xffffffffffffe000,
162 0xfffffffffffff000,
163 0xfffffffffffff800,
164 0xfffffffffffffc00,
165 0xfffffffffffffe00,
166 0xffffffffffffff00,
167 0xffffffffffffff80,
168 0xffffffffffffffc0,
169 0xffffffffffffffe0,
170 0xfffffffffffffff0,
171 0xfffffffffffffff8,
172 0xfffffffffffffffc,
173 0xfffffffffffffffe,
174 0xffffffffffffffff};
175
176//===--------------------------------------------------------------------===//
177// Analyze
178//===--------------------------------------------------------------------===//
179struct ValidityAnalyzeState : public AnalyzeState {
180 ValidityAnalyzeState() : count(0) {
181 }
182
183 idx_t count;
184};
185
186unique_ptr<AnalyzeState> ValidityInitAnalyze(ColumnData &col_data, PhysicalType type) {
187 return make_uniq<ValidityAnalyzeState>();
188}
189
190bool ValidityAnalyze(AnalyzeState &state_p, Vector &input, idx_t count) {
191 auto &state = state_p.Cast<ValidityAnalyzeState>();
192 state.count += count;
193 return true;
194}
195
196idx_t ValidityFinalAnalyze(AnalyzeState &state_p) {
197 auto &state = state_p.Cast<ValidityAnalyzeState>();
198 return (state.count + 7) / 8;
199}
200
201//===--------------------------------------------------------------------===//
202// Scan
203//===--------------------------------------------------------------------===//
204struct ValidityScanState : public SegmentScanState {
205 BufferHandle handle;
206 block_id_t block_id;
207};
208
209unique_ptr<SegmentScanState> ValidityInitScan(ColumnSegment &segment) {
210 auto result = make_uniq<ValidityScanState>();
211 auto &buffer_manager = BufferManager::GetBufferManager(db&: segment.db);
212 result->handle = buffer_manager.Pin(handle&: segment.block);
213 result->block_id = segment.block->BlockId();
214 return std::move(result);
215}
216
217//===--------------------------------------------------------------------===//
218// Scan base data
219//===--------------------------------------------------------------------===//
220void ValidityScanPartial(ColumnSegment &segment, ColumnScanState &state, idx_t scan_count, Vector &result,
221 idx_t result_offset) {
222 auto start = segment.GetRelativeIndex(row_index: state.row_index);
223
224 static_assert(sizeof(validity_t) == sizeof(uint64_t), "validity_t should be 64-bit");
225 auto &scan_state = state.scan_state->Cast<ValidityScanState>();
226
227 auto &result_mask = FlatVector::Validity(vector&: result);
228 auto buffer_ptr = scan_state.handle.Ptr() + segment.GetBlockOffset();
229 D_ASSERT(scan_state.block_id == segment.block->BlockId());
230 auto input_data = reinterpret_cast<validity_t *>(buffer_ptr);
231
232#ifdef DEBUG
233 // this method relies on all the bits we are going to write to being set to valid
234 for (idx_t i = 0; i < scan_count; i++) {
235 D_ASSERT(result_mask.RowIsValid(result_offset + i));
236 }
237#endif
238#if STANDARD_VECTOR_SIZE < 128
239 // fallback for tiny vector sizes
240 // the bitwise ops we use below don't work if the vector size is too small
241 ValidityMask source_mask(input_data);
242 for (idx_t i = 0; i < scan_count; i++) {
243 if (!source_mask.RowIsValid(start + i)) {
244 if (result_mask.AllValid()) {
245 result_mask.Initialize(MaxValue<idx_t>(STANDARD_VECTOR_SIZE, result_offset + scan_count));
246 }
247 result_mask.SetInvalid(result_offset + i);
248 }
249 }
250#else
251 // the code below does what the fallback code above states, but using bitwise ops:
252 auto result_data = (validity_t *)result_mask.GetData();
253
254 // set up the initial positions
255 // we need to find the validity_entry to modify, together with the bit-index WITHIN the validity entry
256 idx_t result_entry = result_offset / ValidityMask::BITS_PER_VALUE;
257 idx_t result_idx = result_offset - result_entry * ValidityMask::BITS_PER_VALUE;
258
259 // same for the input: find the validity_entry we are pulling from, together with the bit-index WITHIN that entry
260 idx_t input_entry = start / ValidityMask::BITS_PER_VALUE;
261 idx_t input_idx = start - input_entry * ValidityMask::BITS_PER_VALUE;
262
263 // now start the bit games
264 idx_t pos = 0;
265 while (pos < scan_count) {
266 // these are the current validity entries we are dealing with
267 idx_t current_result_idx = result_entry;
268 idx_t offset;
269 validity_t input_mask = input_data[input_entry];
270
271 // construct the mask to AND together with the result
272 if (result_idx < input_idx) {
273 // we have to shift the input RIGHT if the result_idx is smaller than the input_idx
274 auto shift_amount = input_idx - result_idx;
275 D_ASSERT(shift_amount > 0 && shift_amount <= ValidityMask::BITS_PER_VALUE);
276
277 input_mask = input_mask >> shift_amount;
278
279 // now the upper "shift_amount" bits are set to 0
280 // we need them to be set to 1
281 // otherwise the subsequent bitwise & will modify values outside of the range of values we want to alter
282 input_mask |= ValidityUncompressed::UPPER_MASKS[shift_amount];
283
284 // after this, we move to the next input_entry
285 offset = ValidityMask::BITS_PER_VALUE - input_idx;
286 input_entry++;
287 input_idx = 0;
288 result_idx += offset;
289 } else if (result_idx > input_idx) {
290 // we have to shift the input LEFT if the result_idx is bigger than the input_idx
291 auto shift_amount = result_idx - input_idx;
292 D_ASSERT(shift_amount > 0 && shift_amount <= ValidityMask::BITS_PER_VALUE);
293
294 // to avoid overflows, we set the upper "shift_amount" values to 0 first
295 input_mask = (input_mask & ~ValidityUncompressed::UPPER_MASKS[shift_amount]) << shift_amount;
296
297 // now the lower "shift_amount" bits are set to 0
298 // we need them to be set to 1
299 // otherwise the subsequent bitwise & will modify values outside of the range of values we want to alter
300 input_mask |= ValidityUncompressed::LOWER_MASKS[shift_amount];
301
302 // after this, we move to the next result_entry
303 offset = ValidityMask::BITS_PER_VALUE - result_idx;
304 result_entry++;
305 result_idx = 0;
306 input_idx += offset;
307 } else {
308 // if the input_idx is equal to result_idx they are already aligned
309 // we just move to the next entry for both after this
310 offset = ValidityMask::BITS_PER_VALUE - result_idx;
311 input_entry++;
312 result_entry++;
313 result_idx = input_idx = 0;
314 }
315 // now we need to check if we should include the ENTIRE mask
316 // OR if we need to mask from the right side
317 pos += offset;
318 if (pos > scan_count) {
319 // we need to set any bits that are past the scan_count on the right-side to 1
320 // this is required so we don't influence any bits that are not part of the scan
321 input_mask |= ValidityUncompressed::UPPER_MASKS[pos - scan_count];
322 }
323 // now finally we can merge the input mask with the result mask
324 if (input_mask != ValidityMask::ValidityBuffer::MAX_ENTRY) {
325 if (!result_data) {
326 result_mask.Initialize(count: MaxValue<idx_t>(STANDARD_VECTOR_SIZE, b: result_offset + scan_count));
327 result_data = (validity_t *)result_mask.GetData();
328 }
329 result_data[current_result_idx] &= input_mask;
330 }
331 }
332#endif
333
334#ifdef DEBUG
335 // verify that we actually accomplished the bitwise ops equivalent that we wanted to do
336 ValidityMask input_mask(input_data);
337 for (idx_t i = 0; i < scan_count; i++) {
338 D_ASSERT(result_mask.RowIsValid(result_offset + i) == input_mask.RowIsValid(start + i));
339 }
340#endif
341}
342
343void ValidityScan(ColumnSegment &segment, ColumnScanState &state, idx_t scan_count, Vector &result) {
344 result.Flatten(count: scan_count);
345
346 auto start = segment.GetRelativeIndex(row_index: state.row_index);
347 if (start % ValidityMask::BITS_PER_VALUE == 0) {
348 auto &scan_state = state.scan_state->Cast<ValidityScanState>();
349
350 // aligned scan: no need to do anything fancy
351 // note: this is only an optimization which avoids having to do messy bitshifting in the common case
352 // it is not required for correctness
353 auto &result_mask = FlatVector::Validity(vector&: result);
354 auto buffer_ptr = scan_state.handle.Ptr() + segment.GetBlockOffset();
355 D_ASSERT(scan_state.block_id == segment.block->BlockId());
356 auto input_data = reinterpret_cast<validity_t *>(buffer_ptr);
357 auto result_data = result_mask.GetData();
358 idx_t start_offset = start / ValidityMask::BITS_PER_VALUE;
359 idx_t entry_scan_count = (scan_count + ValidityMask::BITS_PER_VALUE - 1) / ValidityMask::BITS_PER_VALUE;
360 for (idx_t i = 0; i < entry_scan_count; i++) {
361 auto input_entry = input_data[start_offset + i];
362 if (!result_data && input_entry == ValidityMask::ValidityBuffer::MAX_ENTRY) {
363 continue;
364 }
365 if (!result_data) {
366 result_mask.Initialize(count: MaxValue<idx_t>(STANDARD_VECTOR_SIZE, b: scan_count));
367 result_data = result_mask.GetData();
368 }
369 result_data[i] = input_entry;
370 }
371 } else {
372 // unaligned scan: fall back to scan_partial which does bitshift tricks
373 ValidityScanPartial(segment, state, scan_count, result, result_offset: 0);
374 }
375}
376
377//===--------------------------------------------------------------------===//
378// Fetch
379//===--------------------------------------------------------------------===//
380void ValidityFetchRow(ColumnSegment &segment, ColumnFetchState &state, row_t row_id, Vector &result, idx_t result_idx) {
381 D_ASSERT(row_id >= 0 && row_id < row_t(segment.count));
382 auto &buffer_manager = BufferManager::GetBufferManager(db&: segment.db);
383 auto handle = buffer_manager.Pin(handle&: segment.block);
384 auto dataptr = handle.Ptr() + segment.GetBlockOffset();
385 ValidityMask mask(reinterpret_cast<validity_t *>(dataptr));
386 auto &result_mask = FlatVector::Validity(vector&: result);
387 if (!mask.RowIsValidUnsafe(row_idx: row_id)) {
388 result_mask.SetInvalid(result_idx);
389 }
390}
391
392//===--------------------------------------------------------------------===//
393// Append
394//===--------------------------------------------------------------------===//
395static unique_ptr<CompressionAppendState> ValidityInitAppend(ColumnSegment &segment) {
396 auto &buffer_manager = BufferManager::GetBufferManager(db&: segment.db);
397 auto handle = buffer_manager.Pin(handle&: segment.block);
398 return make_uniq<CompressionAppendState>(args: std::move(handle));
399}
400
401unique_ptr<CompressedSegmentState> ValidityInitSegment(ColumnSegment &segment, block_id_t block_id) {
402 auto &buffer_manager = BufferManager::GetBufferManager(db&: segment.db);
403 if (block_id == INVALID_BLOCK) {
404 auto handle = buffer_manager.Pin(handle&: segment.block);
405 memset(s: handle.Ptr(), c: 0xFF, n: segment.SegmentSize());
406 }
407 return nullptr;
408}
409
410idx_t ValidityAppend(CompressionAppendState &append_state, ColumnSegment &segment, SegmentStatistics &stats,
411 UnifiedVectorFormat &data, idx_t offset, idx_t vcount) {
412 D_ASSERT(segment.GetBlockOffset() == 0);
413 auto &validity_stats = stats.statistics;
414
415 auto max_tuples = segment.SegmentSize() / ValidityMask::STANDARD_MASK_SIZE * STANDARD_VECTOR_SIZE;
416 idx_t append_count = MinValue<idx_t>(a: vcount, b: max_tuples - segment.count);
417 if (data.validity.AllValid()) {
418 // no null values: skip append
419 segment.count += append_count;
420 validity_stats.SetHasNoNull();
421 return append_count;
422 }
423
424 ValidityMask mask(reinterpret_cast<validity_t *>(append_state.handle.Ptr()));
425 for (idx_t i = 0; i < append_count; i++) {
426 auto idx = data.sel->get_index(idx: offset + i);
427 if (!data.validity.RowIsValidUnsafe(row_idx: idx)) {
428 mask.SetInvalidUnsafe(segment.count + i);
429 validity_stats.SetHasNull();
430 } else {
431 validity_stats.SetHasNoNull();
432 }
433 }
434 segment.count += append_count;
435 return append_count;
436}
437
438idx_t ValidityFinalizeAppend(ColumnSegment &segment, SegmentStatistics &stats) {
439 return ((segment.count + STANDARD_VECTOR_SIZE - 1) / STANDARD_VECTOR_SIZE) * ValidityMask::STANDARD_MASK_SIZE;
440}
441
442void ValidityRevertAppend(ColumnSegment &segment, idx_t start_row) {
443 idx_t start_bit = start_row - segment.start;
444
445 auto &buffer_manager = BufferManager::GetBufferManager(db&: segment.db);
446 auto handle = buffer_manager.Pin(handle&: segment.block);
447 idx_t revert_start;
448 if (start_bit % 8 != 0) {
449 // handle sub-bit stuff (yay)
450 idx_t byte_pos = start_bit / 8;
451 idx_t bit_start = byte_pos * 8;
452 idx_t bit_end = (byte_pos + 1) * 8;
453 ValidityMask mask(reinterpret_cast<validity_t *>(handle.Ptr() + byte_pos));
454 for (idx_t i = start_bit; i < bit_end; i++) {
455 mask.SetValid(i - bit_start);
456 }
457 revert_start = bit_end / 8;
458 } else {
459 revert_start = start_bit / 8;
460 }
461 // for the rest, we just memset
462 memset(s: handle.Ptr() + revert_start, c: 0xFF, n: segment.SegmentSize() - revert_start);
463}
464
465//===--------------------------------------------------------------------===//
466// Get Function
467//===--------------------------------------------------------------------===//
468CompressionFunction ValidityUncompressed::GetFunction(PhysicalType data_type) {
469 D_ASSERT(data_type == PhysicalType::BIT);
470 return CompressionFunction(CompressionType::COMPRESSION_UNCOMPRESSED, data_type, ValidityInitAnalyze,
471 ValidityAnalyze, ValidityFinalAnalyze, UncompressedFunctions::InitCompression,
472 UncompressedFunctions::Compress, UncompressedFunctions::FinalizeCompress,
473 ValidityInitScan, ValidityScan, ValidityScanPartial, ValidityFetchRow,
474 UncompressedFunctions::EmptySkip, ValidityInitSegment, ValidityInitAppend,
475 ValidityAppend, ValidityFinalizeAppend, ValidityRevertAppend);
476}
477
478} // namespace duckdb
479