The gate-building SQL functions the query rewriter calls once per row or per group, in C. More...

#include "postgres.h"
#include "fmgr.h"
#include "catalog/namespace.h"
#include "catalog/pg_type.h"
#include "parser/parse_coerce.h"
#include "lib/stringinfo.h"
#include "utils/array.h"
#include "utils/builtins.h"
#include "utils/hsearch.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/uuid.h"
#include "agg_token.h"
#include "provsql_mmap.h"
#include "provsql_utils.h"

Include dependency graph for gate_builders.c:

Go to the source code of this file.

Classes
struct	PlantedScope
	A working table with planted gates. More...
struct	PlantedEntry
struct	VarcharCast

Macros
#define	WRITTEN_VALUES_MAX 65536

Functions
static void	name_begin (StringInfo buf, const char *prefix)
	Start the name of a gate address.
static void	name_add_uuid (StringInfo buf, const pg_uuid_t *u)
	Append a UUID in the text form of `uuid_out`.
static void	name_add_uuid_array (StringInfo buf, const pg_uuid_t *u, int n)
	Append the text form of a `uuid`[], `"{u1,u2,...}"`.
static pg_uuid_t	name_end (StringInfo buf)
	The version-5 UUID of the name accumulated in `buf`.
static pg_uuid_t	constant_uuid (const char *text)
	The UUID `text` (one of the constants of `provsql_utils.h`).
static const pg_uuid_t *	address_of_zero (void)
static const pg_uuid_t *	address_of_one (void)
static int	token_cmp (const void a, const void b)
static Datum	uuid_result (const pg_uuid_t *u)
static int	filtered_tokens (ArrayType arr, const pg_uuid_t neutral, pg_uuid_t **out)
	The elements of a `uuid`[] that are neither NULL nor `neutral`, in order.
static pg_uuid_t	canonical_address (const char canonical_prefix, const pg_uuid_t children, int n)
	The canonical address, `"<prefix>{sorted children}"`.
static Oid	temp_table_oid (const char *name)
	OID of the temporary table `name` of this backend, if any.
static void	planted_forget (PlantedScope *scope)
static PlantedScope *	planted_open_scope (const char *name, bool reset)
	Open the scope of the working table `name`, just (re)created: forget what was planted for the table it replaces, and for every working table that no longer exists.
static bool	is_planted (const pg_uuid_t *address)
pg_uuid_t	provsql_plant_canonical (const char work_name, gate_type type, const pg_uuid_t children, int n, const pg_uuid_t *target, unsigned info1, unsigned info2)
	Pre-create ("plant") a gate at the canonical address of a multiset of tokens, for the working table of the recursive CTE being lowered.
Datum	planted_scope (PG_FUNCTION_ARGS)
	SQL entry point of `planted_open_scope()`, called by the drivers of recursive CTEs right after they (re)create the working table.
Datum	plant_canonical (PG_FUNCTION_ARGS)
	SQL entry point of `provsql_plant_canonical()`.
static pg_uuid_t	nary_gate (gate_type type, const char plain_prefix, const char canonical_prefix, const pg_uuid_t *children, int n)
	A gate of type `type` over `children`, unless this backend planted one at the canonical address of their multiset.
Datum	provenance_times (PG_FUNCTION_ARGS)
	⊗ of a list of tokens.
Datum	provenance_plus (PG_FUNCTION_ARGS)
	⊕ of an array of tokens.
static char *	varchar_of_argument (FunctionCallInfo fcinfo, int argno)
	`CAST(val AS varchar)` of argument `argno`, as a C string.
void	provsql_gate_builders_forget (void)
	Forget what `gate_builders.c` remembers of the store (planted gates, value gates written).
static pg_uuid_t	value_gate (const char prefix, const char suffix, const char *extra)
	The value gate of the text `str`, at the address named `name` (`"value"` followed by `str`, or `"null"`).
static Datum	semimod_gate (const pg_uuid_t value_token, const pg_uuid_t token)
	The semimod gate `value_token` ⊗ `token`.
