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
11class SipHash;
12
13
14namespace DB
15{
16
17namespace 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
24class Arena;
25class ColumnGathererStream;
26class Field;
27
28/// Declares interface to store columns in memory.
29class IColumn : public COW<IColumn>
30{
31private:
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
40public:
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
377protected:
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
385using ColumnPtr = IColumn::Ptr;
386using MutableColumnPtr = IColumn::MutablePtr;
387using Columns = std::vector<ColumnPtr>;
388using MutableColumns = std::vector<MutableColumnPtr>;
389
390using ColumnRawPtrs = std::vector<const IColumn *>;
391//using MutableColumnRawPtrs = std::vector<IColumn *>;
392
393template <typename ... Args>
394struct IsMutableColumns;
395
396template <typename Arg, typename ... Args>
397struct IsMutableColumns<Arg, Args ...>
398{
399 static const bool value = std::is_assignable<MutableColumnPtr &&, Arg>::value && IsMutableColumns<Args ...>::value;
400};
401
402template <>
403struct IsMutableColumns<> { static const bool value = true; };
404
405
406template <typename Type>
407const Type * checkAndGetColumn(const IColumn & column)
408{
409 return typeid_cast<const Type *>(&column);
410}
411
412template <typename Type>
413const Type * checkAndGetColumn(const IColumn * column)
414{
415 return typeid_cast<const Type *>(column);
416}
417
418template <typename Type>
419bool checkColumn(const IColumn & column)
420{
421 return checkAndGetColumn<Type>(&column);
422}
423
424template <typename Type>
425bool 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.
431bool isColumnConst(const IColumn & column);
432
433/// True if column's an ColumnNullable instance. It's just a syntax sugar for type check.
434bool isColumnNullable(const IColumn & column);
435
436}
437