A recursive model index with two layers consiting only of linear monels that maps keys to their tuple_id. More...

#include <Index.hpp>

Inheritance diagram for m::idx::RecursiveModelIndex< Key >:

Collaboration diagram for m::idx::RecursiveModelIndex< Key >:

Data Structures
struct	LinearModel

Public Types
using	base_type = ArrayIndex< Key >

using	key_type = base_type::key_type

using	value_type = base_type::value_type

using	entry_type = base_type::entry_type

using	const_iterator = base_type::const_iterator

using	iterator = entry_type *

Public Member Functions
	RecursiveModelIndex ()

IndexMethod	method () const override
	Returns the `IndexMethod` of the index.

const memory::Memory &	memory () const override
	Returns the underlying memory of the index.

std::size_t	size_in_bytes () const override

void	finalize () override
	Sorts the underlying vector, builds the linear models, and flags the index as finalized.

const_iterator	lower_bound (const key_type key) const override
	Returns an iterator pointing to the first entry of the vector such that `entry.key` < `key` is `false`, i.e.

const_iterator	upper_bound (const key_type key) const override
	Returns an iterator pointing to the first entry of the vector such that `entry.key` < `key` is `true`, i.e.

void	dump (std::ostream &out) const override

void	dump () const override

void	bulkload (const Table &table, const Schema &key_schema) override
	Bulkloads the index from `table` on the key contained in `key_schema` by executing a query and adding one entry after another.

std::size_t	num_entries () const override
	Returns the number of entries in the index.

void	add (const key_type key, const value_type value)
	Adds a single pair of `key` and `value` to the index.

bool	finalized () const
	Returns `true` iff the index is currently finalized.

const_iterator	begin () const

const_iterator	cbegin () const

const_iterator	end () const

const_iterator	cend () const

Static Public Attributes
static constexpr std::size_t	ALLOCATION_SIZE = 1UL << 30
	1 GiB

Protected Member Functions
iterator	begin ()
	Returns an iterator pointing to the first entry of the index.

iterator	end ()
	Returns an interator pointing to the first element following the last entry of the index.

Static Protected Member Functions
static std::string	build_query (const Table &table, const Schema &schema)
	Constructs a query string to select all attributes in `schema` from `table`.

Protected Attributes
std::vector< LinearModel >	models_
	A vector of linear models to index the underlying data.

memory::Memory	memory_
	‍the underlying memory for a vector holding the index entries consisting of pairs of key and value

std::size_t	num_entries_
	number of entries

bool	finalized_
	flag to signalize whether index is finalized, i.e. array is sorted

struct {
const U &_rhs const

key_type rhs = M_CONSTEXPR_COND((std::same_as<U, key_type>), _rhs, _rhs.first)

}	cmp
	Custom comparator class to handle the special case of.

Private Member Functions
std::size_t	predict (const key_type key) const

const_iterator	lower_bound_exponential_search (const_iterator pred, const key_type value) const

const_iterator	upper_bound_exponential_search (const_iterator pred, const key_type value) const

Detailed Description

template<arithmetic Key>
struct m::idx::RecursiveModelIndex< Key >

A recursive model index with two layers consiting only of linear monels that maps keys to their tuple_id.

Definition at line 162 of file Index.hpp.

Member Typedef Documentation

◆ base_type

template<arithmetic Key>

using m::idx::RecursiveModelIndex< Key >::base_type = ArrayIndex<Key>

Definition at line 164 of file Index.hpp.

◆ const_iterator

template<arithmetic Key>

using m::idx::RecursiveModelIndex< Key >::const_iterator = base_type::const_iterator

Definition at line 168 of file Index.hpp.

◆ entry_type

template<arithmetic Key>

using m::idx::RecursiveModelIndex< Key >::entry_type = base_type::entry_type

Definition at line 167 of file Index.hpp.

◆ iterator

template<typename Key >

using m::idx::ArrayIndex< Key >::iterator = entry_type*

inherited

Definition at line 68 of file Index.hpp.

◆ key_type

template<arithmetic Key>

using m::idx::RecursiveModelIndex< Key >::key_type = base_type::key_type

Definition at line 165 of file Index.hpp.

◆ value_type

template<arithmetic Key>

using m::idx::RecursiveModelIndex< Key >::value_type = base_type::value_type

Definition at line 166 of file Index.hpp.

Constructor & Destructor Documentation

◆ RecursiveModelIndex()

template<arithmetic Key>

m::idx::RecursiveModelIndex< Key >::RecursiveModelIndex ( )

inline

Definition at line 236 of file Index.hpp.

Member Function Documentation

◆ add()

template<typename Key >

void ArrayIndex::add	(	const key_type	key,
		const value_type	value
	)

inherited