static const pg_uuid_t *	semimod_token_argument (FunctionCallInfo fcinfo)
Datum	provenance_semimod (PG_FUNCTION_ARGS)
	The semimodule gate `val` ⊗ `token` of an aggregated row.
Datum	provenance_semimod_nullable (PG_FUNCTION_ARGS)
	`provenance_semimod` for the aggregates that see their NULL inputs (`array_agg`, `json_agg`, ...): a NULL value gives a gate over the constant value gate `gate_null()`.
static bool	same_token (const pg_uuid_t a, const pg_uuid_t b)
Datum	provenance_semimod_nested (PG_FUNCTION_ARGS)
	The semimodule gate of a row whose value is itself an aggregate result: `semimod`(the inner aggregate's gate, `token`).
Datum	provenance_semimod_flat (PG_FUNCTION_ARGS)
	The contributions `semimod`(v_i, token ⊗ k_i) of the aggregate result `val`, whose gate aggregates the contributions `semimod(v_i, k_i)`, for an aggregate of the same kind over it.
Datum	provenance_aggregate (PG_FUNCTION_ARGS)
	The `agg` gate of a group, paired with the aggregate's value.
Datum	provenance_monus (PG_FUNCTION_ARGS)
	`token1` ⊖ `token2`.
Datum	provenance_delta (PG_FUNCTION_ARGS)
	δ(`token`).
Datum	provenance_cmp (PG_FUNCTION_ARGS)
	The comparison gate `left` `op` `right` of a HAVING condition.
Datum	annotate (PG_FUNCTION_ARGS)
	A transparent `annotation` gate over `token`, carrying `extra`.
Datum	inversion_free_key (PG_FUNCTION_ARGS)
	The order key of an input on the inversion-free route, `"K<factor> <bytes of root>:<root><bytes of sec>:<sec>"`.
static pg_uuid_t	assumed_gate (const pg_uuid_t token, const char assumption, unsigned info1)
	The `assumed` wrapper of `token` under `assumption`, with `info1` as the route tag (0 for none).
Datum	provenance_assume (PG_FUNCTION_ARGS)
	Wrap `token` in the assumption marker `assumption` (`'boolean'` or `'absorptive'`).
Datum	assume_boolean (PG_FUNCTION_ARGS)
	The Boolean-assumption wrapper the safe-query rewriter puts on every per-row root, tagged `PROVSQL_ROUTE_SQ_REWRITE`.
Datum	provenance_project (PG_FUNCTION_ARGS)
	The where-provenance `project` gate of `token:` its text lists, for each output position, the input position it comes from (NULL for a position given as 0), as `'{{in`,out},...}'.
Datum	provenance_eq (PG_FUNCTION_ARGS)
	The where-provenance `eq` gate of `token`, equating positions `pos1` and `pos2` (its infos).
Datum	provenance_arith (PG_FUNCTION_ARGS)
	The `arith` gate applying operator `op` (a `provsql_arith_op`, its info1) to `children`, in order.

Variables
static const unsigned char	provsql_ns [UUID_LEN]
	`uuid_ns_provsql()`, the namespace of every gate address.
static HTAB *	planted = NULL
static PlantedScope *	planted_scopes = NULL
static PlantedScope *	planted_current = NULL
static int	planted_next_id = 0
static HTAB *	written_values = NULL

Detailed Description

The gate-building SQL functions the query rewriter calls once per row or per group, in C.

These functions used to be PL/pgSQL. Each inner statement of a PL/pgSQL function runs through SPI, an executor start-up and shutdown of about 2 µs, and their keys went through the text form of uuid[] and back; at one call per output row this was most of the cost of provenance tracking. The C versions build the same gates at the same addresses: a gate is addressed by the version-5 UUID, in the ProvSQL namespace, of a text name ("times{u1,u2}", ...), and the names built here are, byte for byte, the ones the PL/pgSQL code built. The regression test gate_builders keeps the former bodies as reference functions and compares the two.

Definition in file gate_builders.c.

Macro Definition Documentation

◆ WRITTEN_VALUES_MAX

#define WRITTEN_VALUES_MAX 65536

