1//===----------------------------------------------------------------------===//
2// DuckDB
3//
4// duckdb/execution/index/art/art.hpp
5//
6//
7//===----------------------------------------------------------------------===//
8
9#pragma once
10
11#include "duckdb/storage/index.hpp"
12
13namespace duckdb {
14
15// classes
16enum class VerifyExistenceType : uint8_t {
17 APPEND = 0, // appends to a table
18 APPEND_FK = 1, // appends to a table that has a foreign key
19 DELETE_FK = 2 // delete from a table that has a foreign key
20};
21class ConflictManager;
22class Node;
23class ARTKey;
24class FixedSizeAllocator;
25
26// structs
27struct ARTIndexScanState;
28struct ARTFlags {
29 vector<bool> vacuum_flags;
30 vector<idx_t> merge_buffer_counts;
31};
32
33class ART : public Index {
34public:
35 //! Constructs an ART
36 ART(const vector<column_t> &column_ids, TableIOManager &table_io_manager,
37 const vector<unique_ptr<Expression>> &unbound_expressions, const IndexConstraintType constraint_type,
38 AttachedDatabase &db, const idx_t block_id = DConstants::INVALID_INDEX,
39 const idx_t block_offset = DConstants::INVALID_INDEX);
40 ~ART() override;
41
42 //! Root of the tree
43 unique_ptr<Node> tree;
44 //! Fixed-size allocators holding the ART nodes
45 vector<unique_ptr<FixedSizeAllocator>> allocators;
46
47public:
48 //! Initialize a single predicate scan on the index with the given expression and column IDs
49 unique_ptr<IndexScanState> InitializeScanSinglePredicate(const Transaction &transaction, const Value &value,
50 const ExpressionType expression_type) override;
51 //! Initialize a two predicate scan on the index with the given expression and column IDs
52 unique_ptr<IndexScanState> InitializeScanTwoPredicates(const Transaction &transaction, const Value &low_value,
53 const ExpressionType low_expression_type,
54 const Value &high_value,
55 const ExpressionType high_expression_type) override;
56 //! Performs a lookup on the index, fetching up to max_count result IDs. Returns true if all row IDs were fetched,
57 //! and false otherwise
58 bool Scan(const Transaction &transaction, const DataTable &table, IndexScanState &state, const idx_t max_count,
59 vector<row_t> &result_ids) override;
60
61 //! Called when data is appended to the index. The lock obtained from InitializeLock must be held
62 PreservedError Append(IndexLock &lock, DataChunk &entries, Vector &row_identifiers) override;
63 //! Verify that data can be appended to the index without a constraint violation
64 void VerifyAppend(DataChunk &chunk) override;
65 //! Verify that data can be appended to the index without a constraint violation using the conflict manager
66 void VerifyAppend(DataChunk &chunk, ConflictManager &conflict_manager) override;
67 //! Delete a chunk of entries from the index. The lock obtained from InitializeLock must be held
68 void Delete(IndexLock &lock, DataChunk &entries, Vector &row_identifiers) override;
69 //! Insert a chunk of entries into the index
70 PreservedError Insert(IndexLock &lock, DataChunk &data, Vector &row_ids) override;
71
72 //! Construct an ART from a vector of sorted keys
73 bool ConstructFromSorted(idx_t count, vector<ARTKey> &keys, Vector &row_identifiers);
74
75 //! Search equal values and fetches the row IDs
76 bool SearchEqual(ARTKey &key, idx_t max_count, vector<row_t> &result_ids);
77 //! Search equal values used for joins that do not need to fetch data
78 void SearchEqualJoinNoFetch(ARTKey &key, idx_t &result_size);
79
80 //! Serializes the index and returns the pair of block_id offset positions
81 BlockPointer Serialize(MetaBlockWriter &writer) override;
82
83 //! Merge another index into this index. The lock obtained from InitializeLock must be held, and the other
84 //! index must also be locked during the merge
85 bool MergeIndexes(IndexLock &state, Index &other_index) override;
86
87 //! Traverses an ART and vacuums the qualifying nodes. The lock obtained from InitializeLock must be held
88 void Vacuum(IndexLock &state) override;
89
90 //! Generate ART keys for an input chunk
91 static void GenerateKeys(ArenaAllocator &allocator, DataChunk &input, vector<ARTKey> &keys);
92
93 //! Generate a string containing all the expressions and their respective values that violate a constraint
94 string GenerateErrorKeyName(DataChunk &input, idx_t row);
95 //! Generate the matching error message for a constraint violation
96 string GenerateConstraintErrorMessage(VerifyExistenceType verify_type, const string &key_name);
97 //! Performs constraint checking for a chunk of input data
98 void CheckConstraintsForChunk(DataChunk &input, ConflictManager &conflict_manager) override;
99
100 //! Returns the string representation of the ART, or only traverses and verifies the index
101 string VerifyAndToString(IndexLock &state, const bool only_verify) override;
102
103 //! Find the node with a matching key, or return nullptr if not found
104 Node Lookup(Node node, const ARTKey &key, idx_t depth);
105
106private:
107 //! Insert a row ID into a leaf
108 bool InsertToLeaf(Node &leaf_node, const row_t &row_id);
109 //! Insert a key into the tree
110 bool Insert(Node &node, const ARTKey &key, idx_t depth, const row_t &row_id);
111 //! Erase a key from the tree (if a leaf has more than one value) or erase the leaf itself
112 void Erase(Node &node, const ARTKey &key, idx_t depth, const row_t &row_id);
113
114 //! Returns all row IDs belonging to a key greater (or equal) than the search key
115 bool SearchGreater(ARTIndexScanState &state, ARTKey &key, bool inclusive, idx_t max_count,
116 vector<row_t> &result_ids);
117 //! Returns all row IDs belonging to a key less (or equal) than the upper_bound
118 bool SearchLess(ARTIndexScanState &state, ARTKey &upper_bound, bool inclusive, idx_t max_count,
119 vector<row_t> &result_ids);
120 //! Returns all row IDs belonging to a key within the range of lower_bound and upper_bound
121 bool SearchCloseRange(ARTIndexScanState &state, ARTKey &lower_bound, ARTKey &upper_bound, bool left_inclusive,
122 bool right_inclusive, idx_t max_count, vector<row_t> &result_ids);
123
124 //! Initializes a merge operation by returning a set containing the buffer count of each fixed-size allocator
125 void InitializeMerge(ARTFlags &flags);
126
127 //! Initializes a vacuum operation by calling the initialize operation of the respective
128 //! node allocator, and returns a vector containing either true, if the allocator at
129 //! the respective position qualifies, or false, if not
130 void InitializeVacuum(ARTFlags &flags);
131 //! Finalizes a vacuum operation by calling the finalize operation of all qualifying
132 //! fixed size allocators
133 void FinalizeVacuum(const ARTFlags &flags);
134
135 //! Internal function to return the string representation of the ART,
136 //! or only traverses and verifies the index
137 string VerifyAndToStringInternal(const bool only_verify);
138};
139
140} // namespace duckdb
141