{"action":"created","comment":{"url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/comments/54823932","id":54823932,"diff_hunk":"@@ -0,0 +1,670 @@\n+/**\n+ *   Copyright 2016 Pivotal Software, Inc.\n+ *\n+ *   Licensed under the Apache License, Version 2.0 (the \"License\");\n+ *   you may not use this file except in compliance with the License.\n+ *   You may obtain a copy of the License at\n+ *\n+ *       http://www.apache.org/licenses/LICENSE-2.0\n+ *\n+ *   Unless required by applicable law or agreed to in writing, software\n+ *   distributed under the License is distributed on an \"AS IS\" BASIS,\n+ *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n+ *   See the License for the specific language governing permissions and\n+ *   limitations under the License.\n+ **/\n+\n+#include \"storage/SMAIndexSubBlock.hpp\"\n+\n+#include <algorithm>\n+#include <cstdint>\n+#include <cstring>\n+#include <iterator>\n+#include <utility>\n+#include <exception>\n+\n+#include \"catalog/CatalogAttribute.hpp\"\n+#include \"catalog/CatalogRelationSchema.hpp\"\n+#include \"compression/CompressionDictionary.hpp\"\n+#include \"expressions/predicate/ComparisonPredicate.hpp\"\n+#include \"expressions/predicate/Predicate.hpp\"\n+#include \"expressions/predicate/PredicateCost.hpp\"\n+#include \"expressions/scalar/Scalar.hpp\"\n+#include \"expressions/scalar/ScalarAttribute.hpp\"\n+#include \"storage/CompressedTupleStorageSubBlock.hpp\"\n+#include \"storage/StorageBlockLayout.pb.h\"\n+#include \"storage/StorageConstants.hpp\"\n+#include \"storage/StorageErrors.hpp\"\n+#include \"storage/SubBlockTypeRegistry.hpp\"\n+#include \"storage/TupleIdSequence.hpp\"\n+#include \"storage/TupleStorageSubBlock.hpp\"\n+#include \"types/Type.hpp\"\n+#include \"types/TypeFactory.hpp\"\n+#include \"types/TypeID.hpp\"\n+#include \"types/TypedValue.hpp\"\n+#include \"types/operations/binary_operations/BinaryOperation.hpp\"\n+#include \"types/operations/binary_operations/BinaryOperationFactory.hpp\"\n+#include \"types/operations/binary_operations/BinaryOperationID.hpp\"\n+#include \"types/operations/comparisons/Comparison.hpp\"\n+#include \"types/operations/comparisons/ComparisonFactory.hpp\"\n+#include \"types/operations/comparisons/ComparisonID.hpp\"\n+#include \"types/operations/comparisons/ComparisonUtil.hpp\"\n+#include \"utility/BitVector.hpp\"\n+#include \"utility/Macros.hpp\"\n+#include \"utility/PtrVector.hpp\"\n+#include \"utility/ScopedBuffer.hpp\"\n+\n+#include \"glog/logging.h\"\n+\n+using std::memcpy;\n+using std::memmove;\n+using std::pair;\n+using std::size_t;\n+using std::sort;\n+using std::uint8_t;\n+using std::uint16_t;\n+using std::uint32_t;\n+using std::vector;\n+using std::exception;\n+\n+namespace quickstep {\n+\n+QUICKSTEP_REGISTER_INDEX(SMAIndexSubBlock, SMA);\n+\n+typedef sma_internal::EntryReference EntryReference;\n+typedef sma_internal::SMAPredicate SMAPredicate;\n+typedef sma_internal::SMAHeader SMAHeader;\n+typedef sma_internal::SMAEntry SMAEntry;\n+typedef sma_internal::Selectivity Selectivity;\n+\n+namespace sma_internal {\n+\n+/**\n+ * @return Selectivity of an equals predicate.\n+ */\n+Selectivity getSelectivity_E(const TypedValue &literal,\n+                                    const TypedValue &min,\n+                                    const TypedValue &max,\n+                                    const UncheckedComparator *less_comparator) {\n+  if (less_comparator->compareTypedValues(literal, min) ||\n+      less_comparator->compareTypedValues(max, literal)) {\n+    return Selectivity::kNone;\n+  }\n+  return Selectivity::kSome;\n+}\n+\n+/**\n+ * @return Selectivity of a less predicate.\n+ */\n+Selectivity getSelectivity_L(const TypedValue &literal,\n+                                    const TypedValue &min,\n+                                    const TypedValue &max,\n+                                    const UncheckedComparator *less_comparator,\n+                                    const UncheckedComparator *equals_comparator) {\n+  if (less_comparator->compareTypedValues(max, literal)) {\n+    return Selectivity::kAll;\n+  } else if (less_comparator->compareTypedValues(literal, min) ||\n+             equals_comparator->compareTypedValues(literal, min)) {\n+    return Selectivity::kNone;\n+  }\n+  return Selectivity::kSome;\n+}\n+\n+/**\n+ * @return Selectivity of a less equals predicate.\n+ */\n+Selectivity getSelectivity_LE(const TypedValue &literal,\n+                                     const TypedValue &min,\n+                                     const TypedValue &max,\n+                                     const UncheckedComparator *less_comparator,\n+                                     const UncheckedComparator *equals_comparator) {\n+  if (less_comparator->compareTypedValues(max, literal) ||\n+      equals_comparator->compareTypedValues(max, literal)) {\n+    return Selectivity::kAll;\n+  } else if (less_comparator->compareTypedValues(literal, min)) {\n+    return Selectivity::kNone;\n+  }\n+  return Selectivity::kSome;\n+}\n+\n+/**\n+ * @return Selectivity of an greater predicate.\n+ */\n+Selectivity getSelectivity_G(const TypedValue &literal,\n+                                    const TypedValue &min,\n+                                    const TypedValue &max,\n+                                    const UncheckedComparator *less_comparator,\n+                                    const UncheckedComparator *equals_comparator) {\n+  if (less_comparator->compareTypedValues(literal, min)) {\n+    return Selectivity::kAll;\n+  } else if (less_comparator->compareTypedValues(max, literal) ||\n+             equals_comparator->compareTypedValues(max, literal)) {\n+    return Selectivity::kNone;\n+  }\n+  return Selectivity::kSome;\n+}\n+\n+/**\n+ * @return Selectivity of a greater or equals predicate.\n+ */\n+Selectivity getSelectivity_GE(const TypedValue &literal,\n+                                     const TypedValue &min,\n+                                     const TypedValue &max,\n+                                     const UncheckedComparator *less_comparator,\n+                                     const UncheckedComparator *equals_comparator) {\n+  if (less_comparator->compareTypedValues(literal, min) ||\n+      equals_comparator->compareTypedValues(literal, min)) {\n+    return Selectivity::kAll;\n+  } else if (less_comparator->compareTypedValues(max, literal)) {\n+    return Selectivity::kNone;\n+  }\n+  return Selectivity::kSome;\n+}\n+\n+Selectivity getSelectivity(const TypedValue &literal,\n+                           const ComparisonID comparison,\n+                           const TypedValue &min,\n+                           const TypedValue &max,\n+                           const UncheckedComparator *less_comparator,\n+                           const UncheckedComparator *equals_comparator) {\n+  switch (comparison) {\n+    case ComparisonID::kEqual:\n+      return getSelectivity_E(literal, min, max, less_comparator);\n+    case ComparisonID::kLess:\n+      return getSelectivity_L(literal, min, max, less_comparator, equals_comparator);\n+    case ComparisonID::kLessOrEqual:\n+      return getSelectivity_LE(literal, min, max, less_comparator, equals_comparator);\n+    case ComparisonID::kGreater:\n+      return getSelectivity_G(literal, min, max, less_comparator, equals_comparator);\n+    case ComparisonID::kGreaterOrEqual:\n+      return getSelectivity_GE(literal, min, max, less_comparator, equals_comparator);\n+    default:\n+      return Selectivity::kUnknown;\n+  }\n+}\n+\n+SMAPredicate* SMAPredicate::ExtractSMAPredicate(const ComparisonPredicate &predicate) {\n+  if (predicate.getLeftOperand().hasStaticValue()) {\n+    DLOG_IF(FATAL, predicate.getRightOperand().getDataSource() != Scalar::kAttribute);\n+    return new SMAPredicate(\n+         static_cast<const ScalarAttribute&>(predicate.getRightOperand()).getAttribute().getID(),\n+         flipComparisonID(predicate.getComparison().getComparisonID()),\n+         predicate.getLeftOperand().getStaticValue().makeReferenceToThis());\n+  } else {\n+    DLOG_IF(FATAL, predicate.getLeftOperand().getDataSource() != Scalar::kAttribute);\n+    return new SMAPredicate(\n+        static_cast<const ScalarAttribute&>(predicate.getLeftOperand()).getAttribute().getID(),\n+        predicate.getComparison().getComparisonID(),\n+        predicate.getRightOperand().getStaticValue().makeReferenceToThis());\n+  }\n+}\n+\n+/**\n+ * @brief Summation will promote lower precision types to higher precision types.\n+ *\n+ * @param type The type id of the type we wish to sum over.\n+ * @return The higher precision sum typeid. Returns kNullType to indicate that the\n+ *         given type cannot be summed (in lieu of a better sigil).\n+ */\n+TypeID getTypeForSum(TypeID type) {\n+  switch (type) {\n+    case kInt:\n+    case kLong:\n+      return kLong;\n+    case kFloat:\n+    case kDouble:\n+      return kDouble;\n+    default:\n+      return kNullType;\n+  }\n+}\n+\n+/**\n+ * @param type A type id.\n+ * @return True if the type can be summed.\n+ */\n+bool canSum(TypeID type) {\n+  return getTypeForSum(type) != kNullType;\n+}\n+\n+/**\n+ * @brief Sets the given entry's sum to zero using the correct promoted type\n+ *        of the sum. Does nothing if the entry's type cannot be summed.\n+ * @note We ignore clearing any old data held in the previous sum because Double\n+ *       and Long types are always represented inline.\n+ *       \n+ * @param entry A pointer to the entry to modify.\n+ */\n+void initializeTypedValueForSum(SMAEntry *entry) {\n+  TypeID sum_type = getTypeForSum(entry->type_id);\n+  if (sum_type == kLong) {\n+    new (&entry->sum_aggregate) TypedValue(static_cast<std::int64_t>(0));\n+  } else if (sum_type == kDouble) {\n+    new (&entry->sum_aggregate) TypedValue(static_cast<double>(0.0));\n+  }\n+}\n+\n+/**\n+ * @brief Correctly zeroes the SMA entry for each possible type.\n+ *\n+ * @param entry The entry for which the min/max references will be zeroed out.\n+ */\n+void initializeTypedValueForMinMax(SMAEntry *entry) {\n+  TypedValue *min = &(entry->min_entry_ref.value);\n+  TypedValue *max = &(entry->max_entry_ref.value);\n+  switch (entry->type_id) {\n+    case kInt: {\n+      new (min) TypedValue(static_cast<int>(0));\n+      new (max) TypedValue(static_cast<int>(0));\n+      return;\n+    }\n+    case kLong: {\n+      new (min) TypedValue(static_cast<std::int64_t>(0));\n+      new (min) TypedValue(static_cast<std::int64_t>(0));\n+      return;\n+    }\n+    case kFloat: {\n+      new (min) TypedValue(static_cast<float>(0));\n+      new (max) TypedValue(static_cast<float>(0));\n+    }\n+    case kDouble: {\n+      new (min) TypedValue(static_cast<double>(0.0));\n+      new (max) TypedValue(static_cast<double>(0.0));\n+      return;\n+    }\n+    case kDatetimeInterval: {\n+      DatetimeIntervalLit zero;\n+      zero.interval_ticks = 0;\n+      new (min) TypedValue(zero);\n+      new (max) TypedValue(zero);\n+      return;\n+    }\n+    case kYearMonthInterval: {\n+      YearMonthIntervalLit zero;\n+      zero.months = 0;\n+      new (min) TypedValue(zero);\n+      new (max) TypedValue(zero);\n+      return;\n+    }\n+    default: {\n+      CHECK(false)\n+          << \"SMA Index was created on an unindexable type: \"\n+          << entry->type_id;\n+    }\n+  }\n+}\n+\n+}  // namespace sma_internal\n+\n+\n+SMAIndexSubBlock::SMAIndexSubBlock(const TupleStorageSubBlock &tuple_store,\n+                                   const IndexSubBlockDescription &description,\n+                                   const bool new_block,\n+                                   void *sub_block_memory,\n+                                   const std::size_t sub_block_memory_size)\n+    : IndexSubBlock(tuple_store,\n+                    description,\n+                    new_block,\n+                    sub_block_memory,\n+                    sub_block_memory_size),\n+      header_(nullptr),\n+      entries_(nullptr),\n+      total_attributes_(tuple_store.getRelation().size()),\n+      attribute_to_entry_(nullptr),\n+      indexed_attributes_(0),\n+      initialized_(false),\n+      add_operations_(new UncheckedBinaryOperator*[kNumTypeIDs]),\n+      less_comparisons_(new UncheckedComparator*[kNumTypeIDs]),\n+      equal_comparisons_(new UncheckedComparator*[kNumTypeIDs]) {\n+  CHECK(DescriptionIsValid(relation_, description_))\n+      << \"Attempted to construct an SMAIndexSubBlock from an invalid description.\";\n+\n+  indexed_attributes_ = description.ExtensionSize(SMAIndexSubBlockDescription::indexed_attribute_id);\n+\n+  CHECK((sizeof(sma_internal::SMAHeader)\n+            + (indexed_attributes_ * sizeof(SMAEntry))) <= sub_block_memory_size_)\n+      << \"Attempted to create SMAIndexSubBlock without enough space allocated.\";\n+\n+  header_ = reinterpret_cast<SMAHeader*>(sub_block_memory_);\n+  entries_ = reinterpret_cast<SMAEntry*>(header_ + 1);\n+  attribute_to_entry_ = new int[total_attributes_];\n+  // Set each attribute to invalid.\n+  for (std::size_t i = 0; i < total_attributes_; ++i) {\n+    attribute_to_entry_[i] = -1;\n+  }\n+\n+  if (new_block) {\n+    header_->index_consistent = false;\n+  }\n+\n+  // Zero the comparator arrays so we don't try to reference invalid memory later.\n+  memset(less_comparisons_, 0, sizeof(UncheckedComparator*) * kNumTypeIDs);\n+  memset(equal_comparisons_, 0, sizeof(UncheckedComparator*) * kNumTypeIDs);\n+  memset(add_operations_, 0, sizeof(UncheckedBinaryOperator*) * kNumTypeIDs);\n+\n+  // Iterate through each attribute which is being indexed.\n+  for (std::size_t indexed_attribute_num = 0;\n+       indexed_attribute_num < indexed_attributes_;\n+       ++indexed_attribute_num) {\n+    const attribute_id attribute = description_.GetExtension(\n+        SMAIndexSubBlockDescription::indexed_attribute_id,\n+        indexed_attribute_num);\n+\n+    const Type &attribute_type = tuple_store_.getRelation().getAttributeById(attribute)->getType();\n+    SMAEntry *entry = entries_ + indexed_attribute_num;\n+\n+    // Initialize the operator map.\n+    if (sma_internal::canSum(attribute_type.getTypeID())) {\n+      TypeID attr_typeid = attribute_type.getTypeID();\n+      TypeID attr_sum_typeid = sma_internal::getTypeForSum(attr_typeid);\n+      if (add_operations_[attr_typeid] == nullptr) {\n+        add_operations_[attr_typeid]\n+          = BinaryOperationFactory::GetBinaryOperation(BinaryOperationID::kAdd)\n+              .makeUncheckedBinaryOperatorForTypes(TypeFactory::GetType(attr_typeid),\n+                                                   TypeFactory::GetType(attr_sum_typeid));\n+      }\n+    }\n+\n+    // Initialize comparison map. Maps attribute type to comparison function.\n+    int attr_typeid = static_cast<int>(attribute_type.getTypeID());\n+    if (less_comparisons_[attr_typeid] == nullptr) {\n+      DCHECK(equal_comparisons_[attr_typeid] == nullptr);\n+      less_comparisons_[attr_typeid]\n+          = ComparisonFactory::GetComparison(ComparisonID::kLess)\n+              .makeUncheckedComparatorForTypes(attribute_type, attribute_type);\n+      equal_comparisons_[attr_typeid]\n+          = ComparisonFactory::GetComparison(ComparisonID::kEqual)\n+              .makeUncheckedComparatorForTypes(attribute_type, attribute_type);\n+    }\n+\n+    // Map the attribute's id to its entry's index.\n+    attribute_to_entry_[attribute] = indexed_attribute_num;\n+\n+    if (!header_->index_consistent) {\n+      resetEntry(entry, attribute, attribute_type);\n+    } else {\n+      // If the data held by min/max is out of line, we must retrieve it as we initialize.\n+      if (!TypedValue::RepresentedInline(entry->type_id)) {\n+        // First, set to 0 so that we don't try to free invalid memory on copy.\n+        // Next, copy from the tuple store. This will copy and give us ownership of out of line data.\n+        if (entry->min_entry_ref.valid) {\n+          new (&entry->min_entry_ref.value) TypedValue();\n+          entry->min_entry_ref.value = tuple_store\n+              .getAttributeValueTyped(entry->min_entry_ref.entry_ref_tuple, entry->attribute);\n+          entry->min_entry_ref.value.ensureNotReference();\n+        }\n+        if (entry->max_entry_ref.valid) {\n+          new (&entry->max_entry_ref.value) TypedValue();\n+          entry->max_entry_ref.value = tuple_store\n+              .getAttributeValueTyped(entry->max_entry_ref.entry_ref_tuple, entry->attribute);\n+          entry->max_entry_ref.value.ensureNotReference();\n+        }\n+      }\n+    }\n+  }\n+  initialized_ = true;\n+}\n+\n+SMAIndexSubBlock::~SMAIndexSubBlock() {\n+  // Any typed values which have out of line data must be cleared.\n+  freeOutOfLineData();\n+\n+  // Clear any operators which have been allocated.\n+  for (int i = 0; i < kNumTypeIDs; ++i) {\n+    if (add_operations_[i] != nullptr) {\n+      delete add_operations_[i];\n+    }\n+    if (equal_comparisons_[i] != nullptr) {\n+      delete equal_comparisons_[i];\n+    }\n+    if (less_comparisons_[i] != nullptr) {\n+      delete less_comparisons_[i];\n+    }\n+  }\n+\n+  // Delete the operator arrays.\n+  delete[] add_operations_;\n+  delete[] equal_comparisons_;\n+  delete[] less_comparisons_;\n+  delete[] attribute_to_entry_;\n+}\n+\n+void SMAIndexSubBlock::resetEntry(SMAEntry *entry,\n+                                  attribute_id attribute,\n+                                  const Type &attribute_type) {\n+  entry->attribute = attribute;\n+  entry->type_id = attribute_type.getTypeID();\n+\n+  // Clearing min/max will free any out of line data.\n+  if (entry->min_entry_ref.valid) {\n+    entry->min_entry_ref.value.clear();\n+    entry->min_entry_ref.valid = false;\n+  }\n+  if (entry->max_entry_ref.valid) {\n+    entry->max_entry_ref.value.clear();\n+    entry->max_entry_ref.valid = false;\n+  }\n+  sma_internal::initializeTypedValueForSum(entry);\n+}\n+\n+void SMAIndexSubBlock::resetEntries() {\n+  freeOutOfLineData();\n+\n+  for (std::size_t indexed_attribute_num = 0;\n+       indexed_attribute_num < indexed_attributes_;\n+       ++indexed_attribute_num) {\n+    const attribute_id attribute = description_.GetExtension(\n+        SMAIndexSubBlockDescription::indexed_attribute_id,\n+        indexed_attribute_num);\n+\n+    const Type &attribute_type = tuple_store_.getRelation().getAttributeById(attribute)->getType();\n+    resetEntry(entries_ + indexed_attribute_num, attribute, attribute_type);\n+  }\n+}\n+\n+void SMAIndexSubBlock::freeOutOfLineData() {\n+  // For each entry, clear the min and max typed values (frees out of line data).\n+  for (std::size_t indexed_attribute_num = 0;\n+       indexed_attribute_num < indexed_attributes_;\n+       ++indexed_attribute_num) {\n+    SMAEntry &entry = entries_[indexed_attribute_num];\n+    if (!TypedValue::RepresentedInline(entry.type_id)) {\n+      if (entry.min_entry_ref.valid) {\n+        entry.min_entry_ref.value.clear();\n+      }\n+      if (entry.max_entry_ref.valid) {\n+        entry.max_entry_ref.value.clear();\n+      }\n+    }\n+  }\n+}\n+\n+bool SMAIndexSubBlock::DescriptionIsValid(const CatalogRelationSchema &relation,\n+                                          const IndexSubBlockDescription &description) {\n+  if (!description.IsInitialized()) {\n+    return false;\n+  }\n+  if (description.sub_block_type() != IndexSubBlockDescription::SMA) {\n+    return false;\n+  }\n+  // Must have at least one indexed attribute.\n+  if (description.ExtensionSize(SMAIndexSubBlockDescription::indexed_attribute_id) == 0) {\n+    return false;\n+  }\n+  // Check that all key attributes exist.\n+  for (int indexed_attribute_num = 0;\n+       indexed_attribute_num < description.ExtensionSize(SMAIndexSubBlockDescription::indexed_attribute_id);\n+       ++indexed_attribute_num) {\n+    attribute_id indexed_attribute_id = description.GetExtension(\n+        SMAIndexSubBlockDescription::indexed_attribute_id, indexed_attribute_num);\n+    if (!relation.hasAttributeWithId(indexed_attribute_id)) {\n+      return false;\n+    }\n+  }\n+  return true;\n+}\n+\n+std::size_t SMAIndexSubBlock::EstimateBytesPerTuple(\n+    const CatalogRelationSchema &relation,\n+    const IndexSubBlockDescription &description) {\n+  // TODO(marc): Returning 1 almost always gives too much space. An enhancement\n+  // would be to inform the storage subblock that this index uses space w.r.t.\n+  // # of attributes being indexed, not tuples.\n+  return 1;\n+}\n+\n+bool SMAIndexSubBlock::bulkAddEntries(const TupleIdSequence &tuples) {\n+  header_->index_consistent = false;\n+  return true;  // There will always be space for the entry.\n+}\n+\n+void SMAIndexSubBlock::bulkRemoveEntries(const TupleIdSequence &tuples) {\n+  header_->index_consistent = false;\n+}\n+\n+bool SMAIndexSubBlock::addEntry(const tuple_id tuple) {\n+  header_->index_consistent = false;\n+  return true;  // There will always be space to insert the entry.\n+}\n+\n+void SMAIndexSubBlock::removeEntry(const tuple_id tuple) {\n+  header_->index_consistent = false;\n+}\n+\n+bool SMAIndexSubBlock::rebuild() {\n+  resetEntries();\n+  header_->count_aggregate = 0;\n+  if (tuple_store_.isPacked()) {\n+    for (tuple_id tid = 0; tid <= tuple_store_.getMaxTupleID(); ++tid) {\n+      addTuple(tid);\n+    }\n+  } else {\n+    for (tuple_id tid = 0; tid <= tuple_store_.getMaxTupleID(); ++tid) {\n+      if (tuple_store_.hasTupleWithID(tid)) {\n+        addTuple(tid);\n+      }\n+    }\n+  }\n+  header_->index_consistent = true;\n+  return true;\n+}\n+\n+void SMAIndexSubBlock::addTuple(tuple_id tuple) {\n+  for (std::size_t index = 0; index < indexed_attributes_; ++index) {\n+    SMAEntry *entry = entries_ + index;\n+    TypedValue tuple_value = tuple_store_.getAttributeValueTyped(tuple, entry->attribute);\n+\n+    // Ignore all nulls.\n+    if (tuple_value.isNull()) {","path":"storage/SMAIndexSubBlock.cpp","position":558,"original_position":558,"commit_id":"5a9e5c7365b0838984cd6c1c9254b19ee5f42b74","original_commit_id":"5a9e5c7365b0838984cd6c1c9254b19ee5f42b74","user":{"login":"hbdeshmukh","id":3750801,"avatar_url":"https://avatars.githubusercontent.com/u/3750801?v=3","gravatar_id":"","url":"https://api.github.com/users/hbdeshmukh","html_url":"https://github.com/hbdeshmukh","followers_url":"https://api.github.com/users/hbdeshmukh/followers","following_url":"https://api.github.com/users/hbdeshmukh/following{/other_user}","gists_url":"https://api.github.com/users/hbdeshmukh/gists{/gist_id}","starred_url":"https://api.github.com/users/hbdeshmukh/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hbdeshmukh/subscriptions","organizations_url":"https://api.github.com/users/hbdeshmukh/orgs","repos_url":"https://api.github.com/users/hbdeshmukh/repos","events_url":"https://api.github.com/users/hbdeshmukh/events{/privacy}","received_events_url":"https://api.github.com/users/hbdeshmukh/received_events","type":"User","site_admin":false},"body":"I see that you are ignoring nulls. I had asked this question somewhere else, found the answer here. ","created_at":"2016-03-03T01:32:32Z","updated_at":"2016-03-03T01:32:32Z","html_url":"https://github.com/pivotalsoftware/quickstep/pull/35#discussion_r54823932","pull_request_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/35","_links":{"self":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/comments/54823932"},"html":{"href":"https://github.com/pivotalsoftware/quickstep/pull/35#discussion_r54823932"},"pull_request":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/35"}}},"pull_request":{"url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/35","id":59419862,"html_url":"https://github.com/pivotalsoftware/quickstep/pull/35","diff_url":"https://github.com/pivotalsoftware/quickstep/pull/35.diff","patch_url":"https://github.com/pivotalsoftware/quickstep/pull/35.patch","issue_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/35","number":35,"state":"open","locked":false,"title":"SMA Index","user":{"login":"cramja","id":5708822,"avatar_url":"https://avatars.githubusercontent.com/u/5708822?v=3","gravatar_id":"","url":"https://api.github.com/users/cramja","html_url":"https://github.com/cramja","followers_url":"https://api.github.com/users/cramja/followers","following_url":"https://api.github.com/users/cramja/following{/other_user}","gists_url":"https://api.github.com/users/cramja/gists{/gist_id}","starred_url":"https://api.github.com/users/cramja/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cramja/subscriptions","organizations_url":"https://api.github.com/users/cramja/orgs","repos_url":"https://api.github.com/users/cramja/repos","events_url":"https://api.github.com/users/cramja/events{/privacy}","received_events_url":"https://api.github.com/users/cramja/received_events","type":"User","site_admin":false},"body":"## SMAIndexSubBlock and Tests\r\nAs we discussed in the code review on Friday, this is a new index which calculates and stores MIN/MAX/COUNT/SUM. It is primarily used for avoiding scans of blocks. \r\n\r\n**Big Picture Features**\r\n* Works with all attribute types.\r\n* Works with all storage block types.\r\n* Unit tests are comprehensive and based off of unit tests for CSBTree.\r\n\r\n**TODOs**\r\nIn this PR I have added the sub block and unit tests for the sub block. It is a simple matter to tie in the index to the existing code inside of TupleStorageSubBlock and I have not done so because the changes in this PR are entirely insular: they do not change outside classes. \r\n\r\nAdditionally, the EstimateBytesPerTuple function needs to be rethought because the SMA index scales in size according to how many attributes are indexed and not with how many tuples there are in the subblock.\r\n\r\n**Notes**\r\nTo test the possible memory leak issue we discussed in the meeting, I ran the unit tests through valgrind on @pateljm 's suggestion. This revealed memory leaks, but only in the context of the unit tests which I have since resolved and valgrind shows no memory leaks: \r\n\r\n```\r\n==2886== LEAK SUMMARY:\r\n==2886==    definitely lost: 0 bytes in 0 blocks\r\n==2886==    indirectly lost: 0 bytes in 0 blocks\r\n==2886==      possibly lost: 5,053 bytes in 80 blocks\r\n==2886==    still reachable: 84,280 bytes in 183 blocks\r\n==2886==         suppressed: 0 bytes in 0 blocks\r\n```\r\n\r\nI assigned this PR to @hbdeshmukh because we have talked about this PR together in the past and we share the same office so that will likely make resolving issues easier.","created_at":"2016-02-15T22:17:27Z","updated_at":"2016-03-03T01:32:32Z","closed_at":null,"merged_at":null,"merge_commit_sha":"e1a36ba6ffd72b549ad8e3052faff7438a7b552b","assignee":{"login":"hbdeshmukh","id":3750801,"avatar_url":"https://avatars.githubusercontent.com/u/3750801?v=3","gravatar_id":"","url":"https://api.github.com/users/hbdeshmukh","html_url":"https://github.com/hbdeshmukh","followers_url":"https://api.github.com/users/hbdeshmukh/followers","following_url":"https://api.github.com/users/hbdeshmukh/following{/other_user}","gists_url":"https://api.github.com/users/hbdeshmukh/gists{/gist_id}","starred_url":"https://api.github.com/users/hbdeshmukh/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hbdeshmukh/subscriptions","organizations_url":"https://api.github.com/users/hbdeshmukh/orgs","repos_url":"https://api.github.com/users/hbdeshmukh/repos","events_url":"https://api.github.com/users/hbdeshmukh/events{/privacy}","received_events_url":"https://api.github.com/users/hbdeshmukh/received_events","type":"User","site_admin":false},"milestone":null,"commits_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/35/commits","review_comments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/35/comments","review_comment_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/comments{/number}","comments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/35/comments","statuses_url":"https://api.github.com/repos/pivotalsoftware/quickstep/statuses/5a9e5c7365b0838984cd6c1c9254b19ee5f42b74","head":{"label":"pivotalsoftware:sma-index-staging","ref":"sma-index-staging","sha":"5a9e5c7365b0838984cd6c1c9254b19ee5f42b74","user":{"login":"pivotalsoftware","id":4247270,"avatar_url":"https://avatars.githubusercontent.com/u/4247270?v=3","gravatar_id":"","url":"https://api.github.com/users/pivotalsoftware","html_url":"https://github.com/pivotalsoftware","followers_url":"https://api.github.com/users/pivotalsoftware/followers","following_url":"https://api.github.com/users/pivotalsoftware/following{/other_user}","gists_url":"https://api.github.com/users/pivotalsoftware/gists{/gist_id}","starred_url":"https://api.github.com/users/pivotalsoftware/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pivotalsoftware/subscriptions","organizations_url":"https://api.github.com/users/pivotalsoftware/orgs","repos_url":"https://api.github.com/users/pivotalsoftware/repos","events_url":"https://api.github.com/users/pivotalsoftware/events{/privacy}","received_events_url":"https://api.github.com/users/pivotalsoftware/received_events","type":"Organization","site_admin":false},"repo":{"id":45578105,"name":"quickstep","full_name":"pivotalsoftware/quickstep","owner":{"login":"pivotalsoftware","id":4247270,"avatar_url":"https://avatars.githubusercontent.com/u/4247270?v=3","gravatar_id":"","url":"https://api.github.com/users/pivotalsoftware","html_url":"https://github.com/pivotalsoftware","followers_url":"https://api.github.com/users/pivotalsoftware/followers","following_url":"https://api.github.com/users/pivotalsoftware/following{/other_user}","gists_url":"https://api.github.com/users/pivotalsoftware/gists{/gist_id}","starred_url":"https://api.github.com/users/pivotalsoftware/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pivotalsoftware/subscriptions","organizations_url":"https://api.github.com/users/pivotalsoftware/orgs","repos_url":"https://api.github.com/users/pivotalsoftware/repos","events_url":"https://api.github.com/users/pivotalsoftware/events{/privacy}","received_events_url":"https://api.github.com/users/pivotalsoftware/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/pivotalsoftware/quickstep","description":"Quickstep Project","fork":false,"url":"https://api.github.com/repos/pivotalsoftware/quickstep","forks_url":"https://api.github.com/repos/pivotalsoftware/quickstep/forks","keys_url":"https://api.github.com/repos/pivotalsoftware/quickstep/keys{/key_id}","collaborators_url":"https://api.github.com/repos/pivotalsoftware/quickstep/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/pivotalsoftware/quickstep/teams","hooks_url":"https://api.github.com/repos/pivotalsoftware/quickstep/hooks","issue_events_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/events{/number}","events_url":"https://api.github.com/repos/pivotalsoftware/quickstep/events","assignees_url":"https://api.github.com/repos/pivotalsoftware/quickstep/assignees{/user}","branches_url":"https://api.github.com/repos/pivotalsoftware/quickstep/branches{/branch}","tags_url":"https://api.github.com/repos/pivotalsoftware/quickstep/tags","blobs_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/refs{/sha}","trees_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/trees{/sha}","statuses_url":"https://api.github.com/repos/pivotalsoftware/quickstep/statuses/{sha}","languages_url":"https://api.github.com/repos/pivotalsoftware/quickstep/languages","stargazers_url":"https://api.github.com/repos/pivotalsoftware/quickstep/stargazers","contributors_url":"https://api.github.com/repos/pivotalsoftware/quickstep/contributors","subscribers_url":"https://api.github.com/repos/pivotalsoftware/quickstep/subscribers","subscription_url":"https://api.github.com/repos/pivotalsoftware/quickstep/subscription","commits_url":"https://api.github.com/repos/pivotalsoftware/quickstep/commits{/sha}","git_commits_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/commits{/sha}","comments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/comments{/number}","issue_comment_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/comments{/number}","contents_url":"https://api.github.com/repos/pivotalsoftware/quickstep/contents/{+path}","compare_url":"https://api.github.com/repos/pivotalsoftware/quickstep/compare/{base}...{head}","merges_url":"https://api.github.com/repos/pivotalsoftware/quickstep/merges","archive_url":"https://api.github.com/repos/pivotalsoftware/quickstep/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/pivotalsoftware/quickstep/downloads","issues_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues{/number}","pulls_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls{/number}","milestones_url":"https://api.github.com/repos/pivotalsoftware/quickstep/milestones{/number}","notifications_url":"https://api.github.com/repos/pivotalsoftware/quickstep/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/pivotalsoftware/quickstep/labels{/name}","releases_url":"https://api.github.com/repos/pivotalsoftware/quickstep/releases{/id}","deployments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/deployments","created_at":"2015-11-05T01:06:50Z","updated_at":"2016-02-05T22:07:46Z","pushed_at":"2016-03-02T23:57:36Z","git_url":"git://github.com/pivotalsoftware/quickstep.git","ssh_url":"git@github.com:pivotalsoftware/quickstep.git","clone_url":"https://github.com/pivotalsoftware/quickstep.git","svn_url":"https://github.com/pivotalsoftware/quickstep","homepage":null,"size":6274,"stargazers_count":5,"watchers_count":5,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":6,"mirror_url":null,"open_issues_count":11,"forks":6,"open_issues":11,"watchers":5,"default_branch":"master"}},"base":{"label":"pivotalsoftware:master","ref":"master","sha":"b846e989d7e34bf2e6dfb1b7bdb73bf9760145bd","user":{"login":"pivotalsoftware","id":4247270,"avatar_url":"https://avatars.githubusercontent.com/u/4247270?v=3","gravatar_id":"","url":"https://api.github.com/users/pivotalsoftware","html_url":"https://github.com/pivotalsoftware","followers_url":"https://api.github.com/users/pivotalsoftware/followers","following_url":"https://api.github.com/users/pivotalsoftware/following{/other_user}","gists_url":"https://api.github.com/users/pivotalsoftware/gists{/gist_id}","starred_url":"https://api.github.com/users/pivotalsoftware/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pivotalsoftware/subscriptions","organizations_url":"https://api.github.com/users/pivotalsoftware/orgs","repos_url":"https://api.github.com/users/pivotalsoftware/repos","events_url":"https://api.github.com/users/pivotalsoftware/events{/privacy}","received_events_url":"https://api.github.com/users/pivotalsoftware/received_events","type":"Organization","site_admin":false},"repo":{"id":45578105,"name":"quickstep","full_name":"pivotalsoftware/quickstep","owner":{"login":"pivotalsoftware","id":4247270,"avatar_url":"https://avatars.githubusercontent.com/u/4247270?v=3","gravatar_id":"","url":"https://api.github.com/users/pivotalsoftware","html_url":"https://github.com/pivotalsoftware","followers_url":"https://api.github.com/users/pivotalsoftware/followers","following_url":"https://api.github.com/users/pivotalsoftware/following{/other_user}","gists_url":"https://api.github.com/users/pivotalsoftware/gists{/gist_id}","starred_url":"https://api.github.com/users/pivotalsoftware/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pivotalsoftware/subscriptions","organizations_url":"https://api.github.com/users/pivotalsoftware/orgs","repos_url":"https://api.github.com/users/pivotalsoftware/repos","events_url":"https://api.github.com/users/pivotalsoftware/events{/privacy}","received_events_url":"https://api.github.com/users/pivotalsoftware/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/pivotalsoftware/quickstep","description":"Quickstep Project","fork":false,"url":"https://api.github.com/repos/pivotalsoftware/quickstep","forks_url":"https://api.github.com/repos/pivotalsoftware/quickstep/forks","keys_url":"https://api.github.com/repos/pivotalsoftware/quickstep/keys{/key_id}","collaborators_url":"https://api.github.com/repos/pivotalsoftware/quickstep/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/pivotalsoftware/quickstep/teams","hooks_url":"https://api.github.com/repos/pivotalsoftware/quickstep/hooks","issue_events_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/events{/number}","events_url":"https://api.github.com/repos/pivotalsoftware/quickstep/events","assignees_url":"https://api.github.com/repos/pivotalsoftware/quickstep/assignees{/user}","branches_url":"https://api.github.com/repos/pivotalsoftware/quickstep/branches{/branch}","tags_url":"https://api.github.com/repos/pivotalsoftware/quickstep/tags","blobs_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/refs{/sha}","trees_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/trees{/sha}","statuses_url":"https://api.github.com/repos/pivotalsoftware/quickstep/statuses/{sha}","languages_url":"https://api.github.com/repos/pivotalsoftware/quickstep/languages","stargazers_url":"https://api.github.com/repos/pivotalsoftware/quickstep/stargazers","contributors_url":"https://api.github.com/repos/pivotalsoftware/quickstep/contributors","subscribers_url":"https://api.github.com/repos/pivotalsoftware/quickstep/subscribers","subscription_url":"https://api.github.com/repos/pivotalsoftware/quickstep/subscription","commits_url":"https://api.github.com/repos/pivotalsoftware/quickstep/commits{/sha}","git_commits_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/commits{/sha}","comments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/comments{/number}","issue_comment_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/comments{/number}","contents_url":"https://api.github.com/repos/pivotalsoftware/quickstep/contents/{+path}","compare_url":"https://api.github.com/repos/pivotalsoftware/quickstep/compare/{base}...{head}","merges_url":"https://api.github.com/repos/pivotalsoftware/quickstep/merges","archive_url":"https://api.github.com/repos/pivotalsoftware/quickstep/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/pivotalsoftware/quickstep/downloads","issues_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues{/number}","pulls_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls{/number}","milestones_url":"https://api.github.com/repos/pivotalsoftware/quickstep/milestones{/number}","notifications_url":"https://api.github.com/repos/pivotalsoftware/quickstep/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/pivotalsoftware/quickstep/labels{/name}","releases_url":"https://api.github.com/repos/pivotalsoftware/quickstep/releases{/id}","deployments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/deployments","created_at":"2015-11-05T01:06:50Z","updated_at":"2016-02-05T22:07:46Z","pushed_at":"2016-03-02T23:57:36Z","git_url":"git://github.com/pivotalsoftware/quickstep.git","ssh_url":"git@github.com:pivotalsoftware/quickstep.git","clone_url":"https://github.com/pivotalsoftware/quickstep.git","svn_url":"https://github.com/pivotalsoftware/quickstep","homepage":null,"size":6274,"stargazers_count":5,"watchers_count":5,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":6,"mirror_url":null,"open_issues_count":11,"forks":6,"open_issues":11,"watchers":5,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/35"},"html":{"href":"https://github.com/pivotalsoftware/quickstep/pull/35"},"issue":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/35"},"comments":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/35/comments"},"review_comments":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/35/comments"},"review_comment":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/35/commits"},"statuses":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/statuses/5a9e5c7365b0838984cd6c1c9254b19ee5f42b74"}}}}