Definition at line 471 of file gate_builders.c.

Function Documentation

◆ address_of_one()

const pg_uuid_t * address_of_one ( void )

static

Definition at line 104 of file gate_builders.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ address_of_zero()

const pg_uuid_t * address_of_zero ( void )

static

Definition at line 97 of file gate_builders.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ annotate()

Datum annotate ( PG_FUNCTION_ARGS )

A transparent annotation gate over token, carrying extra.

The address hashes extra along with the child: two annotations of one token with different texts are different gates. NULL on a NULL token.

Definition at line 841 of file gate_builders.c.

Here is the call graph for this function:

◆ assume_boolean()

Datum assume_boolean ( PG_FUNCTION_ARGS )

The Boolean-assumption wrapper the safe-query rewriter puts on every per-row root, tagged PROVSQL_ROUTE_SQ_REWRITE.

Definition at line 923 of file gate_builders.c.

Here is the call graph for this function:

◆ assumed_gate()

pg_uuid_t assumed_gate	(	const pg_uuid_t *	token,
		const char *	assumption,
		unsigned	info1 )

static

The assumed wrapper of token under assumption, with info1 as the route tag (0 for none).

Definition at line 889 of file gate_builders.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ canonical_address()

pg_uuid_t canonical_address	(	const char *	canonical_prefix,
		const pg_uuid_t *	children,
		int	n )

static

The canonical address, "<prefix>{sorted children}".

Definition at line 146 of file gate_builders.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ constant_uuid()

pg_uuid_t constant_uuid ( const char * text )

static

The UUID text (one of the constants of provsql_utils.h).

Definition at line 93 of file gate_builders.c.

Here is the caller graph for this function:

◆ filtered_tokens()

int filtered_tokens	(	ArrayType *	arr,
		const pg_uuid_t *	neutral,
		pg_uuid_t **	out )

static

The elements of a uuid[] that are neither NULL nor neutral, in order.

Returns: their number; *out is palloc'd.

Definition at line 125 of file gate_builders.c.

Here is the caller graph for this function:

◆ inversion_free_key()

Datum inversion_free_key ( PG_FUNCTION_ARGS )

The order key of an input on the inversion-free route, "K<factor> <bytes of root>:<root><bytes of sec>:<sec>".

Strict.

Definition at line 868 of file gate_builders.c.

◆ is_planted()

bool is_planted ( const pg_uuid_t * address )

static

Definition at line 263 of file gate_builders.c.

Here is the caller graph for this function:

◆ name_add_uuid()

void name_add_uuid	(	StringInfo	buf,
		const pg_uuid_t *	u )

static

Append a UUID in the text form of uuid_out.

Definition at line 52 of file gate_builders.c.

Here is the caller graph for this function:

◆ name_add_uuid_array()

void name_add_uuid_array	(	StringInfo	buf,
		const pg_uuid_t *	u,
		int	n )

static

Append the text form of a uuid[], "{u1,u2,...}".

Definition at line 67 of file gate_builders.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ name_begin()

void name_begin	(	StringInfo	buf,
		const char *	prefix )

static

Start the name of a gate address.

The buffer opens with the namespace, which the version-5 UUID hashes in front of the name, so that the hash runs over the buffer as it is.

Definition at line 45 of file gate_builders.c.

Here is the caller graph for this function:

◆ name_end()

pg_uuid_t name_end ( StringInfo buf )

static

The version-5 UUID of the name accumulated in buf.

Definition at line 80 of file gate_builders.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ nary_gate()

pg_uuid_t nary_gate	(	gate_type	type,
		const char *	plain_prefix,
		const char *	canonical_prefix,
		const pg_uuid_t *	children,
		int	n )

static

A gate of type type over children, unless this backend planted one at the canonical address of their multiset.

Definition at line 335 of file gate_builders.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ plant_canonical()

Datum plant_canonical ( PG_FUNCTION_ARGS )

SQL entry point of provsql_plant_canonical().

Definition at line 314 of file gate_builders.c.

Here is the call graph for this function:

◆ planted_forget()

void planted_forget ( PlantedScope * scope )

static

