SpnEstimator that estimates cardinalities based on Sum-Product Networks. More...

#include <CardinalityEstimator.hpp>

Inheritance diagram for m::SpnEstimator:

Collaboration diagram for m::SpnEstimator:

Data Structures
struct	SpnDataModel

Public Types
using	SpnIdentifier = std::pair< ThreadSafePooledString, ThreadSafePooledString >

using	SpnJoin = std::pair< SpnIdentifier, SpnIdentifier >

using	table_spn_map = std::unordered_map< ThreadSafePooledString, std::reference_wrapper< const SpnWrapper > >

Public Member Functions
	SpnEstimator (ThreadSafePooledString name_of_database)

	~SpnEstimator ()

void	learn_spns ()
	Learn an Spn on every table in the database.

void	learn_new_spn (const ThreadSafePooledString &name_of_table)
	Add a new Spn for a table in the database.

std::unique_ptr< DataModel >	empty_model () const override

std::unique_ptr< DataModel >	estimate_scan (const QueryGraph &G, Subproblem P) const override

std::unique_ptr< DataModel >	estimate_filter (const QueryGraph &G, const DataModel &data, const cnf::CNF &filter) const override

std::unique_ptr< DataModel >	estimate_limit (const QueryGraph &G, const DataModel &data, std::size_t limit, std::size_t offset) const override

std::unique_ptr< DataModel >	estimate_grouping (const QueryGraph &G, const DataModel &data, const std::vector< group_type > &groups) const override

std::unique_ptr< DataModel >	estimate_join (const QueryGraph &G, const DataModel &left, const DataModel &right, const cnf::CNF &condition) const override

template<typename PlanTable >
std::unique_ptr< DataModel >	operator() (estimate_join_all_tag, PlanTable &&PT, const QueryGraph &G, Subproblem to_join, const cnf::CNF &condition) const

std::size_t	predict_cardinality (const DataModel &data) const override

Private Member Functions
void	print (std::ostream &out) const override

Static Private Member Functions
static std::pair< unsigned, bool >	find_spn_id (const SpnDataModel &data, SpnJoin &join)
	Function to compute which of the two join identifiers belongs to the given data model and which attribute to choose.

static std::size_t	max_frequency (const SpnDataModel &data, SpnJoin &join)
	Compute the maximum frequency of values of the attribute in the join.

static std::size_t	max_frequency (const SpnDataModel &data, const ThreadSafePooledString &attribute)
	Compute the maximum frequency of values of the attribute .

Private Attributes
std::unordered_map< ThreadSafePooledString, SpnWrapper * >	table_to_spn_
	‍the map from every table to its respective Spn, initially empty

ThreadSafePooledString	name_of_database_
	‍the name of the database, the estimator is built on

Detailed Description

SpnEstimator that estimates cardinalities based on Sum-Product Networks.

Definition at line 323 of file CardinalityEstimator.hpp.

Member Typedef Documentation

◆ SpnIdentifier

using m::SpnEstimator::SpnIdentifier = std::pair<ThreadSafePooledString, ThreadSafePooledString>

Definition at line 325 of file CardinalityEstimator.hpp.

◆ SpnJoin

using m::SpnEstimator::SpnJoin = std::pair<SpnIdentifier, SpnIdentifier>

Definition at line 326 of file CardinalityEstimator.hpp.

◆ table_spn_map

using m::SpnEstimator::table_spn_map = std::unordered_map<ThreadSafePooledString, std::reference_wrapper<const SpnWrapper> >

Definition at line 327 of file CardinalityEstimator.hpp.

Constructor & Destructor Documentation

◆ SpnEstimator()

m::SpnEstimator::SpnEstimator ( ThreadSafePooledString name_of_database )

inlineexplicit

Definition at line 355 of file CardinalityEstimator.hpp.

◆ ~SpnEstimator()

SpnEstimator::~SpnEstimator ( )

Definition at line 528 of file CardinalityEstimator.cpp.

References table_to_spn_.

Member Function Documentation

◆ empty_model()

std::unique_ptr< DataModel > SpnEstimator::empty_model ( ) const

override

Definition at line 585 of file CardinalityEstimator.cpp.

◆ estimate_filter()

std::unique_ptr< DataModel > SpnEstimator::estimate_filter	(	const QueryGraph &	G,
		const DataModel &	data,
		const cnf::CNF &	filter
	)		const

override

Definition at line 607 of file CardinalityEstimator.cpp.

References M_insist.

◆ estimate_grouping()

std::unique_ptr< DataModel > SpnEstimator::estimate_grouping	(	const QueryGraph &	G,
		const DataModel &	data,
		const std::vector< group_type > &	groups
	)		const

override

Definition at line 646 of file CardinalityEstimator.cpp.

◆ estimate_join()

std::unique_ptr< DataModel > SpnEstimator::estimate_join	(	const QueryGraph &	G,
		const DataModel &	left,
		const DataModel &	right,
		const cnf::CNF &	condition
	)		const

override

Definition at line 672 of file CardinalityEstimator.cpp.

References max_frequency().

◆ estimate_limit()

std::unique_ptr< DataModel > SpnEstimator::estimate_limit	(	const QueryGraph &	G,
		const DataModel &	data,
		std::size_t	limit,
		std::size_t	offset
	)		const

override

Definition at line 639 of file CardinalityEstimator.cpp.

