zclllyybb commented on code in PR #60192: URL: https://github.com/apache/doris/pull/60192#discussion_r2780901311
########## regression-test/suites/query_p0/sql_functions/array_functions/array_combinations.groovy: ########## @@ -0,0 +1,44 @@ +// 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. + +suite("array_combinations") { Review Comment: should add more testcases, about empty column, f(literal, col), null, second arg>2 ... ########## be/src/vec/functions/array/function_array_combinations.cpp: ########## @@ -0,0 +1,182 @@ +// 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. + +#include "common/compiler_util.h" +#include "common/logging.h" +#include "common/status.h" +#include "runtime/define_primitive_type.h" +#include "runtime/primitive_type.h" +#include "vec/columns/column.h" +#include "vec/columns/column_array.h" +#include "vec/columns/column_const.h" +#include "vec/common/assert_cast.h" +#include "vec/core/field.h" +#include "vec/core/types.h" +#include "vec/data_types/data_type.h" +#include "vec/data_types/data_type_array.h" +#include "vec/data_types/data_type_decimal.h" +#include "vec/data_types/data_type_nullable.h" +#include "vec/functions/function.h" +#include "vec/functions/function_helpers.h" +#include "vec/functions/simple_function_factory.h" + +namespace doris::vectorized { +// array_combinations([1, 2, 3],2) -> [[1,2], [1,3], [2,3]] +// array_combinations([1, NULL, 3, NULL, 5]，4) -> [[1,NULL,3,NULL], [1,NULL,3,5], [NULL,3,NULL,5]] + +class FunctionArrayCombinations : public IFunction { +public: + static constexpr auto name = "array_combinations"; + static FunctionPtr create() { return std::make_shared<FunctionArrayCombinations>(); } + bool is_variadic() const override { return false; } + String get_name() const override { return name; } + + size_t get_number_of_arguments() const override { return 2; } + + DataTypePtr get_return_type_impl(const DataTypes& arguments) const override { + const auto* array_type = assert_cast<const DataTypeArray*>(arguments[0].get()); + auto elem_t = make_nullable(array_type->get_nested_type()); + auto res = std::make_shared<DataTypeArray>( + make_nullable(std::make_shared<DataTypeArray>(elem_t))); + return res; + } + + Status execute_impl(FunctionContext* context, Block& block, const ColumnNumbers& arguments, + uint32_t result, size_t input_rows_count) const override { + auto array = block.get_by_position(arguments[0]).column; + ColumnPtr num = + block.get_by_position(arguments[1]).column->convert_to_full_column_if_const(); + + Int64 combination_length = num->get_int(0); + + if (combination_length > MAX_COMBINATION_LENGTH || combination_length < 0) { + return Status::RuntimeError( + fmt::format("execute failed, function {}'s second argument must be bigger than " + "0 and not bigger than 5", + get_name())); + } + + ColumnPtr res; + const auto* src_arr = assert_cast<const ColumnArray*>(remove_nullable(array).get()); + const auto& offsets = + assert_cast<const ColumnArray::ColumnOffsets&>(src_arr->get_offsets_column()); + Status error = Status::OK(); + vector_const(src_arr, input_rows_count, res, offsets, combination_length, error); + if (!error.ok()) { + return error; + } + block.replace_by_position(result, std::move(res)); + return Status::OK(); + } + +private: + static const size_t MAX_COMBINATION_LENGTH = 5; + static const size_t MAX_COMBINATION_COUNT = 100000; + size_t _combination_count(size_t array_length, size_t combination_length) const { + // Then combinationCount(n, k) = combinationCount(n-1, k-1) * n/k (https://en.wikipedia.org/wiki/Combination#Number_of_k-combinations) + // The formula is recursive. Here, instead of starting with k=combinationCount, n=arrayLength and recursing, + // we start with k=0 n=(arrayLength-combinationLength) and proceed "bottom up". + + size_t combinations = 1; + + for (int i = 1; i <= combination_length; i++) { + combinations = combinations * (array_length - combination_length + i) / i; + } + + return combinations; + } + + ALWAYS_INLINE std::vector<size_t> _first_combination(Int64 combination_length, + size_t length) const { + std::vector<size_t> comb(combination_length + 1); + for (size_t i = 0; i < static_cast<size_t>(combination_length); ++i) { + comb[i] = i; + } + comb[combination_length] = length; + return comb; + } + + bool _next_combination(std::vector<size_t>& comb, Int64 combination_length) const { Review Comment: explain why this function could generate next comb ########## fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/functions/scalar/ArrayCombinations.java: ########## @@ -18,52 +18,67 @@ package org.apache.doris.nereids.trees.expressions.functions.scalar; import org.apache.doris.catalog.FunctionSignature; +import org.apache.doris.nereids.exceptions.AnalysisException; import org.apache.doris.nereids.trees.expressions.Expression; import org.apache.doris.nereids.trees.expressions.functions.ExplicitlyCastableSignature; import org.apache.doris.nereids.trees.expressions.functions.PropagateNullable; -import org.apache.doris.nereids.trees.expressions.shape.UnaryExpression; +import org.apache.doris.nereids.trees.expressions.literal.IntegerLikeLiteral; import org.apache.doris.nereids.trees.expressions.visitor.ExpressionVisitor; -import org.apache.doris.nereids.types.QuantileStateType; -import org.apache.doris.nereids.types.StringType; +import org.apache.doris.nereids.types.ArrayType; +import org.apache.doris.nereids.types.BigIntType; +import org.apache.doris.nereids.types.coercion.AnyDataType; +import org.apache.doris.nereids.types.coercion.FollowToAnyDataType; import com.google.common.base.Preconditions; import com.google.common.collect.ImmutableList; import java.util.List; /** - * Function 'quantile_state_to_base64'. + * ScalarFunction 'combinations' */ -public class QuantileStateToBase64 extends ScalarFunction - implements UnaryExpression, ExplicitlyCastableSignature, PropagateNullable { +public class ArrayCombinations extends ScalarFunction + implements ExplicitlyCastableSignature, PropagateNullable { public static final List<FunctionSignature> SIGNATURES = ImmutableList.of( - FunctionSignature.ret(StringType.INSTANCE).args(QuantileStateType.INSTANCE) - ); + FunctionSignature.ret(ArrayType.of(ArrayType.of(new FollowToAnyDataType(0)))) + .args(ArrayType.of(new AnyDataType(0)), BigIntType.INSTANCE)); /** - * constructor with 1 argument. + * constructor with 2 arguments. */ - public QuantileStateToBase64(Expression arg) { - super("quantile_state_to_base64", arg); + public ArrayCombinations(Expression arg0, Expression arg1) { + super("array_combinations", arg0, arg1); + } + + @Override + public void checkLegalityBeforeTypeCoercion() { + if (!(child(1) instanceof IntegerLikeLiteral)) { + throw new AnalysisException("Array_Combinations's second argument must be a constant literal."); + } } - /** - * withChildren. - */ @Override - public QuantileStateToBase64 withChildren(List<Expression> children) { - Preconditions.checkArgument(children.size() == 1); - return new QuantileStateToBase64(children.get(0)); + public void checkLegalityAfterRewrite() { + super.checkLegalityBeforeTypeCoercion(); Review Comment: why `super`? ########## be/src/vec/functions/array/function_array_combinations.cpp: ########## @@ -0,0 +1,184 @@ +// 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. + +#include "common/compiler_util.h" +#include "common/logging.h" +#include "common/status.h" +#include "runtime/define_primitive_type.h" +#include "runtime/primitive_type.h" +#include "vec/columns/column.h" +#include "vec/columns/column_array.h" +#include "vec/columns/column_const.h" +#include "vec/common/assert_cast.h" +#include "vec/core/field.h" +#include "vec/core/types.h" +#include "vec/data_types/data_type.h" +#include "vec/data_types/data_type_array.h" +#include "vec/data_types/data_type_decimal.h" +#include "vec/data_types/data_type_nullable.h" +#include "vec/functions/function.h" +#include "vec/functions/function_helpers.h" +#include "vec/functions/simple_function_factory.h" + +namespace doris::vectorized { +// array_combinations([1, 2, 3],2) -> [[1,2], [1,3], [2,3]] +// array_combinations([1, NULL, 3, NULL, 5]，4) -> [[1,NULL,3,NULL], [1,NULL,3,5], [NULL,3,NULL,5]] + +class FunctionArrayCombinations : public IFunction { +public: + static constexpr auto name = "array_combinations"; + static FunctionPtr create() { return std::make_shared<FunctionArrayCombinations>(); } + bool is_variadic() const override { return false; } + String get_name() const override { return name; } + + size_t get_number_of_arguments() const override { return 2; } + + DataTypePtr get_return_type_impl(const DataTypes& arguments) const override { + const auto* array_type = assert_cast<const DataTypeArray*>(arguments[0].get()); + auto elem_t = make_nullable(array_type->get_nested_type()); + auto res = std::make_shared<DataTypeArray>( + make_nullable(std::make_shared<DataTypeArray>(elem_t))); + return res; + } + + Status execute_impl(FunctionContext* context, Block& block, const ColumnNumbers& arguments, + uint32_t result, size_t input_rows_count) const override { + auto array = block.get_by_position(arguments[0]).column; + ColumnPtr num = block.get_by_position(arguments[1]).column; + + Int64 combination_length = num->get_int(0); + + if (combination_length > MAX_COMBINATION_LENGTH || combination_length < 0) { + return Status::RuntimeError( + fmt::format("execute failed, function {}'s second argument must be bigger than " + "0 and not bigger than 5", + get_name())); + } + + ColumnPtr res; + const auto* src_arr = assert_cast<const ColumnArray*>(remove_nullable(array).get()); + const auto& offsets = + assert_cast<const ColumnArray::ColumnOffsets&>(src_arr->get_offsets_column()); + Status status = vector_const(src_arr, input_rows_count, res, offsets, combination_length); + if (!status.ok()) { + return status; + } + block.replace_by_position(result, std::move(res)); + return status; + } + + ColumnNumbers get_arguments_that_are_always_constant() const override { return {1}; } + +private: + static const size_t MAX_COMBINATION_LENGTH = 5; + static const size_t MAX_COMBINATION_COUNT = 100000; + + // Then combinationCount(n, k) = combinationCount(n-1, k-1) * n/k (https://en.wikipedia.org/wiki/Combination#Number_of_k-combinations) + // The formula is recursive. Here, instead of starting with k=combinationCount, n=arrayLength and recursing, + // we start with k=0 n=(arrayLength-combinationLength) and proceed "bottom up". + size_t _combination_count(size_t array_length, size_t combination_length) const { + size_t combinations = 1; + + for (int i = 1; i <= combination_length; i++) { + combinations = combinations * (array_length - combination_length + i) / i; + } + + return combinations; + } + + ALWAYS_INLINE std::vector<size_t> _first_combination(Int64 combination_length, + size_t length) const { + std::vector<size_t> comb(combination_length + 1); + for (size_t i = 0; i < static_cast<size_t>(combination_length); ++i) { + comb[i] = i; + } + comb[combination_length] = length; + return comb; + } + + // generate next combination + bool _next_combination(std::vector<size_t>& comb, Int64 combination_length) const { + for (size_t i = 0; i < static_cast<size_t>(combination_length); ++i) { + if (comb[i] + 1 < comb[i + 1]) { + ++comb[i]; + for (size_t j = 0; j < i; ++j) { + comb[j] = j; + } + return true; + } + } + return false; + } + + Status vector_const(const ColumnArray* nested_src_column_ptr, size_t input_rows_count, + ColumnPtr& res, const ColumnArray::ColumnOffsets& offsets, + Int64 combination_length) const { + const auto& src_data = nested_src_column_ptr->get_data(); + const auto& src_offsets = offsets.get_data(); + + auto inner_data = src_data.clone_empty(); + auto inner_offsets = ColumnArray::ColumnOffsets::create(); + auto inner_arr = ColumnArray::create(std::move(inner_data), std::move(inner_offsets)); + auto* inner = assert_cast<ColumnArray*>(inner_arr.get()); + + auto outer_offsets = ColumnArray::ColumnOffsets::create(); + auto& outer_offsets_data = outer_offsets->get_data(); + outer_offsets_data.resize(input_rows_count); + + size_t prev_off = 0, outer_off = 0; + + for (size_t row = 0; row < input_rows_count; ++row) { + size_t curr_off = src_offsets[row]; + size_t row_len = curr_off - prev_off; + + if (combination_length <= 0 || static_cast<size_t>(combination_length) > row_len) { + outer_offsets_data[row] = outer_off; + prev_off = curr_off; + continue; + } + std::vector comb = _first_combination(combination_length, row_len); + inner->reserve(inner->size() + _combination_count(row_len, combination_length)); + outer_off += _combination_count(row_len, combination_length); + if (outer_off > MAX_COMBINATION_COUNT) { + return Status::RuntimeError( Review Comment: `InvalidArgument` instead ########## be/src/vec/functions/array/function_array_combinations.cpp: ########## @@ -0,0 +1,184 @@ +// 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. + +#include "common/compiler_util.h" +#include "common/logging.h" +#include "common/status.h" +#include "runtime/define_primitive_type.h" +#include "runtime/primitive_type.h" +#include "vec/columns/column.h" +#include "vec/columns/column_array.h" +#include "vec/columns/column_const.h" +#include "vec/common/assert_cast.h" +#include "vec/core/field.h" +#include "vec/core/types.h" +#include "vec/data_types/data_type.h" +#include "vec/data_types/data_type_array.h" +#include "vec/data_types/data_type_decimal.h" +#include "vec/data_types/data_type_nullable.h" +#include "vec/functions/function.h" +#include "vec/functions/function_helpers.h" +#include "vec/functions/simple_function_factory.h" + +namespace doris::vectorized { +// array_combinations([1, 2, 3],2) -> [[1,2], [1,3], [2,3]] +// array_combinations([1, NULL, 3, NULL, 5]，4) -> [[1,NULL,3,NULL], [1,NULL,3,5], [NULL,3,NULL,5]] + +class FunctionArrayCombinations : public IFunction { +public: + static constexpr auto name = "array_combinations"; + static FunctionPtr create() { return std::make_shared<FunctionArrayCombinations>(); } + bool is_variadic() const override { return false; } + String get_name() const override { return name; } + + size_t get_number_of_arguments() const override { return 2; } + + DataTypePtr get_return_type_impl(const DataTypes& arguments) const override { + const auto* array_type = assert_cast<const DataTypeArray*>(arguments[0].get()); + auto elem_t = make_nullable(array_type->get_nested_type()); + auto res = std::make_shared<DataTypeArray>( + make_nullable(std::make_shared<DataTypeArray>(elem_t))); + return res; + } + + Status execute_impl(FunctionContext* context, Block& block, const ColumnNumbers& arguments, + uint32_t result, size_t input_rows_count) const override { + auto array = block.get_by_position(arguments[0]).column; + ColumnPtr num = block.get_by_position(arguments[1]).column; + + Int64 combination_length = num->get_int(0); + + if (combination_length > MAX_COMBINATION_LENGTH || combination_length < 0) { + return Status::RuntimeError( + fmt::format("execute failed, function {}'s second argument must be bigger than " + "0 and not bigger than 5", + get_name())); + } + + ColumnPtr res; + const auto* src_arr = assert_cast<const ColumnArray*>(remove_nullable(array).get()); + const auto& offsets = + assert_cast<const ColumnArray::ColumnOffsets&>(src_arr->get_offsets_column()); + Status status = vector_const(src_arr, input_rows_count, res, offsets, combination_length); + if (!status.ok()) { + return status; + } + block.replace_by_position(result, std::move(res)); + return status; + } + + ColumnNumbers get_arguments_that_are_always_constant() const override { return {1}; } + +private: + static const size_t MAX_COMBINATION_LENGTH = 5; + static const size_t MAX_COMBINATION_COUNT = 100000; + + // Then combinationCount(n, k) = combinationCount(n-1, k-1) * n/k (https://en.wikipedia.org/wiki/Combination#Number_of_k-combinations) + // The formula is recursive. Here, instead of starting with k=combinationCount, n=arrayLength and recursing, + // we start with k=0 n=(arrayLength-combinationLength) and proceed "bottom up". + size_t _combination_count(size_t array_length, size_t combination_length) const { + size_t combinations = 1; + + for (int i = 1; i <= combination_length; i++) { + combinations = combinations * (array_length - combination_length + i) / i; + } + + return combinations; + } + + ALWAYS_INLINE std::vector<size_t> _first_combination(Int64 combination_length, + size_t length) const { + std::vector<size_t> comb(combination_length + 1); + for (size_t i = 0; i < static_cast<size_t>(combination_length); ++i) { + comb[i] = i; + } + comb[combination_length] = length; + return comb; + } + + // generate next combination + bool _next_combination(std::vector<size_t>& comb, Int64 combination_length) const { + for (size_t i = 0; i < static_cast<size_t>(combination_length); ++i) { + if (comb[i] + 1 < comb[i + 1]) { + ++comb[i]; + for (size_t j = 0; j < i; ++j) { + comb[j] = j; + } + return true; + } + } + return false; + } + + Status vector_const(const ColumnArray* nested_src_column_ptr, size_t input_rows_count, + ColumnPtr& res, const ColumnArray::ColumnOffsets& offsets, + Int64 combination_length) const { Review Comment: directly pass `combination_length` as uint -- 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]