Definition at line 212 of file gate_builders.c.

Here is the caller graph for this function:

◆ planted_open_scope()

PlantedScope * planted_open_scope	(	const char *	name,
		bool	reset )

static

Open the scope of the working table name, just (re)created: forget what was planted for the table it replaces, and for every working table that no longer exists.

Definition at line 238 of file gate_builders.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ planted_scope()

Datum planted_scope ( PG_FUNCTION_ARGS )

SQL entry point of planted_open_scope(), called by the drivers of recursive CTEs right after they (re)create the working table.

Definition at line 306 of file gate_builders.c.

Here is the call graph for this function:

◆ provenance_aggregate()

Datum provenance_aggregate ( PG_FUNCTION_ARGS )

The agg gate of a group, paired with the aggregate's value.

The address hashes everything the gate records: the aggregate function and the scalar flag (info1 and the high bit of info2), the children, then the result type (the low bits of info2) and the value text (the extra), after a colon each. A gate's infos and text are written once, so what is written has to follow from the address: SUM(x) and AVG(x) over the same children, a scalar and a grouped aggregate, array_agg over integers and over their texts (same children, another result type), or a floating-point sum whose rounding depends on the plan, are all different gates. NULL children are rows whose value was NULL; they are dropped. No child gives 𝟘 for a group, and an agg gate without children for a scalar aggregation, whose value over no row is still defined.

Definition at line 676 of file gate_builders.c.

Here is the call graph for this function:

◆ provenance_arith()

Datum provenance_arith ( PG_FUNCTION_ARGS )

The arith gate applying operator op (a provsql_arith_op, its info1) to children, in order.

Definition at line 1015 of file gate_builders.c.

Here is the call graph for this function:

◆ provenance_assume()

Datum provenance_assume ( PG_FUNCTION_ARGS )

Wrap token in the assumption marker assumption ('boolean' or 'absorptive').

NULL on a NULL token.

Definition at line 908 of file gate_builders.c.

Here is the call graph for this function:

◆ provenance_cmp()

Datum provenance_cmp ( PG_FUNCTION_ARGS )

The comparison gate left op right of a HAVING condition.

A comparison with a NULL operand is unknown in every possible world: the row is annotated 𝟘. Hence not strict: a NULL result would read as the neutral of ⊗ and turn "unknown" into "certainly true".

Definition at line 810 of file gate_builders.c.

Here is the call graph for this function:

◆ provenance_delta()

Datum provenance_delta ( PG_FUNCTION_ARGS )

δ(token).

A NULL token is an untracked source, 𝟙, and δ(𝟙) = 𝟙; δ(𝟘) = 𝟘.

Definition at line 784 of file gate_builders.c.

Here is the call graph for this function:

◆ provenance_eq()

Datum provenance_eq ( PG_FUNCTION_ARGS )

The where-provenance eq gate of token, equating positions pos1 and pos2 (its infos).

Definition at line 989 of file gate_builders.c.

Here is the call graph for this function:

◆ provenance_monus()

Datum provenance_monus ( PG_FUNCTION_ARGS )

token1 ⊖ token2.

A NULL second argument is the row without a match in the outer join of the difference: nothing to subtract, and X ⊖ 𝟘 = X. (Not the NULL ≡ 𝟙 of provenance_times: each combinator reads NULL as its own neutral.) X ⊖ X = 𝟘 and 𝟘 ⊖ X = 𝟘 are applied as well.

Definition at line 751 of file gate_builders.c.

Here is the call graph for this function:

◆ provenance_plus()

Datum provenance_plus ( PG_FUNCTION_ARGS )

⊕ of an array of tokens.

Strict.

A NULL token stands for a row absent from the disjunction: it reads as the ⊕-neutral 𝟘 and is dropped, like gate_zero itself. No survivor gives 𝟘, a single one is returned as it is. (The PL/pgSQL version returned, for no survivor, a plus gate without children: array_length of the empty selection is NULL, which sent that case to the general branch. Evaluators read such a gate as 𝟘, and stored circuits may contain it.)

Definition at line 389 of file gate_builders.c.