◆ estimate_scan()

std::unique_ptr< DataModel > SpnEstimator::estimate_scan	(	const QueryGraph &	G,
		Subproblem	P
	)		const

override

Definition at line 590 of file CardinalityEstimator.cpp.

References m::SmallBitset::begin(), M_insist, m::SpnWrapper::num_rows(), m::SmallBitset::size(), m::QueryGraph::sources(), and table_to_spn_.

◆ find_spn_id()

std::pair< unsigned, bool > SpnEstimator::find_spn_id	(	const SpnDataModel &	data,
		SpnJoin &	join
	)

staticprivate

Function to compute which of the two join identifiers belongs to the given data model and which attribute to choose.

Parameters

data	the data model
join	the join condition as a pair of identifiers

Returns: a pair of the spn internal id of the attribute and whether the attribute is a primary key

Definition at line 544 of file CardinalityEstimator.cpp.

References m::SpnEstimator::SpnDataModel::spns_.

Referenced by max_frequency().

◆ learn_new_spn()

void SpnEstimator::learn_new_spn ( const ThreadSafePooledString & name_of_table )

Add a new Spn for a table in the database.

Definition at line 536 of file CardinalityEstimator.cpp.

References m::SpnWrapper::learn_spn_table(), name_of_database_, and table_to_spn_.

◆ learn_spns()

void SpnEstimator::learn_spns ( )

Learn an Spn on every table in the database.

Also used to initialize spns after data inserted in tables.

Definition at line 534 of file CardinalityEstimator.cpp.

References m::SpnWrapper::learn_spn_database(), name_of_database_, and table_to_spn_.

◆ max_frequency() [1/2]

std::size_t SpnEstimator::max_frequency	(	const SpnDataModel &	data,
		const ThreadSafePooledString &	attribute
	)

staticprivate

Compute the maximum frequency of values of the attribute .

Parameters

data	the data model
attribute	the attribute

Returns: the maximum frequency of the values of the attribute

Definition at line 573 of file CardinalityEstimator.cpp.

References m::SpnWrapper::estimate_number_distinct_values(), m::SpnWrapper::get_attribute_to_id(), m::SpnEstimator::SpnDataModel::num_rows_, and m::SpnEstimator::SpnDataModel::spns_.

◆ max_frequency() [2/2]

std::size_t SpnEstimator::max_frequency	(	const SpnDataModel &	data,
		SpnJoin &	join
	)

staticprivate

Compute the maximum frequency of values of the attribute in the join.

Parameters

data	the data model
join	the join condition as a pair of identifiers

Returns: the maximum frequency of the values of the attribute

Definition at line 563 of file CardinalityEstimator.cpp.

References m::SpnWrapper::estimate_number_distinct_values(), find_spn_id(), m::SpnEstimator::SpnDataModel::num_rows_, and m::SpnEstimator::SpnDataModel::spns_.

Referenced by estimate_join(), and operator()().

◆ operator()()

template<typename PlanTable >

std::unique_ptr< DataModel > SpnEstimator::operator()	(	estimate_join_all_tag	,
		PlanTable &&	PT,
		const QueryGraph &	G,
		Subproblem	to_join,
		const cnf::CNF &	condition
	)		const

Definition at line 727 of file CardinalityEstimator.cpp.

References m::SmallBitset::begin(), m::SmallBitset::empty(), m::SmallBitset::end(), M_insist, m::SpnEstimator::SpnDataModel::max_frequencies_, max_frequency(), m::SpnEstimator::SpnDataModel::num_rows_, and m::SpnEstimator::SpnDataModel::spns_.

◆ predict_cardinality()

std::size_t SpnEstimator::predict_cardinality ( const DataModel & data ) const

override

Definition at line 792 of file CardinalityEstimator.cpp.

◆ print()

void SpnEstimator::print ( std::ostream & out ) const

overrideprivate

Definition at line 798 of file CardinalityEstimator.cpp.

Field Documentation

◆ name_of_database_

ThreadSafePooledString m::SpnEstimator::name_of_database_

private

‍the name of the database, the estimator is built on

Definition at line 352 of file CardinalityEstimator.hpp.

Referenced by learn_new_spn(), and learn_spns().

◆ table_to_spn_

std::unordered_map<ThreadSafePooledString, SpnWrapper*> m::SpnEstimator::table_to_spn_

private

‍the map from every table to its respective Spn, initially empty

Definition at line 350 of file CardinalityEstimator.hpp.

Referenced by estimate_scan(), learn_new_spn(), learn_spns(), and ~SpnEstimator().

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

include/mutable/catalog/CardinalityEstimator.hpp
src/catalog/CardinalityEstimator.cpp

Data Structures

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ SpnIdentifier

◆ SpnJoin

◆ table_spn_map

Constructor & Destructor Documentation

◆ SpnEstimator()

◆ ~SpnEstimator()

Member Function Documentation

◆ empty_model()

◆ estimate_filter()

◆ estimate_grouping()

◆ estimate_join()

◆ estimate_limit()

◆ estimate_scan()

◆ find_spn_id()

◆ learn_new_spn()

◆ learn_spns()

◆ max_frequency() [1/2]

◆ max_frequency() [2/2]

◆ operator()()

◆ predict_cardinality()

◆ print()

Field Documentation

◆ name_of_database_

◆ table_to_spn_