pitrou commented on code in PR #49679: URL: https://github.com/apache/arrow/pull/49679#discussion_r3631221605
########## cpp/src/arrow/compute/kernels/vector_search_sorted.cc: ########## @@ -0,0 +1,1166 @@ +// 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 "arrow/compute/api_vector.h" + +#include <algorithm> +#include <memory> +#include <optional> +#include <ranges> +#include <type_traits> +#include <utility> + +#include "arrow/array/array_primitive.h" +#include "arrow/array/array_run_end.h" +#include "arrow/array/concatenate.h" +#include "arrow/array/util.h" +#include "arrow/buffer_builder.h" +#include "arrow/chunk_resolver.h" +#include "arrow/compute/function.h" +#include "arrow/compute/kernels/codegen_internal.h" +#include "arrow/compute/kernels/vector_sort_internal.h" +#include "arrow/compute/registry.h" +#include "arrow/compute/registry_internal.h" +#include "arrow/type_traits.h" +#include "arrow/util/checked_cast.h" +#include "arrow/util/logging_internal.h" +#include "arrow/util/ree_util.h" +#include "arrow/util/unreachable.h" + +namespace arrow { + +using internal::checked_cast; + +namespace compute::internal { +namespace { + +/// Return the static default options instance used by the meta-function. +const SearchSortedOptions* GetDefaultSearchSortedOptions() { + static const auto kDefaultSearchSortedOptions = SearchSortedOptions::Defaults(); + return &kDefaultSearchSortedOptions; +} + +const FunctionDoc search_sorted_doc( + "Find insertion indices for sorted input", + ("Return the index where each needle should be inserted in a sorted input array\n" + "to maintain ascending order.\n" + "\n" + "With side='left', returns the first suitable index (lower bound).\n" + "With side='right', returns the last suitable index (upper bound).\n" + "\n" + "The searched values may be provided as an array or chunked array and must\n" + "already be sorted in ascending order. Null values in the searched array are\n" + "supported when clustered entirely at the start or\n" + "entirely at the end. Non-null needles are matched only against the non-null\n" + "portion of the searched array. Needles may be a scalar, array, or chunked\n" + "array. Null needles emit nulls in the output."), + {"values", "needles"}, "SearchSortedOptions"); + +// This file implements search_sorted as a normalization pipeline around one +// typed binary-search core. +// +// The searched values are first validated, unwrapped to their logical type, +// and adapted to a uniform accessor interface. Plain arrays and chunked arrays +// expose logical element access directly. Run-end encoded (REE) arrays expose a +// search domain over physical runs while still translating insertion positions +// back to logical indices. The typed accessors are intentionally thin: shared +// offset, length, run-resolution, and logical-index bookkeeping lives in +// non-templated helpers so that the binary search is specialized by physical +// value type without cloning the surrounding normalization logic. +// +// Values null handling is normalized before any search happens. Nulls are only +// accepted when clustered entirely at the start or entirely at the end of the +// sorted values. The implementation computes the contiguous non-null logical +// window once and then searches only within that window. For REE values this +// requires logical null counting, because nullness lives in the values child +// rather than in a top-level validity bitmap. +// +// Needles are normalized before accessor dispatch where possible. Null scalar +// needles return a null scalar result immediately. Non-null scalar needles are +// materialized as length-1 arrays so the main implementation only needs one +// array-oriented emit path. REE needles are handled separately: the kernel +// searches each physical REE value once, rebuilds a temporary REE UInt64 +// result with the same logical run ends, and then run-end decodes it back to +// the dense public output shape. Plain array needles are visited element by +// element through one callback interface that propagates logical nulls. +// +// The actual comparison/search step is shared across all normalized inputs. +// After dispatching to the logical/physical Arrow representation, the kernel +// runs a lower-bound or upper-bound binary search depending on +// `SearchSortedOptions::side`, then maps the found position back to the caller- +// visible logical insertion index. +// +// Output materialization is centralized in a UInt64 builder with an optional +// validity bitmap. Non-null-only needles only build the values buffer, while +// nullable needles also emit the null bitmap. Logical null detection uses +// `ComputeLogicalNullCount()` so plain arrays, chunked arrays, and REE inputs +// all participate in the same output-nullability decision. +// +// High-level flow: +// +// values datum +// | +// +--> ValidateSortedValuesInput +// | +// +--> LogicalType / FindNonNullValuesRange +// | +// +--> VisitValuesAccessor +// | +// +--> PlainArrayAccessor +// | +// +--> RunEndEncodedValuesAccessor +// | +// +--> ChunkedArrayAccessor +// | +// `--> ChunkedRunEndEncodedValuesAccessor +// +// needles datum +// | +// +--> ValidateNeedleInput +// | +// +--> scalar null +// | `--> return null scalar +// | +// +--> scalar value +// | `--> MakeArrayFromScalar(length=1) +// | +// +--> REE needles +// | +--> search physical runs once +// | +--> rebuild temporary REE uint64 result +// | `--> RunEndDecode back to dense output +// | +// `--> DatumHasNulls / VisitNeedleRuns +// | +// +--> plain array -> one logical element per slot +// | +// `--> chunked input -> recurse chunk by chunk +// +// normalized values accessor + normalized needle runs +// | +// `--> FindInsertionPoint<T> +// | +// +--> side = left -> lower_bound semantics +// | +// `--> side = right -> upper_bound semantics +// +// result materialization +// | +// +--> no needle nulls +// | `--> InsertionIndexBuilder<false> +// | `--> fill uint64 buffer directly +// | +// `--> nullable needles +// `--> InsertionIndexBuilder<true> +// +--> AppendNulls for null runs +// `--> bulk fill repeated indices and validity bits +// +// A rough map of the file: +// +// [validation + type helpers] +// | +// [value accessors] +// | +// [needle visitors] +// | +// [typed search + output helpers] +// | +// [meta-function dispatch] +// + +#define VISIT_SEARCH_SORTED_PHYSICAL_TYPES(VISIT) \ + VISIT(BooleanType) \ + VISIT(Int8Type) \ + VISIT(Int16Type) \ + VISIT(Int32Type) \ + VISIT(Int64Type) \ + VISIT(UInt8Type) \ + VISIT(UInt16Type) \ + VISIT(UInt32Type) \ + VISIT(UInt64Type) \ + VISIT(FloatType) \ + VISIT(DoubleType) \ + VISIT(BinaryType) \ + VISIT(LargeBinaryType) \ + VISIT(BinaryViewType) Review Comment: Not a bad suggestion from Copilot, but then we should also include Float16, Decimal32 and Decimal64. -- 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]
