src/kudu/tablet/rowset_tree.h

// 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 <cstdint>
#include <functional>
#include <memory>
#include <optional>
#include <unordered_map>
#include <vector>

#include "kudu/gutil/map-util.h"
#include "kudu/tablet/rowset.h"
#include "kudu/util/slice.h"
#include "kudu/util/status.h"

namespace kudu {

template<class Traits>
class IntervalTree;

namespace tablet {

struct RowSetIntervalTraits;
struct RowSetWithBounds;

// Class which encapsulates the set of rowsets which are active for a given
// Tablet. This provides efficient lookup by key for RowSets which may overlap
// that key range.
//
// Additionally, the rowset tree maintains information about the implicit
// intervals generated by the row sets (for instance, if a tablet has
// rowsets [0, 2] and [1, 3] it has three implicit contiguous intervals:
// [0, 1], [1, 2], and [2, 3].
class RowSetTree {
 public:
  // An RSEndpoint is a POD which associates a rowset, an EndpointType
  // (either the START or STOP of an interval), and the key at which the
  // endpoint is located.
  enum EndpointType {
    START,
    STOP
  };
  struct RSEndpoint {
    RSEndpoint(RowSet *rowset, EndpointType endpoint, Slice slice)
        : rowset_(rowset), endpoint_(endpoint), slice_(slice) {}

    RowSet* rowset_;
    enum EndpointType endpoint_;
    Slice slice_;
  };

  RowSetTree();
  Status Reset(const RowSetVector &rowsets);
  ~RowSetTree();

  // Return all RowSets whose range may contain the given encoded key.
  //
  // The returned pointers are guaranteed to be valid at least until this
  // RowSetTree object is Reset().
  void FindRowSetsWithKeyInRange(const Slice &encoded_key,
                                 std::vector<RowSet *> *rowsets) const;

  // Call 'cb(rowset, index)' for each (rowset, index) pair such that
  // 'encoded_keys[index]' may be within the bounds of 'rowset'.
  //
  // See IntervalTree::ForEachIntervalContainingPoints for additional
  // information on the particular order in which the callback will be called.
  //
  // REQUIRES: 'encoded_keys' must be in sorted order.
  void ForEachRowSetContainingKeys(const std::vector<Slice>& encoded_keys,
                                   const std::function<void(RowSet*, int)>& cb) const;

  // When 'lower_bound' is std::nullopt, it means negative infinity.
  // When 'upper_bound' is std::nullopt, it means positive infinity.
  // So the query interval can be one of below:
  //  [-OO, +OO)
  //  [-OO, upper_bound)
  //  [lower_bound, +OO)
  //  [lower_bound, upper_bound)
  void FindRowSetsIntersectingInterval(const std::optional<Slice>& lower_bound,
                                       const std::optional<Slice>& upper_bound,
                                       std::vector<RowSet*>* rowsets) const;

  const RowSetVector &all_rowsets() const { return all_rowsets_; }

  RowSet* drs_by_id(int64_t drs_id) const {
    return FindPtrOrNull(drs_by_id_, drs_id);
  }

  // Iterates over RowSetTree::RSEndpoint, guaranteed to be ordered and for
  // any rowset to appear exactly twice, once at its start slice and once at
  // its stop slice, equivalent to its GetBounds() values.
  const std::vector<RSEndpoint>& key_endpoints() const { return key_endpoints_; }

 private:
  // Interval tree of the rowsets. Used to efficiently find rowsets which might contain
  // a probe row.
  std::unique_ptr<IntervalTree<RowSetIntervalTraits>> tree_;

  // Ordered map of all the interval endpoints, holding the implicit contiguous
  // intervals
  // TODO map to usage statistics as well. See KUDU-???
  std::vector<RSEndpoint> key_endpoints_;

  // Container for all of the entries in tree_. IntervalTree does
  // not itself manage memory, so this provides a simple way to enumerate
  // all the entry structs and free them in the destructor.
  std::vector<RowSetWithBounds *> entries_;

  // All of the rowsets which were put in this RowSetTree.
  RowSetVector all_rowsets_;

  // The DiskRowSets in this RowSetTree, keyed by their id.
  std::unordered_map<int64_t, RowSet*> drs_by_id_;

  // Rowsets for which the bounds are unknown -- e.g because they
  // are mutable (MemRowSets).
  //
  // These have to be consulted for every access, so are not
  // stored in the interval tree.
  RowSetVector unbounded_rowsets_;

  bool initted_;
};

} // namespace tablet
} // namespace kudu