WasmOperator.cpp File Reference

#include "backend/WasmOperator.hpp"
#include "backend/Interpreter.hpp"
#include "backend/WasmAlgo.hpp"
#include "backend/WasmMacro.hpp"
#include <mutable/catalog/Catalog.hpp>
#include <mutable/parse/AST.hpp>
#include <mutable/util/fn.hpp>
#include <numeric>

Include dependency graph for WasmOperator.cpp:

Go to the source code of this file.

Data Structures
struct	aggregate_info_t
	‍helper struct for aggregates More...
struct	avg_aggregate_info_t
	‍helper struct for AVG aggregates More...
struct	index_scan_bounds_t
	‍helper struct holding the bounds for index scan More...
struct	print_info

Macros
#define	SET_CALLBACK_FNS(INDEX, KEY)
#define	RESOLVE_KEYTYPE(INDEX)
#define	SET_CALLBACK_FNS(INDEX, KEY)    scan_fn = M_STR(idx_scan_##INDEX##_##KEY)
#define	RESOLVE_KEYTYPE(INDEX)
#define	RESOLVE_INDEX_METHOD(ATTRTYPE, SQLTYPE)    index_scan_resolve_index_method<IndexMethod, ATTRTYPE, SQLTYPE>(bounds, M, std::move(setup), std::move(pipeline), std::move(teardown))
#define	DECLARE(CLASS)
#define	INSTANTIATE(CLASS)

Functions
void	write_result_set (const Schema &schema, const DataLayoutFactory &factory, uint32_t window_size, const m::wasm::MatchBase &child)
	Emits code to write the result set of the Schema schema using the DataLayout created by factory.
std::pair< std::vector< aggregate_info_t >, std::unordered_map< Schema::Identifier, avg_aggregate_info_t > >	compute_aggregate_info (const std::vector< std::reference_wrapper< const FnApplicationExpr > > &aggregates, const Schema &schema, std::size_t aggregates_offset=0)
	Computes and returns information about the aggregates aggregates which are contained in the schema schema starting at offset aggregates_offset.
std::pair< std::vector< Schema::Identifier >, std::vector< Schema::Identifier > >	decompose_equi_predicate (const cnf::CNF &cnf, const Schema &schema_left)
	Decompose the equi-predicate cnf, i.e.
U32x1	get_num_rows (const ThreadSafePooledString &table_name)
	Returns the number of rows of table table_name.
Ptr< void >	get_base_address (const ThreadSafePooledString &table_name)
	Returns a pointer to the beginning of table table_name in the WebAssembly linear memory.
uint32_t	compute_initial_ht_capacity (const Operator &op, double load_factor)
	Computes the initial hash table capacity for op.
bool	is_valid_bound (const ast::Expr &expr)
	Returns true iff expr is a valid bound.
std::pair< const Constant &, bool >	get_valid_bound (const ast::Expr &expr)
	Given an Expr expr representing a valid bound, returns a pair consiting of a constant and a boolean flag indicating whether the constant is negative.
index_scan_bounds_t	extract_index_scan_bounds (const cnf::CNF &cnf)
	Extracts the bounds for performing index scan from CNF cnf.
template<idx::IndexMethod IndexMethod, typename Index , sql_type SqlT>
void	index_scan_codegen_compilation (const Index &index, const index_scan_bounds_t &bounds, const Match< IndexScan< IndexMethod > > &M, setup_t setup, pipeline_t pipeline, teardown_t teardown)
template<idx::IndexMethod IndexMethod, typename Index >
void	index_scan_codegen_interpretation (const Index &index, const index_scan_bounds_t &bounds, const Match< IndexScan< IndexMethod > > &M, setup_t setup, pipeline_t pipeline, teardown_t teardown)
template<idx::IndexMethod IndexMethod, typename Index , sql_type SqlT>
void	index_scan_codegen_hybrid (const Index &index, const index_scan_bounds_t &bounds, const Match< IndexScan< IndexMethod > > &M, setup_t setup, pipeline_t pipeline, teardown_t teardown)
template<idx::IndexMethod IndexMethod, typename Index , sql_type SqlT>
void	index_scan_resolve_strategy (const Index &index, const index_scan_bounds_t &bounds, const Match< IndexScan< IndexMethod > > &M, setup_t setup, pipeline_t pipeline, teardown_t teardown)
	Resolves the index scan strategy and calls the appropriate codegen function.