Adds a single pair of key and value to the index.

Note that finalize() has to be called afterwards for the vector to be sorted and the index to be usable.

Definition at line 147 of file Index.cpp.

References m::Catalog::Get(), and m::Catalog::pool().

◆ begin() [1/2]

template<typename Key >

iterator m::idx::ArrayIndex< Key >::begin ( )

inlineprotectedinherited

Returns an iterator pointing to the first entry of the index.

Definition at line 145 of file Index.hpp.

References m::memory::Memory::addr(), and m::idx::ArrayIndex< Key >::memory_.

Referenced by m::idx::ArrayIndex< Key >::cbegin(), m::idx::ArrayIndex< Key >::finalize(), m::idx::ArrayIndex< Key >::lower_bound(), m::idx::RecursiveModelIndex< Key >::lower_bound(), m::idx::RecursiveModelIndex< Key >::lower_bound_exponential_search(), m::idx::ArrayIndex< Key >::upper_bound(), m::idx::RecursiveModelIndex< Key >::upper_bound(), and m::idx::RecursiveModelIndex< Key >::upper_bound_exponential_search().

◆ begin() [2/2]

template<typename Key >

const_iterator m::idx::ArrayIndex< Key >::begin ( ) const

inlineinherited

Definition at line 147 of file Index.hpp.

References m::memory::Memory::addr(), and m::idx::ArrayIndex< Key >::memory_.

◆ build_query()

std::string IndexBase::build_query	(	const Table &	table,
		const Schema &	schema
	)

staticprotectedinherited

Constructs a query string to select all attributes in schema from table.

Definition at line 40 of file Index.cpp.

References m::Schema::at(), m::Schema::entry_type::id, m::Table::name(), and m::Schema::num_entries().

◆ bulkload()

template<typename Key >

void ArrayIndex::bulkload	(	const Table &	table,
		const Schema &	key_schema
	)

overridevirtualinherited

Bulkloads the index from table on the key contained in key_schema by executing a query and adding one entry after another.

The index is finalized in the end. Throws m::invalid_arguent if key_schema contains more than one entry or key_type and the attribute type of the entry in key_schema do not match.

Implements m::idx::IndexBase.

Definition at line 58 of file Index.cpp.

References m::Value::as(), m::Schema::at(), CHECK, m::Catalog::create_backend(), m::execute_query(), m::Catalog::Get(), m::Options::Get(), m::Tuple::get(), M_unreachable, m::Schema::num_entries(), m::statement_from_string(), m::Schema::entry_type::type, and m::visit().

◆ cbegin()

template<typename Key >

const_iterator m::idx::ArrayIndex< Key >::cbegin ( ) const

inlineinherited

Definition at line 148 of file Index.hpp.

References m::idx::ArrayIndex< Key >::begin().

◆ cend()

template<typename Key >

const_iterator m::idx::ArrayIndex< Key >::cend ( ) const

inlineinherited

Definition at line 154 of file Index.hpp.

References m::idx::ArrayIndex< Key >::end().

◆ dump() [1/2]

template<arithmetic Key>

void m::idx::RecursiveModelIndex< Key >::dump ( ) const

inlineoverridevirtual

Reimplemented from m::idx::ArrayIndex< Key >.

Definition at line 267 of file Index.hpp.

References m::idx::RecursiveModelIndex< Key >::dump().

Referenced by m::idx::RecursiveModelIndex< Key >::dump().

◆ dump() [2/2]

template<arithmetic Key>

void m::idx::RecursiveModelIndex< Key >::dump ( std::ostream & out ) const

inlineoverridevirtual

Reimplemented from m::idx::ArrayIndex< Key >.

Definition at line 266 of file Index.hpp.

◆ end() [1/2]

template<typename Key >

iterator m::idx::ArrayIndex< Key >::end ( )

inlineprotectedinherited

Returns an interator pointing to the first element following the last entry of the index.

Definition at line 151 of file Index.hpp.

References m::memory::Memory::addr(), m::idx::ArrayIndex< Key >::memory_, and m::idx::ArrayIndex< Key >::num_entries_.

Referenced by m::idx::ArrayIndex< Key >::cend(), m::idx::ArrayIndex< Key >::finalize(), m::idx::ArrayIndex< Key >::lower_bound(), m::idx::RecursiveModelIndex< Key >::lower_bound_exponential_search(), m::idx::ArrayIndex< Key >::upper_bound(), and m::idx::RecursiveModelIndex< Key >::upper_bound_exponential_search().

◆ end() [2/2]

template<typename Key >

const_iterator m::idx::ArrayIndex< Key >::end ( ) const

inlineinherited

Definition at line 153 of file Index.hpp.

