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	container_type = base_type::container_type

using	const_iterator = base_type::const_iterator

Public Member Functions
	RecursiveModelIndex ()

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

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
	Returns an iterator pointing to the first entry of the index.

const_iterator	cbegin () const

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

const_iterator	cend () const

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.

container_type	data_
	A vector holding the index entries consisting of pairs of key and value.

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 136 of file Index.hpp.

Member Typedef Documentation

◆ base_type

template<arithmetic Key>

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

Definition at line 138 of file Index.hpp.

◆ const_iterator

template<arithmetic Key>

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

Definition at line 143 of file Index.hpp.

◆ container_type

template<arithmetic Key>

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

Definition at line 142 of file Index.hpp.

◆ entry_type

template<arithmetic Key>

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

Definition at line 141 of file Index.hpp.

◆ key_type

template<arithmetic Key>

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

Definition at line 139 of file Index.hpp.

◆ value_type

template<arithmetic Key>

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

Definition at line 140 of file Index.hpp.

Constructor & Destructor Documentation

◆ RecursiveModelIndex()

template<arithmetic Key>

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

inline

Definition at line 211 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 142 of file Index.cpp.

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

◆ begin()

template<typename Key >

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

inlineinherited

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

Definition at line 124 of file Index.hpp.

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

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

◆ 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 53 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 125 of file Index.hpp.

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

◆ cend()

template<typename Key >

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

inlineinherited

Definition at line 128 of file Index.hpp.

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

◆ dump() [1/2]

template<arithmetic Key>

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

inlineoverridevirtual

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

Definition at line 236 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 235 of file Index.hpp.

◆ end()

template<typename Key >

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

inlineinherited

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

Definition at line 127 of file Index.hpp.

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

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

◆ 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 154 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 105 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 222 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 244 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().

◆ 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 214 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 89 of file Index.hpp.

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

◆ predict()

template<arithmetic Key>

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

inlineprivate

Definition at line 239 of file Index.hpp.

References m::idx::ArrayIndex< Key >::data_, and m::idx::RecursiveModelIndex< Key >::models_.

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

◆ 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 230 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 268 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

◆

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:54

Definition at line 70 of file Index.hpp.

◆ data_

template<typename Key >

container_type m::idx::ArrayIndex< Key >::data_

protectedinherited

A vector holding the index entries consisting of pairs of key and value.

Definition at line 61 of file Index.hpp.

Referenced by m::idx::ArrayIndex< Key >::begin(), m::idx::ArrayIndex< Key >::cbegin(), m::idx::ArrayIndex< Key >::cend(), m::idx::ArrayIndex< Key >::end(), m::idx::ArrayIndex< Key >::finalize(), m::idx::ArrayIndex< Key >::lower_bound(), m::idx::ArrayIndex< Key >::num_entries(), m::idx::RecursiveModelIndex< Key >::predict(), and m::idx::ArrayIndex< Key >::upper_bound().

◆ 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 62 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().

◆ 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 208 of file Index.hpp.

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

◆ 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 72 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 Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Member Typedef Documentation

◆ base_type

◆ const_iterator

◆ container_type

◆ entry_type

◆ key_type

◆ value_type

Constructor & Destructor Documentation

◆ RecursiveModelIndex()

Member Function Documentation

◆ add()

◆ begin()

◆ build_query()

◆ bulkload()

◆ cbegin()

◆ cend()

◆ dump() [1/2]

◆ dump() [2/2]

◆ end()

◆ finalize()

◆ finalized()

◆ lower_bound()

◆ lower_bound_exponential_search()

◆ method()

◆ num_entries()

◆ predict()

◆ upper_bound()

◆ upper_bound_exponential_search()

Field Documentation

◆

◆ const

◆ data_

◆ finalized_

◆ models_

◆ rhs