template<idx::IndexMethod IndexMethod, typename AttrT , sql_type SqlT>
void	index_scan_resolve_index_method (const index_scan_bounds_t &bounds, const Match< IndexScan< IndexMethod > > &M, setup_t setup, pipeline_t pipeline, teardown_t teardown)
	Resolves the index method and calls the appropriate codegen function.
template<idx::IndexMethod IndexMethod>
void	index_scan_resolve_attribute_type (const Match< IndexScan< IndexMethod > > &M, setup_t setup, pipeline_t pipeline, teardown_t teardown)
	Resolves the attribute type and calls the appropriate codegen function.

Macro Definition Documentation

DECLARE

#define DECLARE

(

CLASS

)

Value:

    void operator()(Const<CLASS> &M) override { \
        if constexpr (PreOrder) try { callback_(M); } catch (visit_skip_subtree) { return; } \
        super::operator()(M); \
        if constexpr (not PreOrder) callback_(M); \
    }

Definition at line 6360 of file WasmOperator.cpp.

INSTANTIATE

#define INSTANTIATE

(

CLASS

)

Value:

    template struct m::wasm::CLASS; \
    template struct m::Match<m::wasm::CLASS>;

Definition at line 6389 of file WasmOperator.cpp.

RESOLVE_INDEX_METHOD

#define RESOLVE_INDEX_METHOD	(		ATTRTYPE,
			SQLTYPE
	)		index_scan_resolve_index_method<IndexMethod, ATTRTYPE, SQLTYPE>(bounds, M, std::move(setup), std::move(pipeline), std::move(teardown))

RESOLVE_KEYTYPE [1/2]

#define RESOLVE_KEYTYPE

(

INDEX

)

Value:

        if constexpr(std::same_as<SqlT, _Boolx1>) { \
            SET_CALLBACK_FNS(INDEX, b); \
        } else if constexpr(std::same_as<sql_type, _I8x1>) { \
            SET_CALLBACK_FNS(INDEX, i1); \
        } else if constexpr(std::same_as<sql_type, _I16x1>) { \
            SET_CALLBACK_FNS(INDEX, i2); \
        } else if constexpr(std::same_as<sql_type, _I32x1>) { \
            SET_CALLBACK_FNS(INDEX, i4); \
        } else if constexpr(std::same_as<sql_type, _I64x1>) { \
            SET_CALLBACK_FNS(INDEX, i8); \
        } else if constexpr(std::same_as<sql_type, _Floatx1>) { \
            SET_CALLBACK_FNS(INDEX, f); \
        } else if constexpr(std::same_as<sql_type, _Doublex1>) { \
            SET_CALLBACK_FNS(INDEX, d); \
        } else if constexpr(std::same_as<sql_type, NChar>) { \
            SET_CALLBACK_FNS(IDNEX, p); \
        } else { \
            M_unreachable("incompatible SQL type"); \
        }

RESOLVE_KEYTYPE [2/2]

#define RESOLVE_KEYTYPE

(

INDEX

)

Value:

    if constexpr(std::same_as<SqlT, _Boolx1>) { \
        SET_CALLBACK_FNS(INDEX, b); \
    } else if constexpr(std::same_as<sql_type, _I8x1>) { \
        SET_CALLBACK_FNS(INDEX, i1); \
    } else if constexpr(std::same_as<sql_type, _I16x1>) { \
        SET_CALLBACK_FNS(INDEX, i2); \
    } else if constexpr(std::same_as<sql_type, _I32x1>) { \
        SET_CALLBACK_FNS(INDEX, i4); \
    } else if constexpr(std::same_as<sql_type, _I64x1>) { \
        SET_CALLBACK_FNS(INDEX, i8); \
    } else if constexpr(std::same_as<sql_type, _Floatx1>) { \
        SET_CALLBACK_FNS(INDEX, f); \
    } else if constexpr(std::same_as<sql_type, _Doublex1>) { \
        SET_CALLBACK_FNS(INDEX, d); \
    } else if constexpr(std::same_as<sql_type, NChar>) { \
        SET_CALLBACK_FNS(IDNEX, p); \
    } else { \
        M_unreachable("incompatible SQL type"); \
    }

SET_CALLBACK_FNS [1/2]

#define SET_CALLBACK_FNS	(		INDEX,
			KEY
	)