References m::memory::Memory::addr(), m::idx::ArrayIndex< Key >::memory_, and m::idx::ArrayIndex< Key >::num_entries_.

◆ finalize()

template<arithmetic Key>

void RecursiveModelIndex::finalize

overridevirtual

Sorts the underlying vector, builds the linear models, and flags the index as finalized.

Reimplemented from m::idx::ArrayIndex< Key >.

Definition at line 163 of file Index.cpp.

◆ finalized()

template<typename Key >

bool m::idx::ArrayIndex< Key >::finalized ( ) const

inlineinherited

Returns true iff the index is currently finalized.

Definition at line 125 of file Index.hpp.

References m::idx::ArrayIndex< Key >::finalized_.

Referenced by m::idx::RecursiveModelIndex< Key >::lower_bound(), and m::idx::RecursiveModelIndex< Key >::upper_bound().

◆ lower_bound()

template<arithmetic Key>

const_iterator m::idx::RecursiveModelIndex< Key >::lower_bound ( const key_type key ) const

inlineoverridevirtual

Returns an iterator pointing to the first entry of the vector such that entry.key < key is false, i.e.

that is greater than or equal to key, or end() if no such element is found. Throws m::exception if the index is not finalized.

Reimplemented from m::idx::ArrayIndex< Key >.

Definition at line 253 of file Index.hpp.

References m::idx::ArrayIndex< Key >::begin(), m::idx::ArrayIndex< Key >::finalized(), m::idx::RecursiveModelIndex< Key >::lower_bound_exponential_search(), and m::idx::RecursiveModelIndex< Key >::predict().

◆ lower_bound_exponential_search()

template<arithmetic Key>

const_iterator m::idx::RecursiveModelIndex< Key >::lower_bound_exponential_search	(	const_iterator	pred,
		const key_type	value
	)		const

inlineprivate

Definition at line 275 of file Index.hpp.

References m::and, m::idx::ArrayIndex< Key >::begin(), m::idx::ArrayIndex< Key >::cmp, and m::idx::ArrayIndex< Key >::end().

Referenced by m::idx::RecursiveModelIndex< Key >::lower_bound().

◆ memory()

template<arithmetic Key>

const memory::Memory & m::idx::RecursiveModelIndex< Key >::memory ( ) const

inlineoverridevirtual

Returns the underlying memory of the index.

Reimplemented from m::idx::ArrayIndex< Key >.

Definition at line 242 of file Index.hpp.

◆ method()

template<arithmetic Key>

IndexMethod m::idx::RecursiveModelIndex< Key >::method ( ) const

inlineoverridevirtual

Returns the IndexMethod of the index.

Reimplemented from m::idx::ArrayIndex< Key >.

Definition at line 239 of file Index.hpp.

References m::idx::Rmi.

◆ num_entries()

template<typename Key >

std::size_t m::idx::ArrayIndex< Key >::num_entries ( ) const

inlineoverridevirtualinherited

Returns the number of entries in the index.

Implements m::idx::IndexBase.

Definition at line 102 of file Index.hpp.

References m::idx::ArrayIndex< Key >::num_entries_.

Referenced by m::idx::RecursiveModelIndex< Key >::predict().

◆ predict()

template<arithmetic Key>

std::size_t m::idx::RecursiveModelIndex< Key >::predict ( const key_type key ) const

inlineprivate

Definition at line 270 of file Index.hpp.

References m::idx::RecursiveModelIndex< Key >::models_, and m::idx::ArrayIndex< Key >::num_entries().

Referenced by m::idx::RecursiveModelIndex< Key >::lower_bound(), and m::idx::RecursiveModelIndex< Key >::upper_bound().

◆ size_in_bytes()

template<arithmetic Key>

std::size_t m::idx::RecursiveModelIndex< Key >::size_in_bytes ( ) const

inlineoverridevirtual

Reimplemented from m::idx::ArrayIndex< Key >.

Definition at line 245 of file Index.hpp.

◆ upper_bound()

template<arithmetic Key>

const_iterator m::idx::RecursiveModelIndex< Key >::upper_bound ( const key_type key ) const

inlineoverridevirtual

Returns an iterator pointing to the first entry of the vector such that entry.key < key is true, i.e.

that is strictly greater than key, or end() if no such element is found. Throws m::exception if the index is not finalized.

Reimplemented from m::idx::ArrayIndex< Key >.

Definition at line 261 of file Index.hpp.

References m::idx::ArrayIndex< Key >::begin(), m::idx::ArrayIndex< Key >::finalized(), m::idx::RecursiveModelIndex< Key >::predict(), and m::idx::RecursiveModelIndex< Key >::upper_bound_exponential_search().

◆ upper_bound_exponential_search()

template<arithmetic Key>

