Update data-dependent flags of vectors in data-changing APIs

[kagamiori]

Background

Recently, a bug in CoalesceExpr and SwitchExpr was discovered that these two special forms compose a result vector of values from multiple of their input vectors, but do not maintain data-dependent flags of the result vectors properly, such as MapVector::sortedKeys_ that indicates whether keys in all rows of a map vector are sorted in descending order. Not maintaining this flag properly could lead to incorrect evaluation results when the results of these two special forms are consumed by functions that use that flag, such as the map_zip_with function. (#4116)

Looking at this problem from a broader perspective, we found that there are other data-dependent flags besides MapVector::sortedKeys_ that should be taken care of as well. We need to make sure all such flags are updated correctly when data in the vector are updated.

Data-dependent flags

Data-dependent flags of vectors include the followings:

1. std::optional<vector_size_t> BaseVector::nullCount_
2. std::optional<vector_size_t> BaseVector::distinctValueCount_
3. std::optional<ByteCount> BaseVector::representedByteCount_
4. std::optional<ByteCount> BaseVector::storageByteCount_
5. std::optional<bool> SimpleVector::isSorted_
6. bool SimpleVector::isAllAscii_
7. SelectivityVector SimpleVector::asciiSetRows_
8. SimpleVector::stats_ that contains std::optional<T> min and std::optional<T> max
9. bool MapVector::sortedKeys_

Data-changing APIs

Functions that change the data in a vector are the followings:

1. BaseVector::setNull(vector_size_t idx, bool value)
2. BaseVector::addNulls(const uint64_t* bits, const SelectivityVector& rows)
3. BaseVector::clearNulls(const SelectivityVector& rows)
4. BaseVector::clearNulls(vector_size_t begin, vector_size_t end)
5. BaseVector::copyRanges(const BaseVector* source, const folly::Range<const CopyRange*>& ranges)
6. BaseVector::setNulls(const BufferPtr& nulls)
7. FlatVector::set(vector_size_t idx, T value)
8. FlatVector::setNoCopy(const vector_size_t idx, const StringView& value)
9. FlatVector::copyValuesAndNulls(const BaseVector* source, ...)
10. ConstantVector::setValue(const std::string& string)
11. ArrayVector::setElements(VectorPtr elements) (Not affecting the aforementioned flags)
12. MapVector::setKeysAndValues(VectorPtr keys, VectorPtr values)
13. static MapVector::canonicalize(const std::shared_ptr& map, ...)
14. In addition, data in a vector can be changed through BaseVector::mutableNulls(), FlatVector::mutableValues(), and DictionaryVector::mutableIndices() APIs.

Brainstorm

To make the data-dependent flags consistent with values in the vector, we need to make sure all the APIs that could change the data in a vector update all the relevant flags properly. To make maintenance easier, it would be helpful to get ride of flags that are not used at all and won't be used in the near future (e.g., BaseVector::representedByteCount_ and BaseVector::storageByteCount_).

To update the data-dependent flags properly, the most naive approach is to set them to the most conservative values (e.g., std::nullopt meaning this property is unknown), but this may make some flags overly conservative and hence affect the performance of functions that rely on these flags (e.g., isAllAscii_). On the other hand, some of the data-changing APIs may be called on a per-row basis, so it may be better to update the flags after the calls on all rows in the caller (e.g., SimpleVector::stats_ and BaseVector::setNull()) Also, data changing through BaseVector::mutableNulls(), FlatVector::mutableValues(), and DictionaryVector::mutableIndices() cannot be captured inside these calls, so the update of flags have to happen in their callers, or we can only reset the flags to their conservative default values.

So I suggest the followings.

1. We first look at the use of the data-dependent flags and delete those that are not needed.
2. For flags that are rarely used in query evaluation, we set them to the conservative default values in data-changing APIs. E.g., SimpleVector::stats_.
3. For data-changing APIs that are rarely used in query evaluation, we set flags to the conservative default values in them. E.g., MapVector::setKeysAndValues().
4. For BaseVector::mutableNulls(), FlatVector::mutableValues(), and DictionaryVector::mutableIndices(), they are used in ConjunctExpr and a few other UDFs and UDAFs. We can possibly update the flags in their callers.
5. For the rest flags and APIs, if updating a flag inside an APIs requires looping through values at all rows, then we set the flag to its conservative default value. Otherwise, we update the flag in that API.

[kagamiori]

cc @mbasmanova

[mbasmanova]

A similar bug was fixed in MapVector::prepareForReuse in #3291

[mbasmanova]

@kagamiori Wei, thank you for putting together a comprehensive description of the problem. To add a bit more context, the only flags being used in Velox are SimpleVector::isAllAscii_, asciiSetRows_ and MapVector:: sortedKeys_. Other flags are not being used and not being maintained. However, Saber may be using these. Let's check with them to see if the flags can be removed.

This problem applies not only to expression evaluation but to any code that modifies vector data. It would be nice to update the description to make that clear (otherwise, currently it sounds like the problem is specific to expression evaluation).

As a general rule, we say that the code that modifies the vector needs to ensure that vector is mutable (e.g. singly referenced and contains singly-referenced buffers and inner vectors). This is usually done by calling either BaseVector::prepareForReuse or ensureWritable APIs. We need to make sure these APIs reset data-dependent flags.

[kagamiori]

This problem applies not only to expression evaluation but to any code that modifies vector data. It would be nice to update the description to make that clear (otherwise, currently it sounds like the problem is specific to expression evaluation).

Makes sense. I've updated the description.

As a general rule, we say that the code that modifies the vector needs to ensure that vector is mutable (e.g. singly referenced and contains singly-referenced buffers and inner vectors). This is usually done by calling either BaseVector::prepareForReuse or ensureWritable APIs. We need to make sure these APIs reset data-dependent flags.

Thinking about this problem twice, I realize that the proposed suggestion of updating some flags in the caller of data-changing APIs is really not an option because we cannot control how custom code uses these APIs. The option of resetting data-dependent flags to default values in BaseVector::prepareForReuse() and ensureWritable() is a more centralized approach that would be easier to understand and maintain. (This option will make the result of SwitchExpr and CoalesceExpr always has default flag values if more than one branches are taken. We can start by resetting the flags to default and if this affect the performance of subsequent functions that rely on these flags, we can update the flags at the end of SwitchExpr and CoalesceExpr.)