| /** |
| * 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 "storage/CompressedStoreUtil.hpp" |
| |
| #include <cmath> |
| #include <cstddef> |
| #include <cstdint> |
| #include <limits> |
| #include <type_traits> |
| #include <utility> |
| |
| #include "catalog/CatalogRelationSchema.hpp" |
| #include "catalog/CatalogTypedefs.hpp" |
| #include "compression/CompressionDictionary.hpp" |
| #include "expressions/predicate/ComparisonPredicate.hpp" |
| #include "expressions/predicate/Predicate.hpp" |
| #include "expressions/scalar/Scalar.hpp" |
| #include "expressions/scalar/ScalarAttribute.hpp" |
| #include "types/DoubleType.hpp" |
| #include "types/FloatType.hpp" |
| #include "types/IntType.hpp" |
| #include "types/LongType.hpp" |
| #include "types/Type.hpp" |
| #include "types/TypedValue.hpp" |
| #include "types/TypeID.hpp" |
| #include "types/operations/comparisons/Comparison.hpp" |
| #include "types/operations/comparisons/ComparisonID.hpp" |
| #include "utility/Macros.hpp" |
| |
| #include "glog/logging.h" |
| |
| namespace quickstep { |
| |
| PredicateTransformResult CompressedAttributePredicateTransformer::TransformPredicateOnCompressedAttribute( |
| const CatalogRelationSchema &relation, |
| const ComparisonPredicate &predicate, |
| const CompressionDictionary *dictionary, |
| const std::int64_t maximum_truncated_value) { |
| // The predicate must be a comparison of a compressed attribute with |
| // a literal. |
| DCHECK(predicate.isAttributeLiteralComparisonPredicate()); |
| |
| const CatalogAttribute *comparison_attribute = nullptr; |
| bool left_literal = false; |
| if (predicate.getLeftOperand().hasStaticValue()) { |
| DCHECK(predicate.getRightOperand().getDataSource() == Scalar::kAttribute); |
| comparison_attribute |
| = &(static_cast<const ScalarAttribute&>(predicate.getRightOperand()).getAttribute()); |
| left_literal = true; |
| } else { |
| DCHECK(predicate.getLeftOperand().getDataSource() == Scalar::kAttribute); |
| comparison_attribute |
| = &(static_cast<const ScalarAttribute&>(predicate.getLeftOperand()).getAttribute()); |
| left_literal = false; |
| } |
| |
| DCHECK_EQ(relation.getID(), comparison_attribute->getParent().getID()); |
| TypedValue comparison_literal; |
| const Type *comparison_literal_type; |
| if (left_literal) { |
| comparison_literal = predicate.getLeftOperand().getStaticValue().makeReferenceToThis(); |
| comparison_literal_type = &predicate.getLeftOperand().getType(); |
| } else { |
| comparison_literal = predicate.getRightOperand().getStaticValue().makeReferenceToThis(); |
| comparison_literal_type = &predicate.getRightOperand().getType(); |
| } |
| |
| if (comparison_literal.isNull()) { |
| // Comparisons with null are always false. |
| return PredicateTransformResult(PredicateTransformResultType::kNone); |
| } |
| |
| if (predicate.getComparison().getComparisonID() == ComparisonID::kEqual) { |
| return TransformEqualPredicateOnCompressedAttribute(comparison_literal, |
| *comparison_literal_type, |
| dictionary, |
| maximum_truncated_value); |
| } else if (predicate.getComparison().getComparisonID() == ComparisonID::kNotEqual) { |
| return TransformNotEqualPredicateOnCompressedAttribute(comparison_literal, |
| *comparison_literal_type, |
| dictionary, |
| maximum_truncated_value); |
| } else { |
| if (left_literal) { |
| switch (predicate.getComparison().getComparisonID()) { |
| case ComparisonID::kLess: |
| return TransformOtherComparisonPredicateOnCompressedAttribute(ComparisonID::kGreater, |
| comparison_literal, |
| *comparison_literal_type, |
| dictionary, |
| maximum_truncated_value); |
| case ComparisonID::kLessOrEqual: |
| return TransformOtherComparisonPredicateOnCompressedAttribute(ComparisonID::kGreaterOrEqual, |
| comparison_literal, |
| *comparison_literal_type, |
| dictionary, |
| maximum_truncated_value); |
| case ComparisonID::kGreater: |
| return TransformOtherComparisonPredicateOnCompressedAttribute(ComparisonID::kLess, |
| comparison_literal, |
| *comparison_literal_type, |
| dictionary, |
| maximum_truncated_value); |
| case ComparisonID::kGreaterOrEqual: |
| return TransformOtherComparisonPredicateOnCompressedAttribute(ComparisonID::kLessOrEqual, |
| comparison_literal, |
| *comparison_literal_type, |
| dictionary, |
| maximum_truncated_value); |
| default: |
| FATAL_ERROR("Unexpected ComparisonID in " |
| "CompressedAttributePredicateTransformer::getMatchesForPredicate()"); |
| } |
| } else { |
| return TransformOtherComparisonPredicateOnCompressedAttribute( |
| predicate.getComparison().getComparisonID(), |
| comparison_literal, |
| *comparison_literal_type, |
| dictionary, |
| maximum_truncated_value); |
| } |
| } |
| } |
| |
| namespace { |
| |
| // Helper class for figuring out information about comparisons with truncated |
| // values. Has different partial specializations for integer types and |
| // floating-point types. |
| template <typename NumericLiteralT, typename Enable = void> |
| class TruncationHelper { |
| }; |
| |
| // Partial specialization for integer types. |
| template <typename NumericLiteralT> |
| class TruncationHelper< |
| NumericLiteralT, |
| typename std::enable_if<std::is_integral<NumericLiteralT>::value>::type> { |
| public: |
| // Whether an int64_t represents 'right_value' exactly. For Int and Long, |
| // this is always true. |
| static bool LongIsExact(const TypedValue &right_literal) { |
| return true; |
| } |
| |
| // Get 'right_literal' truncated to a code. |
| static std::uint32_t GetAsCode(const TypedValue &right_literal) { |
| return right_literal.getLiteral<NumericLiteralT>(); |
| } |
| |
| // Get the effective literal value to use in place of 'right_literal' when |
| // evaluating the comparison specified by 'comp'. Since LongIsExact() is |
| // always true for integer types, no adjustment is needed. |
| static std::int64_t GetEffectiveLiteralForComparison(const ComparisonID comp, |
| const TypedValue &right_literal) { |
| return right_literal.getLiteral<NumericLiteralT>(); |
| } |
| |
| // Determine whether 'value' is in the range of truncated codes between 0 and |
| // 'maximum_truncated_value'. |
| static bool ValueInRange(const TypedValue &value, |
| const std::int64_t maximum_truncated_value) { |
| const std::int64_t value_as_int64 = value.getLiteral<NumericLiteralT>(); |
| return (value_as_int64 >= 0) && (value_as_int64 <= maximum_truncated_value); |
| } |
| }; |
| |
| // Partial specialization for floating-point types. |
| template <typename NumericLiteralT> |
| class TruncationHelper< |
| NumericLiteralT, |
| typename std::enable_if<std::is_floating_point<NumericLiteralT>::value>::type> { |
| public: |
| // Whether an int64_t represents 'right_value' exactly. For floating-point |
| // types, 'right_value' may have a fractional part or a large exponent that |
| // makes it out-of-range. |
| static bool LongIsExact(const TypedValue &right_literal) { |
| const double value_as_double = right_literal.getLiteral<NumericLiteralT>(); |
| return value_as_double == static_cast<std::int64_t>(value_as_double); |
| } |
| |
| // Get 'right_literal' truncated to a code. |
| static std::uint32_t GetAsCode(const TypedValue &right_literal) { |
| return right_literal.getLiteral<NumericLiteralT>(); |
| } |
| |
| // Get the effective literal value to use in place of 'right_literal' when |
| // evaluating the comparison specified by 'comp'. If LongIsExact() is true, |
| // then no adjustment is needed. Otherwise, the value is rounded up or down |
| // as needed to make the comparison evaluate correctly. |
| static std::int64_t GetEffectiveLiteralForComparison(const ComparisonID comp, |
| const TypedValue &right_literal) { |
| const double value_as_double = right_literal.getLiteral<NumericLiteralT>(); |
| const std::int64_t value_as_int64 = value_as_double; |
| if (value_as_double == value_as_int64) { |
| // The value has no fractional part, so no adjustment is needed. |
| return value_as_int64; |
| } |
| |
| switch (comp) { |
| case ComparisonID::kLess: |
| case ComparisonID::kGreaterOrEqual: |
| return std::ceil(value_as_double); |
| case ComparisonID::kLessOrEqual: |
| case ComparisonID::kGreater: |
| return std::floor(value_as_double); |
| default: { |
| LOG(FATAL) << "Unexpected ComparisonID (not <, <=, >, or >=)"; |
| } |
| } |
| } |
| |
| // Determine whether 'value' is in the range of truncated codes between 0 and |
| // 'maximum_truncated_value'. |
| static bool ValueInRange(const TypedValue &value, |
| const std::int64_t maximum_truncated_value) { |
| const NumericLiteralT value_literal = value.getLiteral<NumericLiteralT>(); |
| return (value_literal >= 0) && (value_literal <= maximum_truncated_value); |
| } |
| }; |
| |
| } // namespace |
| |
| std::int64_t CompressedAttributePredicateTransformer::GetEffectiveLiteralValueForComparisonWithTruncatedAttribute( |
| const ComparisonID comp, |
| const TypedValue &right_literal, |
| const Type &right_literal_type) { |
| switch (right_literal_type.getTypeID()) { |
| case kInt: |
| return TruncationHelper<IntType::cpptype>::GetEffectiveLiteralForComparison( |
| comp, |
| right_literal); |
| case kLong: |
| return TruncationHelper<LongType::cpptype>::GetEffectiveLiteralForComparison( |
| comp, |
| right_literal); |
| case kFloat: |
| return TruncationHelper<FloatType::cpptype>::GetEffectiveLiteralForComparison( |
| comp, |
| right_literal); |
| case kDouble: |
| return TruncationHelper<DoubleType::cpptype>::GetEffectiveLiteralForComparison( |
| comp, |
| right_literal); |
| default: { |
| LOG(FATAL) << "Type not recognized as numeric: " << right_literal_type.getName(); |
| } |
| } |
| } |
| |
| bool CompressedAttributePredicateTransformer::CompressedComparisonIsAlwaysTrueForTruncatedAttribute( |
| const ComparisonID comp, |
| const TypedValue &right_literal, |
| const Type &right_literal_type, |
| const std::int64_t maximum_truncated_value) { |
| // First, check equality and inequality. |
| switch (comp) { |
| case ComparisonID::kEqual: |
| return false; |
| case ComparisonID::kNotEqual: |
| // When comparing against truncated codes, not-equal is always true if |
| // 'right_literal' has a fractional part, or if it is less than zero or |
| // greater than the largest truncated value. |
| switch (right_literal_type.getTypeID()) { |
| case kInt: { |
| return (!TruncationHelper<IntType::cpptype>::LongIsExact(right_literal)) |
| || (!TruncationHelper<IntType::cpptype>::ValueInRange(right_literal, |
| maximum_truncated_value)); |
| } |
| case kLong: { |
| return (!TruncationHelper<LongType::cpptype>::LongIsExact(right_literal)) |
| || (!TruncationHelper<LongType::cpptype>::ValueInRange(right_literal, |
| maximum_truncated_value)); |
| } |
| case kFloat: { |
| return (!TruncationHelper<FloatType::cpptype>::LongIsExact(right_literal)) |
| || (!TruncationHelper<FloatType::cpptype>::ValueInRange(right_literal, |
| maximum_truncated_value)); |
| } |
| case kDouble: { |
| return (!TruncationHelper<DoubleType::cpptype>::LongIsExact(right_literal)) |
| || (!TruncationHelper<DoubleType::cpptype>::ValueInRange(right_literal, |
| maximum_truncated_value)); |
| } |
| default: { |
| LOG(FATAL) << "Type not recognized as numeric: " << right_literal_type.getName(); |
| } |
| } |
| default: |
| break; |
| } |
| |
| std::int64_t effective_literal |
| = GetEffectiveLiteralValueForComparisonWithTruncatedAttribute(comp, |
| right_literal, |
| right_literal_type); |
| |
| switch (comp) { |
| case ComparisonID::kLess: |
| if (effective_literal > maximum_truncated_value) { |
| return true; |
| } else { |
| return false; |
| } |
| case ComparisonID::kLessOrEqual: |
| if (effective_literal >= maximum_truncated_value) { |
| return true; |
| } else { |
| return false; |
| } |
| case ComparisonID::kGreater: |
| if (effective_literal < 0) { |
| return true; |
| } else { |
| return false; |
| } |
| case ComparisonID::kGreaterOrEqual: |
| if (effective_literal <= 0) { |
| return true; |
| } else { |
| return false; |
| } |
| default: |
| FATAL_ERROR("Unexpected ComparisonID in CompressedAttributePredicateTransformer::" |
| "CompressedComparisonIsAlwaysTrueForTruncatedAttribute()"); |
| } |
| } |
| |
| bool CompressedAttributePredicateTransformer::CompressedComparisonIsAlwaysFalseForTruncatedAttribute( |
| const ComparisonID comp, |
| const TypedValue &right_literal, |
| const Type &right_literal_type, |
| const std::int64_t maximum_truncated_value) { |
| // First, check equality and inequality. |
| switch (comp) { |
| case ComparisonID::kEqual: |
| // When comparing against truncated codes, equal is always false if |
| // 'right_literal' has a fractional part, or if it is less than zero or |
| // greater than the largest truncated value. |
| switch (right_literal_type.getTypeID()) { |
| case kInt: { |
| return (!TruncationHelper<IntType::cpptype>::LongIsExact(right_literal)) |
| || (!TruncationHelper<IntType::cpptype>::ValueInRange(right_literal, |
| maximum_truncated_value)); |
| } |
| case kLong: { |
| return (!TruncationHelper<LongType::cpptype>::LongIsExact(right_literal)) |
| || (!TruncationHelper<LongType::cpptype>::ValueInRange(right_literal, |
| maximum_truncated_value)); |
| } |
| case kFloat: { |
| return (!TruncationHelper<FloatType::cpptype>::LongIsExact(right_literal)) |
| || (!TruncationHelper<FloatType::cpptype>::ValueInRange(right_literal, |
| maximum_truncated_value)); |
| } |
| case kDouble: { |
| return (!TruncationHelper<DoubleType::cpptype>::LongIsExact(right_literal)) |
| || (!TruncationHelper<DoubleType::cpptype>::ValueInRange(right_literal, |
| maximum_truncated_value)); |
| } |
| default: { |
| LOG(FATAL) << "Type not recognized as numeric: " << right_literal_type.getName(); |
| } |
| } |
| case ComparisonID::kNotEqual: |
| return false; |
| default: |
| break; |
| } |
| |
| std::int64_t effective_literal |
| = GetEffectiveLiteralValueForComparisonWithTruncatedAttribute(comp, |
| right_literal, |
| right_literal_type); |
| switch (comp) { |
| case ComparisonID::kLess: |
| if (effective_literal <= 0) { |
| return true; |
| } else { |
| return false; |
| } |
| case ComparisonID::kLessOrEqual: |
| if (effective_literal < 0) { |
| return true; |
| } else { |
| return false; |
| } |
| case ComparisonID::kGreater: |
| if (effective_literal >= maximum_truncated_value) { |
| return true; |
| } else { |
| return false; |
| } |
| case ComparisonID::kGreaterOrEqual: |
| if (effective_literal > maximum_truncated_value) { |
| return true; |
| } else { |
| return false; |
| } |
| default: |
| FATAL_ERROR("Unexpected ComparisonID in CompressedAttributePredicateTransformer::" |
| "CompressedComparisonIsAlwaysFalseForTruncatedAttribute()"); |
| } |
| } |
| |
| PredicateTransformResult CompressedAttributePredicateTransformer |
| ::TransformEqualPredicateOnCompressedAttribute( |
| const TypedValue &right_literal, |
| const Type &right_literal_type, |
| const CompressionDictionary *dictionary, |
| const std::int64_t maximum_truncated_value) { |
| std::uint32_t match_code; |
| if (dictionary) { |
| match_code = dictionary->getCodeForTypedValue(right_literal, right_literal_type); |
| if (match_code == dictionary->numberOfCodes()) { |
| return PredicateTransformResult(PredicateTransformResultType::kNone); |
| } |
| } else { |
| if (CompressedComparisonIsAlwaysFalseForTruncatedAttribute(ComparisonID::kEqual, |
| right_literal, |
| right_literal_type, |
| maximum_truncated_value)) { |
| return PredicateTransformResult(PredicateTransformResultType::kNone); |
| } |
| // At this point, we know that 'right_literal' should not have a fractional |
| // part and should be in the range of truncated codes. |
| switch (right_literal_type.getTypeID()) { |
| case kInt: |
| DCHECK(TruncationHelper<IntType::cpptype>::LongIsExact(right_literal)); |
| match_code = TruncationHelper<IntType::cpptype>::GetAsCode(right_literal); |
| break; |
| case kLong: |
| DCHECK(TruncationHelper<LongType::cpptype>::LongIsExact(right_literal)); |
| match_code = TruncationHelper<LongType::cpptype>::GetAsCode(right_literal); |
| break; |
| case kFloat: |
| DCHECK(TruncationHelper<FloatType::cpptype>::LongIsExact(right_literal)); |
| match_code = TruncationHelper<FloatType::cpptype>::GetAsCode(right_literal); |
| break; |
| case kDouble: |
| DCHECK(TruncationHelper<DoubleType::cpptype>::LongIsExact(right_literal)); |
| match_code = TruncationHelper<DoubleType::cpptype>::GetAsCode(right_literal); |
| break; |
| default: |
| LOG(FATAL) << "Type not recognized as numeric: " << right_literal_type.getName(); |
| } |
| } |
| |
| return PredicateTransformResult(PredicateTransformResultType::kBasicComparison, |
| ComparisonID::kEqual, |
| match_code); |
| } |
| |
| PredicateTransformResult CompressedAttributePredicateTransformer |
| ::TransformNotEqualPredicateOnCompressedAttribute( |
| const TypedValue &right_literal, |
| const Type &right_literal_type, |
| const CompressionDictionary *dictionary, |
| const std::int64_t maximum_truncated_value) { |
| std::uint32_t match_code; |
| std::uint32_t null_code = std::numeric_limits<std::uint32_t>::max(); |
| if (dictionary) { |
| match_code = dictionary->getCodeForTypedValue(right_literal, right_literal_type); |
| null_code = dictionary->getNullCode(); |
| if (match_code == dictionary->numberOfCodes()) { |
| if (dictionary->containsNull()) { |
| return PredicateTransformResult(PredicateTransformResultType::kBasicComparison, |
| ComparisonID::kNotEqual, |
| null_code); |
| } else { |
| // Get all tuples. |
| return PredicateTransformResult(PredicateTransformResultType::kAll); |
| } |
| } |
| } else { |
| if (CompressedComparisonIsAlwaysTrueForTruncatedAttribute(ComparisonID::kNotEqual, |
| right_literal, |
| right_literal_type, |
| maximum_truncated_value)) { |
| return PredicateTransformResult(PredicateTransformResultType::kAll); |
| } |
| // At this point, we know that 'right_literal' should not have a fractional |
| // part and should be in the range of truncated codes. |
| switch (right_literal_type.getTypeID()) { |
| case kInt: |
| DCHECK(TruncationHelper<IntType::cpptype>::LongIsExact(right_literal)); |
| match_code = TruncationHelper<IntType::cpptype>::GetAsCode(right_literal); |
| break; |
| case kLong: |
| DCHECK(TruncationHelper<LongType::cpptype>::LongIsExact(right_literal)); |
| match_code = TruncationHelper<LongType::cpptype>::GetAsCode(right_literal); |
| break; |
| case kFloat: |
| DCHECK(TruncationHelper<FloatType::cpptype>::LongIsExact(right_literal)); |
| match_code = TruncationHelper<FloatType::cpptype>::GetAsCode(right_literal); |
| break; |
| case kDouble: |
| DCHECK(TruncationHelper<DoubleType::cpptype>::LongIsExact(right_literal)); |
| match_code = TruncationHelper<DoubleType::cpptype>::GetAsCode(right_literal); |
| break; |
| default: |
| LOG(FATAL) << "Type not recognized as numeric: " << right_literal_type.getName(); |
| } |
| } |
| |
| if (null_code == std::numeric_limits<std::uint32_t>::max()) { |
| return PredicateTransformResult(PredicateTransformResultType::kBasicComparison, |
| ComparisonID::kNotEqual, |
| match_code); |
| } else { |
| return PredicateTransformResult(PredicateTransformResultType::kBasicComparison, |
| ComparisonID::kNotEqual, |
| match_code, |
| null_code, |
| true); |
| } |
| } |
| |
| PredicateTransformResult CompressedAttributePredicateTransformer |
| ::TransformOtherComparisonPredicateOnCompressedAttribute( |
| const ComparisonID comp, |
| const TypedValue &right_literal, |
| const Type &right_literal_type, |
| const CompressionDictionary *dictionary, |
| const std::int64_t maximum_truncated_value) { |
| std::pair<std::uint32_t, std::uint32_t> match_range; |
| if (dictionary) { |
| match_range = dictionary->getLimitCodesForComparisonTyped(comp, |
| right_literal, |
| right_literal_type); |
| if (match_range.first >= match_range.second) { |
| // No matches. |
| return PredicateTransformResult(PredicateTransformResultType::kNone); |
| } |
| if (match_range.second == dictionary->numberOfCodes()) { |
| // This trick lets us skip an unnecessary comparison. |
| match_range.second = std::numeric_limits<std::uint32_t>::max(); |
| } |
| } else { |
| if (CompressedComparisonIsAlwaysTrueForTruncatedAttribute(comp, |
| right_literal, |
| right_literal_type, |
| maximum_truncated_value)) { |
| return PredicateTransformResult(PredicateTransformResultType::kAll); |
| } |
| if (CompressedComparisonIsAlwaysFalseForTruncatedAttribute(comp, |
| right_literal, |
| right_literal_type, |
| maximum_truncated_value)) { |
| return PredicateTransformResult(PredicateTransformResultType::kNone); |
| } |
| |
| std::int64_t effective_literal |
| = GetEffectiveLiteralValueForComparisonWithTruncatedAttribute(comp, |
| right_literal, |
| right_literal_type); |
| switch (comp) { |
| case ComparisonID::kLess: |
| match_range.first = 0; |
| match_range.second = effective_literal; |
| break; |
| case ComparisonID::kLessOrEqual: |
| match_range.first = 0; |
| match_range.second = effective_literal + 1; |
| break; |
| case ComparisonID::kGreater: |
| match_range.first = effective_literal + 1; |
| match_range.second = std::numeric_limits<std::uint32_t>::max(); |
| break; |
| case ComparisonID::kGreaterOrEqual: |
| match_range.first = effective_literal; |
| match_range.second = std::numeric_limits<std::uint32_t>::max(); |
| break; |
| default: |
| FATAL_ERROR("Unexpected ComparisonID in CompressedAttributePredicateTransformer::" |
| "TransformOtherComparisonPredicateOnCompressedAttribute()"); |
| } |
| } |
| |
| if (match_range.first == 0) { |
| if (match_range.second == std::numeric_limits<std::uint32_t>::max()) { |
| return PredicateTransformResult(PredicateTransformResultType::kAll); |
| } else { |
| return PredicateTransformResult(PredicateTransformResultType::kBasicComparison, |
| ComparisonID::kLess, |
| match_range.second); |
| } |
| } else if (match_range.second == std::numeric_limits<std::uint32_t>::max()) { |
| return PredicateTransformResult(PredicateTransformResultType::kBasicComparison, |
| ComparisonID::kGreaterOrEqual, |
| match_range.first); |
| } else { |
| return PredicateTransformResult(PredicateTransformResultType::kRangeComparison, |
| match_range.first, |
| match_range.second); |
| } |
| } |
| |
| } // namespace quickstep |
