<commit_before>//===----------------------------------------------------------------------===//
//
//                         PelotonDB
//
// btree_multi_index.h
//
// Identification: src/backend/index/btree_multi_index.h
//
// Copyright (c) 2015, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#pragma once

#include <vector>
#include <string>
#include <map>

#include "backend/catalog/manager.h"
#include "backend/common/types.h"
#include "backend/common/synch.h"
#include "backend/storage/tuple.h"
#include "backend/index/index.h"

namespace peloton {
namespace index {

/**
 * B+tree-based index implementation.
 *
 * @see Index
 */
template <typename KeyType, class KeyComparator, class KeyEqualityChecker>
class BtreeIndex : public Index {
  friend class IndexFactory;

  typedef ItemPointer ValueType;
  typedef std::multimap<KeyType, ValueType, KeyComparator> MapType;

 public:
  BtreeIndex(IndexMetadata *metadata)
      : Index(metadata),
        container(KeyComparator(metadata)),
        equals(metadata),
        comparator(metadata) {}

  ~BtreeIndex() {}

  bool InsertEntry(const storage::Tuple *key, const ItemPointer location) {
    {
      index_lock.WriteLock();
      index_key1.SetFromKey(key);

      // Insert the key, val pair
      container.insert(std::pair<KeyType, ValueType>(index_key1, location));

      index_lock.Unlock();
      return true;
    }
  }

  bool DeleteEntry(const storage::Tuple *key, const ItemPointer location) {
    {
      index_lock.WriteLock();
      index_key1.SetFromKey(key);

      // Delete the < key, location > pair
      auto entries = container.equal_range(index_key1);
      for (auto iterator = entries.first; iterator != entries.second;) {
        ItemPointer value = iterator->second;

        if ((value.block == location.block) &&
            (value.offset == location.offset)) {
          // remove matching (key, value) entry
          iterator = container.erase(iterator);
        } else {
          ++iterator;
        }
      }

      index_lock.Unlock();
      return true;
    }
  }

  bool UpdateEntry(const storage::Tuple *key,
                   const ItemPointer location) {
    {
      index_lock.WriteLock();
      index_key1.SetFromKey(key);

      // insert the key, val pair
      container.insert(std::pair<KeyType, ValueType>(index_key1, location));

      index_lock.Unlock();
      return true;
    }
  }

  ItemPointer Exists(const storage::Tuple *key, const ItemPointer location) {
    {
      index_lock.ReadLock();
      index_key1.SetFromKey(key);

      // find the <key, location> pair
      auto entries = container.equal_range(index_key1);
      for (auto entry = entries.first; entry != entries.second; ++entry) {
        ItemPointer value = entry->second;
        if ((value.block == location.block) &&
            (value.offset == location.offset)) {
          index_lock.Unlock();
          return value;
        }
      }

      index_lock.Unlock();
      return INVALID_ITEMPOINTER;
    }
  }

