|
| 1 | +// Licensed to the Apache Software Foundation (ASF) under one |
| 2 | +// or more contributor license agreements. See the NOTICE file |
| 3 | +// distributed with this work for additional information |
| 4 | +// regarding copyright ownership. The ASF licenses this file |
| 5 | +// to you under the Apache License, Version 2.0 (the |
| 6 | +// "License"); you may not use this file except in compliance |
| 7 | +// with the License. You may obtain a copy of the License at |
| 8 | +// |
| 9 | +// http://www.apache.org/licenses/LICENSE-2.0 |
| 10 | +// |
| 11 | +// Unless required by applicable law or agreed to in writing, |
| 12 | +// software distributed under the License is distributed on an |
| 13 | +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| 14 | +// KIND, either express or implied. See the License for the |
| 15 | +// specific language governing permissions and limitations |
| 16 | +// under the License. |
| 17 | + |
| 18 | +#include "core/data_type_serde/arrow_parent_nulls.h" |
| 19 | + |
| 20 | +#include <arrow/array/array_base.h> |
| 21 | +#include <arrow/array/array_nested.h> |
| 22 | +#include <arrow/array/data.h> |
| 23 | +#include <arrow/array/util.h> |
| 24 | +#include <arrow/buffer.h> |
| 25 | +#include <arrow/memory_pool.h> |
| 26 | +#include <arrow/type.h> |
| 27 | +#include <arrow/util/bit_util.h> |
| 28 | +#include <arrow/util/bitmap_ops.h> |
| 29 | + |
| 30 | +#include "common/check.h" |
| 31 | +#include "common/logging.h" |
| 32 | +#include "runtime/exec_env.h" |
| 33 | +#include "util/unaligned.h" |
| 34 | + |
| 35 | +namespace doris { |
| 36 | +namespace { |
| 37 | + |
| 38 | +// The pool that LanceRecordBatchConverter::_query_arrow_memory_pool() picks as well: ExecEnv's |
| 39 | +// doris::ArrowMemoryPool charges the current query's memory tracker and checks its limit, while |
| 40 | +// Arrow's default pool is invisible to both. Only unit tests that never initialize ExecEnv leave |
| 41 | +// it null. |
| 42 | +arrow::MemoryPool* doris_arrow_memory_pool() { |
| 43 | + auto* memory_pool = ExecEnv::GetInstance()->arrow_memory_pool(); |
| 44 | + return memory_pool != nullptr ? memory_pool : arrow::default_memory_pool(); |
| 45 | +} |
| 46 | + |
| 47 | +// Offset `row` of a LIST, LARGE_LIST or MAP parent. The offsets buffer may be misaligned (a Python |
| 48 | +// UDF hands one over), so it is read like the list and map serdes read it: value_offset() is an |
| 49 | +// aligned load of `Offset`, undefined there (UBSAN: load of misaligned address). |
| 50 | +template <typename Offset> |
| 51 | +int64_t load_offset(const Offset* raw_value_offsets, int64_t row) { |
| 52 | + return unaligned_load<Offset>(reinterpret_cast<const uint8_t*>(raw_value_offsets) + |
| 53 | + row * sizeof(Offset)); |
| 54 | +} |
| 55 | + |
| 56 | +// Allocates a validity bitmap of `bit_length` bits from `pool`, with every slot NULL. |
| 57 | +Status allocate_null_bitmap(int64_t bit_length, arrow::MemoryPool* pool, |
| 58 | + std::shared_ptr<arrow::Buffer>* bitmap) { |
| 59 | + auto allocated = arrow::AllocateEmptyBitmap(bit_length, pool); |
| 60 | + if (!allocated.ok()) { |
| 61 | + return Status::InternalError("allocate Arrow child validity bitmap failed: {}", |
| 62 | + allocated.status().message()); |
| 63 | + } |
| 64 | + *bitmap = std::move(allocated).ValueUnsafe(); |
| 65 | + return Status::OK(); |
| 66 | +} |
| 67 | + |
| 68 | +// Whether any of the slots [begin, end) of `data` is non-NULL; without a validity buffer every |
| 69 | +// slot is. Only such a slot needs hiding, so a NULL row that owns no slots, or only NULL ones, |
| 70 | +// costs no bitmap. The slots count from the array offset, the validity bits from the start of |
| 71 | +// the buffer. |
| 72 | +bool has_valid_slot(const arrow::ArrayData& data, int64_t begin, int64_t end) { |
| 73 | + if (begin == end) { |
| 74 | + return false; |
| 75 | + } |
| 76 | + if (data.buffers[0] == nullptr) { |
| 77 | + return true; |
| 78 | + } |
| 79 | + return arrow::internal::CountSetBits(data.buffers[0]->data(), data.offset + begin, |
| 80 | + end - begin) != 0; |
| 81 | +} |
| 82 | + |
| 83 | +// Copies the validity of the slots [begin, end) of `data` to the same bits of `bitmap`. Validity |
| 84 | +// bits are addressed from the start of the buffer, before the array offset. |
| 85 | +void copy_validity(const arrow::ArrayData& data, int64_t begin, int64_t end, uint8_t* bitmap) { |
| 86 | + if (data.buffers[0] != nullptr) { |
| 87 | + arrow::internal::CopyBitmap(data.buffers[0]->data(), data.offset + begin, end - begin, |
| 88 | + bitmap, data.offset + begin); |
| 89 | + } else { |
| 90 | + arrow::bit_util::SetBitsTo(bitmap, data.offset + begin, end - begin, true); |
| 91 | + } |
| 92 | +} |
| 93 | + |
| 94 | +// Returns a copy of `data` whose validity bitmap is `validity`. |
| 95 | +std::shared_ptr<arrow::ArrayData> with_validity(const arrow::ArrayData& data, |
| 96 | + std::shared_ptr<arrow::Buffer> validity) { |
| 97 | + auto masked = data.Copy(); |
| 98 | + masked->buffers[0] = std::move(validity); |
| 99 | + masked->SetNullCount(arrow::kUnknownNullCount); |
| 100 | + return masked; |
| 101 | +} |
| 102 | + |
| 103 | +// Keeps the validity of the slots of `target` that a non-NULL row of `parent` references and |
| 104 | +// marks every other slot NULL. Row `row` references the slots [slot_begin(row), |
| 105 | +// slot_begin(row + 1)) counted from slot `base` of `target`, so the rows of `parent` reference |
| 106 | +// [base + slot_begin(0), base + slot_begin(parent.length())). `*masked` is `target` itself when |
| 107 | +// every slot to hide is NULL already. |
| 108 | +template <typename SlotBegin> |
| 109 | +Status mask_unreferenced_slots(const arrow::Array& parent, const SlotBegin& slot_begin, |
| 110 | + int64_t base, const std::shared_ptr<arrow::ArrayData>& target, |
| 111 | + arrow::MemoryPool* pool, std::shared_ptr<arrow::ArrayData>* masked) { |
| 112 | + *masked = target; |
| 113 | + // An Arrow Null child has no validity buffer and is NULL in every slot already. |
| 114 | + if (target->type->id() == arrow::Type::NA) { |
| 115 | + return Status::OK(); |
| 116 | + } |
| 117 | + const int64_t first = base + slot_begin(0); |
| 118 | + const int64_t last = base + slot_begin(parent.length()); |
| 119 | + // Nothing validated the producer's offsets and lengths yet, and a range outside the child |
| 120 | + // would be written outside the new bitmap. |
| 121 | + if (first < 0 || last < first || last > target->length) { |
| 122 | + return Status::InvalidArgument( |
| 123 | + "Arrow {} references child slots [{}, {}) of a child with length {}", |
| 124 | + parent.type()->ToString(), first, last, target->length); |
| 125 | + } |
| 126 | + // Only a non-NULL slot needs hiding. A child that an earlier pass masked already, like the |
| 127 | + // narrowed Decimal256 leaf that a compaction validates again, therefore costs no bitmap. |
| 128 | + std::shared_ptr<arrow::Buffer> validity; |
| 129 | + const auto keep_referenced_slots = [&]() -> Status { |
| 130 | + RETURN_IF_ERROR(allocate_null_bitmap(target->offset + target->length, pool, &validity)); |
| 131 | + copy_validity(*target, first, last, validity->mutable_data()); |
| 132 | + return Status::OK(); |
| 133 | + }; |
| 134 | + // A sliced parent leaves the slots of the rows outside the slice unreferenced. |
| 135 | + if (has_valid_slot(*target, 0, first) || has_valid_slot(*target, last, target->length)) { |
| 136 | + RETURN_IF_ERROR(keep_referenced_slots()); |
| 137 | + } |
| 138 | + for (int64_t row = 0; row < parent.length(); ++row) { |
| 139 | + if (!parent.IsNull(row)) { |
| 140 | + continue; |
| 141 | + } |
| 142 | + const int64_t begin = base + slot_begin(row); |
| 143 | + const int64_t end = base + slot_begin(row + 1); |
| 144 | + if (begin < first || end < begin || end > last) { |
| 145 | + return Status::InvalidArgument( |
| 146 | + "Arrow {} row {} references child slots [{}, {}) outside [{}, {})", |
| 147 | + parent.type()->ToString(), row, begin, end, first, last); |
| 148 | + } |
| 149 | + // A NULL list or map row may own no slots, and the slots of a NULL row may be NULL |
| 150 | + // already. It hides nothing new then, so such NULL rows allocate nothing. |
| 151 | + if (!has_valid_slot(*target, begin, end)) { |
| 152 | + continue; |
| 153 | + } |
| 154 | + if (validity == nullptr) { |
| 155 | + RETURN_IF_ERROR(keep_referenced_slots()); |
| 156 | + } |
| 157 | + arrow::bit_util::SetBitsTo(validity->mutable_data(), target->offset + begin, end - begin, |
| 158 | + false); |
| 159 | + } |
| 160 | + if (validity != nullptr) { |
| 161 | + *masked = with_validity(*target, std::move(validity)); |
| 162 | + } |
| 163 | + return Status::OK(); |
| 164 | +} |
| 165 | + |
| 166 | +} // namespace |
| 167 | + |
| 168 | +Status mask_arrow_children_hidden_by_null_parents( |
| 169 | + const arrow::Array& parent, int64_t start, int64_t end, |
| 170 | + const std::shared_ptr<arrow::Array>& child, |
| 171 | + const std::function<std::pair<int64_t, int64_t>(int64_t)>& child_slots, |
| 172 | + std::shared_ptr<arrow::Array>* masked) { |
| 173 | + DORIS_CHECK(child != nullptr); |
| 174 | + DORIS_CHECK(masked != nullptr); |
| 175 | + *masked = child; |
| 176 | + // An Arrow Null child has no validity buffer and is NULL in every slot already. |
| 177 | + if (parent.null_count() == 0 || child->type_id() == arrow::Type::NA) { |
| 178 | + return Status::OK(); |
| 179 | + } |
| 180 | + const auto& data = *child->data(); |
| 181 | + std::shared_ptr<arrow::Buffer> validity; |
| 182 | + for (int64_t row = start; row < end; ++row) { |
| 183 | + if (!parent.IsNull(row)) { |
| 184 | + continue; |
| 185 | + } |
| 186 | + const auto [begin, slot_end] = child_slots(row); |
| 187 | + DCHECK(begin >= 0 && begin <= slot_end && slot_end <= data.length); |
| 188 | + // A NULL row hides nothing when it owns no slots, as Arrow's list and map builders |
| 189 | + // write it, or only NULL ones, as after mask_arrow_descendants_not_visible(). Such a row |
| 190 | + // must not allocate: the bitmap covers the whole child, so a caller that reads one large |
| 191 | + // batch a few rows at a time would copy the child's validity for every range. |
| 192 | + if (!has_valid_slot(data, begin, slot_end)) { |
| 193 | + continue; |
| 194 | + } |
| 195 | + if (validity == nullptr) { |
| 196 | + RETURN_IF_ERROR(allocate_null_bitmap(data.offset + data.length, |
| 197 | + doris_arrow_memory_pool(), &validity)); |
| 198 | + copy_validity(data, 0, data.length, validity->mutable_data()); |
| 199 | + } |
| 200 | + arrow::bit_util::SetBitsTo(validity->mutable_data(), data.offset + begin, slot_end - begin, |
| 201 | + false); |
| 202 | + } |
| 203 | + if (validity == nullptr) { |
| 204 | + return Status::OK(); |
| 205 | + } |
| 206 | + *masked = arrow::MakeArray(with_validity(data, std::move(validity))); |
| 207 | + return Status::OK(); |
| 208 | +} |
| 209 | + |
| 210 | +Status mask_arrow_child_slots_not_visible(const arrow::Array& parent, int child_index, |
| 211 | + arrow::MemoryPool* pool, |
| 212 | + std::shared_ptr<arrow::Array>* masked) { |
| 213 | + DORIS_CHECK(pool != nullptr); |
| 214 | + DORIS_CHECK(masked != nullptr); |
| 215 | + DORIS_CHECK(child_index >= 0 && child_index < parent.num_fields()); |
| 216 | + const auto& child = parent.data()->child_data[child_index]; |
| 217 | + std::shared_ptr<arrow::ArrayData> masked_child; |
| 218 | + switch (parent.type_id()) { |
| 219 | + case arrow::Type::LIST: { |
| 220 | + const auto* offsets = static_cast<const arrow::ListArray&>(parent).raw_value_offsets(); |
| 221 | + RETURN_IF_ERROR(mask_unreferenced_slots( |
| 222 | + parent, [offsets](int64_t row) { return load_offset(offsets, row); }, 0, child, |
| 223 | + pool, &masked_child)); |
| 224 | + break; |
| 225 | + } |
| 226 | + case arrow::Type::LARGE_LIST: { |
| 227 | + const auto* offsets = static_cast<const arrow::LargeListArray&>(parent).raw_value_offsets(); |
| 228 | + RETURN_IF_ERROR(mask_unreferenced_slots( |
| 229 | + parent, [offsets](int64_t row) { return load_offset(offsets, row); }, 0, child, |
| 230 | + pool, &masked_child)); |
| 231 | + break; |
| 232 | + } |
| 233 | + case arrow::Type::FIXED_SIZE_LIST: { |
| 234 | + const auto& list = static_cast<const arrow::FixedSizeListArray&>(parent); |
| 235 | + RETURN_IF_ERROR(mask_unreferenced_slots( |
| 236 | + parent, [&list](int64_t row) { return list.value_offset(row); }, 0, child, pool, |
| 237 | + &masked_child)); |
| 238 | + break; |
| 239 | + } |
| 240 | + case arrow::Type::STRUCT: |
| 241 | + RETURN_IF_ERROR(mask_unreferenced_slots( |
| 242 | + parent, [offset = parent.offset()](int64_t row) { return offset + row; }, 0, child, |
| 243 | + pool, &masked_child)); |
| 244 | + break; |
| 245 | + case arrow::Type::MAP: { |
| 246 | + // MapArray::SetData() aborts through ARROW_CHECK_OK(MapArray::ValidateChildData()) once |
| 247 | + // the entries struct or the keys may hold a NULL, so the entries that a map row hides |
| 248 | + // are marked NULL in the items alone. Entry j of the map is item slot entries.offset + j. |
| 249 | + const auto* offsets = static_cast<const arrow::MapArray&>(parent).raw_value_offsets(); |
| 250 | + const auto& items = child->child_data[1]; |
| 251 | + std::shared_ptr<arrow::ArrayData> masked_items; |
| 252 | + RETURN_IF_ERROR(mask_unreferenced_slots( |
| 253 | + parent, [offsets](int64_t row) { return load_offset(offsets, row); }, child->offset, |
| 254 | + items, pool, &masked_items)); |
| 255 | + masked_child = child; |
| 256 | + if (masked_items != items) { |
| 257 | + masked_child = child->Copy(); |
| 258 | + masked_child->child_data[1] = std::move(masked_items); |
| 259 | + } |
| 260 | + break; |
| 261 | + } |
| 262 | + default: |
| 263 | + return Status::InvalidArgument("cannot mask the child slots of Arrow {}", |
| 264 | + parent.type()->ToString()); |
| 265 | + } |
| 266 | + *masked = arrow::MakeArray(masked_child); |
| 267 | + return Status::OK(); |
| 268 | +} |
| 269 | + |
| 270 | +Status mask_arrow_descendants_not_visible(const std::shared_ptr<arrow::Array>& array, |
| 271 | + arrow::MemoryPool* pool, |
| 272 | + std::shared_ptr<arrow::Array>* masked) { |
| 273 | + DORIS_CHECK(array != nullptr); |
| 274 | + DORIS_CHECK(pool != nullptr); |
| 275 | + DORIS_CHECK(masked != nullptr); |
| 276 | + *masked = array; |
| 277 | + const auto type_id = array->type_id(); |
| 278 | + // A leaf has no descendants to mask. Other nested layouts, such as list views, unions and |
| 279 | + // run-end encoded arrays, are left as they are: the slot mask does not know them, and no |
| 280 | + // reader that masks nested arrays maps them to a Doris type. |
| 281 | + if (type_id != arrow::Type::LIST && type_id != arrow::Type::LARGE_LIST && |
| 282 | + type_id != arrow::Type::FIXED_SIZE_LIST && type_id != arrow::Type::MAP && |
| 283 | + type_id != arrow::Type::STRUCT) { |
| 284 | + return Status::OK(); |
| 285 | + } |
| 286 | + const auto& children = array->data()->child_data; |
| 287 | + std::shared_ptr<arrow::ArrayData> masked_data; |
| 288 | + for (int child_index = 0; child_index < array->num_fields(); ++child_index) { |
| 289 | + std::shared_ptr<arrow::Array> child; |
| 290 | + RETURN_IF_ERROR(mask_arrow_child_slots_not_visible(*array, child_index, pool, &child)); |
| 291 | + std::shared_ptr<arrow::Array> masked_child; |
| 292 | + if (type_id == arrow::Type::MAP) { |
| 293 | + // The child is the entries struct, whose keys stay unmasked, so only its items are |
| 294 | + // masked further down. |
| 295 | + const auto& entries = child->data(); |
| 296 | + std::shared_ptr<arrow::Array> items; |
| 297 | + RETURN_IF_ERROR(mask_arrow_descendants_not_visible( |
| 298 | + arrow::MakeArray(entries->child_data[1]), pool, &items)); |
| 299 | + masked_child = child; |
| 300 | + if (items->data() != entries->child_data[1]) { |
| 301 | + auto masked_entries = entries->Copy(); |
| 302 | + masked_entries->child_data[1] = items->data(); |
| 303 | + masked_child = arrow::MakeArray(masked_entries); |
| 304 | + } |
| 305 | + } else { |
| 306 | + RETURN_IF_ERROR(mask_arrow_descendants_not_visible(child, pool, &masked_child)); |
| 307 | + } |
| 308 | + if (masked_child->data() == children[child_index]) { |
| 309 | + continue; |
| 310 | + } |
| 311 | + if (masked_data == nullptr) { |
| 312 | + masked_data = array->data()->Copy(); |
| 313 | + } |
| 314 | + masked_data->child_data[child_index] = masked_child->data(); |
| 315 | + } |
| 316 | + if (masked_data != nullptr) { |
| 317 | + *masked = arrow::MakeArray(masked_data); |
| 318 | + } |
| 319 | + return Status::OK(); |
| 320 | +} |
| 321 | + |
| 322 | +} // namespace doris |
0 commit comments