1#include "duckdb/storage/table/chunk_info.hpp"
2#include "duckdb/transaction/transaction.hpp"
3#include "duckdb/common/serializer.hpp"
4
5namespace duckdb {
6
7struct TransactionVersionOperator {
8 static bool UseInsertedVersion(transaction_t start_time, transaction_t transaction_id, transaction_t id) {
9 return id < start_time || id == transaction_id;
10 }
11
12 static bool UseDeletedVersion(transaction_t start_time, transaction_t transaction_id, transaction_t id) {
13 return !UseInsertedVersion(start_time, transaction_id, id);
14 }
15};
16
17struct CommittedVersionOperator {
18 static bool UseInsertedVersion(transaction_t start_time, transaction_t transaction_id, transaction_t id) {
19 return true;
20 }
21
22 static bool UseDeletedVersion(transaction_t min_start_time, transaction_t min_transaction_id, transaction_t id) {
23 return (id >= min_start_time && id < TRANSACTION_ID_START) || (id >= min_transaction_id);
24 }
25};
26
27static bool UseVersion(TransactionData transaction, transaction_t id) {
28 return TransactionVersionOperator::UseInsertedVersion(start_time: transaction.start_time, transaction_id: transaction.transaction_id, id);
29}
30
31unique_ptr<ChunkInfo> ChunkInfo::Deserialize(Deserializer &source) {
32 auto type = source.Read<ChunkInfoType>();
33 switch (type) {
34 case ChunkInfoType::EMPTY_INFO:
35 return nullptr;
36 case ChunkInfoType::CONSTANT_INFO:
37 return ChunkConstantInfo::Deserialize(source);
38 case ChunkInfoType::VECTOR_INFO:
39 return ChunkVectorInfo::Deserialize(source);
40 default:
41 throw SerializationException("Could not deserialize Chunk Info Type: unrecognized type");
42 }
43}
44
45//===--------------------------------------------------------------------===//
46// Constant info
47//===--------------------------------------------------------------------===//
48ChunkConstantInfo::ChunkConstantInfo(idx_t start)
49 : ChunkInfo(start, ChunkInfoType::CONSTANT_INFO), insert_id(0), delete_id(NOT_DELETED_ID) {
50}
51
52template <class OP>
53idx_t ChunkConstantInfo::TemplatedGetSelVector(transaction_t start_time, transaction_t transaction_id,
54 SelectionVector &sel_vector, idx_t max_count) {
55 if (OP::UseInsertedVersion(start_time, transaction_id, insert_id) &&
56 OP::UseDeletedVersion(start_time, transaction_id, delete_id)) {
57 return max_count;
58 }
59 return 0;
60}
61
62idx_t ChunkConstantInfo::GetSelVector(TransactionData transaction, SelectionVector &sel_vector, idx_t max_count) {
63 return TemplatedGetSelVector<TransactionVersionOperator>(start_time: transaction.start_time, transaction_id: transaction.transaction_id,
64 sel_vector, max_count);
65}
66
67idx_t ChunkConstantInfo::GetCommittedSelVector(transaction_t min_start_id, transaction_t min_transaction_id,
68 SelectionVector &sel_vector, idx_t max_count) {
69 return TemplatedGetSelVector<CommittedVersionOperator>(start_time: min_start_id, transaction_id: min_transaction_id, sel_vector, max_count);
70}
71
72bool ChunkConstantInfo::Fetch(TransactionData transaction, row_t row) {
73 return UseVersion(transaction, id: insert_id) && !UseVersion(transaction, id: delete_id);
74}
75
76void ChunkConstantInfo::CommitAppend(transaction_t commit_id, idx_t start, idx_t end) {
77 D_ASSERT(start == 0 && end == STANDARD_VECTOR_SIZE);
78 insert_id = commit_id;
79}
80
81void ChunkConstantInfo::Serialize(Serializer &serializer) {
82 // we only need to write this node if any tuple deletions have been committed
83 bool is_deleted = insert_id >= TRANSACTION_ID_START || delete_id < TRANSACTION_ID_START;
84 if (!is_deleted) {
85 serializer.Write<ChunkInfoType>(element: ChunkInfoType::EMPTY_INFO);
86 return;
87 }
88 serializer.Write<ChunkInfoType>(element: type);
89 serializer.Write<idx_t>(element: start);
90}
91
92unique_ptr<ChunkInfo> ChunkConstantInfo::Deserialize(Deserializer &source) {
93 auto start = source.Read<idx_t>();
94
95 auto info = make_uniq<ChunkConstantInfo>(args&: start);
96 info->insert_id = 0;
97 info->delete_id = 0;
98 return std::move(info);
99}
100
101//===--------------------------------------------------------------------===//
102// Vector info
103//===--------------------------------------------------------------------===//
104ChunkVectorInfo::ChunkVectorInfo(idx_t start)
105 : ChunkInfo(start, ChunkInfoType::VECTOR_INFO), insert_id(0), same_inserted_id(true), any_deleted(false) {
106 for (idx_t i = 0; i < STANDARD_VECTOR_SIZE; i++) {
107 inserted[i] = 0;
108 deleted[i] = NOT_DELETED_ID;
109 }
110}
111
112template <class OP>
113idx_t ChunkVectorInfo::TemplatedGetSelVector(transaction_t start_time, transaction_t transaction_id,
114 SelectionVector &sel_vector, idx_t max_count) {
115 idx_t count = 0;
116 if (same_inserted_id && !any_deleted) {
117 // all tuples have the same inserted id: and no tuples were deleted
118 if (OP::UseInsertedVersion(start_time, transaction_id, insert_id)) {
119 return max_count;
120 } else {
121 return 0;
122 }
123 } else if (same_inserted_id) {
124 if (!OP::UseInsertedVersion(start_time, transaction_id, insert_id)) {
125 return 0;
126 }
127 // have to check deleted flag
128 for (idx_t i = 0; i < max_count; i++) {
129 if (OP::UseDeletedVersion(start_time, transaction_id, deleted[i])) {
130 sel_vector.set_index(idx: count++, loc: i);
131 }
132 }
133 } else if (!any_deleted) {
134 // have to check inserted flag
135 for (idx_t i = 0; i < max_count; i++) {
136 if (OP::UseInsertedVersion(start_time, transaction_id, inserted[i])) {
137 sel_vector.set_index(idx: count++, loc: i);
138 }
139 }
140 } else {
141 // have to check both flags
142 for (idx_t i = 0; i < max_count; i++) {
143 if (OP::UseInsertedVersion(start_time, transaction_id, inserted[i]) &&
144 OP::UseDeletedVersion(start_time, transaction_id, deleted[i])) {
145 sel_vector.set_index(idx: count++, loc: i);
146 }
147 }
148 }
149 return count;
150}
151
152idx_t ChunkVectorInfo::GetSelVector(transaction_t start_time, transaction_t transaction_id, SelectionVector &sel_vector,
153 idx_t max_count) {
154 return TemplatedGetSelVector<TransactionVersionOperator>(start_time, transaction_id, sel_vector, max_count);
155}
156
157idx_t ChunkVectorInfo::GetCommittedSelVector(transaction_t min_start_id, transaction_t min_transaction_id,
158 SelectionVector &sel_vector, idx_t max_count) {
159 return TemplatedGetSelVector<CommittedVersionOperator>(start_time: min_start_id, transaction_id: min_transaction_id, sel_vector, max_count);
160}
161
162idx_t ChunkVectorInfo::GetSelVector(TransactionData transaction, SelectionVector &sel_vector, idx_t max_count) {
163 return GetSelVector(start_time: transaction.start_time, transaction_id: transaction.transaction_id, sel_vector, max_count);
164}
165
166bool ChunkVectorInfo::Fetch(TransactionData transaction, row_t row) {
167 return UseVersion(transaction, id: inserted[row]) && !UseVersion(transaction, id: deleted[row]);
168}
169
170idx_t ChunkVectorInfo::Delete(transaction_t transaction_id, row_t rows[], idx_t count) {
171 any_deleted = true;
172
173 idx_t deleted_tuples = 0;
174 for (idx_t i = 0; i < count; i++) {
175 if (deleted[rows[i]] == transaction_id) {
176 continue;
177 }
178 // first check the chunk for conflicts
179 if (deleted[rows[i]] != NOT_DELETED_ID) {
180 // tuple was already deleted by another transaction
181 throw TransactionException("Conflict on tuple deletion!");
182 }
183 // after verifying that there are no conflicts we mark the tuple as deleted
184 deleted[rows[i]] = transaction_id;
185 rows[deleted_tuples] = rows[i];
186 deleted_tuples++;
187 }
188 return deleted_tuples;
189}
190
191void ChunkVectorInfo::CommitDelete(transaction_t commit_id, row_t rows[], idx_t count) {
192 for (idx_t i = 0; i < count; i++) {
193 deleted[rows[i]] = commit_id;
194 }
195}
196
197void ChunkVectorInfo::Append(idx_t start, idx_t end, transaction_t commit_id) {
198 if (start == 0) {
199 insert_id = commit_id;
200 } else if (insert_id != commit_id) {
201 same_inserted_id = false;
202 insert_id = NOT_DELETED_ID;
203 }
204 for (idx_t i = start; i < end; i++) {
205 inserted[i] = commit_id;
206 }
207}
208
209void ChunkVectorInfo::CommitAppend(transaction_t commit_id, idx_t start, idx_t end) {
210 if (same_inserted_id) {
211 insert_id = commit_id;
212 }
213 for (idx_t i = start; i < end; i++) {
214 inserted[i] = commit_id;
215 }
216}
217
218void ChunkVectorInfo::Serialize(Serializer &serializer) {
219 SelectionVector sel(STANDARD_VECTOR_SIZE);
220 transaction_t start_time = TRANSACTION_ID_START - 1;
221 transaction_t transaction_id = DConstants::INVALID_INDEX;
222 idx_t count = GetSelVector(start_time, transaction_id, sel_vector&: sel, STANDARD_VECTOR_SIZE);
223 if (count == STANDARD_VECTOR_SIZE) {
224 // nothing is deleted: skip writing anything
225 serializer.Write<ChunkInfoType>(element: ChunkInfoType::EMPTY_INFO);
226 return;
227 }
228 if (count == 0) {
229 // everything is deleted: write a constant vector
230 serializer.Write<ChunkInfoType>(element: ChunkInfoType::CONSTANT_INFO);
231 serializer.Write<idx_t>(element: start);
232 return;
233 }
234 // write a boolean vector
235 serializer.Write<ChunkInfoType>(element: ChunkInfoType::VECTOR_INFO);
236 serializer.Write<idx_t>(element: start);
237 bool deleted_tuples[STANDARD_VECTOR_SIZE];
238 for (idx_t i = 0; i < STANDARD_VECTOR_SIZE; i++) {
239 deleted_tuples[i] = true;
240 }
241 for (idx_t i = 0; i < count; i++) {
242 deleted_tuples[sel.get_index(idx: i)] = false;
243 }
244 serializer.WriteData(buffer: data_ptr_cast(src: deleted_tuples), write_size: sizeof(bool) * STANDARD_VECTOR_SIZE);
245}
246
247unique_ptr<ChunkInfo> ChunkVectorInfo::Deserialize(Deserializer &source) {
248 auto start = source.Read<idx_t>();
249
250 auto result = make_uniq<ChunkVectorInfo>(args&: start);
251 result->any_deleted = true;
252 bool deleted_tuples[STANDARD_VECTOR_SIZE];
253 source.ReadData(buffer: data_ptr_cast(src: deleted_tuples), read_size: sizeof(bool) * STANDARD_VECTOR_SIZE);
254 for (idx_t i = 0; i < STANDARD_VECTOR_SIZE; i++) {
255 if (deleted_tuples[i]) {
256 result->deleted[i] = 0;
257 }
258 }
259 return std::move(result);
260}
261
262} // namespace duckdb
263