delete_file_index.h

Go to the documentation of this file.

/*
 * 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 <functional>
#include <map>
#include <memory>
#include <optional>
#include <unordered_map>
#include <vector>
 
#include "iceberg/expression/literal.h"
#include "iceberg/iceberg_export.h"
#include "iceberg/manifest/manifest_entry.h"
#include "iceberg/result.h"
#include "iceberg/type_fwd.h"
#include "iceberg/util/error_collector.h"
#include "iceberg/util/partition_value_util.h"
 
namespace iceberg {
 
namespace internal {
 
struct ICEBERG_EXPORT EqualityDeleteFile {
  const Schema* schema;
  ManifestEntry wrapped;
  int64_t apply_sequence_number;  // = data_sequence_number - 1
 
  // Lazily converted bounds for pruning
  mutable std::unordered_map<int32_t, Literal> lower_bounds;
  mutable std::unordered_map<int32_t, Literal> upper_bounds;
  mutable bool bounds_converted = false;
 
  EqualityDeleteFile(const Schema* schema, ManifestEntry&& entry)
      : schema(schema),
        wrapped(std::move(entry)),
        apply_sequence_number(wrapped.sequence_number.value() - 1) {}
 
  bool HasLowerAndUpperBounds() const {
    return !wrapped.data_file->lower_bounds.empty() &&
           !wrapped.data_file->upper_bounds.empty();
  }
 
  Result<std::optional<std::reference_wrapper<const Literal>>> LowerBound(
      int32_t id) const {
    ICEBERG_RETURN_UNEXPECTED(ConvertBoundsIfNeeded());
    auto it = lower_bounds.find(id);
    return it != lower_bounds.cend() ? std::make_optional(std::cref(it->second))
                                     : std::nullopt;
  }
 
  Result<std::optional<std::reference_wrapper<const Literal>>> UpperBound(
      int32_t id) const {
    ICEBERG_RETURN_UNEXPECTED(ConvertBoundsIfNeeded());
    auto it = upper_bounds.find(id);
    return it != upper_bounds.cend() ? std::make_optional(std::cref(it->second))
                                     : std::nullopt;
  }
 
 private:
  Status ConvertBoundsIfNeeded() const;
};
 
inline bool RangesOverlap(const Literal& data_lower, const Literal& data_upper,
                          const Literal& delete_lower, const Literal& delete_upper) {
  if (data_lower > delete_upper) {
    return false;
  }
  if (delete_lower > data_upper) {
    return false;
  }
  return true;
}
 
inline bool AllNull(const std::map<int32_t, int64_t>& null_counts,
                    const std::map<int32_t, int64_t>& value_counts, int32_t field_id,
                    bool is_required) {
  if (is_required) {
    return false;
  }
 
  auto null_it = null_counts.find(field_id);
  auto value_it = value_counts.find(field_id);
  if (null_it == null_counts.cend() || value_it == value_counts.cend()) {
    return false;
  }
 
  return null_it->second == value_it->second;
}
 
inline bool AllNonNull(const std::map<int32_t, int64_t>& null_counts, int32_t field_id,
                       bool is_required) {
  if (is_required) {
    return true;
  }
 
  auto it = null_counts.find(field_id);
  if (it == null_counts.cend()) {
    return false;
  }
 
  return it->second <= 0;
}
 
inline bool ContainsNull(const std::map<int32_t, int64_t>& null_counts, int32_t field_id,
                         bool is_required) {
  if (is_required) {
    return false;
  }
 
  auto it = null_counts.find(field_id);
  if (it == null_counts.cend()) {
    return true;  // Unknown, assume may contain null
  }
 
  return it->second > 0;
}
 
ICEBERG_EXPORT Result<bool> CanContainEqDeletesForFile(
    const DataFile& data_file, const EqualityDeleteFile& delete_file);
 
class ICEBERG_EXPORT PositionDeletes {
 public:
  PositionDeletes() = default;
 
  [[nodiscard]] Status Add(ManifestEntry&& entry);
 
  std::vector<std::shared_ptr<DataFile>> Filter(int64_t seq);
 
  std::vector<std::shared_ptr<DataFile>> ReferencedDeleteFiles();
 
  bool empty() const { return files_.empty(); }
 
 private:
  void IndexIfNeeded();
 
  std::vector<ManifestEntry> files_;
  std::vector<int64_t> seqs_;
  bool indexed_ = false;
};
 
class ICEBERG_EXPORT EqualityDeletes {
 public:
  explicit EqualityDeletes(const Schema& schema) : schema_(schema) {}
 
  [[nodiscard]] Status Add(ManifestEntry&& entry);
 
  Result<std::vector<std::shared_ptr<DataFile>>> Filter(int64_t seq,
                                                        const DataFile& data_file);
 
  std::vector<std::shared_ptr<DataFile>> ReferencedDeleteFiles();
 
  bool empty() const { return files_.empty(); }
 
 private:
  void IndexIfNeeded();
 
  const Schema& schema_;
  std::vector<EqualityDeleteFile> files_;
  std::vector<int64_t> seqs_;
  bool indexed_ = false;
};
 
}  // namespace internal
 
class ICEBERG_EXPORT DeleteFileIndex {
 public:
  class Builder;
 
  ~DeleteFileIndex();
 
  DeleteFileIndex(DeleteFileIndex&&) noexcept;
  DeleteFileIndex& operator=(DeleteFileIndex&&) noexcept;
  DeleteFileIndex(const DeleteFileIndex&) = delete;
  DeleteFileIndex& operator=(const DeleteFileIndex&) = delete;
 
  bool empty() const;
 
  bool has_equality_deletes() const;
 
  bool has_position_deletes() const;
 
  std::vector<std::shared_ptr<DataFile>> ReferencedDeleteFiles() const;
 
  Result<std::vector<std::shared_ptr<DataFile>>> ForEntry(
      const ManifestEntry& entry) const;
 
  Result<std::vector<std::shared_ptr<DataFile>>> ForDataFile(int64_t sequence_number,
                                                             const DataFile& file) const;
 
  static Result<Builder> BuilderFor(
      std::shared_ptr<FileIO> io, std::shared_ptr<Schema> schema,
      std::unordered_map<int32_t, std::shared_ptr<PartitionSpec>> specs_by_id,
      std::vector<ManifestFile> delete_manifests);
 
 private:
  friend class Builder;
 
  // Private constructor used by Builder
  DeleteFileIndex(
      std::unique_ptr<internal::EqualityDeletes> global_deletes,
      std::unique_ptr<PartitionMap<std::unique_ptr<internal::EqualityDeletes>>>
          eq_deletes_by_partition,
      std::unique_ptr<PartitionMap<std::unique_ptr<internal::PositionDeletes>>>
          pos_deletes_by_partition,
      std::unique_ptr<
          std::unordered_map<std::string, std::unique_ptr<internal::PositionDeletes>>>
          pos_deletes_by_path,
      std::unique_ptr<std::unordered_map<std::string, ManifestEntry>> dv_by_path);
 
  // Helper methods for finding delete files
  Result<std::vector<std::shared_ptr<DataFile>>> FindGlobalDeletes(
      int64_t seq, const DataFile& data_file) const;
  Result<std::vector<std::shared_ptr<DataFile>>> FindEqPartitionDeletes(
      int64_t seq, const DataFile& data_file) const;
  Result<std::vector<std::shared_ptr<DataFile>>> FindPosPartitionDeletes(
      int64_t seq, const DataFile& data_file) const;
  Result<std::vector<std::shared_ptr<DataFile>>> FindPathDeletes(
      int64_t seq, const DataFile& data_file) const;
  Result<std::shared_ptr<DataFile>> FindDV(int64_t seq, const DataFile& data_file) const;
 
  // Index data structures
  std::unique_ptr<internal::EqualityDeletes> global_deletes_;
  std::unique_ptr<PartitionMap<std::unique_ptr<internal::EqualityDeletes>>>
      eq_deletes_by_partition_;
  std::unique_ptr<PartitionMap<std::unique_ptr<internal::PositionDeletes>>>
      pos_deletes_by_partition_;
  std::unique_ptr<
      std::unordered_map<std::string, std::unique_ptr<internal::PositionDeletes>>>
      pos_deletes_by_path_;
  std::unique_ptr<std::unordered_map<std::string, ManifestEntry>> dv_by_path_;
 
  bool has_eq_deletes_ = false;
  bool has_pos_deletes_ = false;
  bool is_empty_ = true;
};
 
class ICEBERG_EXPORT DeleteFileIndex::Builder : public ErrorCollector {
 public:
  Builder(std::shared_ptr<FileIO> io, std::shared_ptr<Schema> schema,
          std::unordered_map<int32_t, std::shared_ptr<PartitionSpec>> specs_by_id,
          std::vector<ManifestFile> delete_manifests);
 
  ~Builder() override;
 
  Builder(Builder&&) noexcept;
  Builder& operator=(Builder&&) noexcept;
  Builder(const Builder&) = delete;
  Builder& operator=(const Builder&) = delete;
 
  Builder& AfterSequenceNumber(int64_t seq);
 
  Builder& DataFilter(std::shared_ptr<Expression> filter);
 
  Builder& PartitionFilter(std::shared_ptr<Expression> filter);
 
  Builder& FilterPartitions(std::shared_ptr<PartitionSet> partition_set);
 
  Builder& CaseSensitive(bool case_sensitive);
 
  Builder& IgnoreResiduals();
 
  Result<std::unique_ptr<DeleteFileIndex>> Build();
 
 private:
  // Load delete files from manifests
  Result<std::vector<ManifestEntry>> LoadDeleteFiles();
 
  // Add a DV to the index
  Status AddDV(std::unordered_map<std::string, ManifestEntry>& dv_by_path,
               ManifestEntry&& entry);
 
  // Add a position delete file to the index
  Status AddPositionDelete(
      std::unordered_map<std::string, std::unique_ptr<internal::PositionDeletes>>&
          deletes_by_path,
      PartitionMap<std::unique_ptr<internal::PositionDeletes>>& deletes_by_partition,
      ManifestEntry&& entry);
 
  // Add an equality delete file to the index
  Status AddEqualityDelete(
      internal::EqualityDeletes& global_deletes,
      PartitionMap<std::unique_ptr<internal::EqualityDeletes>>& deletes_by_partition,
      ManifestEntry&& entry);
 
  std::shared_ptr<FileIO> io_;
  std::shared_ptr<Schema> schema_;
  std::unordered_map<int32_t, std::shared_ptr<PartitionSpec>> specs_by_id_;
  std::vector<ManifestFile> delete_manifests_;
  int64_t min_sequence_number_ = 0;
  std::shared_ptr<Expression> data_filter_;
  std::shared_ptr<Expression> partition_filter_;
  std::shared_ptr<PartitionSet> partition_set_;
  bool case_sensitive_ = true;
  bool ignore_residuals_ = false;
};
 
}  // namespace iceberg