Value:

        scan_fn        = M_STR(idx_scan_##INDEX##_##KEY); \
        lower_bound_fn = M_STR(idx_lower_bound_##INDEX##_##KEY); \
        upper_bound_fn = M_STR(idx_upper_bound_##INDEX##_##KEY)

SET_CALLBACK_FNS [2/2]

#define SET_CALLBACK_FNS	(		INDEX,
			KEY
	)		scan_fn = M_STR(idx_scan_##INDEX##_##KEY)

Function Documentation

compute_aggregate_info()

std::pair< std::vector< aggregate_info_t >, std::unordered_map< Schema::Identifier, avg_aggregate_info_t > > compute_aggregate_info	(	const std::vector< std::reference_wrapper< const FnApplicationExpr > > &	aggregates,
		const Schema &	schema,
		std::size_t	aggregates_offset = 0
	)

Computes and returns information about the aggregates aggregates which are contained in the schema schema starting at offset aggregates_offset.

The firstly returned element contains general information about each aggregates like its identifier, type, function type, and arguments. The secondly returned element contains additional information about each AVG aggregates like a flag to determine whether it can be computed using a running AVG or lazily at the end. Either way, the corresponding running count and an optional sum are contained in these elements, too.

Definition at line 824 of file WasmOperator.cpp.

References m::and, aggregate_info_t::entry, m::Catalog::Get(), m::Type::Get_Double(), m::Type::Get_Integer(), M_insist, m::Schema::entry_type::NOT_NULLABLE, and m::Schema::num_entries().

Referenced by m::wasm::Aggregation::execute(), m::wasm::HashBasedGrouping::execute(), m::wasm::HashBasedGroupJoin::execute(), and m::wasm::OrderedGrouping::execute().

compute_initial_ht_capacity()

uint32_t compute_initial_ht_capacity	(	const Operator &	op,
		double	load_factor
	)

Computes the initial hash table capacity for op.

The function ensures that the initial capacity is in the range [0, 2^32 - 1] such that the capacity does not exceed the uint32_t value limit.

Definition at line 980 of file WasmOperator.cpp.

References m::wasm::op.

Referenced by m::wasm::HashBasedGrouping::execute(), m::wasm::HashBasedGroupJoin::execute(), and m::wasm::SimpleHashJoin< UniqueBuild, Predicated >::execute().

decompose_equi_predicate()

std::pair< std::vector< Schema::Identifier >, std::vector< Schema::Identifier > > decompose_equi_predicate	(	const cnf::CNF &	cnf,
		const Schema &	schema_left
	)

Decompose the equi-predicate cnf, i.e.

a conjunction of equality comparisons of each two designators, into all identifiers contained in schema schema_left (returned as first element) and all identifiers not contained in the aforementioned schema (return as second element).

Definition at line 940 of file WasmOperator.cpp.

References m::and, m::wasm::binary(), m::Schema::has(), and M_insist.

Referenced by m::wasm::SortMergeJoin< SortLeft, SortRight, Predicated, CmpPredicated >::adapt_post_conditions(), m::wasm::HashBasedGroupJoin::execute(), m::wasm::SimpleHashJoin< UniqueBuild, Predicated >::execute(), and m::wasm::HashBasedGroupJoin::pre_condition().

extract_index_scan_bounds()

index_scan_bounds_t extract_index_scan_bounds

(

const cnf::CNF &

cnf

)

Extracts the bounds for performing index scan from CNF cnf.

CNFs must either consist of

1. a single equality predicate, e.g. "x = 42" or
2. one or two predicates defining a (closed or open) range, e.g. "x > 42 AND x < 109" or "x < 42".

Definition at line 1028 of file WasmOperator.cpp.

References m::and, index_scan_bounds_t::attribute, m::wasm::binary(), m::cnf::CNF::get_required(), index_scan_bounds_t::hi, index_scan_bounds_t::is_inclusive_hi, index_scan_bounds_t::is_inclusive_lo, is_valid_bound(), index_scan_bounds_t::lo, M_insist, and M_unreachable.

Referenced by index_scan_resolve_attribute_type().

get_base_address()

Ptr< void > get_base_address

(

const ThreadSafePooledString &

table_name

)

Returns a pointer to the beginning of table table_name in the WebAssembly linear memory.

Definition at line 971 of file WasmOperator.cpp.

References m::wasm::Module::Get(), and m::wasm::Module::get_global().

Referenced by m::wasm::Scan< SIMDfied >::execute(), m::wasm::SortMergeJoin< SortLeft, SortRight, Predicated, CmpPredicated >::execute(), index_scan_codegen_compilation(), index_scan_codegen_hybrid(), and index_scan_codegen_interpretation().

get_num_rows()

U32x1 get_num_rows

(

const ThreadSafePooledString &

table_name

)

Returns the number of rows of table table_name.

Definition at line 963 of file WasmOperator.cpp.

References m::wasm::Module::Get(), and m::wasm::Module::get_global().

Referenced by m::wasm::Scan< SIMDfied >::execute(), and m::wasm::SortMergeJoin< SortLeft, SortRight, Predicated, CmpPredicated >::execute().

get_valid_bound()

std::pair< const Constant &, bool > get_valid_bound

(

const ast::Expr &

expr

)

Given an Expr expr representing a valid bound, returns a pair consiting of a constant and a boolean flag indicating whether the constant is negative.

Definition at line 1017 of file WasmOperator.cpp.

References is_valid_bound(), and M_insist.

Referenced by index_scan_codegen_compilation(), index_scan_codegen_hybrid(), and index_scan_codegen_interpretation().

index_scan_codegen_compilation()

template<idx::IndexMethod IndexMethod, typename Index , sql_type SqlT>

void index_scan_codegen_compilation	(	const Index &	index,
		const index_scan_bounds_t &	bounds,
		const Match< IndexScan< IndexMethod > > &	M,
		setup_t	setup,
		pipeline_t	pipeline,
		teardown_t	teardown
	)

Definition at line 1468 of file WasmOperator.cpp.

References m::wasm::Module::Allocator, m::wasm::bool, m::option_configs::CALLBACK, m::wasm::compile_load_point_access(), m::wasm::Module::emit_call(), m::option_configs::EXPOSED_MEMORY, m::wasm::Module::Get(), m::wasm::CodeGenContext::Get(), get_base_address(), m::wasm::CodeGenContext::get_literal_address(), m::wasm::CodeGenContext::get_literal_raw_address(), get_valid_bound(), m::WasmEngine::Get_Wasm_Context_By_ID(), index_scan_bounds_t::hi, m::wasm::Module::ID(), IF, m::options::index_scan_compilation_strategy, m::options::index_scan_materialization_strategy, m::option_configs::INLINE, index_scan_bounds_t::is_inclusive_hi, index_scan_bounds_t::is_inclusive_lo, index_scan_bounds_t::lo, M_insist, M_unreachable, m::option_configs::MEMORY, RESOLVE_KEYTYPE, m::wasm::Select(), m::ast::Expr::type(), m::wasm::U, Wasm_insist, and WHILE.

index_scan_codegen_hybrid()

template<idx::IndexMethod IndexMethod, typename Index , sql_type SqlT>

void index_scan_codegen_hybrid	(	const Index &	index,
		const index_scan_bounds_t &	bounds,
		const Match< IndexScan< IndexMethod > > &	M,
		setup_t	setup,
		pipeline_t	pipeline,
		teardown_t	teardown
	)

< id of index in context

Definition at line 1761 of file WasmOperator.cpp.

References m::wasm::Module::Allocator, m::wasm::bool, m::option_configs::CALLBACK, m::wasm::clone(), m::wasm::compile_load_point_access(), m::wasm::Module::emit_call(), m::option_configs::EXPOSED_MEMORY, m::wasm::Module::Get(), get_base_address(), get_valid_bound(), m::WasmEngine::Get_Wasm_Context_By_ID(), index_scan_bounds_t::hi, m::wasm::Module::ID(), IF, m::options::index_scan_compilation_strategy, m::options::index_scan_materialization_strategy, m::option_configs::INLINE, index_scan_bounds_t::is_inclusive_hi, index_scan_bounds_t::is_inclusive_lo, index_scan_bounds_t::lo, M_insist, M_unreachable, m::option_configs::MEMORY, RESOLVE_KEYTYPE, m::wasm::Select(), m::wasm::U, and WHILE.

index_scan_codegen_interpretation()

template<idx::IndexMethod IndexMethod, typename Index >

void index_scan_codegen_interpretation	(	const Index &	index,
		const index_scan_bounds_t &	bounds,
		const Match< IndexScan< IndexMethod > > &	M,
		setup_t	setup,
		pipeline_t	pipeline,
		teardown_t	teardown
	)

Definition at line 1645 of file WasmOperator.cpp.

References m::wasm::Module::Allocator, m::wasm::bool, m::wasm::compile_load_point_access(), FUNCTION, m::wasm::CodeGenContext::Get(), get_base_address(), get_valid_bound(), index_scan_bounds_t::hi, m::options::index_scan_materialization_strategy, m::option_configs::INLINE, index_scan_bounds_t::is_inclusive_hi, index_scan_bounds_t::is_inclusive_lo, index_scan_bounds_t::lo, M_insist, M_unreachable, m::wasm::make_signed(), m::option_configs::MEMORY, PARAMETER, m::wasm::CodeGenContext::scoped_environment(), and WHILE.

index_scan_resolve_attribute_type()

template<idx::IndexMethod IndexMethod>

void index_scan_resolve_attribute_type	(	const Match< IndexScan< IndexMethod > > &	M,
		setup_t	setup,
		pipeline_t	pipeline,
		teardown_t	teardown
	)

Resolves the attribute type and calls the appropriate codegen function.

Definition at line 1974 of file WasmOperator.cpp.

References extract_index_scan_bounds(), M_unreachable, m::wasm::n, RESOLVE_INDEX_METHOD, and m::visit().

Referenced by m::wasm::IndexScan< IndexMethod >::execute().

index_scan_resolve_index_method()

template<idx::IndexMethod IndexMethod, typename AttrT , sql_type SqlT>

void index_scan_resolve_index_method	(	const index_scan_bounds_t &	bounds,
		const Match< IndexScan< IndexMethod > > &	M,
		setup_t	setup,
		pipeline_t	pipeline,
		teardown_t	teardown
	)

Resolves the index method and calls the appropriate codegen function.

Definition at line 1946 of file WasmOperator.cpp.

References m::wasm::and, m::idx::Array, index_scan_bounds_t::attribute, m::Catalog::Get(), m::Catalog::get_database_in_use(), m::Schema::entry_type::id, M_unreachable, m::Schema::Identifier::name, m::Database::name, and m::idx::Rmi.

index_scan_resolve_strategy()

template<idx::IndexMethod IndexMethod, typename Index , sql_type SqlT>

void index_scan_resolve_strategy	(	const Index &	index,
		const index_scan_bounds_t &	bounds,
		const Match< IndexScan< IndexMethod > > &	M,
		setup_t	setup,
		pipeline_t	pipeline,
		teardown_t	teardown
	)

Resolves the index scan strategy and calls the appropriate codegen function.

Definition at line 1931 of file WasmOperator.cpp.

References m::option_configs::COMPILATION, m::option_configs::HYBRID, m::options::index_scan_strategy, m::option_configs::INTERPRETATION, and M_unreachable.

is_valid_bound()

bool is_valid_bound

(

const ast::Expr &

expr

)

Returns true iff expr is a valid bound.

Definition at line 1004 of file WasmOperator.cpp.

References m::and.

Referenced by extract_index_scan_bounds(), get_valid_bound(), and m::wasm::IndexScan< IndexMethod >::pre_condition().

write_result_set()

void write_result_set	(	const Schema &	schema,
		const DataLayoutFactory &	factory,
		uint32_t	window_size,
		const m::wasm::MatchBase &	child
	)

Emits code to write the result set of the Schema schema using the DataLayout created by factory.

The result set is either materialized entirely (if window_size equals 0 indicating infinity) or only partially (if window_size does not equal 0 indicating the used batch size). To emit the code at the correct position, code generation is delegated to the child physical operator child.

< variable to locally count

‍global counter backup since the following code may be called multiple times

< variable to locally count additional result tuples

Definition at line 641 of file WasmOperator.cpp.

References m::and, m::wasm::Buffer< IsGlobal >::base_address(), m::storage::DataLayoutFactory::clone(), m::wasm::Buffer< IsGlobal >::consume(), m::Schema::deduplicate(), m::Schema::drop_constants(), m::wasm::Module::emit_call(), m::MatchBase::execute(), FUNCTION, m::wasm::Module::Get(), m::wasm::CodeGenContext::Get(), m::WasmEngine::Get_Wasm_Context_By_ID(), m::wasm::Module::ID(), IF, m::wasm::CodeGenContext::inc_num_tuples(), M_insist, m::setup_t::Make_Without_Parent(), m::teardown_t::Make_Without_Parent(), m::Schema::num_entries(), m::wasm::num_simd_lanes, m::wasm::CodeGenContext::num_tuples(), m::wasm::CodeGenContext::scoped_environment(), m::wasm::CodeGenContext::set_num_tuples(), m::wasm::Buffer< IsGlobal >::setup(), m::wasm::Buffer< IsGlobal >::size(), m::wasm::Buffer< IsGlobal >::teardown(), and m::U.

Referenced by m::wasm::Callback< SIMDfied >::execute(), and m::wasm::Print< SIMDfied >::execute().