github-actions[bot] commented on code in PR #67311: URL: https://github.com/apache/doris/pull/67311#discussion_r3906029384
########## be/src/exprs/function/function_inner_product.h: ########## @@ -0,0 +1,374 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +#pragma once + +#include "core/assert_cast.h" +#include "core/column/column_const.h" +#include "core/column/column_map.h" +#include "core/column/column_nullable.h" +#include "core/column/column_string.h" +#include "core/data_type/data_type_map.h" +#include "core/string_ref.h" +#include "exec/common/hash_table/hash.h" +#include "exec/common/hash_table/phmap_fwd_decl.h" +#include "exec/common/util.hpp" +#include "exprs/function/array/function_array_distance.h" + +namespace doris { + +namespace detail { + +template <PrimitiveType KeyType> +struct InnerProductMapKeyTraits { + using ColumnType = PrimitiveTypeTraits<KeyType>::ColumnType; + using Key = PrimitiveTypeTraits<KeyType>::CppType; + using KeyAccessor = const Key*; + using Hash = HashCRC32<Key>; + + static KeyAccessor get_key_accessor(const ColumnType& column) { + return column.get_data().data(); + } + + static Key get_key(KeyAccessor keys, size_t index) { return keys[index]; } +}; + +template <> +struct InnerProductMapKeyTraits<TYPE_STRING> { + using ColumnType = ColumnString; + using Key = StringRef; + using KeyAccessor = const ColumnType*; + using Hash = StringRefHash; + + static KeyAccessor get_key_accessor(const ColumnType& column) { return &column; } + + static Key get_key(KeyAccessor keys, size_t index) { return keys->get_data_at(index); } +}; + +} // namespace detail + +class FunctionInnerProduct final : public FunctionArrayDistance<InnerProduct> { +public: + static FunctionPtr create() { return std::make_shared<FunctionInnerProduct>(); } + + DataTypePtr get_return_type_impl(const DataTypes& arguments) const override { + if (arguments.size() != 2) { + throw doris::Exception(ErrorCode::INVALID_ARGUMENT, "Invalid number of arguments"); + } + + const bool both_arrays = arguments[0]->get_primitive_type() == TYPE_ARRAY && + arguments[1]->get_primitive_type() == TYPE_ARRAY; + if (both_arrays) { + return FunctionArrayDistance<InnerProduct>::get_return_type_impl(arguments); + } + + const bool both_maps = arguments[0]->get_primitive_type() == TYPE_MAP && + arguments[1]->get_primitive_type() == TYPE_MAP; + if (!both_maps) { + throw doris::Exception(ErrorCode::INVALID_ARGUMENT, + "Arguments for function {} must be arrays or maps", get_name()); + } + + const auto& left_type = assert_cast<const DataTypeMap&>(*remove_nullable(arguments[0])); + const auto& right_type = assert_cast<const DataTypeMap&>(*remove_nullable(arguments[1])); + if (!left_type.get_key_type()->equals(*right_type.get_key_type())) { + throw doris::Exception(ErrorCode::INVALID_ARGUMENT, + "Map keys for function {} must have the same type", get_name()); + } + const auto key_type = remove_nullable(left_type.get_key_type())->get_primitive_type(); + if (!_is_supported_map_key_type(key_type)) { + throw doris::Exception(ErrorCode::INVALID_ARGUMENT, + "Function {} only supports integer or string map keys", + get_name()); + } + if (remove_nullable(left_type.get_value_type())->get_primitive_type() != TYPE_FLOAT || + remove_nullable(right_type.get_value_type())->get_primitive_type() != TYPE_FLOAT) { + throw doris::Exception(ErrorCode::INVALID_ARGUMENT, + "Map values for function {} must be FLOAT", get_name()); + } + return std::make_shared<DataTypeFloat32>(); + } + + Status execute_impl(FunctionContext* context, Block& block, const ColumnNumbers& arguments, + uint32_t result, size_t input_rows_count) const override { + if (block.get_by_position(arguments[0]).type->get_primitive_type() == TYPE_MAP) { + return _execute_map(block, arguments, result, input_rows_count); + } + return FunctionArrayDistance<InnerProduct>::execute_impl(context, block, arguments, result, + input_rows_count); + } + +private: + using ColumnType = PrimitiveTypeTraits<TYPE_FLOAT>::ColumnType; + + struct MapRange { + size_t begin; + size_t size; + }; + + static ALWAYS_INLINE MapRange _get_map_range(const ColumnMap& map, bool is_const, size_t row) { + const size_t actual_row = index_check_const(row, is_const); + return {map.offset_at(actual_row), map.size_at(actual_row)}; + } + + static bool _is_supported_map_key_type(PrimitiveType type) { + switch (type) { + case TYPE_TINYINT: + case TYPE_SMALLINT: + case TYPE_INT: + case TYPE_BIGINT: + case TYPE_LARGEINT: + case TYPE_CHAR: + case TYPE_VARCHAR: + case TYPE_STRING: + return true; + default: + return false; + } + } + + static const ColumnMap& _get_map_column(const ColumnPtr& column, const char* argument_name, + const String& function_name, bool& is_const) { + const IColumn* raw_column = column.get(); + is_const = is_column_const(*raw_column); + if (is_const) { + raw_column = assert_cast<const ColumnConst*>(raw_column)->get_data_column_ptr().get(); + } + + if (const auto* nullable = check_and_get_column<ColumnNullable>(raw_column)) { + if (raw_column->has_null()) { + throw doris::Exception(ErrorCode::INVALID_ARGUMENT, + "{} for function {} cannot be null", argument_name, + function_name); + } + raw_column = nullable->get_nested_column_ptr().get(); + } + + return assert_cast<const ColumnMap&>(*raw_column); + } + + static const IColumn& _get_key_column(const IColumn& column, const UInt8*& null_map) { + null_map = nullptr; + if (const auto* nullable = check_and_get_column<ColumnNullable>(&column)) { + null_map = nullable->get_null_map_data().data(); + return nullable->get_nested_column(); + } + return column; + } + + static const IColumn& _get_value_column(const IColumn& column, + const ColumnNullable*& nullable_with_null) { + nullable_with_null = nullptr; + if (const auto* nullable = check_and_get_column<ColumnNullable>(&column)) { + if (nullable->has_null()) { + nullable_with_null = nullable; + } + return nullable->get_nested_column(); + } + return column; + } + + template <typename KeyTraits> + static void _validate_retained_values(typename KeyTraits::KeyAccessor keys, + const UInt8* key_null_map, + const ColumnNullable& nullable_values, MapRange range, + const char* argument_name) { + if (!nullable_values.has_null(range.begin, range.begin + range.size)) { + return; + } + + using Key = typename KeyTraits::Key; + doris::flat_hash_set<Key, typename KeyTraits::Hash> seen_keys; + seen_keys.reserve(range.size); + const auto& value_null_map = nullable_values.get_null_map_data(); + bool has_null_key = false; + + // Only the last value for each key is visible. Ignore NULL values shadowed by a later + // duplicate, matching ColumnMap::deduplicate_keys() semantics. + for (size_t i = range.begin + range.size; i > range.begin; --i) { + const size_t index = i - 1; + if (key_null_map != nullptr && key_null_map[index]) { + if (!has_null_key) { + has_null_key = true; + if (value_null_map[index]) { + throw doris::Exception(ErrorCode::INVALID_ARGUMENT, + "{} for function {} cannot have null", argument_name, + InnerProduct::name); + } + } + continue; + } + + if (seen_keys.emplace(KeyTraits::get_key(keys, index)).second && + value_null_map[index]) { + throw doris::Exception(ErrorCode::INVALID_ARGUMENT, + "{} for function {} cannot have null", argument_name, + InnerProduct::name); + } + } + } + + template <PrimitiveType KeyType> + static void _execute_map_typed(const ColumnMap& left, bool left_is_const, + const ColumnMap& right, bool right_is_const, + ColumnType::Container& destination_data, + size_t input_rows_count) { + using KeyTraits = detail::InnerProductMapKeyTraits<KeyType>; + using Key = typename KeyTraits::Key; + using KeyAccessor = typename KeyTraits::KeyAccessor; + using KeyColumn = typename KeyTraits::ColumnType; + + const UInt8* left_key_null_map = nullptr; + const UInt8* right_key_null_map = nullptr; + const auto& left_keys = + assert_cast<const KeyColumn&>(_get_key_column(left.get_keys(), left_key_null_map)); + const auto& right_keys = assert_cast<const KeyColumn&>( + _get_key_column(right.get_keys(), right_key_null_map)); + const ColumnNullable* left_nullable_values = nullptr; + const ColumnNullable* right_nullable_values = nullptr; + const auto& left_values = + assert_cast<const ColumnType&>( + _get_value_column(left.get_values(), left_nullable_values)) + .get_data(); + const auto& right_values = + assert_cast<const ColumnType&>( + _get_value_column(right.get_values(), right_nullable_values)) + .get_data(); + + struct MapData { + KeyAccessor keys; + const UInt8* key_null_map; + const float* values; + const ColumnNullable* nullable_values; + }; + + const MapData left_data {KeyTraits::get_key_accessor(left_keys), left_key_null_map, + left_values.data(), left_nullable_values}; + const MapData right_data {KeyTraits::get_key_accessor(right_keys), right_key_null_map, + right_values.data(), right_nullable_values}; + + // Build the hash table from the smaller map row to minimize temporary memory. + doris::flat_hash_map<Key, float, typename KeyTraits::Hash> values_by_key; + for (size_t row = 0; row < input_rows_count; ++row) { Review Comment: [P1] Avoid reprocessing the constant sparse vector in this row loop. When exactly one argument is a `ColumnConst`, the all-constant shortcut does not fire; `_get_map_range()` returns physical row 0 every time, but this loop still validates and rebuilds or scans all K constant entries for each of N rows. Thus the common `inner_product(map_literal, map_column)` shape does O(N*K + sum(row entries)) key work. Please add an adaptive one-constant path that normalizes/reuses the constant side when beneficial, while preserving last-wins and NULL-key/value rules without forcing O(K) scratch memory when the varying rows are much smaller, and cover a multi-row high-cardinality case. ########## be/src/exprs/function/function_inner_product.h: ########## @@ -0,0 +1,374 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +#pragma once + +#include "core/assert_cast.h" +#include "core/column/column_const.h" +#include "core/column/column_map.h" +#include "core/column/column_nullable.h" +#include "core/column/column_string.h" +#include "core/data_type/data_type_map.h" +#include "core/string_ref.h" +#include "exec/common/hash_table/hash.h" +#include "exec/common/hash_table/phmap_fwd_decl.h" +#include "exec/common/util.hpp" +#include "exprs/function/array/function_array_distance.h" + +namespace doris { + +namespace detail { + +template <PrimitiveType KeyType> +struct InnerProductMapKeyTraits { + using ColumnType = PrimitiveTypeTraits<KeyType>::ColumnType; + using Key = PrimitiveTypeTraits<KeyType>::CppType; + using KeyAccessor = const Key*; + using Hash = HashCRC32<Key>; + + static KeyAccessor get_key_accessor(const ColumnType& column) { + return column.get_data().data(); + } + + static Key get_key(KeyAccessor keys, size_t index) { return keys[index]; } +}; + +template <> +struct InnerProductMapKeyTraits<TYPE_STRING> { + using ColumnType = ColumnString; + using Key = StringRef; + using KeyAccessor = const ColumnType*; + using Hash = StringRefHash; + + static KeyAccessor get_key_accessor(const ColumnType& column) { return &column; } + + static Key get_key(KeyAccessor keys, size_t index) { return keys->get_data_at(index); } +}; + +} // namespace detail + +class FunctionInnerProduct final : public FunctionArrayDistance<InnerProduct> { +public: + static FunctionPtr create() { return std::make_shared<FunctionInnerProduct>(); } + + DataTypePtr get_return_type_impl(const DataTypes& arguments) const override { + if (arguments.size() != 2) { + throw doris::Exception(ErrorCode::INVALID_ARGUMENT, "Invalid number of arguments"); + } + + const bool both_arrays = arguments[0]->get_primitive_type() == TYPE_ARRAY && + arguments[1]->get_primitive_type() == TYPE_ARRAY; + if (both_arrays) { + return FunctionArrayDistance<InnerProduct>::get_return_type_impl(arguments); + } + + const bool both_maps = arguments[0]->get_primitive_type() == TYPE_MAP && + arguments[1]->get_primitive_type() == TYPE_MAP; + if (!both_maps) { + throw doris::Exception(ErrorCode::INVALID_ARGUMENT, + "Arguments for function {} must be arrays or maps", get_name()); + } + + const auto& left_type = assert_cast<const DataTypeMap&>(*remove_nullable(arguments[0])); + const auto& right_type = assert_cast<const DataTypeMap&>(*remove_nullable(arguments[1])); + if (!left_type.get_key_type()->equals(*right_type.get_key_type())) { + throw doris::Exception(ErrorCode::INVALID_ARGUMENT, + "Map keys for function {} must have the same type", get_name()); + } + const auto key_type = remove_nullable(left_type.get_key_type())->get_primitive_type(); + if (!_is_supported_map_key_type(key_type)) { + throw doris::Exception(ErrorCode::INVALID_ARGUMENT, + "Function {} only supports integer or string map keys", + get_name()); + } + if (remove_nullable(left_type.get_value_type())->get_primitive_type() != TYPE_FLOAT || + remove_nullable(right_type.get_value_type())->get_primitive_type() != TYPE_FLOAT) { + throw doris::Exception(ErrorCode::INVALID_ARGUMENT, + "Map values for function {} must be FLOAT", get_name()); + } + return std::make_shared<DataTypeFloat32>(); + } + + Status execute_impl(FunctionContext* context, Block& block, const ColumnNumbers& arguments, + uint32_t result, size_t input_rows_count) const override { + if (block.get_by_position(arguments[0]).type->get_primitive_type() == TYPE_MAP) { + return _execute_map(block, arguments, result, input_rows_count); + } + return FunctionArrayDistance<InnerProduct>::execute_impl(context, block, arguments, result, + input_rows_count); + } + +private: + using ColumnType = PrimitiveTypeTraits<TYPE_FLOAT>::ColumnType; + + struct MapRange { + size_t begin; + size_t size; + }; + + static ALWAYS_INLINE MapRange _get_map_range(const ColumnMap& map, bool is_const, size_t row) { + const size_t actual_row = index_check_const(row, is_const); + return {map.offset_at(actual_row), map.size_at(actual_row)}; + } + + static bool _is_supported_map_key_type(PrimitiveType type) { + switch (type) { + case TYPE_TINYINT: + case TYPE_SMALLINT: + case TYPE_INT: + case TYPE_BIGINT: + case TYPE_LARGEINT: + case TYPE_CHAR: + case TYPE_VARCHAR: + case TYPE_STRING: + return true; + default: + return false; + } + } + + static const ColumnMap& _get_map_column(const ColumnPtr& column, const char* argument_name, + const String& function_name, bool& is_const) { + const IColumn* raw_column = column.get(); + is_const = is_column_const(*raw_column); + if (is_const) { + raw_column = assert_cast<const ColumnConst*>(raw_column)->get_data_column_ptr().get(); + } + + if (const auto* nullable = check_and_get_column<ColumnNullable>(raw_column)) { + if (raw_column->has_null()) { + throw doris::Exception(ErrorCode::INVALID_ARGUMENT, + "{} for function {} cannot be null", argument_name, + function_name); + } + raw_column = nullable->get_nested_column_ptr().get(); + } + + return assert_cast<const ColumnMap&>(*raw_column); + } + + static const IColumn& _get_key_column(const IColumn& column, const UInt8*& null_map) { + null_map = nullptr; + if (const auto* nullable = check_and_get_column<ColumnNullable>(&column)) { + null_map = nullable->get_null_map_data().data(); + return nullable->get_nested_column(); + } + return column; + } + + static const IColumn& _get_value_column(const IColumn& column, + const ColumnNullable*& nullable_with_null) { + nullable_with_null = nullptr; + if (const auto* nullable = check_and_get_column<ColumnNullable>(&column)) { + if (nullable->has_null()) { + nullable_with_null = nullable; + } + return nullable->get_nested_column(); + } + return column; + } + + template <typename KeyTraits> + static void _validate_retained_values(typename KeyTraits::KeyAccessor keys, + const UInt8* key_null_map, + const ColumnNullable& nullable_values, MapRange range, + const char* argument_name) { + if (!nullable_values.has_null(range.begin, range.begin + range.size)) { + return; + } + + using Key = typename KeyTraits::Key; + doris::flat_hash_set<Key, typename KeyTraits::Hash> seen_keys; + seen_keys.reserve(range.size); + const auto& value_null_map = nullable_values.get_null_map_data(); + bool has_null_key = false; + + // Only the last value for each key is visible. Ignore NULL values shadowed by a later + // duplicate, matching ColumnMap::deduplicate_keys() semantics. + for (size_t i = range.begin + range.size; i > range.begin; --i) { + const size_t index = i - 1; + if (key_null_map != nullptr && key_null_map[index]) { + if (!has_null_key) { + has_null_key = true; + if (value_null_map[index]) { + throw doris::Exception(ErrorCode::INVALID_ARGUMENT, + "{} for function {} cannot have null", argument_name, + InnerProduct::name); + } + } + continue; + } + + if (seen_keys.emplace(KeyTraits::get_key(keys, index)).second && + value_null_map[index]) { + throw doris::Exception(ErrorCode::INVALID_ARGUMENT, + "{} for function {} cannot have null", argument_name, + InnerProduct::name); + } + } + } + + template <PrimitiveType KeyType> + static void _execute_map_typed(const ColumnMap& left, bool left_is_const, + const ColumnMap& right, bool right_is_const, + ColumnType::Container& destination_data, + size_t input_rows_count) { + using KeyTraits = detail::InnerProductMapKeyTraits<KeyType>; + using Key = typename KeyTraits::Key; + using KeyAccessor = typename KeyTraits::KeyAccessor; + using KeyColumn = typename KeyTraits::ColumnType; + + const UInt8* left_key_null_map = nullptr; + const UInt8* right_key_null_map = nullptr; + const auto& left_keys = + assert_cast<const KeyColumn&>(_get_key_column(left.get_keys(), left_key_null_map)); + const auto& right_keys = assert_cast<const KeyColumn&>( + _get_key_column(right.get_keys(), right_key_null_map)); + const ColumnNullable* left_nullable_values = nullptr; + const ColumnNullable* right_nullable_values = nullptr; + const auto& left_values = + assert_cast<const ColumnType&>( + _get_value_column(left.get_values(), left_nullable_values)) + .get_data(); + const auto& right_values = + assert_cast<const ColumnType&>( + _get_value_column(right.get_values(), right_nullable_values)) + .get_data(); + + struct MapData { + KeyAccessor keys; + const UInt8* key_null_map; + const float* values; + const ColumnNullable* nullable_values; + }; + + const MapData left_data {KeyTraits::get_key_accessor(left_keys), left_key_null_map, + left_values.data(), left_nullable_values}; + const MapData right_data {KeyTraits::get_key_accessor(right_keys), right_key_null_map, + right_values.data(), right_nullable_values}; + + // Build the hash table from the smaller map row to minimize temporary memory. + doris::flat_hash_map<Key, float, typename KeyTraits::Hash> values_by_key; + for (size_t row = 0; row < input_rows_count; ++row) { + const MapRange left_range = _get_map_range(left, left_is_const, row); + const MapRange right_range = _get_map_range(right, right_is_const, row); + if (left_data.nullable_values != nullptr) { + _validate_retained_values<KeyTraits>(left_data.keys, left_data.key_null_map, + *left_data.nullable_values, left_range, + "First argument"); + } + if (right_data.nullable_values != nullptr) { + _validate_retained_values<KeyTraits>(right_data.keys, right_data.key_null_map, + *right_data.nullable_values, right_range, + "Second argument"); + } + const bool build_left = left_range.size <= right_range.size; Review Comment: [P2] Short-circuit empty rows after the retained-NULL checks above. If either range is empty, the result is already `0.0F`, but selecting the empty side for the build still makes the probe loop perform one guaranteed-miss lookup for every entry in the other map. Assigning zero and continuing here preserves NULL/last-wins behavior and eliminates that avoidable post-validation hash scan (while nullable-value validation may still scan the nonempty row). Please add a high-cardinality empty/nonempty case. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