Here is the call graph for this function:

◆ provenance_project()

Datum provenance_project ( PG_FUNCTION_ARGS )

The where-provenance project gate of token: its text lists, for each output position, the input position it comes from (NULL for a position given as 0), as '{{in,out},...}'.

Definition at line 939 of file gate_builders.c.

Here is the call graph for this function:

◆ provenance_semimod()

Datum provenance_semimod ( PG_FUNCTION_ARGS )

The semimodule gate val ⊗ token of an aggregated row.

A NULL value does not take part in the aggregate (SQL aggregates skip NULL inputs; count(*) passes a constant 1): no gate, NULL is returned and provenance_aggregate drops it.

Definition at line 545 of file gate_builders.c.

Here is the call graph for this function:

◆ provenance_semimod_flat()

Datum provenance_semimod_flat ( PG_FUNCTION_ARGS )

The contributions semimod(v_i, token ⊗ k_i) of the aggregate result val, whose gate aggregates the contributions semimod(v_i, k_i), for an aggregate of the same kind over it.

token ⊗ (⊕ k_i ⊗ v_i) = ⊕ (token ⊗ k_i) ⊗ v_i: the outer aggregate of the rows of the groups, in every semiring. An empty array for a NULL value, which the outer aggregate skips.

Definition at line 616 of file gate_builders.c.

Here is the call graph for this function:

◆ provenance_semimod_nested()

Datum provenance_semimod_nested ( PG_FUNCTION_ARGS )

