1#include "duckdb/common/limits.hpp"
2#include "duckdb/common/swap.hpp"
3#include "duckdb/execution/index/art/art.hpp"
4#include "duckdb/execution/index/art/leaf.hpp"
5#include "duckdb/execution/index/art/leaf_segment.hpp"
6#include "duckdb/execution/index/art/node.hpp"
7#include "duckdb/execution/index/art/node16.hpp"
8#include "duckdb/execution/index/art/node256.hpp"
9#include "duckdb/execution/index/art/node4.hpp"
10#include "duckdb/execution/index/art/node48.hpp"
11#include "duckdb/execution/index/art/prefix.hpp"
12#include "duckdb/execution/index/art/prefix_segment.hpp"
13#include "duckdb/storage/meta_block_reader.hpp"
14#include "duckdb/storage/meta_block_writer.hpp"
15#include "duckdb/storage/table_io_manager.hpp"
16
17namespace duckdb {
18
19//===--------------------------------------------------------------------===//
20// Constructors / Destructors
21//===--------------------------------------------------------------------===//
22
23Node::Node() : SwizzleablePointer() {
24}
25
26Node::Node(MetaBlockReader &reader) : SwizzleablePointer(reader) {
27}
28
29void Node::New(ART &art, Node &node, const NType type) {
30
31 switch (type) {
32 case NType::PREFIX_SEGMENT:
33 PrefixSegment::New(art, node);
34 break;
35 case NType::LEAF_SEGMENT:
36 LeafSegment::New(art, node);
37 break;
38 case NType::NODE_4:
39 Node4::New(art, node);
40 break;
41 case NType::NODE_16:
42 Node16::New(art, node);
43 break;
44 case NType::NODE_48:
45 Node48::New(art, node);
46 break;
47 case NType::NODE_256:
48 Node256::New(art, node);
49 break;
50 default:
51 throw InternalException("Invalid node type for New.");
52 }
53}
54
55void Node::Free(ART &art, Node &node) {
56
57 // recursively free all nodes that are in-memory, and skip swizzled and empty nodes
58
59 if (!node.IsSet()) {
60 return;
61 }
62
63 if (!node.IsSwizzled()) {
64
65 auto type = node.DecodeARTNodeType();
66 if (type != NType::PREFIX_SEGMENT && type != NType::LEAF_SEGMENT) {
67 node.GetPrefix(art).Free(art);
68 }
69
70 // free the prefixes and children of the nodes
71 switch (type) {
72 case NType::LEAF_SEGMENT:
73 LeafSegment::Free(art, node);
74 break;
75 case NType::LEAF:
76 Leaf::Free(art, node);
77 break;
78 case NType::NODE_4:
79 Node4::Free(art, node);
80 break;
81 case NType::NODE_16:
82 Node16::Free(art, node);
83 break;
84 case NType::NODE_48:
85 Node48::Free(art, node);
86 break;
87 case NType::NODE_256:
88 Node256::Free(art, node);
89 break;
90 default:
91 break;
92 }
93
94 Node::GetAllocator(art, type).Free(ptr: node);
95 }
96
97 // overwrite with an empty ART node
98 node.Reset();
99}
100
101//===--------------------------------------------------------------------===//
102// Inserts
103//===--------------------------------------------------------------------===//
104
105void Node::ReplaceChild(const ART &art, const uint8_t byte, const Node child) {
106
107 D_ASSERT(!IsSwizzled());
108
109 switch (DecodeARTNodeType()) {
110 case NType::NODE_4:
111 return Node4::Get(art, ptr: *this).ReplaceChild(byte, child);
112 case NType::NODE_16:
113 return Node16::Get(art, ptr: *this).ReplaceChild(byte, child);
114 case NType::NODE_48:
115 return Node48::Get(art, ptr: *this).ReplaceChild(byte, child);
116 case NType::NODE_256:
117 return Node256::Get(art, ptr: *this).ReplaceChild(byte, child);
118 default:
119 throw InternalException("Invalid node type for ReplaceChild.");
120 }
121}
122
123void Node::InsertChild(ART &art, Node &node, const uint8_t byte, const Node child) {
124
125 switch (node.DecodeARTNodeType()) {
126 case NType::NODE_4:
127 return Node4::InsertChild(art, node, byte, child);
128 case NType::NODE_16:
129 return Node16::InsertChild(art, node, byte, child);
130 case NType::NODE_48:
131 return Node48::InsertChild(art, node, byte, child);
132 case NType::NODE_256:
133 return Node256::InsertChild(art, node, byte, child);
134 default:
135 throw InternalException("Invalid node type for InsertChild.");
136 }
137}
138
139//===--------------------------------------------------------------------===//
140// Deletes
141//===--------------------------------------------------------------------===//
142
143void Node::DeleteChild(ART &art, Node &node, const uint8_t byte) {
144
145 switch (node.DecodeARTNodeType()) {
146 case NType::NODE_4:
147 return Node4::DeleteChild(art, node, byte);
148 case NType::NODE_16:
149 return Node16::DeleteChild(art, node, byte);
150 case NType::NODE_48:
151 return Node48::DeleteChild(art, node, byte);
152 case NType::NODE_256:
153 return Node256::DeleteChild(art, node, byte);
154 default:
155 throw InternalException("Invalid node type for DeleteChild.");
156 }
157}
158
159//===--------------------------------------------------------------------===//
160// Get functions
161//===--------------------------------------------------------------------===//
162
163optional_ptr<Node> Node::GetChild(ART &art, const uint8_t byte) const {
164
165 D_ASSERT(IsSet() && !IsSwizzled());
166
167 optional_ptr<Node> child;
168 switch (DecodeARTNodeType()) {
169 case NType::NODE_4:
170 child = Node4::Get(art, ptr: *this).GetChild(byte);
171 break;
172 case NType::NODE_16:
173 child = Node16::Get(art, ptr: *this).GetChild(byte);
174 break;
175 case NType::NODE_48:
176 child = Node48::Get(art, ptr: *this).GetChild(byte);
177 break;
178 case NType::NODE_256:
179 child = Node256::Get(art, ptr: *this).GetChild(byte);
180 break;
181 default:
182 throw InternalException("Invalid node type for GetChild.");
183 }
184
185 // deserialize the ART node before returning it
186 if (child && child->IsSwizzled()) {
187 child->Deserialize(art);
188 }
189 return child;
190}
191
192optional_ptr<Node> Node::GetNextChild(ART &art, uint8_t &byte, const bool deserialize) const {
193
194 D_ASSERT(IsSet() && !IsSwizzled());
195
196 optional_ptr<Node> child;
197 switch (DecodeARTNodeType()) {
198 case NType::NODE_4:
199 child = Node4::Get(art, ptr: *this).GetNextChild(byte);
200 break;
201 case NType::NODE_16:
202 child = Node16::Get(art, ptr: *this).GetNextChild(byte);
203 break;
204 case NType::NODE_48:
205 child = Node48::Get(art, ptr: *this).GetNextChild(byte);
206 break;
207 case NType::NODE_256:
208 child = Node256::Get(art, ptr: *this).GetNextChild(byte);
209 break;
210 default:
211 throw InternalException("Invalid node type for GetNextChild.");
212 }
213
214 // deserialize the ART node before returning it
215 if (child && deserialize && child->IsSwizzled()) {
216 child->Deserialize(art);
217 }
218 return child;
219}
220
221//===--------------------------------------------------------------------===//
222// (De)serialization
223//===--------------------------------------------------------------------===//
224
225BlockPointer Node::Serialize(ART &art, MetaBlockWriter &writer) {
226
227 if (!IsSet()) {
228 return {(block_id_t)DConstants::INVALID_INDEX, 0};
229 }
230
231 if (IsSwizzled()) {
232 Deserialize(art);
233 }
234
235 switch (DecodeARTNodeType()) {
236 case NType::LEAF:
237 return Leaf::Get(art, ptr: *this).Serialize(art, writer);
238 case NType::NODE_4:
239 return Node4::Get(art, ptr: *this).Serialize(art, writer);
240 case NType::NODE_16:
241 return Node16::Get(art, ptr: *this).Serialize(art, writer);
242 case NType::NODE_48:
243 return Node48::Get(art, ptr: *this).Serialize(art, writer);
244 case NType::NODE_256:
245 return Node256::Get(art, ptr: *this).Serialize(art, writer);
246 default:
247 throw InternalException("Invalid node type for Serialize.");
248 }
249}
250
251void Node::Deserialize(ART &art) {
252
253 MetaBlockReader reader(art.table_io_manager.GetIndexBlockManager(), buffer_id);
254 reader.offset = offset;
255 type = reader.Read<uint8_t>();
256 swizzle_flag = 0;
257
258 auto decoded_type = DecodeARTNodeType();
259 SetPtr(Node::GetAllocator(art, type: decoded_type).New());
260 type = (uint8_t)decoded_type;
261
262 switch (decoded_type) {
263 case NType::LEAF:
264 return Leaf::Get(art, ptr: *this).Deserialize(art, reader);
265 case NType::NODE_4:
266 return Node4::Get(art, ptr: *this).Deserialize(art, reader);
267 case NType::NODE_16:
268 return Node16::Get(art, ptr: *this).Deserialize(art, reader);
269 case NType::NODE_48:
270 return Node48::Get(art, ptr: *this).Deserialize(art, reader);
271 case NType::NODE_256:
272 return Node256::Get(art, ptr: *this).Deserialize(art, reader);
273 default:
274 throw InternalException("Invalid node type for Deserialize.");
275 }
276}
277
278//===--------------------------------------------------------------------===//
279// Utility
280//===--------------------------------------------------------------------===//
281
282string Node::VerifyAndToString(ART &art, const bool only_verify) {
283
284 D_ASSERT(IsSet());
285 if (IsSwizzled()) {
286 return only_verify ? "" : "swizzled";
287 }
288
289 auto type = DecodeARTNodeType();
290 if (type == NType::LEAF) {
291 auto str = Leaf::Get(art, ptr: *this).VerifyAndToString(art, only_verify);
292 return only_verify ? "" : "\n" + str;
293 }
294
295 string str = "Node" + to_string(val: GetCapacity()) + ": [";
296
297 idx_t child_count = 0;
298 uint8_t byte = 0;
299 auto child = GetNextChild(art, byte, deserialize: false);
300 while (child) {
301 child_count++;
302 if (child->IsSwizzled()) {
303 if (!only_verify) {
304 str += "(swizzled)";
305 }
306 } else {
307 str += "(" + to_string(val: byte) + ", " + child->VerifyAndToString(art, only_verify) + ")";
308 if (byte == NumericLimits<uint8_t>::Maximum()) {
309 break;
310 }
311 }
312 byte++;
313 child = GetNextChild(art, byte, deserialize: false);
314 }
315
316 (void)child_count;
317 // ensure that the child count is at least two
318 D_ASSERT(child_count > 1);
319 return only_verify ? "" : "\n" + str + "]";
320}
321
322idx_t Node::GetCapacity() const {
323
324 D_ASSERT(!IsSwizzled());
325
326 switch (DecodeARTNodeType()) {
327 case NType::NODE_4:
328 return Node::NODE_4_CAPACITY;
329 case NType::NODE_16:
330 return Node::NODE_16_CAPACITY;
331 case NType::NODE_48:
332 return Node::NODE_48_CAPACITY;
333 case NType::NODE_256:
334 return Node::NODE_256_CAPACITY;
335 default:
336 throw InternalException("Invalid node type for GetCapacity.");
337 }
338}
339
340Prefix &Node::GetPrefix(ART &art) {
341
342 if (IsSwizzled()) {
343 Deserialize(art);
344 }
345
346 switch (DecodeARTNodeType()) {
347 case NType::LEAF:
348 return Leaf::Get(art, ptr: *this).prefix;
349 case NType::NODE_4:
350 return Node4::Get(art, ptr: *this).prefix;
351 case NType::NODE_16:
352 return Node16::Get(art, ptr: *this).prefix;
353 case NType::NODE_48:
354 return Node48::Get(art, ptr: *this).prefix;
355 case NType::NODE_256:
356 return Node256::Get(art, ptr: *this).prefix;
357 default:
358 throw InternalException("Invalid node type for GetPrefix.");
359 }
360}
361
362NType Node::GetARTNodeTypeByCount(const idx_t count) {
363
364 if (count <= NODE_4_CAPACITY) {
365 return NType::NODE_4;
366 } else if (count <= NODE_16_CAPACITY) {
367 return NType::NODE_16;
368 } else if (count <= NODE_48_CAPACITY) {
369 return NType::NODE_48;
370 }
371 return NType::NODE_256;
372}
373
374FixedSizeAllocator &Node::GetAllocator(const ART &art, NType type) {
375 return *art.allocators[(uint8_t)type - 1];
376}
377
378//===--------------------------------------------------------------------===//
379// Merging
380//===--------------------------------------------------------------------===//
381
382void Node::InitializeMerge(ART &art, const ARTFlags &flags) {
383
384 if (!IsSet()) {
385 return;
386 }
387
388 if (IsSwizzled()) {
389 Deserialize(art);
390 }
391
392 // if not all prefixes are inlined
393 if (flags.merge_buffer_counts[(uint8_t)NType::PREFIX_SEGMENT - 1] != 0) {
394 // initialize prefix segments
395 GetPrefix(art).InitializeMerge(art, buffer_count: flags.merge_buffer_counts[(uint8_t)NType::PREFIX_SEGMENT - 1]);
396 }
397
398 auto type = DecodeARTNodeType();
399 switch (type) {
400 case NType::LEAF:
401 // if not all leaves are inlined
402 if (flags.merge_buffer_counts[(uint8_t)NType::LEAF_SEGMENT - 1] != 0) {
403 // initialize leaf segments
404 Leaf::Get(art, ptr: *this).InitializeMerge(art, buffer_count: flags.merge_buffer_counts[(uint8_t)NType::LEAF_SEGMENT - 1]);
405 }
406 break;
407 case NType::NODE_4:
408 Node4::Get(art, ptr: *this).InitializeMerge(art, flags);
409 break;
410 case NType::NODE_16:
411 Node16::Get(art, ptr: *this).InitializeMerge(art, flags);
412 break;
413 case NType::NODE_48:
414 Node48::Get(art, ptr: *this).InitializeMerge(art, flags);
415 break;
416 case NType::NODE_256:
417 Node256::Get(art, ptr: *this).InitializeMerge(art, flags);
418 break;
419 default:
420 throw InternalException("Invalid node type for InitializeMerge.");
421 }
422
423 buffer_id += flags.merge_buffer_counts[(uint8_t)type - 1];
424}
425
426bool Node::Merge(ART &art, Node &other) {
427
428 if (!IsSet()) {
429 *this = other;
430 other = Node();
431 return true;
432 }
433
434 return ResolvePrefixes(art, other);
435}
436
437bool Node::ResolvePrefixes(ART &art, Node &other) {
438
439 // NOTE: we always merge into the left ART
440
441 D_ASSERT(IsSet());
442 D_ASSERT(other.IsSet());
443
444 // make sure that r_node has the longer (or equally long) prefix
445 if (GetPrefix(art).count > other.GetPrefix(art).count) {
446 swap(a&: *this, b&: other);
447 }
448
449 auto &l_node = *this;
450 auto &r_node = other;
451 auto &l_prefix = l_node.GetPrefix(art);
452 auto &r_prefix = r_node.GetPrefix(art);
453
454 auto mismatch_position = l_prefix.MismatchPosition(art, other: r_prefix);
455
456 // both nodes have no prefix or the same prefix
457 if (mismatch_position == l_prefix.count && l_prefix.count == r_prefix.count) {
458 return MergeInternal(art, other&: r_node);
459 }
460
461 if (mismatch_position == l_prefix.count) {
462 // r_node's prefix contains l_node's prefix
463 // l_node cannot be a leaf, otherwise the key represented by l_node would be a subset of another key
464 // which is not possible by our construction
465 D_ASSERT(l_node.DecodeARTNodeType() != NType::LEAF);
466
467 // test if the next byte (mismatch_position) in r_node (longer prefix) exists in l_node
468 auto mismatch_byte = r_prefix.GetByte(art, position: mismatch_position);
469 auto child_node = l_node.GetChild(art, byte: mismatch_byte);
470
471 // update the prefix of r_node to only consist of the bytes after mismatch_position
472 r_prefix.Reduce(art, reduce_count: mismatch_position);
473
474 // insert r_node as a child of l_node at empty position
475 if (!child_node) {
476 Node::InsertChild(art, node&: l_node, byte: mismatch_byte, child: r_node);
477 r_node.Reset();
478 return true;
479 }
480
481 // recurse
482 return child_node->ResolvePrefixes(art, other&: r_node);
483 }
484
485 // prefixes differ, create new node and insert both nodes as children
486
487 // create new node
488 auto old_l_node = l_node;
489 auto &new_n4 = Node4::New(art, node&: l_node);
490 new_n4.prefix.Initialize(art, other: l_prefix, count_p: mismatch_position);
491
492 // insert old l_node, break up prefix of old l_node
493 auto key_byte = l_prefix.Reduce(art, reduce_count: mismatch_position);
494 Node4::InsertChild(art, node&: l_node, byte: key_byte, child: old_l_node);
495
496 // insert r_node, break up prefix of r_node
497 key_byte = r_prefix.Reduce(art, reduce_count: mismatch_position);
498 Node4::InsertChild(art, node&: l_node, byte: key_byte, child: r_node);
499
500 r_node.Reset();
501 return true;
502}
503
504bool Node::MergeInternal(ART &art, Node &other) {
505
506 D_ASSERT(IsSet());
507 D_ASSERT(other.IsSet());
508
509 // always try to merge the smaller node into the bigger node
510 // because maybe there is enough free space in the bigger node to fit the smaller one
511 // without too much recursion
512 if (this->DecodeARTNodeType() < other.DecodeARTNodeType()) {
513 swap(a&: *this, b&: other);
514 }
515
516 Node empty_node;
517 auto &l_node = *this;
518 auto &r_node = other;
519
520 if (r_node.DecodeARTNodeType() == NType::LEAF) {
521 D_ASSERT(l_node.DecodeARTNodeType() == NType::LEAF);
522
523 if (art.IsUnique()) {
524 return false;
525 }
526
527 Leaf::Get(art, ptr: *this).Merge(art, other&: r_node);
528 return true;
529 }
530
531 uint8_t byte = 0;
532 auto r_child = r_node.GetNextChild(art, byte);
533
534 // while r_node still has children to merge
535 while (r_child) {
536 auto l_child = l_node.GetChild(art, byte);
537 if (!l_child) {
538 // insert child at empty byte
539 Node::InsertChild(art, node&: l_node, byte, child: *r_child);
540 r_node.ReplaceChild(art, byte, child: empty_node);
541
542 } else {
543 // recurse
544 if (!l_child->ResolvePrefixes(art, other&: *r_child)) {
545 return false;
546 }
547 }
548
549 if (byte == NumericLimits<uint8_t>::Maximum()) {
550 break;
551 }
552 byte++;
553 r_child = r_node.GetNextChild(art, byte);
554 }
555
556 Node::Free(art, node&: r_node);
557 return true;
558}
559
560//===--------------------------------------------------------------------===//
561// Vacuum
562//===--------------------------------------------------------------------===//
563
564void Node::Vacuum(ART &art, Node &node, const ARTFlags &flags) {
565
566 if (node.IsSwizzled()) {
567 return;
568 }
569
570 // possibly vacuum prefix segments, if not all prefixes are inlined
571 bool needs_vacuum = flags.vacuum_flags[(uint8_t)NType::PREFIX_SEGMENT - 1];
572 if (needs_vacuum) {
573 // vacuum prefix segments
574 node.GetPrefix(art).Vacuum(art);
575 }
576
577 auto type = node.DecodeARTNodeType();
578 auto &allocator = Node::GetAllocator(art, type);
579 needs_vacuum = flags.vacuum_flags[node.type - 1] && allocator.NeedsVacuum(ptr: node);
580 if (needs_vacuum) {
581 node.SetPtr(allocator.VacuumPointer(ptr: node));
582 node.type = (uint8_t)type;
583 }
584
585 switch (type) {
586 case NType::LEAF: {
587 // possibly vacuum leaf segments, if not all leaves are inlined
588 if (flags.vacuum_flags[(uint8_t)NType::LEAF_SEGMENT - 1]) {
589 Leaf::Get(art, ptr: node).Vacuum(art);
590 }
591 return;
592 }
593 case NType::NODE_4:
594 return Node4::Get(art, ptr: node).Vacuum(art, flags);
595 case NType::NODE_16:
596 return Node16::Get(art, ptr: node).Vacuum(art, flags);
597 case NType::NODE_48:
598 return Node48::Get(art, ptr: node).Vacuum(art, flags);
599 case NType::NODE_256:
600 return Node256::Get(art, ptr: node).Vacuum(art, flags);
601 default:
602 throw InternalException("Invalid node type for Vacuum.");
603 }
604}
605
606} // namespace duckdb
607