1//===----------------------------------------------------------------------===//
2// DuckDB
3//
4// duckdb/storage/index.hpp
5//
6//
7//===----------------------------------------------------------------------===//
8
9#pragma once
10
11#include "duckdb/common/unordered_set.hpp"
12#include "duckdb/common/enums/index_type.hpp"
13#include "duckdb/common/types/data_chunk.hpp"
14#include "duckdb/common/sort/sort.hpp"
15#include "duckdb/parser/parsed_expression.hpp"
16#include "duckdb/planner/expression.hpp"
17#include "duckdb/storage/meta_block_writer.hpp"
18#include "duckdb/execution/expression_executor.hpp"
19#include "duckdb/common/types/constraint_conflict_info.hpp"
20
21namespace duckdb {
22
23class ClientContext;
24class TableIOManager;
25class Transaction;
26class ConflictManager;
27
28struct IndexLock;
29struct IndexScanState;
30
31//! The index is an abstract base class that serves as the basis for indexes
32class Index {
33public:
34 Index(AttachedDatabase &db, IndexType type, TableIOManager &table_io_manager, const vector<column_t> &column_ids,
35 const vector<unique_ptr<Expression>> &unbound_expressions, IndexConstraintType constraint_type);
36 virtual ~Index() = default;
37
38 //! The type of the index
39 IndexType type;
40 //! Associated table io manager
41 TableIOManager &table_io_manager;
42 //! Column identifiers to extract key columns from the base table
43 vector<column_t> column_ids;
44 //! Unordered set of column_ids used by the index
45 unordered_set<column_t> column_id_set;
46 //! Unbound expressions used by the index during optimizations
47 vector<unique_ptr<Expression>> unbound_expressions;
48 //! The physical types stored in the index
49 vector<PhysicalType> types;
50 //! The logical types of the expressions
51 vector<LogicalType> logical_types;
52 //! Index constraint type (primary key, foreign key, ...)
53 IndexConstraintType constraint_type;
54
55 //! Attached database instance
56 AttachedDatabase &db;
57 //! Buffer manager of the database instance
58 BufferManager &buffer_manager;
59
60public:
61 //! Initialize a single predicate scan on the index with the given expression and column IDs
62 virtual unique_ptr<IndexScanState> InitializeScanSinglePredicate(const Transaction &transaction, const Value &value,
63 const ExpressionType expression_type) = 0;
64 //! Initialize a two predicate scan on the index with the given expression and column IDs
65 virtual unique_ptr<IndexScanState> InitializeScanTwoPredicates(const Transaction &transaction,
66 const Value &low_value,
67 const ExpressionType low_expression_type,
68 const Value &high_value,
69 const ExpressionType high_expression_type) = 0;
70 //! Performs a lookup on the index, fetching up to max_count result IDs. Returns true if all row IDs were fetched,
71 //! and false otherwise
72 virtual bool Scan(const Transaction &transaction, const DataTable &table, IndexScanState &state,
73 const idx_t max_count, vector<row_t> &result_ids) = 0;
74
75 //! Obtain a lock on the index
76 virtual void InitializeLock(IndexLock &state);
77 //! Called when data is appended to the index. The lock obtained from InitializeLock must be held
78 virtual PreservedError Append(IndexLock &state, DataChunk &entries, Vector &row_identifiers) = 0;
79 //! Obtains a lock and calls Append while holding that lock
80 PreservedError Append(DataChunk &entries, Vector &row_identifiers);
81 //! Verify that data can be appended to the index without a constraint violation
82 virtual void VerifyAppend(DataChunk &chunk) = 0;
83 //! Verify that data can be appended to the index without a constraint violation using the conflict manager
84 virtual void VerifyAppend(DataChunk &chunk, ConflictManager &conflict_manager) = 0;
85 //! Performs constraint checking for a chunk of input data
86 virtual void CheckConstraintsForChunk(DataChunk &input, ConflictManager &conflict_manager) = 0;
87
88 //! Delete a chunk of entries from the index. The lock obtained from InitializeLock must be held
89 virtual void Delete(IndexLock &state, DataChunk &entries, Vector &row_identifiers) = 0;
90 //! Obtains a lock and calls Delete while holding that lock
91 void Delete(DataChunk &entries, Vector &row_identifiers);
92
93 //! Insert a chunk of entries into the index
94 virtual PreservedError Insert(IndexLock &lock, DataChunk &input, Vector &row_identifiers) = 0;
95
96 //! Merge another index into this index. The lock obtained from InitializeLock must be held, and the other
97 //! index must also be locked during the merge
98 virtual bool MergeIndexes(IndexLock &state, Index &other_index) = 0;
99 //! Obtains a lock and calls MergeIndexes while holding that lock
100 bool MergeIndexes(Index &other_index);
101
102 //! Traverses an ART and vacuums the qualifying nodes. The lock obtained from InitializeLock must be held
103 virtual void Vacuum(IndexLock &state) = 0;
104 //! Obtains a lock and calls Vacuum while holding that lock
105 void Vacuum();
106
107 //! Returns the string representation of an index, or only traverses and verifies the index
108 virtual string VerifyAndToString(IndexLock &state, const bool only_verify) = 0;
109 //! Obtains a lock and calls VerifyAndToString while holding that lock
110 string VerifyAndToString(const bool only_verify);
111
112 //! Returns true if the index is affected by updates on the specified column IDs, and false otherwise
113 bool IndexIsUpdated(const vector<PhysicalIndex> &column_ids) const;
114
115 //! Returns unique flag
116 bool IsUnique() {
117 return (constraint_type == IndexConstraintType::UNIQUE || constraint_type == IndexConstraintType::PRIMARY);
118 }
119 //! Returns primary key flag
120 bool IsPrimary() {
121 return (constraint_type == IndexConstraintType::PRIMARY);
122 }
123 //! Returns foreign key flag
124 bool IsForeign() {
125 return (constraint_type == IndexConstraintType::FOREIGN);
126 }
127
128 //! Serializes the index and returns the pair of block_id offset positions
129 virtual BlockPointer Serialize(MetaBlockWriter &writer);
130 //! Returns the serialized data pointer to the block and offset of the serialized index
131 BlockPointer GetSerializedDataPointer() const {
132 return serialized_data_pointer;
133 }
134
135 //! Execute the index expressions on an input chunk
136 void ExecuteExpressions(DataChunk &input, DataChunk &result);
137 static string AppendRowError(DataChunk &input, idx_t index);
138
139protected:
140 //! Lock used for any changes to the index
141 mutex lock;
142 //! Pointer to serialized index data
143 BlockPointer serialized_data_pointer;
144
145private:
146 //! Bound expressions used during expression execution
147 vector<unique_ptr<Expression>> bound_expressions;
148 //! Expression executor to execute the index expressions
149 ExpressionExecutor executor;
150
151 //! Bind the unbound expressions of the index
152 unique_ptr<Expression> BindExpression(unique_ptr<Expression> expr);
153
154public:
155 template <class TARGET>
156 TARGET &Cast() {
157 D_ASSERT(dynamic_cast<TARGET *>(this));
158 return reinterpret_cast<TARGET &>(*this);
159 }
160
161 template <class TARGET>
162 const TARGET &Cast() const {
163 D_ASSERT(dynamic_cast<const TARGET *>(this));
164 return reinterpret_cast<const TARGET &>(*this);
165 }
166};
167
168} // namespace duckdb
169