1#include "duckdb/common/helper.hpp"
2#include "duckdb/common/radix.hpp"
3#include "duckdb/common/row_operations/row_operations.hpp"
4#include "duckdb/common/types/vector.hpp"
5
6namespace duckdb {
7
8template <class T>
9void TemplatedRadixScatter(UnifiedVectorFormat &vdata, const SelectionVector &sel, idx_t add_count,
10 data_ptr_t *key_locations, const bool desc, const bool has_null, const bool nulls_first,
11 const idx_t offset) {
12 auto source = UnifiedVectorFormat::GetData<T>(vdata);
13 if (has_null) {
14 auto &validity = vdata.validity;
15 const data_t valid = nulls_first ? 1 : 0;
16 const data_t invalid = 1 - valid;
17
18 for (idx_t i = 0; i < add_count; i++) {
19 auto idx = sel.get_index(idx: i);
20 auto source_idx = vdata.sel->get_index(idx) + offset;
21 // write validity and according value
22 if (validity.RowIsValid(row_idx: source_idx)) {
23 key_locations[i][0] = valid;
24 Radix::EncodeData<T>(key_locations[i] + 1, source[source_idx]);
25 // invert bits if desc
26 if (desc) {
27 for (idx_t s = 1; s < sizeof(T) + 1; s++) {
28 *(key_locations[i] + s) = ~*(key_locations[i] + s);
29 }
30 }
31 } else {
32 key_locations[i][0] = invalid;
33 memset(s: key_locations[i] + 1, c: '\0', n: sizeof(T));
34 }
35 key_locations[i] += sizeof(T) + 1;
36 }
37 } else {
38 for (idx_t i = 0; i < add_count; i++) {
39 auto idx = sel.get_index(idx: i);
40 auto source_idx = vdata.sel->get_index(idx) + offset;
41 // write value
42 Radix::EncodeData<T>(key_locations[i], source[source_idx]);
43 // invert bits if desc
44 if (desc) {
45 for (idx_t s = 0; s < sizeof(T); s++) {
46 *(key_locations[i] + s) = ~*(key_locations[i] + s);
47 }
48 }
49 key_locations[i] += sizeof(T);
50 }
51 }
52}
53
54void RadixScatterStringVector(UnifiedVectorFormat &vdata, const SelectionVector &sel, idx_t add_count,
55 data_ptr_t *key_locations, const bool desc, const bool has_null, const bool nulls_first,
56 const idx_t prefix_len, idx_t offset) {
57 auto source = UnifiedVectorFormat::GetData<string_t>(format: vdata);
58 if (has_null) {
59 auto &validity = vdata.validity;
60 const data_t valid = nulls_first ? 1 : 0;
61 const data_t invalid = 1 - valid;
62
63 for (idx_t i = 0; i < add_count; i++) {
64 auto idx = sel.get_index(idx: i);
65 auto source_idx = vdata.sel->get_index(idx) + offset;
66 // write validity and according value
67 if (validity.RowIsValid(row_idx: source_idx)) {
68 key_locations[i][0] = valid;
69 Radix::EncodeStringDataPrefix(dataptr: key_locations[i] + 1, value: source[source_idx], prefix_len);
70 // invert bits if desc
71 if (desc) {
72 for (idx_t s = 1; s < prefix_len + 1; s++) {
73 *(key_locations[i] + s) = ~*(key_locations[i] + s);
74 }
75 }
76 } else {
77 key_locations[i][0] = invalid;
78 memset(s: key_locations[i] + 1, c: '\0', n: prefix_len);
79 }
80 key_locations[i] += prefix_len + 1;
81 }
82 } else {
83 for (idx_t i = 0; i < add_count; i++) {
84 auto idx = sel.get_index(idx: i);
85 auto source_idx = vdata.sel->get_index(idx) + offset;
86 // write value
87 Radix::EncodeStringDataPrefix(dataptr: key_locations[i], value: source[source_idx], prefix_len);
88 // invert bits if desc
89 if (desc) {
90 for (idx_t s = 0; s < prefix_len; s++) {
91 *(key_locations[i] + s) = ~*(key_locations[i] + s);
92 }
93 }
94 key_locations[i] += prefix_len;
95 }
96 }
97}
98
99void RadixScatterListVector(Vector &v, UnifiedVectorFormat &vdata, const SelectionVector &sel, idx_t add_count,
100 data_ptr_t *key_locations, const bool desc, const bool has_null, const bool nulls_first,
101 const idx_t prefix_len, const idx_t width, const idx_t offset) {
102 auto list_data = ListVector::GetData(v);
103 auto &child_vector = ListVector::GetEntry(vector&: v);
104 auto list_size = ListVector::GetListSize(vector: v);
105 child_vector.Flatten(count: list_size);
106
107 // serialize null values
108 if (has_null) {
109 auto &validity = vdata.validity;
110 const data_t valid = nulls_first ? 1 : 0;
111 const data_t invalid = 1 - valid;
112
113 for (idx_t i = 0; i < add_count; i++) {
114 auto idx = sel.get_index(idx: i);
115 auto source_idx = vdata.sel->get_index(idx) + offset;
116 data_ptr_t key_location = key_locations[i] + 1;
117 // write validity and according value
118 if (validity.RowIsValid(row_idx: source_idx)) {
119 key_locations[i][0] = valid;
120 key_locations[i]++;
121 auto &list_entry = list_data[source_idx];
122 if (list_entry.length > 0) {
123 // denote that the list is not empty with a 1
124 key_locations[i][0] = 1;
125 key_locations[i]++;
126 RowOperations::RadixScatter(v&: child_vector, vcount: list_size, sel: *FlatVector::IncrementalSelectionVector(), ser_count: 1,
127 key_locations: key_locations + i, desc: false, has_null: true, nulls_first: false, prefix_len, width: width - 1,
128 offset: list_entry.offset);
129 } else {
130 // denote that the list is empty with a 0
131 key_locations[i][0] = 0;
132 key_locations[i]++;
133 memset(s: key_locations[i], c: '\0', n: width - 2);
134 }
135 // invert bits if desc
136 if (desc) {
137 for (idx_t s = 0; s < width - 1; s++) {
138 *(key_location + s) = ~*(key_location + s);
139 }
140 }
141 } else {
142 key_locations[i][0] = invalid;
143 memset(s: key_locations[i] + 1, c: '\0', n: width - 1);
144 key_locations[i] += width;
145 }
146 }
147 } else {
148 for (idx_t i = 0; i < add_count; i++) {
149 auto idx = sel.get_index(idx: i);
150 auto source_idx = vdata.sel->get_index(idx) + offset;
151 auto &list_entry = list_data[source_idx];
152 data_ptr_t key_location = key_locations[i];
153 if (list_entry.length > 0) {
154 // denote that the list is not empty with a 1
155 key_locations[i][0] = 1;
156 key_locations[i]++;
157 RowOperations::RadixScatter(v&: child_vector, vcount: list_size, sel: *FlatVector::IncrementalSelectionVector(), ser_count: 1,
158 key_locations: key_locations + i, desc: false, has_null: true, nulls_first: false, prefix_len, width: width - 1,
159 offset: list_entry.offset);
160 } else {
161 // denote that the list is empty with a 0
162 key_locations[i][0] = 0;
163 key_locations[i]++;
164 memset(s: key_locations[i], c: '\0', n: width - 1);
165 }
166 // invert bits if desc
167 if (desc) {
168 for (idx_t s = 0; s < width; s++) {
169 *(key_location + s) = ~*(key_location + s);
170 }
171 }
172 }
173 }
174}
175
176void RadixScatterStructVector(Vector &v, UnifiedVectorFormat &vdata, idx_t vcount, const SelectionVector &sel,
177 idx_t add_count, data_ptr_t *key_locations, const bool desc, const bool has_null,
178 const bool nulls_first, const idx_t prefix_len, idx_t width, const idx_t offset) {
179 // serialize null values
180 if (has_null) {
181 auto &validity = vdata.validity;
182 const data_t valid = nulls_first ? 1 : 0;
183 const data_t invalid = 1 - valid;
184
185 for (idx_t i = 0; i < add_count; i++) {
186 auto idx = sel.get_index(idx: i);
187 auto source_idx = vdata.sel->get_index(idx) + offset;
188 // write validity and according value
189 if (validity.RowIsValid(row_idx: source_idx)) {
190 key_locations[i][0] = valid;
191 } else {
192 key_locations[i][0] = invalid;
193 }
194 key_locations[i]++;
195 }
196 width--;
197 }
198 // serialize the struct
199 auto &child_vector = *StructVector::GetEntries(vector&: v)[0];
200 RowOperations::RadixScatter(v&: child_vector, vcount, sel: *FlatVector::IncrementalSelectionVector(), ser_count: add_count,
201 key_locations, desc: false, has_null: true, nulls_first: false, prefix_len, width, offset);
202 // invert bits if desc
203 if (desc) {
204 for (idx_t i = 0; i < add_count; i++) {
205 for (idx_t s = 0; s < width; s++) {
206 *(key_locations[i] - width + s) = ~*(key_locations[i] - width + s);
207 }
208 }
209 }
210}
211
212void RowOperations::RadixScatter(Vector &v, idx_t vcount, const SelectionVector &sel, idx_t ser_count,
213 data_ptr_t *key_locations, bool desc, bool has_null, bool nulls_first,
214 idx_t prefix_len, idx_t width, idx_t offset) {
215 UnifiedVectorFormat vdata;
216 v.ToUnifiedFormat(count: vcount, data&: vdata);
217 switch (v.GetType().InternalType()) {
218 case PhysicalType::BOOL:
219 case PhysicalType::INT8:
220 TemplatedRadixScatter<int8_t>(vdata, sel, add_count: ser_count, key_locations, desc, has_null, nulls_first, offset);
221 break;
222 case PhysicalType::INT16:
223 TemplatedRadixScatter<int16_t>(vdata, sel, add_count: ser_count, key_locations, desc, has_null, nulls_first, offset);
224 break;
225 case PhysicalType::INT32:
226 TemplatedRadixScatter<int32_t>(vdata, sel, add_count: ser_count, key_locations, desc, has_null, nulls_first, offset);
227 break;
228 case PhysicalType::INT64:
229 TemplatedRadixScatter<int64_t>(vdata, sel, add_count: ser_count, key_locations, desc, has_null, nulls_first, offset);
230 break;
231 case PhysicalType::UINT8:
232 TemplatedRadixScatter<uint8_t>(vdata, sel, add_count: ser_count, key_locations, desc, has_null, nulls_first, offset);
233 break;
234 case PhysicalType::UINT16:
235 TemplatedRadixScatter<uint16_t>(vdata, sel, add_count: ser_count, key_locations, desc, has_null, nulls_first, offset);
236 break;
237 case PhysicalType::UINT32:
238 TemplatedRadixScatter<uint32_t>(vdata, sel, add_count: ser_count, key_locations, desc, has_null, nulls_first, offset);
239 break;
240 case PhysicalType::UINT64:
241 TemplatedRadixScatter<uint64_t>(vdata, sel, add_count: ser_count, key_locations, desc, has_null, nulls_first, offset);
242 break;
243 case PhysicalType::INT128:
244 TemplatedRadixScatter<hugeint_t>(vdata, sel, add_count: ser_count, key_locations, desc, has_null, nulls_first, offset);
245 break;
246 case PhysicalType::FLOAT:
247 TemplatedRadixScatter<float>(vdata, sel, add_count: ser_count, key_locations, desc, has_null, nulls_first, offset);
248 break;
249 case PhysicalType::DOUBLE:
250 TemplatedRadixScatter<double>(vdata, sel, add_count: ser_count, key_locations, desc, has_null, nulls_first, offset);
251 break;
252 case PhysicalType::INTERVAL:
253 TemplatedRadixScatter<interval_t>(vdata, sel, add_count: ser_count, key_locations, desc, has_null, nulls_first, offset);
254 break;
255 case PhysicalType::VARCHAR:
256 RadixScatterStringVector(vdata, sel, add_count: ser_count, key_locations, desc, has_null, nulls_first, prefix_len, offset);
257 break;
258 case PhysicalType::LIST:
259 RadixScatterListVector(v, vdata, sel, add_count: ser_count, key_locations, desc, has_null, nulls_first, prefix_len, width,
260 offset);
261 break;
262 case PhysicalType::STRUCT:
263 RadixScatterStructVector(v, vdata, vcount, sel, add_count: ser_count, key_locations, desc, has_null, nulls_first,
264 prefix_len, width, offset);
265 break;
266 default:
267 throw NotImplementedException("Cannot ORDER BY column with type %s", v.GetType().ToString());
268 }
269}
270
271} // namespace duckdb
272