  std::vector<ItemPointer> Scan(const std::vector<Value> &values,
                                const std::vector<oid_t> &key_column_ids,
                                const std::vector<ExpressionType> &expr_types) {
    std::vector<ItemPointer> result;

    {
      index_lock.ReadLock();

      // check if we have leading column equality
      oid_t leading_column_id = 0;
      auto key_column_ids_itr = std::find(
          key_column_ids.begin(), key_column_ids.end(), leading_column_id);
      bool special_case = false;
      if (key_column_ids_itr != key_column_ids.end()) {
        auto offset = std::distance(key_column_ids.begin(), key_column_ids_itr);
        if (expr_types[offset] == EXPRESSION_TYPE_COMPARE_EQUAL) {
          special_case = true;
          LOG_INFO("Special case");
        }
      }

      auto itr = container.begin();
      storage::Tuple *start_key = nullptr;
      // start scanning from upper bound if possible
      if (special_case == true) {
        start_key = new storage::Tuple(metadata->GetKeySchema(), true);
        // set the lower bound tuple
        auto all_equal =
            SetLowerBoundTuple(start_key, values, key_column_ids, expr_types);
        index_key1.SetFromKey(start_key);

        // all equal case
        if (all_equal) {
          itr = container.find(index_key1);
        } else {
          itr = container.upper_bound(index_key1);
        }
      }

      // scan all entries comparing against arbitrary key
      while (itr != container.end()) {
        auto index_key = itr->first;
        auto tuple = index_key.GetTupleForComparison(metadata->GetKeySchema());

        if (Compare(tuple, key_column_ids, expr_types, values) == true) {
          ItemPointer location = itr->second;
          result.push_back(location);
        }
        itr++;
      }

      delete start_key;
<commit_msg>Some refactoring about index: 1. The find/equal_range operations for std::multimap seem to not be thread-safe. When parallel reads occur, one of them would return 0 result for existing elements. By changing the read lock to a write lock, the problem is gone. We may need to look into this case, as std::multimap claims it is read thread safe.<commit_after>//===----------------------------------------------------------------------===//
//
//                         PelotonDB
//
// btree_multi_index.h
//
// Identification: src/backend/index/btree_multi_index.h
//
// Copyright (c) 2015, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#pragma once

#include <vector>
#include <string>
#include <map>

#include "backend/catalog/manager.h"
#include "backend/common/types.h"
#include "backend/common/synch.h"
#include "backend/storage/tuple.h"
#include "backend/index/index.h"

namespace peloton {
namespace index {

/**
 * B+tree-based index implementation.
 *
 * @see Index
 */
template <typename KeyType, class KeyComparator, class KeyEqualityChecker>
class BtreeIndex : public Index {
  friend class IndexFactory;

  typedef ItemPointer ValueType;
  typedef std::multimap<KeyType, ValueType, KeyComparator> MapType;

 public:
  BtreeIndex(IndexMetadata *metadata)
      : Index(metadata),
        container(KeyComparator(metadata)),
        equals(metadata),
        comparator(metadata) {}

  ~BtreeIndex() {}

  bool InsertEntry(const storage::Tuple *key, const ItemPointer location) {
    {
      index_lock.WriteLock();
      index_key1.SetFromKey(key);

      // Insert the key, val pair
      container.insert(std::pair<KeyType, ValueType>(index_key1, location));

      index_lock.Unlock();
      return true;
    }
  }

  bool DeleteEntry(const storage::Tuple *key, const ItemPointer location) {
    {
      index_lock.WriteLock();
      index_key1.SetFromKey(key);

      // Delete the < key, location > pair
      auto entries = container.equal_range(index_key1);
      for (auto iterator = entries.first; iterator != entries.second;) {
        ItemPointer value = iterator->second;

        if ((value.block == location.block) &&
            (value.offset == location.offset)) {
          // remove matching (key, value) entry
          iterator = container.erase(iterator);
        } else {
          ++iterator;
        }
      }

      index_lock.Unlock();
      return true;
    }
  }

  bool UpdateEntry(const storage::Tuple *key,
                   const ItemPointer location) {
    {
      index_lock.WriteLock();
      index_key1.SetFromKey(key);

      // insert the key, val pair
      container.insert(std::pair<KeyType, ValueType>(index_key1, location));

      index_lock.Unlock();
      return true;
    }
  }

  ItemPointer Exists(const storage::Tuple *key, const ItemPointer location) {
    {
      index_lock.ReadLock();
      index_key1.SetFromKey(key);

      // find the <key, location> pair
      auto entries = container.equal_range(index_key1);
      for (auto entry = entries.first; entry != entries.second; ++entry) {
        ItemPointer value = entry->second;
        if ((value.block == location.block) &&
            (value.offset == location.offset)) {
          index_lock.Unlock();
          return value;
        }
      }

      index_lock.Unlock();
      return INVALID_ITEMPOINTER;
    }
  }

  std::vector<ItemPointer> Scan(const std::vector<Value> &values,
                                const std::vector<oid_t> &key_column_ids,
                                const std::vector<ExpressionType> &expr_types) {
    std::vector<ItemPointer> result;

    {
      index_lock.WriteLock();

      // check if we have leading column equality
      oid_t leading_column_id = 0;
      auto key_column_ids_itr = std::find(
          key_column_ids.begin(), key_column_ids.end(), leading_column_id);
      bool special_case = false;
      if (key_column_ids_itr != key_column_ids.end()) {
        auto offset = std::distance(key_column_ids.begin(), key_column_ids_itr);
        if (expr_types[offset] == EXPRESSION_TYPE_COMPARE_EQUAL) {
          special_case = true;
          LOG_INFO("Special case");
        }
      }

      auto itr_begin = container.begin();
      auto itr_end = container.end();
      storage::Tuple *start_key = nullptr;
      // start scanning from upper bound if possible
      if (special_case == true) {
        start_key = new storage::Tuple(metadata->GetKeySchema(), true);
        // set the lower bound tuple
        auto all_equal =
            SetLowerBoundTuple(start_key, values, key_column_ids, expr_types);
        index_key1.SetFromKey(start_key);

        // all equal case
        if (all_equal) {
          //itr_begin = container.find(index_key1);
          /* 'find' may return any one of the elements with the key */
          auto ret = container.equal_range(index_key1);
          itr_begin = ret.first;
          itr_end = ret.second;
          LOG_INFO("equal range return %ld", std::distance(itr_begin, itr_end));
        } else {
          itr_begin = container.upper_bound(index_key1);
        }
      }

      // scan all entries comparing against arbitrary key
      for (auto itr = itr_begin; itr != itr_end; itr++) {
        auto index_key = itr->first;
        auto tuple = index_key.GetTupleForComparison(metadata->GetKeySchema());

        if (Compare(tuple, key_column_ids, expr_types, values) == true) {
          ItemPointer location = itr->second;
          result.push_back(location);
        }
      }

      delete start_key;

{'fraction_non_alphanumeric': 0.13897566979077913, 'fraction_numerical': 0.0033134526176275677, 'mean_word_length': 2.30641627543036, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 43, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7463897', 'n_tokens_mistral': 3041, 'n_tokens_neox': 2975, 'n_words': 703}