ClickHouse · alexey-milovidov · Aug 24, 2020 · Jul 16, 2020 · Jul 16, 2020 · Jul 17, 2020
diff --git a/base/common/StringRef.h b/base/common/StringRef.h
@@ -21,21 +21,26 @@
 #endif
 
 
-/// The thing to avoid creating strings to find substrings in the hash table.
+/**
+ * The std::string_view-like container to avoid creating strings to find substrings in the hash table.
+ */
 struct StringRef
 {
     const char * data = nullptr;
     size_t size = 0;
 
+    /// Non-constexpr due to reinterpret_cast.
     template <typename CharT, typename = std::enable_if_t<sizeof(CharT) == 1>>
-    constexpr StringRef(const CharT * data_, size_t size_) : data(reinterpret_cast<const char *>(data_)), size(size_)
+    StringRef(const CharT * data_, size_t size_) : data(reinterpret_cast<const char *>(data_)), size(size_)
     {
         /// Sanity check for overflowed values.
         assert(size < 0x8000000000000000ULL);
     }
 
+    constexpr StringRef(const char * data_, size_t size_) : data(data_), size(size_) {}
+
     StringRef(const std::string & s) : data(s.data()), size(s.size()) {}
-    constexpr explicit StringRef(const std::string_view & s) : data(s.data()), size(s.size()) {}
+    constexpr explicit StringRef(std::string_view s) : data(s.data()), size(s.size()) {}
     constexpr StringRef(const char * data_) : StringRef(std::string_view{data_}) {}
     constexpr StringRef() = default;
 
@@ -45,6 +50,12 @@ struct StringRef
     constexpr explicit operator std::string_view() const { return {data, size}; }
 };
 
+/// Here constexpr doesn't implicate inline, see https://www.viva64.com/en/w/v1043/
+/// nullptr can't be used because the StringRef values are used in SipHash's pointer arithmetics
+/// and the UBSan thinks that something like nullptr + 8 is UB.
+constexpr const inline char empty_string_ref_addr{};
+constexpr const inline StringRef EMPTY_STRING_REF{&empty_string_ref_addr, 0};
+
 using StringRefs = std::vector<StringRef>;
 
 

diff --git a/src/Columns/ColumnLowCardinality.h b/src/Columns/ColumnLowCardinality.h
@@ -15,6 +15,15 @@ namespace ErrorCodes
     extern const int LOGICAL_ERROR;
 }
 
