kszucs commented on code in PR #45001: URL: https://github.com/apache/arrow/pull/45001#discussion_r3968998058
########## cpp/src/arrow/compute/kernels/scalar_hash.cc: ########## @@ -0,0 +1,531 @@ +// 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 <algorithm> +#include <memory> +#include <string> +#include <utility> +#include <vector> + +#include "arrow/array/array_base.h" +#include "arrow/array/util.h" +#include "arrow/compute/cast.h" +#include "arrow/compute/kernels/common_internal.h" +#include "arrow/compute/key_hash_internal.h" +#include "arrow/compute/light_array_internal.h" +#include "arrow/compute/registry_internal.h" +#include "arrow/compute/util.h" +#include "arrow/result.h" +#include "arrow/util/bit_util.h" +#include "arrow/util/bitmap_ops.h" + +namespace arrow { +namespace compute { +namespace internal { + +// Define symbols visible within `arrow::compute::internal` in this file; +// these symbols are not visible outside of this file. +namespace { + +// ------------------------------ +// Kernel implementations +// It is expected that HashArrowType is either UInt32Type or UInt64Type (default) + +// Free function (not dependent on ArrowType/Hasher) to avoid codegen per instantiation. +// Only called with a plain column; HashArray routes everything else (see +// NeedsRecursiveHash) elsewhere first. +Result<KeyColumnArray> ToColumnArray(const ArraySpan& array) { + KeyColumnMetadata metadata; + const uint8_t* validity_buffer = nullptr; + const uint8_t* fixed_length_buffer = nullptr; + const uint8_t* var_length_buffer = nullptr; + + if (array.GetBuffer(0) != nullptr) { + validity_buffer = array.GetBuffer(0)->data(); + } + if (array.GetBuffer(1) != nullptr) { + fixed_length_buffer = array.GetBuffer(1)->data(); + } + + auto type = array.type; + auto type_id = type->id(); + if (type_id == Type::NA) { + metadata = KeyColumnMetadata(true, 0, true); + } else if (type_id == Type::BOOL) { + metadata = KeyColumnMetadata(true, 0); + } else if (is_fixed_width(type_id)) { + metadata = KeyColumnMetadata(true, type->bit_width() / 8); + } else if (is_binary_like(type_id)) { + metadata = KeyColumnMetadata(false, sizeof(uint32_t)); + if (array.GetBuffer(2) != nullptr) { + var_length_buffer = array.GetBuffer(2)->data(); + } + } else if (is_large_binary_like(type_id)) { + metadata = KeyColumnMetadata(false, sizeof(uint64_t)); + if (array.GetBuffer(2) != nullptr) { + var_length_buffer = array.GetBuffer(2)->data(); + } + } else { + return Status::TypeError("Unsupported column data type ", type->name(), + " used with hash32/hash64 compute kernel"); + } + + return KeyColumnArray(metadata, array.length, validity_buffer, fixed_length_buffer, + var_length_buffer); +} + +// Whether HashArray must handle `type` itself rather than passing it to +// ToColumnArray/HashMultiColumn. Broader than is_nested(): EXTENSION and DICTIONARY +// aren't nested, but ToColumnArray has no case for either (and hashing a dictionary's +// raw indices would be wrong anyway). A zero-width fixed_size_binary isn't nested +// either, but ToColumnArray can only describe it as a fixed-width column of length 0 -- +// exactly how a bit-packed boolean is encoded -- so HashMultiColumn would take each +// row's hash from a bit that doesn't exist (see HashArray's dedicated branch). +bool NeedsRecursiveHash(const DataType& type) { + auto type_id = type.id(); + return type_id == Type::EXTENSION || type_id == Type::DICTIONARY || + is_nested(type_id) || + (type_id == Type::FIXED_SIZE_BINARY && type.byte_width() == 0); +} + +// Writes `array`'s own validity into `out_validity` (a fresh 0-offset bitmap), rebasing +// off array.offset. Only called for types whose validity really is a plain bitmap; union +// and run-end-encoded, which ArraySpan::IsValid computes specially, never reach here. +void WriteOwnValidity(const ArraySpan& array, uint8_t* out_validity) { + if (array.GetBuffer(0) == nullptr) { + // No bitmap: every row shares one answer, all valid except for NullType, which is + // implicitly all-null. + bit_util::SetBitsTo(out_validity, 0, array.length, + /*bits_are_set=*/array.type->id() != Type::NA); + return; + } + ::arrow::internal::CopyBitmap(array.GetBuffer(0)->data(), array.offset, array.length, + out_validity, /*dest_offset=*/0); +} + +// Folds one row's child elements into a single hash. `validity` is the elements' +// validity, 0-based like `value_hashes`, or nullptr when no element is null. +// +// A valid element folds its hash; a null one folds its position into a second +// accumulator, mixed in at the end. A null's own hash is never folded, since a null +// slot's bytes are undefined per the columnar spec. It must still contribute something, +// or [null] would equal [], but no stand-in hash works: any constant collides with a +// real element hashing to it, and 0 in particular is both what a valid integer 0 hashes +// to and what HashMultiColumn writes for a null slot, which made [null] and [0] +// identical. Nothing in the second accumulator can be mistaken for a value hash, so it +// need only record where the nulls are -- positions, so [null, x] and [x, null] differ. +// +// Seeded with CombineHashes(0, 0) rather than 0 just so an empty list doesn't hash to a +// bare 0. +template <typename c_type, typename Hasher> +c_type CombineRange(const c_type* value_hashes, const uint8_t* validity, int64_t start, + int64_t end) { + c_type combined = Hasher::CombineHashes(0, 0); + c_type combined_validity = Hasher::CombineHashes(0, 0); + if (validity == nullptr) { + // Nothing in the child is null, so no element can contribute to combined_validity: + // fold the values alone, with the bit test hoisted out of the loop. + for (int64_t j = start; j < end; j++) { + combined = Hasher::CombineHashes(combined, value_hashes[j]); + } + } else { + for (int64_t j = start; j < end; j++) { + if (bit_util::GetBit(validity, j)) { + combined = Hasher::CombineHashes(combined, value_hashes[j]); + } else { + combined_validity = + Hasher::CombineHashes(combined_validity, static_cast<c_type>(j - start + 1)); + } + } + } + return Hasher::CombineHashes(combined, combined_validity); +} + +template <typename ArrowType, typename Hasher> +struct FastHashScalar { + using c_type = typename ArrowType::c_type; + + // Hashes the [offset, offset + length) slice of `child` into hash values plus real + // validity, always based at offset 0 whatever `child`'s own offset (callers read the + // buffers row-0-based). Only a null row's validity bit is meaningful, not its hash + // value; callers folding these into a parent hash must handle that (see + // HashListArray). + static Result<std::shared_ptr<ArrayData>> HashChild(const ArraySpan& child, + int64_t offset, int64_t length, + LightContext* hash_ctx, + ExecContext* exec_ctx) { + auto sliced = child; + sliced.SetSlice(offset, length); + auto arrow_type = TypeTraits<ArrowType>::type_singleton(); + ARROW_ASSIGN_OR_RAISE(auto buffer, AllocateBuffer(sliced.length * sizeof(c_type), + exec_ctx->memory_pool())); + ARROW_ASSIGN_OR_RAISE(auto validity, + AllocateBitmap(sliced.length, exec_ctx->memory_pool())); + ARROW_RETURN_NOT_OK(HashArray(sliced, hash_ctx, exec_ctx, + buffer->mutable_data_as<c_type>(), + validity->mutable_data())); + return ArrayData::Make(arrow_type, sliced.length, + {std::move(validity), std::move(buffer)}, kUnknownNullCount); + } + + static Status HashStructArray(const ArraySpan& array, LightContext* hash_ctx, + ExecContext* exec_ctx, c_type* out, + uint8_t* out_validity) { + // Row validity is the struct's own ANDed with every field's (in place, as + // swiss_join.cc does for multi-column nulls): an independently-null field makes the + // row invalid too (GH-17211), just like the struct row being null. + WriteOwnValidity(array, out_validity); + + if (array.child_data.empty()) { + // struct<>: HashMultiColumn needs >=1 column, so give every row one fixed hash; + // validity is already fully set above. + c_type empty_struct_hash = Hasher::CombineHashes(0, 0); + for (int64_t i = 0; i < array.length; i++) { + out[i] = empty_struct_hash; + } + return Status::OK(); + } + + std::vector<std::shared_ptr<ArrayData>> child_hashes(array.child_data.size()); + std::vector<KeyColumnArray> columns(array.child_data.size()); + for (size_t i = 0; i < array.child_data.size(); i++) { + // By reference: ArraySpan owns a child_data vector, so copying one heap-allocates. + const ArraySpan& child = array.child_data[i]; + // `child` may have its own offset independent of the struct's (see + // StructArray::GetFlattenedField): struct row r reads child row + // (child.offset + array.offset + r). + if (NeedsRecursiveHash(*child.type)) { + // StructArray::Slice() doesn't reslice child_data, so `child` may be larger + // than this slice of `array` references -- hash only the referenced range. + ARROW_ASSIGN_OR_RAISE(child_hashes[i], + HashChild(child, child.offset + array.offset, array.length, + hash_ctx, exec_ctx)); + ::arrow::internal::BitmapAnd(out_validity, 0, child_hashes[i]->buffers[0]->data(), + 0, array.length, 0, out_validity); + ARROW_ASSIGN_OR_RAISE(auto column, ToColumnArray(*child_hashes[i])); + // child_hashes[i] already covers exactly [0, array.length): no further slice. + columns[i] = column.Slice(0, array.length); + } else { + if (child.GetBuffer(0) != nullptr) { + ::arrow::internal::BitmapAnd(out_validity, 0, child.GetBuffer(0)->data(), + child.offset + array.offset, array.length, 0, + out_validity); + } else if (child.type->id() == Type::NA) { + // No bitmap, but NullType is implicitly all-null: invalidates every row. + bit_util::SetBitsTo(out_validity, 0, array.length, false); + } + ARROW_ASSIGN_OR_RAISE(auto column, ToColumnArray(child)); + columns[i] = column.Slice(child.offset + array.offset, array.length); + } + } + Hasher::HashMultiColumn(columns, hash_ctx, out); + return Status::OK(); + } + + // Handles FIXED_SIZE_LIST, LARGE_LIST, LIST, and MAP. `offsets` is null for + // FIXED_SIZE_LIST, which uses `list_size` as a constant stride instead. + template <typename OffsetT> + static Status HashListArray(const ArraySpan& array, int64_t list_size, + const OffsetT* offsets, LightContext* hash_ctx, + ExecContext* exec_ctx, c_type* out, uint8_t* out_validity) { + // The range of `values` this array actually references, as logical indices relative + // to values.offset. Needed because ArraySpan::SetSlice() doesn't reslice child_data, + // so `values` can be far larger than what this (possibly sliced) array covers. + // offsets[] are already such logical indices; FIXED_SIZE_LIST derives them from its + // constant stride instead. + int64_t rel_start = 0, rel_end = 0; + if (array.length > 0) { + if (offsets != nullptr) { + rel_start = offsets[0]; + rel_end = offsets[array.length]; + } else { + rel_start = array.offset * list_size; + rel_end = (array.offset + array.length) * list_size; + } + } + + // By reference: ArraySpan owns a child_data vector, so copying one heap-allocates. + const ArraySpan& values = array.child_data[0]; + // Element k of the result is original values row (values.offset + rel_start + k). + ARROW_ASSIGN_OR_RAISE(auto value_hashes, + HashChild(values, values.offset + rel_start, + rel_end - rel_start, hash_ctx, exec_ctx)); + const c_type* value_hash_data = value_hashes->buffers[1]->data_as<c_type>(); + + // The validity CombineRange folds is the one HashChild propagated: for a struct + // element that is the struct's own ANDed with every field's, so a struct row with a + // null field counts as null here, matching the documented semantics (a field that is + // null makes the struct row's output null). Passing nullptr when nothing is null + // saves the per-element bit test; it folds the same result either way. + const uint8_t* values_validity = value_hashes->buffers[0]->data(); + if (value_hashes->GetNullCount() == 0) { + values_validity = nullptr; + } + + if (offsets != nullptr) { + // offsets[] index the values child; value_hash_data starts at rel_start. + for (int64_t i = 0; i < array.length; i++) { + out[i] = CombineRange<c_type, Hasher>(value_hash_data, values_validity, + offsets[i] - rel_start, + offsets[i + 1] - rel_start); + } + } else { + // rel_start is array.offset * list_size, so row i starts at i * list_size. + for (int64_t i = 0; i < array.length; i++) { + int64_t start = i * list_size; + out[i] = CombineRange<c_type, Hasher>(value_hash_data, values_validity, start, + start + list_size); + } + } + // A list/map row's validity is its own only -- what's inside it (even a null + // element, or a null row's non-empty offset range) never changes that. value_hashes' + // validity buffer is deliberately not consulted here. + WriteOwnValidity(array, out_validity); + return Status::OK(); + } + + // A map's entries struct isn't a user-visible struct: Arrow requires non-null keys and + // allows null items (MapArray::ValidateChildData), so the struct rule that a null field + // nullifies the row must not apply -- it would mark an entry with a null item absent + // and discard its key, hashing every map with null items alike. Fold the keys and the + // items as two list folds over the map's own offsets instead, which encodes a null item + // just as a null list element is encoded and keeps every key contributing. + static Status HashMapArray(const ArraySpan& array, LightContext* hash_ctx, + ExecContext* exec_ctx, c_type* out, uint8_t* out_validity) { + const ArraySpan& entries = array.child_data[0]; + const int32_t* offsets = array.GetValues<int32_t>(1); + + // Stand each field in as this map's values child. The map's offsets index the entries + // struct's own rows, so rebase the field on that struct's offset. + ArraySpan keys = array; + keys.child_data[0] = entries.child_data[0]; + keys.child_data[0].offset += entries.offset; + ARROW_RETURN_NOT_OK(HashListArray<int32_t>(keys, /*list_size=*/0, offsets, hash_ctx, + exec_ctx, out, out_validity)); + + ArraySpan items = array; + items.child_data[0] = entries.child_data[1]; + items.child_data[0].offset += entries.offset; + ARROW_ASSIGN_OR_RAISE(auto item_buffer, AllocateBuffer(array.length * sizeof(c_type), + exec_ctx->memory_pool())); + c_type* item_hashes = item_buffer->mutable_data_as<c_type>(); + ARROW_RETURN_NOT_OK(HashListArray<int32_t>(items, /*list_size=*/0, offsets, hash_ctx, + exec_ctx, item_hashes, out_validity)); + + for (int64_t i = 0; i < array.length; i++) { + out[i] = Hasher::CombineHashes(out[i], item_hashes[i]); + } + return Status::OK(); + } + + // Routes to the per-shape hashing routine for `array`'s type, writing both hash + // values (`out`) and real per-row validity (`out_validity`, a fresh 0-offset bitmap, + // same convention `out` has via ArraySpan::GetValues). + static Status HashArray(const ArraySpan& array, LightContext* hash_ctx, + ExecContext* exec_ctx, c_type* out, uint8_t* out_validity) { + auto type_id = array.type->id(); + if (type_id == Type::FIXED_SIZE_BINARY && array.type->byte_width() == 0) { + // Zero-width values carry no data, so every row holds the same empty byte string + // and must hash identically. ToColumnArray can only describe this as a fixed-width + // column of length 0, exactly how a bit-packed boolean is encoded too, so + // HashMultiColumn would call HashBit and take each row's hash from a bit that + // doesn't exist -- uninitialized garbage, differing per row and per slice. + std::fill(out, out + array.length, Hasher::CombineHashes(0, 0)); + WriteOwnValidity(array, out_validity); + return Status::OK(); + } else if (!NeedsRecursiveHash(*array.type)) { + ARROW_ASSIGN_OR_RAISE(auto column, ToColumnArray(array)); + std::vector<KeyColumnArray> columns{column.Slice(array.offset, array.length)}; + Hasher::HashMultiColumn(columns, hash_ctx, out); + // A plain column's own validity is the whole story, and HashMultiColumn has + // already folded it into the hash values via ToColumnArray's buffer. + WriteOwnValidity(array, out_validity); + return Status::OK(); + } else if (type_id == Type::EXTENSION) { + auto extension_type = checked_cast<const ExtensionType*>(array.type); + auto storage_array = array; + storage_array.type = extension_type->storage_type().get(); + return HashArray(storage_array, hash_ctx, exec_ctx, out, out_validity); + } else if (type_id == Type::DICTIONARY) { + // Hash the logical values, not the indices -- otherwise two dictionaries + // encoding the same values differently would hash differently, and a valid + // index pointing at a null dictionary entry would be missed. Cast's decode + // (Take under the hood) already produces a correct validity buffer for both, so + // recursing into the decoded array handles validity for free. Reuse the + // caller's ExecContext rather than a synthesized default one, same as other + // kernels' dictionary-decode path (see EnsureDictionaryDecoded). + auto dict_type = checked_cast<const DictionaryType*>(array.type); + ARROW_ASSIGN_OR_RAISE(auto decoded, + Cast(*MakeArray(array.ToArrayData()), dict_type->value_type(), + CastOptions::Safe(dict_type->value_type()), exec_ctx)); + return HashArray(*decoded->data(), hash_ctx, exec_ctx, out, out_validity); + } else if (type_id == Type::STRUCT) { + return HashStructArray(array, hash_ctx, exec_ctx, out, out_validity); + } else if (type_id == Type::MAP) { + return HashMapArray(array, hash_ctx, exec_ctx, out, out_validity); + } else if (type_id == Type::FIXED_SIZE_LIST) { + auto list_size = checked_cast<const FixedSizeListType*>(array.type)->list_size(); + return HashListArray<int32_t>(array, list_size, /*offsets=*/nullptr, hash_ctx, + exec_ctx, out, out_validity); + } else if (type_id == Type::LARGE_LIST) { + return HashListArray<int64_t>(array, /*list_size=*/0, array.GetValues<int64_t>(1), + hash_ctx, exec_ctx, out, out_validity); + } else if (is_list_like(type_id)) { + // MAP took its own branch above; LIST is what is left, with 32-bit offsets. + return HashListArray<int32_t>(array, /*list_size=*/0, array.GetValues<int32_t>(1), + hash_ctx, exec_ctx, out, out_validity); + } else { + // NeedsRecursiveHash claims this type needs recursive handling, but no branch + // above knows how (e.g. a union or run-end-encoded type that somehow slipped + // past HashableMatcher's rejection) -- fail loudly and locally rather than + // silently falling through to a mismatched case. + return Status::NotImplemented("Unsupported column data type ", array.type->name(), + " used with hash32/hash64 compute kernel"); + } + } + + static Status Exec(KernelContext* ctx, const ExecSpan& input_arg, ExecResult* out) { + ARROW_DCHECK_EQ(input_arg.num_values(), 1); + ARROW_DCHECK(input_arg[0].is_array()); + ArraySpan hash_input = input_arg[0].array; + Review Comment: The executor guarantees this, so it is not reachable: for a unary function a scalar argument makes the span all-scalar, and `ScalarExecutor` calls `PromoteExecSpanScalars()` before `Exec` — its own comment reads "In the `all scalar` case, we `promote` the scalars to ArraySpans of length 1, since the kernel implementations do not handle the all scalar case". So `input_arg[0]` is always an array here and the `ARROW_DCHECK` documents that invariant rather than guarding a reachable path. Verified it end to end and added `ScalarInput` to pin it down: a scalar argument hashes exactly as that row of the equivalent array does, comes back as a scalar, and a null scalar still yields null — for both kernels. -- 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]
