Google Git
Sign in
apache / incubator-retired-quickstep / b7a70951ab000c06190d0ab6c366decfc7c1e000 / . / storage / tests / CSBTreeIndexSubBlock_unittest.cpp
blob: 893156d0c21d1b5c954a5cc5c373aadc277692d7 [file] [log] [blame]
/**
* 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.
**/
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <limits>
#include <memory>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
#include "gtest/gtest.h"
#include "catalog/CatalogAttribute.hpp"
#include "catalog/CatalogRelation.hpp"
#include "catalog/CatalogTypedefs.hpp"
#include "expressions/predicate/ComparisonPredicate.hpp"
#include "expressions/scalar/ScalarAttribute.hpp"
#include "expressions/scalar/ScalarLiteral.hpp"
#include "storage/CSBTreeIndexSubBlock.hpp"
#include "storage/CompressedPackedRowStoreTupleStorageSubBlock.hpp"
#include "storage/CompressedTupleStorageSubBlock.hpp"
#include "storage/StorageBlockInfo.hpp"
#include "storage/StorageBlockLayout.pb.h"
#include "storage/StorageErrors.hpp"
#include "storage/TupleIdSequence.hpp"
#include "storage/tests/MockTupleStorageSubBlock.hpp"
#include "types/CharType.hpp"
#include "types/FloatType.hpp"
#include "types/LongType.hpp"
#include "types/TypeFactory.hpp"
#include "types/TypedValue.hpp"
#include "types/TypeID.hpp"
#include "types/VarCharType.hpp"
#include "types/containers/Tuple.hpp"
#include "types/operations/comparisons/Comparison.hpp"
#include "types/operations/comparisons/ComparisonFactory.hpp"
#include "types/operations/comparisons/ComparisonID.hpp"
#include "types/operations/comparisons/ComparisonUtil.hpp"
#include "utility/BitVector.hpp"
#include "utility/Macros.hpp"
#include "utility/ScopedBuffer.hpp"
using std::binary_search;
using std::int64_t;
using std::numeric_limits;
using std::ostringstream;
using std::set;
using std::size_t;
using std::string;
using std::uint8_t;
using std::uint16_t;
using std::uint32_t;
using std::vector;
namespace quickstep {
namespace {
template <typename CodeType>
class CompressedCodeLessComparator : public UncheckedComparator {
public:
~CompressedCodeLessComparator() {
}
bool compareTypedValues(const TypedValue &left, const TypedValue &right) const {
FATAL_ERROR("Can not use CompressedCodeLessComparator to compare TypedValue.");
}
inline bool compareDataPtrs(const void *left, const void *right) const {
return *static_cast<const CodeType*>(left) < *static_cast<const CodeType*>(right);
}
bool compareTypedValueWithDataPtr(const TypedValue &left, const void *right) const {
FATAL_ERROR("Can not use CompressedCodeLessComparator to compare TypedValue.");
}
bool compareDataPtrWithTypedValue(const void *left, const TypedValue &right) const {
FATAL_ERROR("Can not use CompressedCodeLessComparator to compare TypedValue.");
}
};
} // anonymous namespace
class CSBTreeIndexSubBlockTest : public ::testing::Test {
protected:
static const size_t kIndexSubBlockSize = 0x100000; // 1 MB.
// Hack: replace long_attr values equal to this with NULL.
static const int64_t kLongAttrNullValue = -55555;
static const char kCharAttrNullValue[];
static const int kNumSampleTuples = 37;
static const tuple_id kDeleteSequence[kNumSampleTuples];
virtual void SetUp() {
// Create a sample relation with a variety of attribute types.
relation_.reset(new CatalogRelation(NULL, "TestRelation"));
CatalogAttribute *long_attr = new CatalogAttribute(relation_.get(),
"long_attr",
TypeFactory::GetType(kLong, false));
ASSERT_EQ(0, relation_->addAttribute(long_attr));
CatalogAttribute *nullable_long_attr = new CatalogAttribute(relation_.get(),
"nullable_long_attr",
TypeFactory::GetType(kLong, true));
ASSERT_EQ(1, relation_->addAttribute(nullable_long_attr));
CatalogAttribute *float_attr = new CatalogAttribute(relation_.get(),
"float_attr",
TypeFactory::GetType(kFloat, false));
ASSERT_EQ(2, relation_->addAttribute(float_attr));
CatalogAttribute *char_attr = new CatalogAttribute(relation_.get(),
"char_attr",
TypeFactory::GetType(kChar, 4, false));
ASSERT_EQ(3, relation_->addAttribute(char_attr));
CatalogAttribute *nullable_char_attr = new CatalogAttribute(relation_.get(),
"nullable_char_attr",
TypeFactory::GetType(kChar, 4, true));
ASSERT_EQ(4, relation_->addAttribute(nullable_char_attr));
CatalogAttribute *big_char_attr = new CatalogAttribute(relation_.get(),
"big_char_attr",
TypeFactory::GetType(kChar, 80, false));
ASSERT_EQ(5, relation_->addAttribute(big_char_attr));
CatalogAttribute *varchar_attr = new CatalogAttribute(relation_.get(),
"varchar_attr",
TypeFactory::GetType(kVarChar, 8, false));
ASSERT_EQ(6, relation_->addAttribute(varchar_attr));
// Create a MockTupleStorageSubBlock to hold tuples for testing.
tuple_store_.reset(new MockTupleStorageSubBlock(*relation_));
// Don't initialize the CSBTreeIndexSubBlock yet. Different tests will
// index on different attributes.
index_memory_.reset();
index_description_.reset();
index_.reset();
}
// Create index_ of size 'index_memory_size' on the specified 'index_attrs'.
void createIndex(const vector<attribute_id> &index_attrs, const size_t index_memory_size) {
ASSERT_LT(0u, index_attrs.size());
ASSERT_LE(index_attrs.size(), numeric_limits<uint16_t>::max());
// Make the IndexSubBlockDescription.
index_description_.reset(new IndexSubBlockDescription());
index_description_->set_sub_block_type(IndexSubBlockDescription::CSB_TREE);
for (vector<attribute_id>::const_iterator attr_it = index_attrs.begin();
attr_it != index_attrs.end();
++attr_it) {
index_description_->add_indexed_attribute_ids(*attr_it);
}
index_memory_.reset(index_memory_size);
std::memset(index_memory_.get(), 0x0, index_memory_size);
index_.reset(new CSBTreeIndexSubBlock(*tuple_store_,
*index_description_,
true,
index_memory_.get(),
index_memory_size));
}
// Insert a tuple with the specified attribute values into tuple_store_.
tuple_id insertTupleInTupleStore(const int64_t long_val,
const int64_t nullable_long_val,
const float float_val,
const string &char_val,
const string &nullable_char_val,
const string &big_char_val,
const string &varchar_val) {
std::vector<TypedValue> attrs;
attrs.emplace_back(LongType::InstanceNonNullable().makeValue(&long_val));
if (nullable_long_val == kLongAttrNullValue) {
attrs.emplace_back(LongType::InstanceNullable().makeNullValue());
} else {
attrs.emplace_back(LongType::InstanceNullable().makeValue(&nullable_long_val));
}
attrs.emplace_back(FloatType::InstanceNonNullable().makeValue(&float_val));
attrs.emplace_back(CharType::InstanceNonNullable(4).makeValue(
char_val.c_str(),
char_val.size() >= 4 ? 4 : char_val.size() + 1).ensureNotReference());
if (nullable_char_val == kCharAttrNullValue) {
attrs.emplace_back(CharType::InstanceNullable(4).makeNullValue());
} else {
attrs.emplace_back(CharType::InstanceNonNullable(4).makeValue(
nullable_char_val.c_str(),
nullable_char_val.size() >= 4 ? 4 : nullable_char_val.size() + 1).ensureNotReference());
}
attrs.emplace_back(CharType::InstanceNonNullable(80).makeValue(
big_char_val.c_str(),
big_char_val.size() >= 80 ? 80 : big_char_val.size() + 1).ensureNotReference());
TypedValue varchar_typed_value
= VarCharType::InstanceNonNullable(varchar_val.size()).makeValue(
varchar_val.c_str(),
varchar_val.size() + 1);
// Test strings are sometimes longer than 8 characters, so truncate if
// needed.
varchar_typed_value = VarCharType::InstanceNonNullable(8).coerceValue(
varchar_typed_value,
VarCharType::InstanceNonNullable(varchar_val.size()));
varchar_typed_value.ensureNotReference();
attrs.emplace_back(std::move(varchar_typed_value));
// MockTupleStorageSubBlock takes ownership of new tuple passed in with
// addTupleMock() method.
return tuple_store_->addTupleMock(new Tuple(std::move(attrs)));
}
// Generate a sample tuple based on 'base_value' and insert in into
// tuple_store_. The sample tuple will have long_attr equal to 'base_value',
// float_attr equal to 0.25 * base_value, and each of char_attr,
// big_char_attr, and varchar_attr equal to the string representation of
// 'base_value' with 'string_suffix' appended on to it. If 'generate_nulls'
// is true, then both nullable_long_attr and nullable_char_attr will be NULL,
// otherwise nullable_long_attr will be equal to 'base_value' and
// nullable_char_attr will be equal to the other string values. Returns the
// tuple_id of the inserted tuple.
tuple_id generateAndInsertTuple(const int64_t base_value,
const bool generate_nulls,
const string &string_suffix) {
ostringstream string_value_buffer;
string_value_buffer << base_value << string_suffix;
if (generate_nulls) {
return insertTupleInTupleStore(base_value,
kLongAttrNullValue,
0.25 * base_value,
string_value_buffer.str(),
kCharAttrNullValue,
string_value_buffer.str(),
string_value_buffer.str());
} else {
return insertTupleInTupleStore(base_value,
base_value,
0.25 * base_value,
string_value_buffer.str(),
string_value_buffer.str(),
string_value_buffer.str(),
string_value_buffer.str());
}
}
// Put some sample tuples in 'tuple_store_'. If 'add_to_index' is true, an
// entry is added to 'index_' after each tuple is inserted. If
// 'rebuild_index' is true, 'index_' is entirely rebuilt after each tuple is
// inserted. If 'check_consistency' is true, checkIndexConsistency() is
// called after every change to the index.
void insertSampleData(const bool add_to_index,
const bool rebuild_index,
const bool check_consistency) {
tuple_id previous_inserted_id = -1;
tuple_id inserted_id = -1;
// 10 tuples in order.
for (int tnum = 0; tnum < 10; ++tnum) {
inserted_id = generateAndInsertTuple(tnum, false, "aa");
ASSERT_EQ(previous_inserted_id + 1, inserted_id);
previous_inserted_id = inserted_id;
updateIndex(inserted_id, add_to_index, rebuild_index, check_consistency);
}
// A couple of tuples in the middle.
inserted_id = generateAndInsertTuple(4, false, "bb");
ASSERT_EQ(previous_inserted_id + 1, inserted_id);
previous_inserted_id = inserted_id;
updateIndex(inserted_id, add_to_index, rebuild_index, check_consistency);
inserted_id = generateAndInsertTuple(4, false, "cc");
ASSERT_EQ(previous_inserted_id + 1, inserted_id);
previous_inserted_id = inserted_id;
updateIndex(inserted_id, add_to_index, rebuild_index, check_consistency);
// 10 tuples in reverse order.
for (int tnum = 0; tnum < 10; ++tnum) {
inserted_id = generateAndInsertTuple(-tnum, false, "dd");
ASSERT_EQ(previous_inserted_id + 1, inserted_id);
previous_inserted_id = inserted_id;
updateIndex(inserted_id, add_to_index, rebuild_index, check_consistency);
}
// Some tuples with NULLs.
inserted_id = generateAndInsertTuple(0, true, "aa");
ASSERT_EQ(previous_inserted_id + 1, inserted_id);
previous_inserted_id = inserted_id;
updateIndex(inserted_id, add_to_index, rebuild_index, check_consistency);
inserted_id = generateAndInsertTuple(7, true, "aa");
ASSERT_EQ(previous_inserted_id + 1, inserted_id);
previous_inserted_id = inserted_id;
updateIndex(inserted_id, add_to_index, rebuild_index, check_consistency);
inserted_id = generateAndInsertTuple(-7, true, "dd");
ASSERT_EQ(previous_inserted_id + 1, inserted_id);
previous_inserted_id = inserted_id;
updateIndex(inserted_id, add_to_index, rebuild_index, check_consistency);
// Some way-out-there values.
inserted_id = generateAndInsertTuple(numeric_limits<int64_t>::min(), false, "0000");
ASSERT_EQ(previous_inserted_id + 1, inserted_id);
previous_inserted_id = inserted_id;
updateIndex(inserted_id, add_to_index, rebuild_index, check_consistency);
inserted_id = generateAndInsertTuple(numeric_limits<int64_t>::max(), false, "zzzz");
ASSERT_EQ(previous_inserted_id + 1, inserted_id);
previous_inserted_id = inserted_id;
updateIndex(inserted_id, add_to_index, rebuild_index, check_consistency);
// Some duplicate values.
for (int tnum = 0; tnum < 5; ++tnum) {
inserted_id = generateAndInsertTuple(2 * tnum, false, "aa");
ASSERT_EQ(previous_inserted_id + 1, inserted_id);
previous_inserted_id = inserted_id;
updateIndex(inserted_id, add_to_index, rebuild_index, check_consistency);
inserted_id = generateAndInsertTuple(-2 * tnum, false, "dd");
ASSERT_EQ(previous_inserted_id + 1, inserted_id);
previous_inserted_id = inserted_id;
updateIndex(inserted_id, add_to_index, rebuild_index, check_consistency);
}
}
// Helper method for insertSampleData(). If 'add_to_index' is true, an entry
// for 'new_tuple' is added to 'index_'. If 'rebuild_index' is true, then
// index_->rebuild() is called. If 'check_consistency' is true,
// checkIndexConsistency() is called after 'index_' is modified.
void updateIndex(const tuple_id new_tuple,
const bool add_to_index,
const bool rebuild_index,
const bool check_consistency) {
if (add_to_index) {
EXPECT_TRUE(index_->addEntry(new_tuple));
}
if (rebuild_index) {
EXPECT_TRUE(index_->rebuild());
}
if (check_consistency) {
checkIndexConsistency();
}
}
// Remove tuples previously inserted by insertSampleData() in a different
// order. If 'remove_from_index' is true, entries for each removed tuple will
// be removed from 'index_' one-by-one. If 'rebuild_index' is true, then
// 'index_' will be rebuilt after each tuple is removed. If
// 'check_consistency' is true, checkIndexConsistency() is called after each
// modification to 'index_'.
void deleteSampleData(const bool remove_from_index,
const bool rebuild_index,
const bool check_consistency) {
for (int i = 0; i < kNumSampleTuples; ++i) {
ASSERT_TRUE(tuple_store_->hasTupleWithID(kDeleteSequence[i]));
if (remove_from_index) {
index_->removeEntry(kDeleteSequence[i]);
if (check_consistency) {
checkIndexConsistency();
}
}
ASSERT_FALSE(tuple_store_->deleteTuple(kDeleteSequence[i]));
if (rebuild_index) {
EXPECT_TRUE(index_->rebuild());
if (check_consistency) {
checkIndexConsistency();
}
}
}
}
// Check that index_'s data structures are internally consistent.
void checkIndexConsistency() {
checkIndexBalance();
checkIndexOrdering();
checkIndexNodeGroupAllocationConsistency();
checkIndexSiblingConsistency();
}
// Determine the depth along the left edge of the tree, then verify that all
// leaves are at the same level.
void checkIndexBalance() const {
int depth = 0;
const CSBTreeIndexSubBlock::NodeHeader *current_node_header
= static_cast<const CSBTreeIndexSubBlock::NodeHeader*>(index_->getRootNode());
while (!current_node_header->is_leaf) {
++depth;
current_node_header = static_cast<const CSBTreeIndexSubBlock::NodeHeader*>(
index_->getNode(current_node_header->node_group_reference, 0));
}
checkNodeBalance(index_->getRootNode(), depth);
}
// Check that '*node' is balanced. 'depth' counts down level-by-level to 0 at
// the leaves.
void checkNodeBalance(const void *node, const int depth) const {
const CSBTreeIndexSubBlock::NodeHeader *node_header
= static_cast<const CSBTreeIndexSubBlock::NodeHeader*>(node);
if (node_header->is_leaf) {
EXPECT_EQ(0, depth);
} else {
ASSERT_GT(node_header->num_keys, 0);
ASSERT_LE(node_header->num_keys, index_->max_keys_internal_);
ASSERT_GE(node_header->node_group_reference, 0);
// Cast to unsigned to suppress GCC warning. Safe because of previous
// assertion.
ASSERT_LE(static_cast<unsigned int>(node_header->node_group_reference),
index_->node_group_used_bitmap_->size());
// If an internal node is not the root, it should be at least half-full.
if (node != index_->getRootNode()) {
EXPECT_GE(node_header->num_keys, index_->max_keys_internal_ / 2);
}
for (uint16_t child_number = 0;
child_number <= node_header->num_keys;
++child_number) {
checkNodeBalance(index_->getNode(node_header->node_group_reference, child_number), depth - 1);
}
}
}
// Check that the nodes in index_ are well-ordered.
void checkIndexOrdering() const {
if (index_->key_is_composite_) {
checkIndexOrderingWithComparator(*(index_->composite_key_comparator_));
} else if (index_->key_is_compressed_) {
const CompressedTupleStorageSubBlock &compressed_tuple_store
= static_cast<const CompressedTupleStorageSubBlock&>(index_->tuple_store_);
switch (compressed_tuple_store.compressedGetCompressedAttributeSize(
index_->indexed_attribute_ids_.front())) {
case 1:
checkIndexOrderingWithComparator(CompressedCodeLessComparator<std::uint8_t>());
break;
case 2:
checkIndexOrderingWithComparator(CompressedCodeLessComparator<std::uint16_t>());
break;
case 4:
checkIndexOrderingWithComparator(CompressedCodeLessComparator<std::uint32_t>());
break;
default:
FATAL_ERROR("Unexpected compressed key byte-length (not 1, 2, or 4) encountered "
"in CSBTreeIndexSubBlockTest::checkIndexOrdering()");
}
} else {
InvokeOnLessComparatorForTypeIgnoreNullability(
*(index_->key_type_),
[&](const auto &comp) { // NOLINT(build/c++11)
this->checkIndexOrderingWithComparator(comp);
});
}
}
template <typename ComparatorT>
void checkIndexOrderingWithComparator(const ComparatorT &key_comparator) const {
const void *root_node = index_->getRootNode();
if (static_cast<const CSBTreeIndexSubBlock::NodeHeader*>(root_node)->is_leaf) {
checkLeafNodeOrdering(root_node, nullptr, nullptr, key_comparator);
} else {
checkInternalNodeOrdering(root_node, nullptr, nullptr, key_comparator);
}
}
// Check that the subtree of 'index_' anchored at '*node' is properly
// ordered. If '*min_bound_key' is not NULL, all entries in the subtree
// should be greater than or equal to '*min_bound_key'. If '*max_bound_key'
// is not NULL, all entries in the subtree should be less than or equal to
// '*max_bound_key'. In all cases, keys within a node should be in ascending
// order, and non-leaf nodes should have at least one key.
template <typename ComparatorT>
void checkInternalNodeOrdering(const void *node,
const void *min_bound_key,
const void *max_bound_key,
const ComparatorT &key_comparator) const {
const CSBTreeIndexSubBlock::NodeHeader *node_header
= static_cast<const CSBTreeIndexSubBlock::NodeHeader*>(node);
ASSERT_FALSE(node_header->is_leaf);
// NodeHeader sanity check.
ASSERT_GT(node_header->num_keys, 0);
ASSERT_LE(node_header->num_keys, index_->max_keys_internal_);
ASSERT_GE(node_header->node_group_reference, 0);
// Cast to unsigned to supress GCC warning. Safe due to previous assertion.
ASSERT_LE(static_cast<unsigned int>(node_header->node_group_reference),
index_->node_group_used_bitmap_->size());
EXPECT_TRUE(index_->node_group_used_bitmap_->getBit(node_header->node_group_reference));
// Check the first child.
const void *first_child = index_->getNode(node_header->node_group_reference, 0);
const void *first_key = static_cast<const char*>(node) + sizeof(CSBTreeIndexSubBlock::NodeHeader);
bool children_are_leaves;
if (static_cast<const CSBTreeIndexSubBlock::NodeHeader*>(first_child)->is_leaf) {
children_are_leaves = true;
checkLeafNodeOrdering(first_child, min_bound_key, first_key, key_comparator);
} else {
children_are_leaves = false;
checkInternalNodeOrdering(first_child, min_bound_key, first_key, key_comparator);
}
// Check other children.
for (uint16_t key_num = 0;
key_num < node_header->num_keys;
++key_num) {
const void *key_ptr = static_cast<const char*>(node)
+ sizeof(CSBTreeIndexSubBlock::NodeHeader)
+ key_num * index_->key_length_bytes_;
if (key_num > 0) {
const void *previous_key_ptr = static_cast<const char*>(key_ptr) - index_->key_length_bytes_;
// Previous key should be less than this key OR equal.
if (!key_comparator.compareDataPtrs(previous_key_ptr, key_ptr)) {
EXPECT_FALSE(key_comparator.compareDataPtrs(key_ptr, previous_key_ptr));
}
}
const void *child_node = index_->getNode(node_header->node_group_reference, key_num + 1);
if (children_are_leaves) {
EXPECT_TRUE(static_cast<const CSBTreeIndexSubBlock::NodeHeader*>(child_node)->is_leaf);
} else {
EXPECT_FALSE(static_cast<const CSBTreeIndexSubBlock::NodeHeader*>(child_node)->is_leaf);
}
if (key_num == node_header->num_keys - 1) {
// Last child has same maximum bound as parent.
if (static_cast<const CSBTreeIndexSubBlock::NodeHeader*>(child_node)->is_leaf) {
checkLeafNodeOrdering(child_node, key_ptr, max_bound_key, key_comparator);
} else {
checkInternalNodeOrdering(child_node, key_ptr, max_bound_key, key_comparator);
}
} else {
const void *next_key_ptr = static_cast<const char*>(key_ptr) + index_->key_length_bytes_;
if (static_cast<const CSBTreeIndexSubBlock::NodeHeader*>(child_node)->is_leaf) {
checkLeafNodeOrdering(child_node, key_ptr, next_key_ptr, key_comparator);
} else {
checkInternalNodeOrdering(child_node, key_ptr, next_key_ptr, key_comparator);
}
}
}
}
// Check that the keys in the leaf node '*node' are in ascending order. If
// '*min_bound_key' is non-NULL, make sure that all keys in '*node' are
// greater than or equal to '*min_bound_key'. If '*max_bound_key' is
// non-NULL, make sure that all keys in '*node' are less than or equal to
// '*max_bound_key'. Also check that all tuple_ids referenced in '*node' are
// valid.
template <typename ComparatorT>
void checkLeafNodeOrdering(const void *node,
const void *min_bound_key,
const void *max_bound_key,
const ComparatorT &key_comparator) const {
const CSBTreeIndexSubBlock::NodeHeader *node_header
= static_cast<const CSBTreeIndexSubBlock::NodeHeader*>(node);
ASSERT_TRUE(node_header->is_leaf);
// NodeHeader sanity check.
EXPECT_LE(node_header->num_keys, index_->max_keys_leaf_);
if (node_header->node_group_reference == CSBTreeIndexSubBlock::kNodeGroupNextLeaf) {
// Every leaf node but the last should have a '*max_bound_key'.
EXPECT_NE(max_bound_key, nullptr);
} else if (node_header->node_group_reference == CSBTreeIndexSubBlock::kNodeGroupNone) {
// The rightmost leaf should have no maximum bound.
EXPECT_EQ(nullptr, max_bound_key);
} else {
// Last node in a group.
EXPECT_GE(node_header->node_group_reference, 0);
EXPECT_TRUE(index_->node_group_used_bitmap_->getBit(node_header->node_group_reference));
EXPECT_NE(max_bound_key, nullptr);
}
// Check the entries.
for (uint16_t entry_num = 0;
entry_num < node_header->num_keys;
++entry_num) {
const void *key_ptr = static_cast<const char*>(node)
+ sizeof(CSBTreeIndexSubBlock::NodeHeader)
+ entry_num * index_->key_tuple_id_pair_length_bytes_;
if (entry_num > 0) {
const void *previous_key_ptr = static_cast<const char*>(key_ptr)
- index_->key_tuple_id_pair_length_bytes_;
// Previous key should be less than this key OR equal.
if (!key_comparator.compareDataPtrs(previous_key_ptr, key_ptr)) {
EXPECT_FALSE(key_comparator.compareDataPtrs(key_ptr, previous_key_ptr));
}
}
if (min_bound_key != nullptr) {
if (!key_comparator.compareDataPtrs(min_bound_key, key_ptr)) {
EXPECT_FALSE(key_comparator.compareDataPtrs(key_ptr, min_bound_key));
}
}
if (max_bound_key != nullptr) {
if (!key_comparator.compareDataPtrs(key_ptr, max_bound_key)) {
EXPECT_FALSE(key_comparator.compareDataPtrs(max_bound_key, key_ptr));
}
}
const tuple_id *tuple_ptr = reinterpret_cast<const tuple_id*>(
static_cast<const char*>(key_ptr) + index_->key_length_bytes_);
EXPECT_GE(*tuple_ptr, 0);
}
}
// Check that all node groups reachable from the root node are marked as used
// in the index's node_group_used_bitmap_, and that no other groups are
// marked as used. Also check that the root node group is not a child of any
// node, and all other node groups are the child of exactly one internal
// node. Finally, check that the count of free node groups
// (index_->num_free_node_groups_) and the location of the first free node
// group (index_->next_free_node_group_) are correct.
void checkIndexNodeGroupAllocationConsistency() {
set<int> referenced_node_groups;
ASSERT_GE(index_->getRootNodeGroupNumber(), 0);
referenced_node_groups.insert(index_->getRootNodeGroupNumber());
collectReferencedNodeGroups(index_->getRootNode(), &referenced_node_groups);
int first_free_group = CSBTreeIndexSubBlock::kNodeGroupNone;
for (unsigned int node_group_num = 0;
node_group_num < index_->node_group_used_bitmap_->size();
++node_group_num) {
if (referenced_node_groups.find(node_group_num) == referenced_node_groups.end()) {
EXPECT_FALSE(index_->node_group_used_bitmap_->getBit(node_group_num));
if (first_free_group == CSBTreeIndexSubBlock::kNodeGroupNone) {
first_free_group = node_group_num;
}
} else {
EXPECT_TRUE(index_->node_group_used_bitmap_->getBit(node_group_num));
}
}
EXPECT_EQ(first_free_group, index_->next_free_node_group_);
ASSERT_GE(index_->num_free_node_groups_, 0);
EXPECT_EQ(index_->node_group_used_bitmap_->size() - referenced_node_groups.size(),
static_cast<unsigned int>(index_->num_free_node_groups_));
}
void collectReferencedNodeGroups(const void *node,
set<int> *referenced_node_groups) {
const CSBTreeIndexSubBlock::NodeHeader *node_header
= static_cast<const CSBTreeIndexSubBlock::NodeHeader*>(node);
if (!node_header->is_leaf) {
ASSERT_GE(node_header->node_group_reference, 0);
// The same node group should not be the child of more than one node.
EXPECT_EQ(0u, referenced_node_groups->count(node_header->node_group_reference));
referenced_node_groups->insert(node_header->node_group_reference);
for (uint16_t child_num = 0;
child_num < node_header->num_keys + 1;
++child_num) {
collectReferencedNodeGroups(index_->getNode(node_header->node_group_reference, child_num),
referenced_node_groups);
}
}
}
void checkIndexSiblingConsistency() {
int last_leaf_sibling = checkNodeSiblingConsistency(index_->getRootNode(),
index_->getRootNodeGroupNumber(),
CSBTreeIndexSubBlock::kNodeGroupNone);
EXPECT_EQ(CSBTreeIndexSubBlock::kNodeGroupNone, last_leaf_sibling);
}
int checkNodeSiblingConsistency(const void *node,
const int node_group_from_parent,
int node_group_from_sibling) {
const CSBTreeIndexSubBlock::NodeHeader *node_header
= static_cast<const CSBTreeIndexSubBlock::NodeHeader*>(node);
if (node_header->is_leaf) {
EXPECT_GE(node_group_from_parent, 0);
if (node_group_from_sibling != CSBTreeIndexSubBlock::kNodeGroupNone) {
EXPECT_EQ(node_group_from_parent, node_group_from_sibling);
}
if (node_header->node_group_reference == CSBTreeIndexSubBlock::kNodeGroupNextLeaf) {
return node_group_from_parent;
} else {
return node_header->node_group_reference;
}
} else {
for (uint16_t child_num = 0;
child_num < node_header->num_keys + 1;
++child_num) {
node_group_from_sibling
= checkNodeSiblingConsistency(index_->getNode(node_header->node_group_reference, child_num),
node_header->node_group_reference,
node_group_from_sibling);
}
return node_group_from_sibling;
}
}
// Create a ComparisonPredicate of the form "attribute comp literal".
template <typename AttributeType>
ComparisonPredicate* generateNumericComparisonPredicate(
const ComparisonID comp,
const attribute_id attribute,
const typename AttributeType::cpptype literal) {
ScalarAttribute *scalar_attribute = new ScalarAttribute(*relation_->getAttributeById(attribute));
ScalarLiteral *scalar_literal
= new ScalarLiteral(AttributeType::InstanceNonNullable().makeValue(&literal),
AttributeType::InstanceNonNullable());
return new ComparisonPredicate(ComparisonFactory::GetComparison(comp), scalar_attribute, scalar_literal);
}
ComparisonPredicate* generateStringComparisonPredicate(
const ComparisonID comp,
const attribute_id attribute,
const string &literal) {
ScalarAttribute *scalar_attribute = new ScalarAttribute(*relation_->getAttributeById(attribute));
ScalarLiteral *scalar_literal = new ScalarLiteral(
VarCharType::InstanceNonNullable(literal.size()).makeValue(
literal.c_str(),
literal.size() + 1).ensureNotReference(),
VarCharType::InstanceNonNullable(literal.size()));
return new ComparisonPredicate(ComparisonFactory::GetComparison(comp), scalar_attribute, scalar_literal);
}
std::unique_ptr<CatalogRelation> relation_;
std::unique_ptr<MockTupleStorageSubBlock> tuple_store_;
ScopedBuffer index_memory_;
std::unique_ptr<IndexSubBlockDescription> index_description_;
std::unique_ptr<CSBTreeIndexSubBlock> index_;
};
const char CSBTreeIndexSubBlockTest::kCharAttrNullValue[] = "_NULLSTRING";
const tuple_id CSBTreeIndexSubBlockTest::kDeleteSequence[]
= { 0, 5, 10, 20, 30, 36, 1, 2, 3, 4, 9, 8, 7, 6, 35, 12, 14, 16, 18, 11,
13, 15, 17, 19, 21, 22, 29, 28, 23, 27, 24, 26, 25, 34, 31, 32, 33 };
typedef CSBTreeIndexSubBlockTest CSBTreeIndexSubBlockDeathTest;
TEST_F(CSBTreeIndexSubBlockTest, BlockTooSmallTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(0); // long_attr
EXPECT_THROW(createIndex(indexed_attrs, 100), BlockMemoryTooSmall);
}
TEST_F(CSBTreeIndexSubBlockTest, KeyTooLargeTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(5); // big_char_attr
EXPECT_THROW(createIndex(indexed_attrs, kIndexSubBlockSize), CSBTreeKeyTooLarge);
}
TEST_F(CSBTreeIndexSubBlockTest, LongKeyInsertTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(0);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, true);
}
TEST_F(CSBTreeIndexSubBlockTest, LongKeyDeleteTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(0);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, false);
deleteSampleData(true, false, true);
}
TEST_F(CSBTreeIndexSubBlockTest, LongKeyRebuildTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(0);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(false, true, true);
deleteSampleData(false, true, true);
}
TEST_F(CSBTreeIndexSubBlockTest, LongKeyGetMatchesForPredicateTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(0);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, false);
std::unique_ptr<ComparisonPredicate> pred;
std::unique_ptr<TupleIdSequence> match_sequence;
// Test an equality predicate with several matches.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kEqual, 0, 0));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(5u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(0));
EXPECT_TRUE(match_sequence->get(12));
EXPECT_TRUE(match_sequence->get(22));
EXPECT_TRUE(match_sequence->get(27));
EXPECT_TRUE(match_sequence->get(28));
// Test an equality predicate with a single match.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kEqual, 0, -3));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(1u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(15));
// Test an equality predicate with no matches.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kEqual, 0, 42));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_TRUE(match_sequence->empty());
// Test an equality predicate with the least value.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kEqual, 0, numeric_limits<int64_t>::min()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(1u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(25));
// Test an equality predicate with the greatest value.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kEqual, 0, numeric_limits<int64_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(1u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(26));
// Test an inequality predicate.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kNotEqual, 0, 0));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(32u, match_sequence->numTuples());
EXPECT_FALSE(match_sequence->get(0));
EXPECT_FALSE(match_sequence->get(12));
EXPECT_FALSE(match_sequence->get(22));
EXPECT_FALSE(match_sequence->get(27));
EXPECT_FALSE(match_sequence->get(28));
// Test a less-than predicate.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLess, 0, -6));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(6u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(19));
EXPECT_TRUE(match_sequence->get(20));
EXPECT_TRUE(match_sequence->get(21));
EXPECT_TRUE(match_sequence->get(24));
EXPECT_TRUE(match_sequence->get(25));
EXPECT_TRUE(match_sequence->get(36));
// Test a less-than-or-equal predicate.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLessOrEqual, 0, -6));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(8u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(18));
EXPECT_TRUE(match_sequence->get(19));
EXPECT_TRUE(match_sequence->get(20));
EXPECT_TRUE(match_sequence->get(21));
EXPECT_TRUE(match_sequence->get(24));
EXPECT_TRUE(match_sequence->get(25));
EXPECT_TRUE(match_sequence->get(34));
EXPECT_TRUE(match_sequence->get(36));
// Test a greater-than predicate.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreater, 0, 6));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(6u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(7));
EXPECT_TRUE(match_sequence->get(8));
EXPECT_TRUE(match_sequence->get(9));
EXPECT_TRUE(match_sequence->get(23));
EXPECT_TRUE(match_sequence->get(26));
EXPECT_TRUE(match_sequence->get(35));
// Test a greater-than-or-equal predicate.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreaterOrEqual, 0, 6));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(8u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(6));
EXPECT_TRUE(match_sequence->get(7));
EXPECT_TRUE(match_sequence->get(8));
EXPECT_TRUE(match_sequence->get(9));
EXPECT_TRUE(match_sequence->get(23));
EXPECT_TRUE(match_sequence->get(26));
EXPECT_TRUE(match_sequence->get(33));
EXPECT_TRUE(match_sequence->get(35));
}
TEST_F(CSBTreeIndexSubBlockTest, NullableLongKeyInsertTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(1);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, true);
}
TEST_F(CSBTreeIndexSubBlockTest, NullableLongKeyDeleteTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(1);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, false);
deleteSampleData(true, false, true);
}
TEST_F(CSBTreeIndexSubBlockTest, NullableLongKeyRebuildTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(1);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(false, true, true);
deleteSampleData(false, true, true);
}
TEST_F(CSBTreeIndexSubBlockTest, NullableLongKeyGetMatchesForPredicateTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(1);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, false);
std::unique_ptr<ComparisonPredicate> pred;
std::unique_ptr<TupleIdSequence> match_sequence;
// Test an equality predicate with several matches.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kEqual, 1, 0));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(4u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(0));
EXPECT_TRUE(match_sequence->get(12));
EXPECT_TRUE(match_sequence->get(27));
EXPECT_TRUE(match_sequence->get(28));
// Test an inequality predicate.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kNotEqual, 1, 0));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(30u, match_sequence->numTuples());
EXPECT_FALSE(match_sequence->get(0));
EXPECT_FALSE(match_sequence->get(12));
EXPECT_FALSE(match_sequence->get(22));
EXPECT_FALSE(match_sequence->get(23));
EXPECT_FALSE(match_sequence->get(24));
EXPECT_FALSE(match_sequence->get(27));
EXPECT_FALSE(match_sequence->get(28));
// Test a less-than predicate.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLess, 1, -6));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(5u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(19));
EXPECT_TRUE(match_sequence->get(20));
EXPECT_TRUE(match_sequence->get(21));
EXPECT_TRUE(match_sequence->get(25));
EXPECT_TRUE(match_sequence->get(36));
// Test a less-than-or-equal predicate.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLessOrEqual, 1, -6));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(7u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(18));
EXPECT_TRUE(match_sequence->get(19));
EXPECT_TRUE(match_sequence->get(20));
EXPECT_TRUE(match_sequence->get(21));
EXPECT_TRUE(match_sequence->get(25));
EXPECT_TRUE(match_sequence->get(34));
EXPECT_TRUE(match_sequence->get(36));
// Test a greater-than predicate.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreater, 1, 6));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(5u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(7));
EXPECT_TRUE(match_sequence->get(8));
EXPECT_TRUE(match_sequence->get(9));
EXPECT_TRUE(match_sequence->get(26));
EXPECT_TRUE(match_sequence->get(35));
// Test a greater-than-or-equal predicate.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreaterOrEqual, 1, 6));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(7u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(6));
EXPECT_TRUE(match_sequence->get(7));
EXPECT_TRUE(match_sequence->get(8));
EXPECT_TRUE(match_sequence->get(9));
EXPECT_TRUE(match_sequence->get(26));
EXPECT_TRUE(match_sequence->get(33));
EXPECT_TRUE(match_sequence->get(35));
}
TEST_F(CSBTreeIndexSubBlockTest, FloatKeyInsertTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(2);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, true);
}
TEST_F(CSBTreeIndexSubBlockTest, FloatKeyDeleteTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(2);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, false);
deleteSampleData(true, false, true);
}
TEST_F(CSBTreeIndexSubBlockTest, FloatKeyRebuildTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(2);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(false, true, true);
deleteSampleData(false, true, true);
}
TEST_F(CSBTreeIndexSubBlockTest, FloatKeyGetMatchesForPredicateTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(2);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, false);
std::unique_ptr<ComparisonPredicate> pred;
std::unique_ptr<TupleIdSequence> match_sequence;
// Test an equality predicate with several matches.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kEqual, 2, 0.0));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(5u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(0));
EXPECT_TRUE(match_sequence->get(12));
EXPECT_TRUE(match_sequence->get(22));
EXPECT_TRUE(match_sequence->get(27));
EXPECT_TRUE(match_sequence->get(28));
// Test an equality predicate with a single match.
pred.reset(generateNumericComparisonPredicate<FloatType>(ComparisonID::kEqual, 2, -0.75));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(1u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(15));
// Test an equality predicate with no matches.
pred.reset(generateNumericComparisonPredicate<FloatType>(ComparisonID::kEqual, 2, 42.0));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_TRUE(match_sequence->empty());
// Test an equality predicate with the least value.
pred.reset(generateNumericComparisonPredicate<FloatType>(ComparisonID::kEqual,
2,
0.25 * numeric_limits<int64_t>::min()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(1u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(25));
// Test an equality predicate with the greatest value.
pred.reset(generateNumericComparisonPredicate<FloatType>(ComparisonID::kEqual,
2,
0.25 * numeric_limits<int64_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(1u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(26));
// Test an inequality predicate.
pred.reset(generateNumericComparisonPredicate<FloatType>(ComparisonID::kNotEqual, 2, 0.0));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(32u, match_sequence->numTuples());
EXPECT_FALSE(match_sequence->get(0));
EXPECT_FALSE(match_sequence->get(12));
EXPECT_FALSE(match_sequence->get(22));
EXPECT_FALSE(match_sequence->get(27));
EXPECT_FALSE(match_sequence->get(28));
// Test a less-than predicate.
pred.reset(generateNumericComparisonPredicate<FloatType>(ComparisonID::kLess, 2, -1.5));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(6u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(19));
EXPECT_TRUE(match_sequence->get(20));
EXPECT_TRUE(match_sequence->get(21));
EXPECT_TRUE(match_sequence->get(24));
EXPECT_TRUE(match_sequence->get(25));
EXPECT_TRUE(match_sequence->get(36));
// Test a less-than-or-equal predicate.
pred.reset(generateNumericComparisonPredicate<FloatType>(ComparisonID::kLessOrEqual, 2, -1.5));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(8u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(18));
EXPECT_TRUE(match_sequence->get(19));
EXPECT_TRUE(match_sequence->get(20));
EXPECT_TRUE(match_sequence->get(21));
EXPECT_TRUE(match_sequence->get(24));
EXPECT_TRUE(match_sequence->get(25));
EXPECT_TRUE(match_sequence->get(34));
EXPECT_TRUE(match_sequence->get(36));
// Test a greater-than predicate.
pred.reset(generateNumericComparisonPredicate<FloatType>(ComparisonID::kGreater, 2, 1.5));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(6u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(7));
EXPECT_TRUE(match_sequence->get(8));
EXPECT_TRUE(match_sequence->get(9));
EXPECT_TRUE(match_sequence->get(23));
EXPECT_TRUE(match_sequence->get(26));
EXPECT_TRUE(match_sequence->get(35));
// Test a greater-than-or-equal predicate.
pred.reset(generateNumericComparisonPredicate<FloatType>(ComparisonID::kGreaterOrEqual, 2, 1.5));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(8u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(6));
EXPECT_TRUE(match_sequence->get(7));
EXPECT_TRUE(match_sequence->get(8));
EXPECT_TRUE(match_sequence->get(9));
EXPECT_TRUE(match_sequence->get(23));
EXPECT_TRUE(match_sequence->get(26));
EXPECT_TRUE(match_sequence->get(33));
EXPECT_TRUE(match_sequence->get(35));
}
TEST_F(CSBTreeIndexSubBlockTest, CharKeyInsertTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(3);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, true);
}
TEST_F(CSBTreeIndexSubBlockTest, CharKeyDeleteTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(3);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, false);
deleteSampleData(true, false, true);
}
TEST_F(CSBTreeIndexSubBlockTest, CharKeyRebuildTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(3);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(false, true, true);
deleteSampleData(false, true, true);
}
TEST_F(CSBTreeIndexSubBlockTest, CharKeyGetMatchesForPredicateTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(3);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, false);
std::unique_ptr<ComparisonPredicate> pred;
std::unique_ptr<TupleIdSequence> match_sequence;
// Test an equality predicate with several matches.
pred.reset(generateStringComparisonPredicate(ComparisonID::kEqual, 3, "0aa"));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(3u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(0));
EXPECT_TRUE(match_sequence->get(22));
EXPECT_TRUE(match_sequence->get(27));
// Test an equality predicate with a single match.
pred.reset(generateStringComparisonPredicate(ComparisonID::kEqual, 3, "-3dd"));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(1u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(15));
// Test an equality predicate with no matches.
pred.reset(generateStringComparisonPredicate(ComparisonID::kEqual, 3, "foo"));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_TRUE(match_sequence->empty());
// Test an equality predicate with the least value.
pred.reset(generateStringComparisonPredicate(ComparisonID::kEqual, 3, "-1dd"));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(1u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(13));
// Test an equality predicate with the greatest value.
pred.reset(generateStringComparisonPredicate(ComparisonID::kEqual, 3, "9aa"));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(1u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(9));
// Test an inequality predicate.
pred.reset(generateStringComparisonPredicate(ComparisonID::kNotEqual, 3, "0aa"));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(34u, match_sequence->numTuples());
EXPECT_FALSE(match_sequence->get(0));
EXPECT_FALSE(match_sequence->get(22));
EXPECT_FALSE(match_sequence->get(27));
// Test a less-than predicate.
pred.reset(generateStringComparisonPredicate(ComparisonID::kLess, 3, "-6dd"));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(7u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(13));
EXPECT_TRUE(match_sequence->get(14));
EXPECT_TRUE(match_sequence->get(15));
EXPECT_TRUE(match_sequence->get(16));
EXPECT_TRUE(match_sequence->get(17));
EXPECT_TRUE(match_sequence->get(30));
EXPECT_TRUE(match_sequence->get(32));
// Test a less-than-or-equal predicate.
pred.reset(generateStringComparisonPredicate(ComparisonID::kLessOrEqual, 3, "-6dd"));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(9u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(13));
EXPECT_TRUE(match_sequence->get(14));
EXPECT_TRUE(match_sequence->get(15));
EXPECT_TRUE(match_sequence->get(16));
EXPECT_TRUE(match_sequence->get(17));
EXPECT_TRUE(match_sequence->get(18));
EXPECT_TRUE(match_sequence->get(30));
EXPECT_TRUE(match_sequence->get(32));
EXPECT_TRUE(match_sequence->get(34));
// Test a greater-than predicate.
pred.reset(generateStringComparisonPredicate(ComparisonID::kGreater, 3, "6aa"));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(6u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(7));
EXPECT_TRUE(match_sequence->get(8));
EXPECT_TRUE(match_sequence->get(9));
EXPECT_TRUE(match_sequence->get(23));
EXPECT_TRUE(match_sequence->get(26));
EXPECT_TRUE(match_sequence->get(35));
// Test a greater-than-or-equal predicate.
pred.reset(generateStringComparisonPredicate(ComparisonID::kGreaterOrEqual, 3, "6aa"));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(8u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(6));
EXPECT_TRUE(match_sequence->get(7));
EXPECT_TRUE(match_sequence->get(8));
EXPECT_TRUE(match_sequence->get(9));
EXPECT_TRUE(match_sequence->get(23));
EXPECT_TRUE(match_sequence->get(26));
EXPECT_TRUE(match_sequence->get(33));
EXPECT_TRUE(match_sequence->get(35));
}
TEST_F(CSBTreeIndexSubBlockTest, NullableCharKeyInsertTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(4);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, true);
}
TEST_F(CSBTreeIndexSubBlockTest, NullableCharKeyDeleteTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(4);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, false);
deleteSampleData(true, false, true);
}
TEST_F(CSBTreeIndexSubBlockTest, NullableCharKeyRebuildTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(4);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(false, true, true);
deleteSampleData(false, true, true);
}
TEST_F(CSBTreeIndexSubBlockTest, NullableCharKeyGetMatchesForPredicateTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(4);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, false);
std::unique_ptr<ComparisonPredicate> pred;
std::unique_ptr<TupleIdSequence> match_sequence;
// Test an equality predicate with several matches.
pred.reset(generateStringComparisonPredicate(ComparisonID::kEqual, 4, "0aa"));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(2u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(0));
EXPECT_TRUE(match_sequence->get(27));
// Test an inequality predicate.
pred.reset(generateStringComparisonPredicate(ComparisonID::kNotEqual, 4, "0aa"));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(32u, match_sequence->numTuples());
EXPECT_FALSE(match_sequence->get(0));
EXPECT_FALSE(match_sequence->get(27));
// Test a less-than predicate.
pred.reset(generateStringComparisonPredicate(ComparisonID::kLess, 4, "-6dd"));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(7u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(13));
EXPECT_TRUE(match_sequence->get(14));
EXPECT_TRUE(match_sequence->get(15));
EXPECT_TRUE(match_sequence->get(16));
EXPECT_TRUE(match_sequence->get(17));
EXPECT_TRUE(match_sequence->get(30));
EXPECT_TRUE(match_sequence->get(32));
// Test a less-than-or-equal predicate.
pred.reset(generateStringComparisonPredicate(ComparisonID::kLessOrEqual, 4, "-6dd"));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(9u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(13));
EXPECT_TRUE(match_sequence->get(14));
EXPECT_TRUE(match_sequence->get(15));
EXPECT_TRUE(match_sequence->get(16));
EXPECT_TRUE(match_sequence->get(17));
EXPECT_TRUE(match_sequence->get(18));
EXPECT_TRUE(match_sequence->get(30));
EXPECT_TRUE(match_sequence->get(32));
EXPECT_TRUE(match_sequence->get(34));
// Test a greater-than predicate.
pred.reset(generateStringComparisonPredicate(ComparisonID::kGreater, 4, "6aa"));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(5u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(7));
EXPECT_TRUE(match_sequence->get(8));
EXPECT_TRUE(match_sequence->get(9));
EXPECT_TRUE(match_sequence->get(26));
EXPECT_TRUE(match_sequence->get(35));
// Test a greater-than-or-equal predicate.
pred.reset(generateStringComparisonPredicate(ComparisonID::kGreaterOrEqual, 4, "6aa"));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(7u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(6));
EXPECT_TRUE(match_sequence->get(7));
EXPECT_TRUE(match_sequence->get(8));
EXPECT_TRUE(match_sequence->get(9));
EXPECT_TRUE(match_sequence->get(26));
EXPECT_TRUE(match_sequence->get(33));
EXPECT_TRUE(match_sequence->get(35));
}
TEST_F(CSBTreeIndexSubBlockTest, CompositeKeyInsertTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(0);
indexed_attrs.push_back(3);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, true);
}
TEST_F(CSBTreeIndexSubBlockTest, CompositeKeyDeleteTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(0);
indexed_attrs.push_back(3);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, false);
deleteSampleData(true, false, true);
}
TEST_F(CSBTreeIndexSubBlockTest, CompositeKeyRebuildTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(0);
indexed_attrs.push_back(3);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(false, true, true);
deleteSampleData(false, true, true);
}
TEST_F(CSBTreeIndexSubBlockTest, NullableCompositeKeyInsertTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(0);
indexed_attrs.push_back(4);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, true);
}
TEST_F(CSBTreeIndexSubBlockTest, NullableCompositeKeyDeleteTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(0);
indexed_attrs.push_back(4);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, false);
deleteSampleData(true, false, true);
}
TEST_F(CSBTreeIndexSubBlockTest, NullableCompositeKeyRebuildTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(0);
indexed_attrs.push_back(4);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(false, true, true);
deleteSampleData(false, true, true);
}
TEST_F(CSBTreeIndexSubBlockDeathTest, UnsetSubBlockTypeTest) {
index_description_.reset(new IndexSubBlockDescription());
index_description_->add_indexed_attribute_ids(0);
index_memory_.reset(kIndexSubBlockSize);
EXPECT_DEATH(index_.reset(new CSBTreeIndexSubBlock(*tuple_store_,
*index_description_,
true,
index_memory_.get(),
kIndexSubBlockSize)),
"");
}
TEST_F(CSBTreeIndexSubBlockDeathTest, NoIndexedAttributeTest) {
index_description_.reset(new IndexSubBlockDescription());
index_description_->set_sub_block_type(IndexSubBlockDescription::CSB_TREE);
index_memory_.reset(kIndexSubBlockSize);
EXPECT_DEATH(index_.reset(new CSBTreeIndexSubBlock(*tuple_store_,
*index_description_,
true,
index_memory_.get(),
kIndexSubBlockSize)),
"");
}
TEST_F(CSBTreeIndexSubBlockDeathTest, IndexOnVariableLengthAttributeTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(6); // varchar_attr
EXPECT_DEATH(createIndex(indexed_attrs, kIndexSubBlockSize), "");
}
TEST_F(CSBTreeIndexSubBlockDeathTest, IndexOnNonexistentAttributeTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(7);
EXPECT_DEATH(createIndex(indexed_attrs, kIndexSubBlockSize), "");
}
TEST_F(CSBTreeIndexSubBlockDeathTest, GetMatchesForPredicateOnNonIndexedAttributeTest) {
vector<attribute_id> indexed_attrs;
indexed_attrs.push_back(0);
createIndex(indexed_attrs, kIndexSubBlockSize);
insertSampleData(true, false, false);
std::unique_ptr<ComparisonPredicate> pred;
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kEqual, 1, 0));
EXPECT_DEATH(index_->getMatchesForPredicate(*pred, nullptr), "");
}
// Test special functionality with a CompressedTupleStorageSubBlock and
// truncation-compressed key.
TEST_F(CSBTreeIndexSubBlockTest, TruncatedCompressedKeyTest) {
// Create a relation with just a single attribute, which will be compressed.
relation_.reset(new CatalogRelation(NULL, "TestRelation"));
CatalogAttribute *truncated_long_attr = new CatalogAttribute(relation_.get(),
"truncated_long_attr",
TypeFactory::GetType(kLong, false));
ASSERT_EQ(0, relation_->addAttribute(truncated_long_attr));
// Create a CompressedPackedRowStoreTupleStorageSubBlock.
TupleStorageSubBlockDescription compressed_tuple_store_description;
compressed_tuple_store_description.set_sub_block_type(
TupleStorageSubBlockDescription::COMPRESSED_PACKED_ROW_STORE);
compressed_tuple_store_description.AddExtension(
CompressedPackedRowStoreTupleStorageSubBlockDescription::compressed_attribute_id,
0);
ScopedBuffer compressed_tuple_store_memory(kIndexSubBlockSize);
std::unique_ptr<CompressedPackedRowStoreTupleStorageSubBlock> compressed_tuple_store;
compressed_tuple_store.reset(new CompressedPackedRowStoreTupleStorageSubBlock(
*relation_,
compressed_tuple_store_description,
true,
compressed_tuple_store_memory.get(),
kIndexSubBlockSize));
// Create an index on the compressed tuple store.
IndexSubBlockDescription compressed_index_description;
compressed_index_description.set_sub_block_type(IndexSubBlockDescription::CSB_TREE);
compressed_index_description.add_indexed_attribute_ids(0);
index_memory_.reset(kIndexSubBlockSize);
std::memset(index_memory_.get(), 0x0, kIndexSubBlockSize);
index_.reset(new CSBTreeIndexSubBlock(*compressed_tuple_store,
compressed_index_description,
true,
index_memory_.get(),
kIndexSubBlockSize));
// Bulk-load some tuples into the compressed tuple store.
for (int tuple_num = 0; tuple_num < 100; ++tuple_num) {
std::vector<TypedValue> attrs;
attrs.emplace_back(static_cast<int64_t>(tuple_num));
ASSERT_TRUE(compressed_tuple_store->insertTupleInBatch(Tuple(std::move(attrs))));
}
for (int tuple_num = 0; tuple_num < 100; ++tuple_num) {
std::vector<TypedValue> attrs;
attrs.emplace_back(static_cast<int64_t>(100 - tuple_num));
ASSERT_TRUE(compressed_tuple_store->insertTupleInBatch(Tuple(std::move(attrs))));
}
// Build the tuple-store.
compressed_tuple_store->rebuild();
EXPECT_FALSE(compressed_tuple_store->compressedAttributeIsDictionaryCompressed(0));
EXPECT_TRUE(compressed_tuple_store->compressedAttributeIsTruncationCompressed(0));
EXPECT_EQ(1u, compressed_tuple_store->compressedGetCompressedAttributeSize(0));
// Build the index.
ASSERT_TRUE(index_->rebuild());
checkIndexConsistency();
// Evaluate some predicates.
std::unique_ptr<ComparisonPredicate> pred;
std::unique_ptr<TupleIdSequence> match_sequence;
// Equality with a couple of matches.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kEqual, 0, 50));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(2u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(50));
EXPECT_TRUE(match_sequence->get(150));
// Equality in-range, but with no match.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kEqual, 0, 101));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(0u, match_sequence->numTuples());
// Equality out-of-range.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kEqual, 0, -1));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(0u, match_sequence->numTuples());
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kEqual,
0,
1 + numeric_limits<uint8_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(0u, match_sequence->numTuples());
// Inequality (inverses of equality checks above).
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kNotEqual, 0, 50));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(198u, match_sequence->numTuples());
EXPECT_FALSE(match_sequence->get(50));
EXPECT_FALSE(match_sequence->get(150));
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kNotEqual, 0, 101));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(200u, match_sequence->numTuples());
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kNotEqual, 0, -1));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(200u, match_sequence->numTuples());
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kNotEqual,
0,
1 + numeric_limits<uint8_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(200u, match_sequence->numTuples());
// Less-than predicates.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLess, 0, 50));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(99u, match_sequence->numTuples());
for (tuple_id tuple_num = 0; tuple_num < 200; ++tuple_num) {
if ((tuple_num < 50) || (tuple_num > 150)) {
EXPECT_TRUE(match_sequence->get(tuple_num));
} else {
EXPECT_FALSE(match_sequence->get(tuple_num));
}
}
// Less-than predicate, in-range and matches everything.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLess, 0, 101));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(200u, match_sequence->numTuples());
// Less-than predicate, out-of-range (matches nothing).
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLess, 0, 0));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(0u, match_sequence->numTuples());
// Less-than predicate, out-of-range (matches everything).
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLess, 0, 1 + numeric_limits<uint8_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(200u, match_sequence->numTuples());
// Less-than-or-equal predicates.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLessOrEqual, 0, 50));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(101u, match_sequence->numTuples());
for (tuple_id tuple_num = 0; tuple_num < 200; ++tuple_num) {
if ((tuple_num <= 50) || (tuple_num >= 150)) {
EXPECT_TRUE(match_sequence->get(tuple_num));
} else {
EXPECT_FALSE(match_sequence->get(tuple_num));
}
}
// Less-than-or-equal predicate, in-range and matches everything.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLessOrEqual, 0, 100));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(200u, match_sequence->numTuples());
// Less-than-or-equal predicate, out-of-range (matches nothing).
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLessOrEqual, 0, -1));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(0u, match_sequence->numTuples());
// Less-than-or-equal predicate, out-of-range (matches everything).
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLessOrEqual,
0,
numeric_limits<uint8_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(200u, match_sequence->numTuples());
// Greater-than predicates.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreater, 0, 50));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(99u, match_sequence->numTuples());
for (tuple_id tuple_num = 0; tuple_num < 200; ++tuple_num) {
if ((tuple_num > 50) && (tuple_num < 150)) {
EXPECT_TRUE(match_sequence->get(tuple_num));
} else {
EXPECT_FALSE(match_sequence->get(tuple_num));
}
}
// Greater-than predicate, in-range and matches nothing.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreater, 0, 100));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(0u, match_sequence->numTuples());
// Greater-than predicate, out-of-range (matches nothing).
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreater, 0, numeric_limits<uint8_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(0u, match_sequence->numTuples());
// Greater-than predicate, out-of-range (matches everything).
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreater, 0, -1));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(200u, match_sequence->numTuples());
// Greater-than-or-equal predicates.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreaterOrEqual, 0, 50));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(101u, match_sequence->numTuples());
for (tuple_id tuple_num = 0; tuple_num < 200; ++tuple_num) {
if ((tuple_num >= 50) && (tuple_num <= 150)) {
EXPECT_TRUE(match_sequence->get(tuple_num));
} else {
EXPECT_FALSE(match_sequence->get(tuple_num));
}
}
// Greater-than-or-equal predicate, in-range and matches nothing.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreaterOrEqual, 0, 101));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(0u, match_sequence->numTuples());
// Greater-than-or-equal predicate, out-of-range (matches nothing).
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreaterOrEqual,
0,
1 + numeric_limits<uint8_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(0u, match_sequence->numTuples());
// Greater-than-or-equal predicate, out-of-range (matches everything).
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreaterOrEqual, 0, 0));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(200u, match_sequence->numTuples());
}
// Test special functionality with a CompressedTupleStorageSubBlock and
// dictionary-compressed key.
TEST_F(CSBTreeIndexSubBlockTest, DictionaryCompressedKeyTest) {
// Create a relation with just a single attribute, which will be compressed.
relation_.reset(new CatalogRelation(NULL, "TestRelation"));
CatalogAttribute *dict_long_attr = new CatalogAttribute(relation_.get(),
"dict_long_attr",
TypeFactory::GetType(kLong, false));
ASSERT_EQ(0, relation_->addAttribute(dict_long_attr));
// Create a CompressedPackedRowStoreTupleStorageSubBlock.
TupleStorageSubBlockDescription compressed_tuple_store_description;
compressed_tuple_store_description.set_sub_block_type(
TupleStorageSubBlockDescription::COMPRESSED_PACKED_ROW_STORE);
compressed_tuple_store_description.AddExtension(
CompressedPackedRowStoreTupleStorageSubBlockDescription::compressed_attribute_id,
0);
ScopedBuffer compressed_tuple_store_memory(kIndexSubBlockSize);
std::unique_ptr<CompressedPackedRowStoreTupleStorageSubBlock> compressed_tuple_store;
compressed_tuple_store.reset(new CompressedPackedRowStoreTupleStorageSubBlock(
*relation_,
compressed_tuple_store_description,
true,
compressed_tuple_store_memory.get(),
kIndexSubBlockSize));
// Create an index on the compressed tuple store.
IndexSubBlockDescription compressed_index_description;
compressed_index_description.set_sub_block_type(IndexSubBlockDescription::CSB_TREE);
compressed_index_description.add_indexed_attribute_ids(0);
index_memory_.reset(kIndexSubBlockSize);
std::memset(index_memory_.get(), 0x0, kIndexSubBlockSize);
index_.reset(new CSBTreeIndexSubBlock(*compressed_tuple_store,
compressed_index_description,
true,
index_memory_.get(),
kIndexSubBlockSize));
// Bulk-load some tuples into the compressed tuple store.
for (int tuple_num = 0; tuple_num < 100; ++tuple_num) {
std::vector<TypedValue> attrs;
attrs.emplace_back(static_cast<int64_t>(
static_cast<int64_t>(tuple_num) + numeric_limits<uint32_t>::max()));
ASSERT_TRUE(compressed_tuple_store->insertTupleInBatch(Tuple(std::move(attrs))));
}
for (int tuple_num = 0; tuple_num < 100; ++tuple_num) {
std::vector<TypedValue> attrs;
attrs.emplace_back(static_cast<int64_t>(
static_cast<int64_t>(100 - tuple_num) + numeric_limits<uint32_t>::max()));
ASSERT_TRUE(compressed_tuple_store->insertTupleInBatch(Tuple(std::move(attrs))));
}
// Build the tuple-store.
compressed_tuple_store->rebuild();
EXPECT_TRUE(compressed_tuple_store->compressedAttributeIsDictionaryCompressed(0));
EXPECT_FALSE(compressed_tuple_store->compressedAttributeIsTruncationCompressed(0));
EXPECT_EQ(1u, compressed_tuple_store->compressedGetCompressedAttributeSize(0));
// Build the index.
ASSERT_TRUE(index_->rebuild());
checkIndexConsistency();
// Evaluate some predicates.
std::unique_ptr<ComparisonPredicate> pred;
std::unique_ptr<TupleIdSequence> match_sequence;
// Equality with a couple of matches.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kEqual,
0,
static_cast<int64_t>(50) + numeric_limits<uint32_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(2u, match_sequence->numTuples());
EXPECT_TRUE(match_sequence->get(50));
EXPECT_TRUE(match_sequence->get(150));
// Equality with no match.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kEqual, 0, 0));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(0u, match_sequence->numTuples());
// Inequality (inverses of equality checks above).
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kNotEqual,
0,
static_cast<int64_t>(50) + numeric_limits<uint32_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(198u, match_sequence->numTuples());
EXPECT_FALSE(match_sequence->get(50));
EXPECT_FALSE(match_sequence->get(150));
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kNotEqual, 0, 0));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(200u, match_sequence->numTuples());
// Less-than predicates.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLess,
0,
static_cast<int64_t>(50) + numeric_limits<uint32_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(99u, match_sequence->numTuples());
for (tuple_id tuple_num = 0; tuple_num < 200; ++tuple_num) {
if ((tuple_num < 50) || (tuple_num > 150)) {
EXPECT_TRUE(match_sequence->get(tuple_num));
} else {
EXPECT_FALSE(match_sequence->get(tuple_num));
}
}
// Less-than predicate which matches everything.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLess,
0,
static_cast<int64_t>(101)
+ numeric_limits<uint32_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(200u, match_sequence->numTuples());
// Less-than predicate which matches nothing.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLess, 0, numeric_limits<uint32_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(0u, match_sequence->numTuples());
// Less-than-or-equal predicates.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLessOrEqual,
0,
static_cast<int64_t>(50) + numeric_limits<uint32_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(101u, match_sequence->numTuples());
for (tuple_id tuple_num = 0; tuple_num < 200; ++tuple_num) {
if ((tuple_num <= 50) || (tuple_num >= 150)) {
EXPECT_TRUE(match_sequence->get(tuple_num));
} else {
EXPECT_FALSE(match_sequence->get(tuple_num));
}
}
// Less-than-or-equal predicate which matches everything.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLessOrEqual,
0,
static_cast<int64_t>(100)
+ numeric_limits<uint32_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(200u, match_sequence->numTuples());
// Less-than-or-equal predicate which matches nothing.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kLessOrEqual,
0,
numeric_limits<uint32_t>::max() - 1));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(0u, match_sequence->numTuples());
// Greater-than predicates.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreater,
0,
static_cast<int64_t>(50) + numeric_limits<uint32_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(99u, match_sequence->numTuples());
for (tuple_id tuple_num = 0; tuple_num < 200; ++tuple_num) {
if ((tuple_num > 50) && (tuple_num < 150)) {
EXPECT_TRUE(match_sequence->get(tuple_num));
} else {
EXPECT_FALSE(match_sequence->get(tuple_num));
}
}
// Greater-than predicate which matches nothing.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreater,
0,
static_cast<int64_t>(100)
+ numeric_limits<uint32_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(0u, match_sequence->numTuples());
// Greater-than predicate which matches everything.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreater,
0,
numeric_limits<uint32_t>::max() - 1));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(200u, match_sequence->numTuples());
// Greater-than-or-equal predicates.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreaterOrEqual,
0,
static_cast<int64_t>(50) + numeric_limits<uint32_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(101u, match_sequence->numTuples());
for (tuple_id tuple_num = 0; tuple_num < 200; ++tuple_num) {
if ((tuple_num >= 50) && (tuple_num <= 150)) {
EXPECT_TRUE(match_sequence->get(tuple_num));
} else {
EXPECT_FALSE(match_sequence->get(tuple_num));
}
}
// Greater-than-or-equal predicate which matches nothing.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreaterOrEqual,
0,
static_cast<int64_t>(101)
+ numeric_limits<uint32_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(0u, match_sequence->numTuples());
// Greater-than-or-equal predicate which matches everything.
pred.reset(generateNumericComparisonPredicate<LongType>(ComparisonID::kGreaterOrEqual,
0,
numeric_limits<uint32_t>::max()));
match_sequence.reset(index_->getMatchesForPredicate(*pred, nullptr));
EXPECT_EQ(200u, match_sequence->numTuples());
}
} // namespace quickstep