Is it possible to extend Velox to support StringWithDictionary in Clickhouse?

[xumingming]

Clickhouse has a data type named StringWithDictionary(see [1] for more details), it is basically a dictionary encoded format for string data, but it is not the DictionaryVector in Velox, two reasons:

• The data is distinct in StringWithDictionary's dictionary, while it is not in DictionaryVector.
• Different batches of StringWithDictionary's data has consistent mapping from dictId to string value, while it is not in DictionaryVector.

I am thinking that to support feature like StringWithDictionary, we need to support a new type of Vector? is it possible to implement as a plugin of Velox or we have to change Velox core?

[1]. https://presentations.clickhouse.com/meetup19/string_optimization.pdf

[majetideepak]

| The data is distinct in StringWithDictionary's dictionary, while it is not in DictionaryVector.
@xumingming can you explain this difference with an example? Thanks.

[xumingming]

@majetideepak The dictionary in storage layer(e.g. StringWithDictionary) is to map string value to an integer dictId, so it should be distinct according to its semantic, e.g. If we have a column for person's name, and its cardinality is low, we can construct a mapping:

dictId -> value
-------------
1 -> james
2 -> bond
3 -> lily
4 -> lucy

Then in operator like Aggregation if user want to aggregate on this person's name column, we can instead aggregate on the dictId, which transform string calculation into an integer calculation, thus improve performance.

While DictionaryVector's design intention is to reduce data materialization, e.g. We have data:

james
bond
james
lily

if the data is processed by Filter operator, and the second row(bond) is filtered out, instead of construct a new vector, we can just construct a DictionaryVector over the original one to avoid materialization:

index: 
  - 0
  - 2
  - 3
  
values: 
  - james
  - bond
  - james
  - lily

We can see that there are duplicates(james) in the data, if a downstream Aggregation operator want to aggregate on the string column, it needs to aggregate on the string column itself, it can not aggregate on the integer index, because it will give wrong results.

[pedroerp]

For your aggregation example, I had the impression that VectorHasher will already do this for you and map strings to a smaller range of ids (even if they are not dictionary encoded).

https://github.com/facebookincubator/velox/blob/main/velox/exec/VectorHasher.h

[pedroerp]

Different batches of StringWithDictionary's data has consistent mapping from dictId to string value, while it is not in DictionaryVector.

We usually achieve this by having multiple DictionaryVectors (one per batch), and having them wrap around the same internal Vector (the one that has the distinct values). It should achieve the same effect you're looking for, while at the same time being more flexible so it can be used in different scenarios.

[xumingming]

@pedroerp Yeah, we can represent a StringWithDictionary using DictionaryVector, but when we see a DictionaryVector in Velox code, we can't be sure whether it is a StringWithDictionary or not, thus can't apply optimizations Clickhouse done for StringWithDictionary.

[xumingming]

@pedroerp Do you have suggestions?

[pedroerp]

Dictionaries in Velox can be used to reduce or increase the cardinality of the internal data, so you can't make any assumptions about whether the data has repeated values or not, unless you explicitly control how the vector is created.

[Yuhta]

We have a flag in vector called memoDisabled_, which is roughly equivalent to whether the dictionary is for filtering or not. Also there are other adaptivity tricks we can use to decide if a dictionary is reused or not. I don't think an extra vector type is worth the trouble here.

[mbasmanova]

@xumingming Maybe we could look at some specific queries and compare the performance between Velox and ClickHouse. If Velox is sufficiently slower, we can then think about how to optimize. Would you like try this route?