1 | #pragma once |
2 | |
3 | #include <Common/COW.h> |
4 | #include <Common/PODArray_fwd.h> |
5 | #include <Common/Exception.h> |
6 | #include <Common/typeid_cast.h> |
7 | #include <common/StringRef.h> |
8 | #include <Core/Types.h> |
9 | |
10 | |
11 | class SipHash; |
12 | |
13 | |
14 | namespace DB |
15 | { |
16 | |
17 | namespace ErrorCodes |
18 | { |
19 | extern const int CANNOT_GET_SIZE_OF_FIELD; |
20 | extern const int NOT_IMPLEMENTED; |
21 | extern const int SIZES_OF_COLUMNS_DOESNT_MATCH; |
22 | } |
23 | |
24 | class Arena; |
25 | class ColumnGathererStream; |
26 | class Field; |
27 | |
28 | /// Declares interface to store columns in memory. |
29 | class IColumn : public COW<IColumn> |
30 | { |
31 | private: |
32 | friend class COW<IColumn>; |
33 | |
34 | /// Creates the same column with the same data. |
35 | /// This is internal method to use from COW. |
36 | /// It performs shallow copy with copy-ctor and not useful from outside. |
37 | /// If you want to copy column for modification, look at 'mutate' method. |
38 | virtual MutablePtr clone() const = 0; |
39 | |
40 | public: |
41 | /// Name of a Column. It is used in info messages. |
42 | virtual std::string getName() const { return getFamilyName(); } |
43 | |
44 | /// Name of a Column kind, without parameters (example: FixedString, Array). |
45 | virtual const char * getFamilyName() const = 0; |
46 | |
47 | /** If column isn't constant, returns nullptr (or itself). |
48 | * If column is constant, transforms constant to full column (if column type allows such transform) and return it. |
49 | */ |
50 | virtual Ptr convertToFullColumnIfConst() const { return getPtr(); } |
51 | |
52 | /// If column isn't ColumnLowCardinality, return itself. |
53 | /// If column is ColumnLowCardinality, transforms is to full column. |
54 | virtual Ptr convertToFullColumnIfLowCardinality() const { return getPtr(); } |
55 | |
56 | /// Creates empty column with the same type. |
57 | virtual MutablePtr cloneEmpty() const { return cloneResized(0); } |
58 | |
59 | /// Creates column with the same type and specified size. |
60 | /// If size is less current size, then data is cut. |
61 | /// If size is greater, than default values are appended. |
62 | virtual MutablePtr cloneResized(size_t /*size*/) const { throw Exception("Cannot cloneResized() column " + getName(), ErrorCodes::NOT_IMPLEMENTED); } |
63 | |
64 | /// Returns number of values in column. |
65 | virtual size_t size() const = 0; |
66 | |
67 | /// There are no values in columns. |
68 | bool empty() const { return size() == 0; } |
69 | |
70 | /// Returns value of n-th element in universal Field representation. |
71 | /// Is used in rare cases, since creation of Field instance is expensive usually. |
72 | virtual Field operator[](size_t n) const = 0; |
73 | |
74 | /// Like the previous one, but avoids extra copying if Field is in a container, for example. |
75 | virtual void get(size_t n, Field & res) const = 0; |
76 | |
77 | /// If possible, returns pointer to memory chunk which contains n-th element (if it isn't possible, throws an exception) |
78 | /// Is used to optimize some computations (in aggregation, for example). |
79 | virtual StringRef getDataAt(size_t n) const = 0; |
80 | |
81 | /// Like getData, but has special behavior for columns that contain variable-length strings. |
82 | /// Returns zero-ending memory chunk (i.e. its size is 1 byte longer). |
83 | virtual StringRef getDataAtWithTerminatingZero(size_t n) const |
84 | { |
85 | return getDataAt(n); |
86 | } |
87 | |
88 | /// If column stores integers, it returns n-th element transformed to UInt64 using static_cast. |
89 | /// If column stores floating point numbers, bits of n-th elements are copied to lower bits of UInt64, the remaining bits are zeros. |
90 | /// Is used to optimize some computations (in aggregation, for example). |
91 | virtual UInt64 get64(size_t /*n*/) const |
92 | { |
93 | throw Exception("Method get64 is not supported for " + getName(), ErrorCodes::NOT_IMPLEMENTED); |
94 | } |
95 | |
96 | /// If column stores native numeric type, it returns n-th element casted to Float64 |
97 | /// Is used in regression methods to cast each features into uniform type |
98 | virtual Float64 getFloat64(size_t /*n*/) const |
99 | { |
100 | throw Exception("Method getFloat64 is not supported for " + getName(), ErrorCodes::NOT_IMPLEMENTED); |
101 | } |
102 | |
103 | virtual Float32 getFloat32(size_t /*n*/) const |
104 | { |
105 | throw Exception("Method getFloat32 is not supported for " + getName(), ErrorCodes::NOT_IMPLEMENTED); |
106 | } |
107 | |
108 | /** If column is numeric, return value of n-th element, casted to UInt64. |
109 | * For NULL values of Nullable column it is allowed to return arbitrary value. |
110 | * Otherwise throw an exception. |
111 | */ |
112 | virtual UInt64 getUInt(size_t /*n*/) const |
113 | { |
114 | throw Exception("Method getUInt is not supported for " + getName(), ErrorCodes::NOT_IMPLEMENTED); |
115 | } |
116 | |
117 | virtual Int64 getInt(size_t /*n*/) const |
118 | { |
119 | throw Exception("Method getInt is not supported for " + getName(), ErrorCodes::NOT_IMPLEMENTED); |
120 | } |
121 | |
122 | virtual bool isDefaultAt(size_t n) const { return get64(n) == 0; } |
123 | virtual bool isNullAt(size_t /*n*/) const { return false; } |
124 | |
125 | /** If column is numeric, return value of n-th element, casted to bool. |
126 | * For NULL values of Nullable column returns false. |
127 | * Otherwise throw an exception. |
128 | */ |
129 | virtual bool getBool(size_t /*n*/) const |
130 | { |
131 | throw Exception("Method getBool is not supported for " + getName(), ErrorCodes::NOT_IMPLEMENTED); |
132 | } |
133 | |
134 | /// Removes all elements outside of specified range. |
135 | /// Is used in LIMIT operation, for example. |
136 | virtual Ptr cut(size_t start, size_t length) const |
137 | { |
138 | MutablePtr res = cloneEmpty(); |
139 | res->insertRangeFrom(*this, start, length); |
140 | return res; |
141 | } |
142 | |
143 | /// Appends new value at the end of column (column's size is increased by 1). |
144 | /// Is used to transform raw strings to Blocks (for example, inside input format parsers) |
145 | virtual void insert(const Field & x) = 0; |
146 | |
147 | /// Appends n-th element from other column with the same type. |
148 | /// Is used in merge-sort and merges. It could be implemented in inherited classes more optimally than default implementation. |
149 | virtual void insertFrom(const IColumn & src, size_t n); |
150 | |
151 | /// Appends range of elements from other column with the same type. |
152 | /// Could be used to concatenate columns. |
153 | virtual void insertRangeFrom(const IColumn & src, size_t start, size_t length) = 0; |
154 | |
155 | /// Appends one element from other column with the same type multiple times. |
156 | virtual void insertManyFrom(const IColumn & src, size_t position, size_t length) |
157 | { |
158 | for (size_t i = 0; i < length; ++i) |
159 | insertFrom(src, position); |
160 | } |
161 | |
162 | /// Appends data located in specified memory chunk if it is possible (throws an exception if it cannot be implemented). |
163 | /// Is used to optimize some computations (in aggregation, for example). |
164 | /// Parameter length could be ignored if column values have fixed size. |
165 | /// All data will be inserted as single element |
166 | virtual void insertData(const char * pos, size_t length) = 0; |
167 | |
168 | /// Appends "default value". |
169 | /// Is used when there are need to increase column size, but inserting value doesn't make sense. |
170 | /// For example, ColumnNullable(Nested) absolutely ignores values of nested column if it is marked as NULL. |
171 | virtual void insertDefault() = 0; |
172 | |
173 | /// Appends "default value" multiple times. |
174 | virtual void insertManyDefaults(size_t length) |
175 | { |
176 | for (size_t i = 0; i < length; ++i) |
177 | insertDefault(); |
178 | } |
179 | |
180 | /** Removes last n elements. |
181 | * Is used to support exception-safety of several operations. |
182 | * For example, sometimes insertion should be reverted if we catch an exception during operation processing. |
183 | * If column has less than n elements or n == 0 - undefined behavior. |
184 | */ |
185 | virtual void popBack(size_t n) = 0; |
186 | |
187 | /** Serializes n-th element. Serialized element should be placed continuously inside Arena's memory. |
188 | * Serialized value can be deserialized to reconstruct original object. Is used in aggregation. |
189 | * The method is similar to getDataAt(), but can work when element's value cannot be mapped to existing continuous memory chunk, |
190 | * For example, to obtain unambiguous representation of Array of strings, strings data should be interleaved with their sizes. |
191 | * Parameter begin should be used with Arena::allocContinue. |
192 | */ |
193 | virtual StringRef serializeValueIntoArena(size_t n, Arena & arena, char const *& begin) const = 0; |
194 | |
195 | /// Deserializes a value that was serialized using IColumn::serializeValueIntoArena method. |
196 | /// Returns pointer to the position after the read data. |
197 | virtual const char * deserializeAndInsertFromArena(const char * pos) = 0; |
198 | |
199 | /// Update state of hash function with value of n-th element. |
200 | /// On subsequent calls of this method for sequence of column values of arbitrary types, |
201 | /// passed bytes to hash must identify sequence of values unambiguously. |
202 | virtual void updateHashWithValue(size_t n, SipHash & hash) const = 0; |
203 | |
204 | /** Removes elements that don't match the filter. |
205 | * Is used in WHERE and HAVING operations. |
206 | * If result_size_hint > 0, then makes advance reserve(result_size_hint) for the result column; |
207 | * if 0, then don't makes reserve(), |
208 | * otherwise (i.e. < 0), makes reserve() using size of source column. |
209 | */ |
210 | using Filter = PaddedPODArray<UInt8>; |
211 | virtual Ptr filter(const Filter & filt, ssize_t result_size_hint) const = 0; |
212 | |
213 | /// Permutes elements using specified permutation. Is used in sortings. |
214 | /// limit - if it isn't 0, puts only first limit elements in the result. |
215 | using Permutation = PaddedPODArray<size_t>; |
216 | virtual Ptr permute(const Permutation & perm, size_t limit) const = 0; |
217 | |
218 | /// Creates new column with values column[indexes[:limit]]. If limit is 0, all indexes are used. |
219 | /// Indexes must be one of the ColumnUInt. For default implementation, see selectIndexImpl from ColumnsCommon.h |
220 | virtual Ptr index(const IColumn & indexes, size_t limit) const = 0; |
221 | |
222 | /** Compares (*this)[n] and rhs[m]. Column rhs should have the same type. |
223 | * Returns negative number, 0, or positive number (*this)[n] is less, equal, greater than rhs[m] respectively. |
224 | * Is used in sortings. |
225 | * |
226 | * If one of element's value is NaN or NULLs, then: |
227 | * - if nan_direction_hint == -1, NaN and NULLs are considered as least than everything other; |
228 | * - if nan_direction_hint == 1, NaN and NULLs are considered as greatest than everything other. |
229 | * For example, if nan_direction_hint == -1 is used by descending sorting, NaNs will be at the end. |
230 | * |
231 | * For non Nullable and non floating point types, nan_direction_hint is ignored. |
232 | */ |
233 | virtual int compareAt(size_t n, size_t m, const IColumn & rhs, int nan_direction_hint) const = 0; |
234 | |
235 | /** Returns a permutation that sorts elements of this column, |
236 | * i.e. perm[i]-th element of source column should be i-th element of sorted column. |
237 | * reverse - reverse ordering (acsending). |
238 | * limit - if isn't 0, then only first limit elements of the result column could be sorted. |
239 | * nan_direction_hint - see above. |
240 | */ |
241 | virtual void getPermutation(bool reverse, size_t limit, int nan_direction_hint, Permutation & res) const = 0; |
242 | |
243 | /** Copies each element according offsets parameter. |
244 | * (i-th element should be copied offsets[i] - offsets[i - 1] times.) |
245 | * It is necessary in ARRAY JOIN operation. |
246 | */ |
247 | using Offset = UInt64; |
248 | using Offsets = PaddedPODArray<Offset>; |
249 | virtual Ptr replicate(const Offsets & offsets) const = 0; |
250 | |
251 | /** Split column to smaller columns. Each value goes to column index, selected by corresponding element of 'selector'. |
252 | * Selector must contain values from 0 to num_columns - 1. |
253 | * For default implementation, see scatterImpl. |
254 | */ |
255 | using ColumnIndex = UInt64; |
256 | using Selector = PaddedPODArray<ColumnIndex>; |
257 | virtual std::vector<MutablePtr> scatter(ColumnIndex num_columns, const Selector & selector) const = 0; |
258 | |
259 | /// Insert data from several other columns according to source mask (used in vertical merge). |
260 | /// For now it is a helper to de-virtualize calls to insert*() functions inside gather loop |
261 | /// (descendants should call gatherer_stream.gather(*this) to implement this function.) |
262 | /// TODO: interface decoupled from ColumnGathererStream that allows non-generic specializations. |
263 | virtual void gather(ColumnGathererStream & gatherer_stream) = 0; |
264 | |
265 | /** Computes minimum and maximum element of the column. |
266 | * In addition to numeric types, the function is completely implemented for Date and DateTime. |
267 | * For strings and arrays function should return default value. |
268 | * (except for constant columns; they should return value of the constant). |
269 | * If column is empty function should return default value. |
270 | */ |
271 | virtual void getExtremes(Field & min, Field & max) const = 0; |
272 | |
273 | /// Reserves memory for specified amount of elements. If reservation isn't possible, does nothing. |
274 | /// It affects performance only (not correctness). |
275 | virtual void reserve(size_t /*n*/) {} |
276 | |
277 | /// Size of column data in memory (may be approximate) - for profiling. Zero, if could not be determined. |
278 | virtual size_t byteSize() const = 0; |
279 | |
280 | /// Size of memory, allocated for column. |
281 | /// This is greater or equals to byteSize due to memory reservation in containers. |
282 | /// Zero, if could not be determined. |
283 | virtual size_t allocatedBytes() const = 0; |
284 | |
285 | /// Make memory region readonly with mprotect if it is large enough. |
286 | /// The operation is slow and performed only for debug builds. |
287 | virtual void protect() {} |
288 | |
289 | /// If the column contains subcolumns (such as Array, Nullable, etc), do callback on them. |
290 | /// Shallow: doesn't do recursive calls; don't do call for itself. |
291 | using ColumnCallback = std::function<void(WrappedPtr&)>; |
292 | virtual void forEachSubcolumn(ColumnCallback) {} |
293 | |
294 | /// Columns have equal structure. |
295 | /// If true - you can use "compareAt", "insertFrom", etc. methods. |
296 | virtual bool structureEquals(const IColumn &) const |
297 | { |
298 | throw Exception("Method structureEquals is not supported for " + getName(), ErrorCodes::NOT_IMPLEMENTED); |
299 | } |
300 | |
301 | |
302 | MutablePtr mutate() const && |
303 | { |
304 | MutablePtr res = shallowMutate(); |
305 | res->forEachSubcolumn([](WrappedPtr & subcolumn) { subcolumn = std::move(*subcolumn).mutate(); }); |
306 | return res; |
307 | } |
308 | |
309 | |
310 | /** Some columns can contain another columns inside. |
311 | * So, we have a tree of columns. But not all combinations are possible. |
312 | * There are the following rules: |
313 | * |
314 | * ColumnConst may be only at top. It cannot be inside any column. |
315 | * ColumnNullable can contain only simple columns. |
316 | */ |
317 | |
318 | /// Various properties on behaviour of column type. |
319 | |
320 | /// True if column contains something nullable inside. It's true for ColumnNullable, can be true or false for ColumnConst, etc. |
321 | virtual bool isNullable() const { return false; } |
322 | |
323 | /// It's a special kind of column, that contain single value, but is not a ColumnConst. |
324 | virtual bool isDummy() const { return false; } |
325 | |
326 | /** Memory layout properties. |
327 | * |
328 | * Each value of a column can be placed in memory contiguously or not. |
329 | * |
330 | * Example: simple columns like UInt64 or FixedString store their values contiguously in single memory buffer. |
331 | * |
332 | * Example: Tuple store values of each component in separate subcolumn, so the values of Tuples with at least two components are not contiguous. |
333 | * Another example is Nullable. Each value have null flag, that is stored separately, so the value is not contiguous in memory. |
334 | * |
335 | * There are some important cases, when values are not stored contiguously, but for each value, you can get contiguous memory segment, |
336 | * that will unambiguously identify the value. In this case, methods getDataAt and insertData are implemented. |
337 | * Example: String column: bytes of strings are stored concatenated in one memory buffer |
338 | * and offsets to that buffer are stored in another buffer. The same is for Array of fixed-size contiguous elements. |
339 | * |
340 | * To avoid confusion between these cases, we don't have isContiguous method. |
341 | */ |
342 | |
343 | /// Values in column have fixed size (including the case when values span many memory segments). |
344 | virtual bool valuesHaveFixedSize() const { return isFixedAndContiguous(); } |
345 | |
346 | /// Values in column are represented as continuous memory segment of fixed size. Implies valuesHaveFixedSize. |
347 | virtual bool isFixedAndContiguous() const { return false; } |
348 | |
349 | /// If isFixedAndContiguous, returns the underlying data array, otherwise throws an exception. |
350 | virtual StringRef getRawData() const { throw Exception("Column " + getName() + " is not a contiguous block of memory" , ErrorCodes::NOT_IMPLEMENTED); } |
351 | |
352 | /// If valuesHaveFixedSize, returns size of value, otherwise throw an exception. |
353 | virtual size_t sizeOfValueIfFixed() const { throw Exception("Values of column " + getName() + " are not fixed size." , ErrorCodes::CANNOT_GET_SIZE_OF_FIELD); } |
354 | |
355 | /// Column is ColumnVector of numbers or ColumnConst of it. Note that Nullable columns are not numeric. |
356 | /// Implies isFixedAndContiguous. |
357 | virtual bool isNumeric() const { return false; } |
358 | |
359 | /// If the only value column can contain is NULL. |
360 | /// Does not imply type of object, because it can be ColumnNullable(ColumnNothing) or ColumnConst(ColumnNullable(ColumnNothing)) |
361 | virtual bool onlyNull() const { return false; } |
362 | |
363 | /// Can be inside ColumnNullable. |
364 | virtual bool canBeInsideNullable() const { return false; } |
365 | |
366 | virtual bool lowCardinality() const { return false; } |
367 | |
368 | |
369 | virtual ~IColumn() = default; |
370 | IColumn() = default; |
371 | IColumn(const IColumn &) = default; |
372 | |
373 | /** Print column name, size, and recursively print all subcolumns. |
374 | */ |
375 | String dumpStructure() const; |
376 | |
377 | protected: |
378 | |
379 | /// Template is to devirtualize calls to insertFrom method. |
380 | /// In derived classes (that use final keyword), implement scatter method as call to scatterImpl. |
381 | template <typename Derived> |
382 | std::vector<MutablePtr> scatterImpl(ColumnIndex num_columns, const Selector & selector) const; |
383 | }; |
384 | |
385 | using ColumnPtr = IColumn::Ptr; |
386 | using MutableColumnPtr = IColumn::MutablePtr; |
387 | using Columns = std::vector<ColumnPtr>; |
388 | using MutableColumns = std::vector<MutableColumnPtr>; |
389 | |
390 | using ColumnRawPtrs = std::vector<const IColumn *>; |
391 | //using MutableColumnRawPtrs = std::vector<IColumn *>; |
392 | |
393 | template <typename ... Args> |
394 | struct IsMutableColumns; |
395 | |
396 | template <typename Arg, typename ... Args> |
397 | struct IsMutableColumns<Arg, Args ...> |
398 | { |
399 | static const bool value = std::is_assignable<MutableColumnPtr &&, Arg>::value && IsMutableColumns<Args ...>::value; |
400 | }; |
401 | |
402 | template <> |
403 | struct IsMutableColumns<> { static const bool value = true; }; |
404 | |
405 | |
406 | template <typename Type> |
407 | const Type * checkAndGetColumn(const IColumn & column) |
408 | { |
409 | return typeid_cast<const Type *>(&column); |
410 | } |
411 | |
412 | template <typename Type> |
413 | const Type * checkAndGetColumn(const IColumn * column) |
414 | { |
415 | return typeid_cast<const Type *>(column); |
416 | } |
417 | |
418 | template <typename Type> |
419 | bool checkColumn(const IColumn & column) |
420 | { |
421 | return checkAndGetColumn<Type>(&column); |
422 | } |
423 | |
424 | template <typename Type> |
425 | bool checkColumn(const IColumn * column) |
426 | { |
427 | return checkAndGetColumn<Type>(column); |
428 | } |
429 | |
430 | /// True if column's an ColumnConst instance. It's just a syntax sugar for type check. |
431 | bool isColumnConst(const IColumn & column); |
432 | |
433 | /// True if column's an ColumnNullable instance. It's just a syntax sugar for type check. |
434 | bool isColumnNullable(const IColumn & column); |
435 | |
436 | } |
437 | |