The semimodule gate of a row whose value is itself an aggregate result: semimod(the inner aggregate's gate, token).

The contribution of an outer aggregate that reads an aggregate result of another kind (an avg of a count, a max of a sum, an aggregate of an arithmetic expression over aggregates). Such a value is not one value of the database but one per possible world, so the M side of the semimod is the inner aggregate's own gate rather than a gate_value: an evaluator that reads a value per world (the sampler) resolves it, and the closed forms, which read the M side as a constant, decline it.

Definition at line 592 of file gate_builders.c.

Here is the call graph for this function:

◆ provenance_semimod_nullable()

Datum provenance_semimod_nullable ( PG_FUNCTION_ARGS )

provenance_semimod for the aggregates that see their NULL inputs (array_agg, json_agg, ...): a NULL value gives a gate over the constant value gate gate_null().

Definition at line 564 of file gate_builders.c.

Here is the call graph for this function:

◆ provenance_times()

Datum provenance_times ( PG_FUNCTION_ARGS )

⊗ of a list of tokens.

A NULL token is the token slot of an untracked source, which is certain: it reads as the ⊗-neutral 𝟙 and is dropped, like gate_one itself. No survivor gives 𝟙, a single one is returned as it is.

Definition at line 363 of file gate_builders.c.

Here is the call graph for this function:

◆ provsql_gate_builders_forget()

void provsql_gate_builders_forget ( void )

Forget what gate_builders.c remembers of the store (planted gates, value gates written).

For circuit_cleanup, which may remove gates.

Definition at line 473 of file gate_builders.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ provsql_plant_canonical()

pg_uuid_t provsql_plant_canonical	(	const char *	work_name,
		gate_type	type,
		const pg_uuid_t *	children,
		int	n,
		const pg_uuid_t *	target,
		unsigned	info1,
		unsigned	info2 )

Pre-create ("plant") a gate at the canonical address of a multiset of tokens, for the working table of the recursive CTE being lowered.

The gate, of type type (gate_plus or gate_times), has the single child target and the given infos; its address is remembered in this backend, where provenance_plus / provenance_times return it in place of an ordinary gate over children. Defined in gate_builders.c.

Parameters

work_name	working table the tokens belong to; NULL for the one declared last by `planted_scope()`
type	`gate_plus` or `gate_times`
children	the multiset the planted gate stands for
n	number of `children`
target	root of the certified circuit, the gate's single child
info1	first info of the planted gate
info2	second info of the planted gate

Returns: the address of the planted gate

Definition at line 267 of file gate_builders.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ same_token()

bool same_token	(	const pg_uuid_t *	a,
		const pg_uuid_t *	b )

static

Definition at line 738 of file gate_builders.c.

Here is the caller graph for this function:

◆ semimod_gate()

Datum semimod_gate	(	const pg_uuid_t *	value_token,
		const pg_uuid_t *	token )

static

The semimod gate value_token ⊗ token.

Definition at line 517 of file gate_builders.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ semimod_token_argument()

const pg_uuid_t * semimod_token_argument ( FunctionCallInfo fcinfo )

static

Definition at line 531 of file gate_builders.c.

Here is the caller graph for this function:

◆ temp_table_oid()

Oid temp_table_oid ( const char * name )

static

OID of the temporary table name of this backend, if any.

Definition at line 207 of file gate_builders.c.

Here is the caller graph for this function:

◆ token_cmp()

int token_cmp	(	const void *	a,
		const void *	b )

static

Definition at line 111 of file gate_builders.c.

Here is the caller graph for this function:

◆ uuid_result()

Datum uuid_result ( const pg_uuid_t * u )

static

Definition at line 115 of file gate_builders.c.

Here is the caller graph for this function:

◆ value_gate()

pg_uuid_t value_gate	(	const char *	prefix,
		const char *	suffix,
		const char *	extra )

static

The value gate of the text str, at the address named name ("value" followed by str, or "null").

Definition at line 484 of file gate_builders.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ varchar_of_argument()

char * varchar_of_argument	(	FunctionCallInfo	fcinfo,
		int	argno )

static

CAST(val AS varchar) of argument argno, as a C string.

Definition at line 420 of file gate_builders.c.

Here is the caller graph for this function:

Variable Documentation

◆ planted

HTAB* planted = NULL

static

Definition at line 201 of file gate_builders.c.

◆ planted_current

PlantedScope* planted_current = NULL

static

Definition at line 203 of file gate_builders.c.

◆ planted_next_id

int planted_next_id = 0

static

Definition at line 204 of file gate_builders.c.

◆ planted_scopes

PlantedScope* planted_scopes = NULL

static

Definition at line 202 of file gate_builders.c.

◆ provsql_ns

const unsigned char provsql_ns[UUID_LEN]

static

Initial value:

                                      = {
  0x92, 0x0d, 0x4f, 0x02, 0x87, 0x18, 0x53, 0x19,
  0x95, 0x32, 0xd4, 0xab, 0x83, 0xa6, 0x44, 0x89
}

uuid_ns_provsql(), the namespace of every gate address.

Definition at line 34 of file gate_builders.c.

◆ written_values

HTAB* written_values = NULL

static

Definition at line 470 of file gate_builders.c.

Classes

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ WRITTEN_VALUES_MAX

Function Documentation

◆ address_of_one()

◆ address_of_zero()

◆ annotate()

◆ assume_boolean()

◆ assumed_gate()

◆ canonical_address()

◆ constant_uuid()

◆ filtered_tokens()

◆ inversion_free_key()

◆ is_planted()

◆ name_add_uuid()

◆ name_add_uuid_array()

◆ name_begin()

◆ name_end()

◆ nary_gate()

◆ plant_canonical()

◆ planted_forget()

◆ planted_open_scope()

◆ planted_scope()

◆ provenance_aggregate()

◆ provenance_arith()

◆ provenance_assume()

◆ provenance_cmp()

◆ provenance_delta()

◆ provenance_eq()

◆ provenance_monus()

◆ provenance_plus()

◆ provenance_project()

◆ provenance_semimod()

◆ provenance_semimod_flat()

◆ provenance_semimod_nested()

◆ provenance_semimod_nullable()

◆ provenance_times()

◆ provsql_gate_builders_forget()

◆ provsql_plant_canonical()

◆ same_token()

◆ semimod_gate()

◆ semimod_token_argument()

◆ temp_table_oid()

◆ token_cmp()

◆ uuid_result()

◆ value_gate()

◆ varchar_of_argument()

Variable Documentation

◆ planted

◆ planted_current

◆ planted_next_id

◆ planted_scopes

◆ provsql_ns

◆ written_values