Skip to main content

Browse the archive

Revision df38c1ce660628f05b4686eeaf0b548295ce7967 authored by Mike Kolupaev on 22 April 2019, 15:17:45 UTC, committed by Facebook Github Bot on 22 April 2019, 15:20:35 UTC 
Add BlockBasedTableOptions::index_shortening (#5174)
 
Summary:
Introduce BlockBasedTableOptions::index_shortening to give users control on which key shortening techniques to be used in building index blocks. Before this patch, both separators and successor keys where shortened in indexes. With this patch, the default is set to kShortenSeparators to only shorten the separators. Since each index block has many separators and only one successor (last key), the change should not have negative impact on index block size. However it should prevent many unnecessary block loads where due to approximation introduced by shorted successor, seek would land us to the previous block and then fix it by moving to the next one.
Pull Request resolved: https://github.com/facebook/rocksdb/pull/5174

Differential Revision: D14884185

Pulled By: al13n321

fbshipit-source-id: 1b08bc8c03edcf09b6b8c16e9a7eea08ad4dd534
1 parent de76909
Raw File
vector_iterator.h 
// Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
#pragma once

#include <algorithm>
#include <string>
#include <vector>

#include "db/dbformat.h"
#include "rocksdb/iterator.h"
#include "rocksdb/slice.h"
#include "table/internal_iterator.h"

namespace rocksdb {

// Iterator over a vector of keys/values
class VectorIterator : public InternalIterator {
 public:
  VectorIterator(std::vector<std::string> keys, std::vector<std::string> values,
                 const InternalKeyComparator* icmp)
      : keys_(std::move(keys)),
        values_(std::move(values)),
        indexed_cmp_(icmp, &keys_),
        current_(keys.size()) {
    assert(keys_.size() == values_.size());

    indices_.reserve(keys_.size());
    for (size_t i = 0; i < keys_.size(); i++) {
      indices_.push_back(i);
    }
    std::sort(indices_.begin(), indices_.end(), indexed_cmp_);
  }

  virtual bool Valid() const override {
    return !indices_.empty() && current_ < indices_.size();
  }

  virtual void SeekToFirst() override { current_ = 0; }
  virtual void SeekToLast() override { current_ = indices_.size() - 1; }

  virtual void Seek(const Slice& target) override {
    current_ = std::lower_bound(indices_.begin(), indices_.end(), target,
                                indexed_cmp_) -
               indices_.begin();
  }

  virtual void SeekForPrev(const Slice& target) override {
    current_ = std::lower_bound(indices_.begin(), indices_.end(), target,
                                indexed_cmp_) -
               indices_.begin();
    if (!Valid()) {
      SeekToLast();
    } else {
      Prev();
    }
  }

  virtual void Next() override { current_++; }
  virtual void Prev() override { current_--; }

  virtual Slice key() const override {
    return Slice(keys_[indices_[current_]]);
  }
  virtual Slice value() const override {
    return Slice(values_[indices_[current_]]);
  }

  virtual Status status() const override { return Status::OK(); }

  virtual bool IsKeyPinned() const override { return true; }
  virtual bool IsValuePinned() const override { return true; }

 private:
  struct IndexedKeyComparator {
    IndexedKeyComparator(const InternalKeyComparator* c,
                         const std::vector<std::string>* ks)
        : cmp(c), keys(ks) {}

    bool operator()(size_t a, size_t b) const {
      return cmp->Compare((*keys)[a], (*keys)[b]) < 0;
    }

    bool operator()(size_t a, const Slice& b) const {
      return cmp->Compare((*keys)[a], b) < 0;
    }

    bool operator()(const Slice& a, size_t b) const {
      return cmp->Compare(a, (*keys)[b]) < 0;
    }

    const InternalKeyComparator* cmp;
    const std::vector<std::string>* keys;
  };

  std::vector<std::string> keys_;
  std::vector<std::string> values_;
  IndexedKeyComparator indexed_cmp_;
  std::vector<size_t> indices_;
  size_t current_;
};

}  // namespace rocksdb
back to top