blob: e896a7a3920f75b7fcf08d143a40bf6f0655084f [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
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* KIND, either express or implied. See the License for the
* specific language governing permissions and limitations
* under the License.
#include <unordered_map>
#include <vector>
#include "catalog/CatalogTypedefs.hpp"
#include "expressions/predicate/PredicateCost.hpp"
#include "storage/SubBlockTypeRegistryMacros.hpp"
#include "storage/TupleStorageSubBlock.hpp"
#include "types/TypedValue.hpp"
#include "utility/BitVector.hpp"
#include "utility/Macros.hpp"
#include "utility/PtrVector.hpp"
namespace quickstep {
template <typename K, typename V> class PtrMap;
class CatalogRelationSchema;
class ComparisonPredicate;
class TupleStorageSubBlockDescription;
class Type;
class ValueAccessor;
/** \addtogroup Storage
* @{
* @brief An implementation of TupleStorageSubBlock as a simple column store
* with a single sort column and no compression or holes.
* @warning This implementation does NOT support variable-length attributes.
* It is an error to attempt to construct a
* BasicColumnStoreTupleStorageSubBlock for a relation with any
* variable-length attributes.
class BasicColumnStoreTupleStorageSubBlock : public TupleStorageSubBlock {
BasicColumnStoreTupleStorageSubBlock(const CatalogRelationSchema &relation,
const TupleStorageSubBlockDescription &description,
const bool new_block,
void *sub_block_memory,
const std::size_t sub_block_memory_size);
~BasicColumnStoreTupleStorageSubBlock() override {
* @brief Determine whether a TupleStorageSubBlockDescription is valid for
* this type of TupleStorageSubBlock.
* @param relation The relation a tuple store described by description would
* belong to.
* @param description A description of the parameters for this type of
* TupleStorageSubBlock, which will be checked for validity.
* @return Whether description is well-formed and valid for this type of
* TupleStorageSubBlock belonging to relation (i.e. whether a
* TupleStorageSubBlock of this type, belonging to relation, can be
* constructed according to description).
static bool DescriptionIsValid(const CatalogRelationSchema &relation,
const TupleStorageSubBlockDescription &description);
* @brief Estimate the average number of bytes (including any applicable
* overhead) used to store a single tuple in this type of
* TupleStorageSubBlock. Used by StorageBlockLayout::finalize() to
* divide block memory amongst sub-blocks.
* @warning description must be valid. DescriptionIsValid() should be called
* first if necessary.
* @param relation The relation tuples belong to.
* @param description A description of the parameters for this type of
* TupleStorageSubBlock.
* @return The average/ammortized number of bytes used to store a single
* tuple of relation in a TupleStorageSubBlock of this type described
* by description.
static std::size_t EstimateBytesPerTuple(const CatalogRelationSchema &relation,
const TupleStorageSubBlockDescription &description);
bool supportsUntypedGetAttributeValue(const attribute_id attr) const override {
return true;
bool supportsAdHocInsert() const override {
return true;
bool adHocInsertIsEfficient() const override {
// Ad-hoc insert is only efficient if it doesn't require resorting the
// whole block.
return !sort_specified_;
TupleStorageSubBlockType getTupleStorageSubBlockType() const override {
return kBasicColumnStore;
bool isEmpty() const override {
return (header_->num_tuples == 0);
bool isPacked() const override {
return true;
tuple_id getMaxTupleID() const override {
return header_->num_tuples - 1;
bool hasTupleWithID(const tuple_id tuple) const override {
return ((tuple >=0) && (tuple < header_->num_tuples));
InsertResult insertTuple(const Tuple &tuple) override;
bool insertTupleInBatch(const Tuple &tuple) override;
tuple_id bulkInsertTuples(ValueAccessor *accessor) override;
tuple_id bulkInsertTuplesWithRemappedAttributes(
const std::vector<attribute_id> &attribute_map,
ValueAccessor *accessor) override;
const void* getAttributeValue(const tuple_id tuple,
const attribute_id attr) const override;
TypedValue getAttributeValueTyped(const tuple_id tuple,
const attribute_id attr) const override;
ValueAccessor* createValueAccessor(
const TupleIdSequence *sequence = nullptr) const override;
bool canSetAttributeValuesInPlaceTyped(
const tuple_id tuple,
const std::unordered_map<attribute_id, TypedValue> &new_values) const override;
void setAttributeValueInPlaceTyped(const tuple_id tuple,
const attribute_id attr,
const TypedValue &value) override;
bool deleteTuple(const tuple_id tuple) override;
bool bulkDeleteTuples(TupleIdSequence *tuples) override;
predicate_cost_t estimatePredicateEvaluationCost(
const ComparisonPredicate &predicate) const override;
// This override can quickly evaluate comparisons between the sort column
// and a literal value.
TupleIdSequence* getMatchesForPredicate(const ComparisonPredicate &predicate,
const TupleIdSequence *filter) const override;
void rebuild() override {
if (sort_specified_ && !sorted_) {
bool isInsertOrderPreserving() const override {
// Rebuild reorders inserts based on sort column if any is specified.
return !sort_specified_;
struct BasicColumnStoreHeader {
tuple_id num_tuples;
tuple_id nulls_in_sort_column;
bool hasSpaceToInsert(const tuple_id num_tuples) const {
return (num_tuples <= max_tuples_ - header_->num_tuples);
// Copy attribute values from 'tuple' into the appropriate column stripes
// at the offset specified by 'position'. If 'position' is not at the current
// end of tuples in this block, subsequent tuples are shifted back to make
// room for the new tuple.
void insertTupleAtPosition(const Tuple &tuple,
const tuple_id position);
// Move 'num_tuples' values in each column from 'src_tuple' to
// 'dest_position'. This should usually be paired with a call to
// shiftNullBitmaps().
void shiftTuples(const tuple_id dest_position,
const tuple_id src_tuple,
const tuple_id num_tuples);
// Shift the tails of 'column_null_bitmaps_' (starting from 'from_position')
// by 'distance' bits (forward shift if 'distance' is negative, backward
// shift if positive).
void shiftNullBitmaps(const tuple_id from_position,
const tuple_id distance);
// Sort all columns according to ascending order of values in the sort
// column. Returns true if any reordering occured. This should only be called
// when 'sort_specified_' is true, otherwise the block is always "built".
bool rebuildInternal();
tuple_id max_tuples_;
bool sort_specified_, sorted_;
attribute_id sort_column_id_;
const Type *sort_column_type_;
BasicColumnStoreHeader *header_;
std::vector<void*> column_stripes_;
PtrVector<BitVector<false>, true> column_null_bitmaps_;
/** @} */
} // namespace quickstep