const_iterator m::idx::RecursiveModelIndex< Key >::upper_bound_exponential_search	(	const_iterator	pred,
		const key_type	value
	)		const

inlineprivate

Definition at line 299 of file Index.hpp.

References m::and, m::idx::ArrayIndex< Key >::begin(), m::idx::ArrayIndex< Key >::cmp, and m::idx::ArrayIndex< Key >::end().

Referenced by m::idx::RecursiveModelIndex< Key >::upper_bound().

Field Documentation

◆ ALLOCATION_SIZE

template<typename Key >

constexpr std::size_t m::idx::ArrayIndex< Key >::ALLOCATION_SIZE = 1UL << 30

staticconstexprinherited

1 GiB

Definition at line 60 of file Index.hpp.

◆

struct { ... } m::idx::ArrayIndex< Key >::cmp

Custom comparator class to handle the special case of.

Template Parameters

key_type being const char*.

Referenced by m::idx::ArrayIndex< Key >::finalize(), m::idx::ArrayIndex< Key >::lower_bound(), m::idx::RecursiveModelIndex< Key >::lower_bound_exponential_search(), m::idx::ArrayIndex< Key >::upper_bound(), and m::idx::RecursiveModelIndex< Key >::upper_bound_exponential_search().

◆ const

template<typename Key >

const U& _rhs m::idx::ArrayIndex< Key >::const

inherited

Initial value:

{

key_type lhs = M_CONSTEXPR_COND((std::same_as<T, key_type>), _lhs, _lhs.first)

M_CONSTEXPR_COND

#define M_CONSTEXPR_COND(COND, IF_TRUE, IF_FALSE)

Definition: macro.hpp:54

m::idx::ArrayIndex::key_type

Key key_type

Definition: Index.hpp:65

Definition at line 83 of file Index.hpp.

◆ finalized_

template<typename Key >

bool m::idx::ArrayIndex< Key >::finalized_

protectedinherited

flag to signalize whether index is finalized, i.e. array is sorted

Definition at line 75 of file Index.hpp.

Referenced by m::idx::ArrayIndex< Key >::finalize(), m::idx::ArrayIndex< Key >::finalized(), m::idx::ArrayIndex< Key >::lower_bound(), and m::idx::ArrayIndex< Key >::upper_bound().

◆ memory_

template<typename Key >

memory::Memory m::idx::ArrayIndex< Key >::memory_

protectedinherited

‍the underlying memory for a vector holding the index entries consisting of pairs of key and value

Definition at line 73 of file Index.hpp.

Referenced by m::idx::ArrayIndex< Key >::begin(), m::idx::ArrayIndex< Key >::end(), and m::idx::ArrayIndex< Key >::memory().

◆ models_

template<arithmetic Key>

std::vector<LinearModel> m::idx::RecursiveModelIndex< Key >::models_

protected

A vector of linear models to index the underlying data.

Definition at line 233 of file Index.hpp.

Referenced by m::idx::RecursiveModelIndex< Key >::predict().

◆ num_entries_

template<typename Key >

std::size_t m::idx::ArrayIndex< Key >::num_entries_

protectedinherited

number of entries

Definition at line 74 of file Index.hpp.

Referenced by m::idx::ArrayIndex< Key >::end(), m::idx::ArrayIndex< Key >::num_entries(), and m::idx::ArrayIndex< Key >::size_in_bytes().

◆ rhs

template<typename Key >

key_type m::idx::ArrayIndex< Key >::rhs = M_CONSTEXPR_COND((std::same_as<U, key_type>), _rhs, _rhs.first)

inherited

Definition at line 85 of file Index.hpp.

The documentation for this struct was generated from the following files:

include/mutable/storage/Index.hpp
src/storage/Index.cpp

Data Structures

Public Types

Public Member Functions

Static Public Attributes

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Member Typedef Documentation

◆ base_type

◆ const_iterator

◆ entry_type

◆ iterator

◆ key_type

◆ value_type

Constructor & Destructor Documentation

◆ RecursiveModelIndex()

Member Function Documentation

◆ add()

◆ begin() [1/2]

◆ begin() [2/2]

◆ build_query()

◆ bulkload()

◆ cbegin()

◆ cend()

◆ dump() [1/2]

◆ dump() [2/2]

◆ end() [1/2]

◆ end() [2/2]

◆ finalize()

◆ finalized()

◆ lower_bound()

◆ lower_bound_exponential_search()

◆ memory()

◆ method()

◆ num_entries()

◆ predict()

◆ size_in_bytes()

◆ upper_bound()

◆ upper_bound_exponential_search()

Field Documentation

◆ ALLOCATION_SIZE

◆

◆ const

◆ finalized_

◆ memory_

◆ models_

◆ num_entries_

◆ rhs