+/**
+ * How data is stored (in a nutshell):
+ * we have a dictionary @e reverse_index in ColumnUnique that holds pairs (DataType, UIntXX) and a column
+ * with UIntXX holding actual data indices.
+ * To obtain the value's index, call #getOrFindIndex.
+ * To operate on the data (so called indices column), call #getIndexes.
+ *
+ * @note The indices column always contains the default value (empty StringRef) with the first index.
+ */
 class ColumnLowCardinality final : public COWHelper<IColumn, ColumnLowCardinality>
 {
     friend class COWHelper<IColumn, ColumnLowCardinality>;

diff --git a/src/Columns/ColumnNullable.cpp b/src/Columns/ColumnNullable.cpp
@@ -14,7 +14,6 @@ namespace DB
 
 namespace ErrorCodes
 {
-    extern const int NOT_IMPLEMENTED;
     extern const int LOGICAL_ERROR;
     extern const int ILLEGAL_COLUMN;
     extern const int SIZES_OF_NESTED_COLUMNS_ARE_INCONSISTENT;
@@ -105,11 +104,6 @@ void ColumnNullable::get(size_t n, Field & res) const
         getNestedColumn().get(n, res);
 }
 
-StringRef ColumnNullable::getDataAt(size_t /*n*/) const
-{
-    throw Exception{"Method getDataAt is not supported for " + getName(), ErrorCodes::NOT_IMPLEMENTED};
-}
-
 void ColumnNullable::insertData(const char * pos, size_t length)
 {
     if (pos == nullptr)

diff --git a/src/Columns/ColumnNullable.h b/src/Columns/ColumnNullable.h
@@ -51,9 +51,20 @@ class ColumnNullable final : public COWHelper<IColumn, ColumnNullable>
     bool isNullAt(size_t n) const override { return assert_cast<const ColumnUInt8 &>(*null_map).getData()[n] != 0;}
     Field operator[](size_t n) const override;
     void get(size_t n, Field & res) const override;
-    bool getBool(size_t n) const override { return isNullAt(n) ? 0 : nested_column->getBool(n); }
+    bool getBool(size_t n) const override { return isNullAt(n) ? false : nested_column->getBool(n); }
     UInt64 get64(size_t n) const override { return nested_column->get64(n); }
-    StringRef getDataAt(size_t n) const override;
+
+    /**
+     * If isNullAt(n) returns false, returns the nested column's getDataAt(n), otherwise returns a special value
+     * EMPTY_STRING_REF indicating that data is not present.
+     */
+    StringRef getDataAt(size_t n) const override
+    {
+        if (isNullAt(n))
+            return EMPTY_STRING_REF;
+
+        return getNestedColumn().getDataAt(n);
+    }
 
     /// Will insert null value if pos=nullptr
     void insertData(const char * pos, size_t length) override;

diff --git a/src/Columns/ColumnUnique.h b/src/Columns/ColumnUnique.h
@@ -16,6 +16,7 @@
 #include <ext/range.h>
 
 #include <common/unaligned.h>
+#include "Columns/ColumnConst.h"
 
 
 namespace DB
@@ -90,14 +91,13 @@ class ColumnUnique final : public COWHelper<IColumnUnique, ColumnUnique<ColumnTy
     void protect() override { column_holder->protect(); }
     size_t allocatedBytes() const override
     {
-        return column_holder->allocatedBytes()
-               + index.allocatedBytes()
-               + (nested_null_mask ? nested_null_mask->allocatedBytes() : 0);
+        return column_holder->allocatedBytes() + reverse_index.allocatedBytes()
+            + (nested_null_mask ? nested_null_mask->allocatedBytes() : 0);
     }
     void forEachSubcolumn(IColumn::ColumnCallback callback) override
     {
         callback(column_holder);
-        index.setColumn(getRawColumnPtr());
+        reverse_index.setColumn(getRawColumnPtr());
         if (is_nullable)
             nested_column_nullable = ColumnNullable::create(column_holder, nested_null_mask);
     }
@@ -109,16 +109,30 @@ class ColumnUnique final : public COWHelper<IColumnUnique, ColumnUnique<ColumnTy
         return false;
     }
 
-    const UInt64 * tryGetSavedHash() const override { return index.tryGetSavedHash(); }
+    const UInt64 * tryGetSavedHash() const override { return reverse_index.tryGetSavedHash(); }
 
     UInt128 getHash() const override { return hash.getHash(*getRawColumnPtr()); }
 
-private:
+    std::optional<UInt64> getOrFindValueIndex(StringRef value) const override
+    {
+        if (std::optional<UInt64> res = reverse_index.getIndex(value); res)
+            return res;
+
+        auto& nested = *getNestedColumn();
+
+        for (size_t i = 0; i < nested.size(); ++i)
+            if (nested.getDataAt(i) == value)
+                return i;
+
+        return {};
+    }
 
+private:
     IColumn::WrappedPtr column_holder;
     bool is_nullable;
     size_t size_of_value_if_fixed = 0;
-    ReverseIndex<UInt64, ColumnType> index;
+
+    ReverseIndex<UInt64, ColumnType> reverse_index;
 
     /// For DataTypeNullable, stores null map.
     IColumn::WrappedPtr nested_null_mask;
@@ -169,21 +183,20 @@ template <typename ColumnType>
 ColumnUnique<ColumnType>::ColumnUnique(const ColumnUnique & other)
     : column_holder(other.column_holder)
     , is_nullable(other.is_nullable)
-    , size_of_value_if_fixed (other.size_of_value_if_fixed)
-    , index(numSpecialValues(is_nullable), 0)
+    , size_of_value_if_fixed(other.size_of_value_if_fixed)
+    , reverse_index(numSpecialValues(is_nullable), 0)
 {
-    index.setColumn(getRawColumnPtr());
+    reverse_index.setColumn(getRawColumnPtr());
     createNullMask();
 }
 
 template <typename ColumnType>
 ColumnUnique<ColumnType>::ColumnUnique(const IDataType & type)
-    : is_nullable(type.isNullable())
-    , index(numSpecialValues(is_nullable), 0)
+    : is_nullable(type.isNullable()), reverse_index(numSpecialValues(is_nullable), 0)
 {
     const auto & holder_type = is_nullable ? *static_cast<const DataTypeNullable &>(type).getNestedType() : type;
     column_holder = holder_type.createColumn()->cloneResized(numSpecialValues());
-    index.setColumn(getRawColumnPtr());
+    reverse_index.setColumn(getRawColumnPtr());
     createNullMask();
 
     if (column_holder->valuesHaveFixedSize())
@@ -192,16 +205,14 @@ ColumnUnique<ColumnType>::ColumnUnique(const IDataType & type)
 
 template <typename ColumnType>
 ColumnUnique<ColumnType>::ColumnUnique(MutableColumnPtr && holder, bool is_nullable_)
-    : column_holder(std::move(holder))
-    , is_nullable(is_nullable_)
-    , index(numSpecialValues(is_nullable_), 0)
+    : column_holder(std::move(holder)), is_nullable(is_nullable_), reverse_index(numSpecialValues(is_nullable_), 0)
 {
     if (column_holder->size() < numSpecialValues())
         throw Exception("Too small holder column for ColumnUnique.", ErrorCodes::ILLEGAL_COLUMN);
     if (isColumnNullable(*column_holder))
         throw Exception("Holder column for ColumnUnique can't be nullable.", ErrorCodes::ILLEGAL_COLUMN);
 
-    index.setColumn(getRawColumnPtr());
+    reverse_index.setColumn(getRawColumnPtr());
     createNullMask();
 
     if (column_holder->valuesHaveFixedSize())
@@ -288,12 +299,10 @@ size_t ColumnUnique<ColumnType>::uniqueInsertFrom(const IColumn & src, size_t n)
 template <typename ColumnType>
 size_t ColumnUnique<ColumnType>::uniqueInsertData(const char * pos, size_t length)
 {
-    auto column = getRawColumnPtr();
+    if (auto index = getNestedTypeDefaultValueIndex(); getRawColumnPtr()->getDataAt(index) == StringRef(pos, length))
+        return index;
 
-    if (column->getDataAt(getNestedTypeDefaultValueIndex()) == StringRef(pos, length))
-        return getNestedTypeDefaultValueIndex();
-
-    auto insertion_point = index.insert(StringRef(pos, length));
+    auto insertion_point = reverse_index.insert({pos, length});
 
     updateNullMask();
 
@@ -320,6 +329,7 @@ StringRef ColumnUnique<ColumnType>::serializeValueIntoArena(size_t n, Arena & ar
         return StringRef(nested_ref.data - s, nested_ref.size + s);
     }
 
+
     return column_holder->serializeValueIntoArena(n, arena, begin);
 }
 
@@ -513,14 +523,14 @@ MutableColumnPtr ColumnUnique<ColumnType>::uniqueInsertRangeImpl(
 
             if (secondary_index && next_position >= max_dictionary_size)
             {
-                auto insertion_point = index.getInsertionPoint(ref);
-                if (insertion_point == index.lastInsertionPoint())
+                auto insertion_point = reverse_index.getInsertionPoint(ref);
+                if (insertion_point == reverse_index.lastInsertionPoint())
                     res = insert_key(ref, *secondary_index);
                 else
                     positions[num_added_rows] = insertion_point;
             }
             else
-                res = insert_key(ref, index);
+                res = insert_key(ref, reverse_index);
 
             if (res)
                 return res;

diff --git a/src/Columns/ColumnVector.h b/src/Columns/ColumnVector.h
@@ -22,31 +22,31 @@ namespace ErrorCodes
   * Floating-point numbers are compared this way that NaNs always end up at the end
   *  (if you don't do this, the sort would not work at all).
   */
-template <typename T>
+template <class T, class U = T>
 struct CompareHelper
 {
-    static bool less(T a, T b, int /*nan_direction_hint*/) { return a < b; }
-    static bool greater(T a, T b, int /*nan_direction_hint*/) { return a > b; }
+    static constexpr bool less(T a, U b, int /*nan_direction_hint*/) { return a < b; }
+    static constexpr bool greater(T a, U b, int /*nan_direction_hint*/) { return a > b; }
 
     /** Compares two numbers. Returns a number less than zero, equal to zero, or greater than zero if a < b, a == b, a > b, respectively.
       * If one of the values is NaN, then
       * - if nan_direction_hint == -1 - NaN are considered less than all numbers;
       * - if nan_direction_hint == 1 - NaN are considered to be larger than all numbers;
       * Essentially: nan_direction_hint == -1 says that the comparison is for sorting in descending order.
       */
-    static int compare(T a, T b, int /*nan_direction_hint*/)
+    static constexpr int compare(T a, U b, int /*nan_direction_hint*/)
     {
         return a > b ? 1 : (a < b ? -1 : 0);
     }
 };
 
-template <typename T>
+template <class T>
 struct FloatCompareHelper
 {
-    static bool less(T a, T b, int nan_direction_hint)
+    static constexpr bool less(T a, T b, int nan_direction_hint)
     {
-        bool isnan_a = std::isnan(a);
-        bool isnan_b = std::isnan(b);
+        const bool isnan_a = std::isnan(a);
+        const bool isnan_b = std::isnan(b);
 
         if (isnan_a && isnan_b)
             return false;
@@ -58,10 +58,10 @@ struct FloatCompareHelper
         return a < b;
     }
 
-    static bool greater(T a, T b, int nan_direction_hint)
+    static constexpr bool greater(T a, T b, int nan_direction_hint)
     {
-        bool isnan_a = std::isnan(a);
-        bool isnan_b = std::isnan(b);
+        const bool isnan_a = std::isnan(a);
+        const bool isnan_b = std::isnan(b);
 
         if (isnan_a && isnan_b)
             return false;
@@ -73,10 +73,11 @@ struct FloatCompareHelper
         return a > b;
     }
 
-    static int compare(T a, T b, int nan_direction_hint)
+    static constexpr int compare(T a, T b, int nan_direction_hint)
     {
-        bool isnan_a = std::isnan(a);
-        bool isnan_b = std::isnan(b);
+        const bool isnan_a = std::isnan(a);
+        const bool isnan_b = std::isnan(b);
+
         if (unlikely(isnan_a || isnan_b))
         {
             if (isnan_a && isnan_b)
@@ -91,9 +92,8 @@ struct FloatCompareHelper
     }
 };
 
-template <> struct CompareHelper<Float32> : public FloatCompareHelper<Float32> {};
-template <> struct CompareHelper<Float64> : public FloatCompareHelper<Float64> {};
-
+template <class U> struct CompareHelper<Float32, U> : public FloatCompareHelper<Float32> {};
+template <class U> struct CompareHelper<Float64, U> : public FloatCompareHelper<Float64> {};
 
 /** A template for columns that use a simple array to store.
  */
@@ -201,6 +201,12 @@ class ColumnVector final : public COWHelper<ColumnVectorHelper, ColumnVector<T>>
         data.push_back(value);
     }
 
+    template <class U>
+    constexpr int compareAtOther(size_t n, size_t m, const ColumnVector<U> & rhs, int nan_direction_hint) const
+    {
+        return CompareHelper<T, U>::compare(data[n], rhs.data[m], nan_direction_hint);
+    }
+
     /// This method implemented in header because it could be possibly devirtualized.
     int compareAt(size_t n, size_t m, const IColumn & rhs_, int nan_direction_hint) const override
     {

diff --git a/src/Columns/IColumnUnique.h b/src/Columns/IColumnUnique.h
@@ -1,4 +1,5 @@
 #pragma once
+#include <optional>
 #include <Columns/IColumn.h>
 #include <Common/UInt128.h>
 
@@ -9,6 +10,7 @@ namespace ErrorCodes
     extern const int NOT_IMPLEMENTED;
 }
 
+/// Sort of a dictionary
 class IColumnUnique : public IColumn
 {
 public:
@@ -68,6 +70,24 @@ class IColumnUnique : public IColumn
     const char * getFamilyName() const override { return "ColumnUnique"; }
     TypeIndex getDataType() const override { return getNestedColumn()->getDataType(); }
 
+    /**
+     * Given some value (usually, of type @e ColumnType) @p value that is convertible to DB::StringRef, obtains its
+     * index in the DB::ColumnUnique::reverse_index hashtable.
+     *
+     * The reverse index (StringRef => UInt64) is built lazily, so there are two variants:
+     * - On the function call it's present. Therefore we obtain the index in O(1).
+     * - The reverse index is absent. We search for the index linearly.
+     *
+     * @see DB::ReverseIndex
+     * @see DB::ColumnUnique
+     *
+     * The most common example uses https://clickhouse.tech/docs/en/sql-reference/data-types/lowcardinality/ columns.
+     * Consider data type @e LC(String). The inner type here is @e String which is more or less a contigous memory
+     * region, so it can be easily represented as a @e StringRef. So we pass that ref to this function and get its
+     * index in the dictionary, which can be used to operate with the indices column.
+     */
+    virtual std::optional<UInt64> getOrFindValueIndex(StringRef value) const = 0;
+
     void insert(const Field &) override
     {
         throw Exception("Method insert is not supported for ColumnUnique.", ErrorCodes::NOT_IMPLEMENTED);