ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
having_semantics.hpp
Go to the documentation of this file.
1/**
2 * @file having_semantics.hpp
3 * @brief Provenance evaluation helper for HAVING-clause circuits.
4 *
5 * When a query includes a HAVING clause, ProvSQL creates a special
6 * sub-circuit that encodes the aggregate predicate. Before the main
7 * provenance circuit can be evaluated over a semiring, these HAVING
8 * sub-circuits must first be evaluated to determine which groups
9 * pass the filter.
10 *
11 * The single public entry point @c provsql_having() rewrites HAVING
12 * comparison gates in the circuit, for any compiled semiring, by
13 * enumerating possible worlds -- or, for @c MIN / @c MAX against a
14 * constant, by the equivalent single-scan closed form: in every
15 * absorptive semiring for the existential comparisons (@c MIN below,
16 * @c MAX above a constant), and when ⊗ moreover distributes over ⊖ for
17 * the others. If the HAVING gate type is incompatible with the
18 * requested semiring, the function is a no-op.
19 */
20#ifndef PROVSQL_HAVING_SEMANTICS_HPP
21#define PROVSQL_HAVING_SEMANTICS_HPP
22
23#include <algorithm>
24#include <cstdint>
25#include <cmath>
26#include <functional>
27#include <map>
28#include <set>
29#include <stdexcept>
30#include <string>
31#include <vector>
32
33#include "GenericCircuit.hpp"
34extern "C" {
35#include "access/xact.h"
36}
37#include "provsql_utils.h"
38#include "subset.hpp"
39#include "Aggregation.h"
40
41/** @cond INTERNAL */
42namespace provsql_having_detail {
43/** @brief One comparison of a joint resolution: @c L @c op @c R. */
44struct JointAtom {
45 gate_t L;
46 gate_t R;
48};
49std::vector<gate_t> collect_sp_cmp_gates(GenericCircuit &c, gate_t start);
50bool extract_constant_string(GenericCircuit &c, gate_t x, std::string &C_out);
51bool semimod_extract_string_and_K(GenericCircuit &c, gate_t semimod_gate, std::string &m_out, gate_t &k_gate_out);
52bool aggtype_is_text(unsigned oid);
53bool aggtype_is_integer(unsigned oid);
54bool aggtype_is_boolean(unsigned oid);
55// True if @p oid is boolean, or an array whose element type is boolean. Used
56// by the array_agg comparison to reconcile PostgreSQL's two boolean text forms
57// (scalar 'true'/'false' vs array-element 't'/'f').
58bool aggtype_elem_is_boolean(unsigned oid);
59bool aggtype_is_numeric(unsigned oid);
60
61/**
62 * @brief Map values of type @p typoid, given as text, and a threshold to
63 * their dense ranks under the type's comparison function.
64 *
65 * @return @c false when the type has no comparison function.
66 */
67bool rank_values_by_type(unsigned typoid, const std::vector<std::string> &vals,
68 const std::string &threshold,
69 std::vector<long> &ranks, long &threshold_rank);
70/** @brief @c PROVSQL_GATE_NULL_UUID, the value gate of the NULL value. */
71constexpr const char *GATE_NULL_UUID = PROVSQL_GATE_NULL_UUID;
72
73/**
74 * @brief The text standing for a NULL array element, on both sides of an
75 * @c array_agg comparison.
76 *
77 * It starts with a NUL byte, which no PostgreSQL text value contains, so it
78 * equals itself and no actual element: exactly how array equality treats
79 * NULL elements.
80 */
81inline const std::string &array_null_element() {
82 static const std::string null_element("\0NULL", 5);
83 return null_element;
84}
85
86bool parse_array_literal(const std::string &s, std::vector<std::string> &out);
87bool parse_decimal_scaled(const std::string &s, long &mantissa, int &scale);
88bool rescale_to(long mantissa, int scale, int target_scale, long &out);
89ComparisonOperator map_cmp_op(GenericCircuit &c, gate_t cmp_gate, bool &ok);
91}
92/** @endcond */
93
94/**
95 * @brief Rewrite HAVING comparison gates in the circuit into their
96 * possible-world provenance (world enumeration, or the MIN / MAX
97 * single-scan closed form where the semiring allows it).
98 *
99 * @tparam SemiringT The semiring type used for evaluation.
100 * @tparam MapT The provenance mapping type (gate_t → semiring value).
101 * @param c Circuit to rewrite.
102 * @param g Root gate of the sub-circuit to inspect.
103 * @param mapping Provenance mapping updated in place.
104 * @param S Semiring instance (default-constructed for stateless semirings).
105 */
106template <typename SemiringT, typename MapT>
109 gate_t g,
110 MapT &mapping,
111 SemiringT S = SemiringT{})
112{
113 using namespace provsql_having_detail;
114
115 std::vector<gate_t> cmp_gates = collect_sp_cmp_gates(c, g);
116
117 if (cmp_gates.empty())
118 return;
119
120 // The provenance of a selection on aggregates is a sum over the worlds of
121 // the group, each a product of the annotations of its present and missing
122 // contributors: a product in no order of the query's, which only a
123 // commutative semiring reads unambiguously.
124 if (!S.commutative())
125 throw CircuitRefusal(
126 PROVSQL_GAP, "having-noncommutative",
127 "A HAVING condition's provenance is a product over the worlds "
128 "of its group, in no order of the query: it has no value in a "
129 "semiring whose multiplication does not commute.");
130
131 // Whether the world enumeration over these contributor annotations can
132 // be built *certified*: the semiring persists d-DNNF certificates
133 // (circuit-building BoolExpr), every contributor is an independent
134 // literal (base Bernoulli or constant) so world terms are decomposable,
135 // no literal repeats (a repeat would couple two contributors), and the
136 // contributor count is small enough that the complete-worlds
137 // enumeration the certificate requires stays affordable.
138 auto certifiable_contributors =
139 [&](const std::vector<typename SemiringT::value_type> &kv) -> bool {
140 if (!S.certifying())
141 return false;
142 if (kv.size() > 16)
143 return false;
144 for (size_t i = 0; i < kv.size(); ++i) {
145 if (!S.independent_literal(kv[i]))
146 return false;
147 // Distinctness among non-constant literals (constants are
148 // variable-free, so repeats of one() / zero() are harmless).
149 if (kv[i] == S.one() || kv[i] == S.zero())
150 continue;
151 for (size_t j = 0; j < i; ++j)
152 if (kv[j] == kv[i])
153 return false;
154 }
155 return true;
156 };
157
158 // Combine a set of valid-world bitmasks (from an exhaustive enumeration) into
159 // the m-semiring predicate-provenance. Shared by every HAVING domain that
160 // enumerates exact worlds (the numeric comparison, the boolean aggregates
161 // and array_agg): a certifying semiring gets one certified world term per
162 // world under a deterministic OR; otherwise each world contributes
163 // ∏present ⊗ (1 ⊖ ⊕missing). The monus factor is dropped when the
164 // enumeration is an @p upset (an absorptive semiring pruned the family to
165 // a generating subfamily of minimal worlds) or when the family is
166 // @p monotone -- closed under supersets, i.e. the complete valid worlds of
167 // a comparison preserved as the group grows -- and the semiring is
168 // idempotent: over such a family the monus cancels from the possible-world
169 // sum, ⊕_W ann_U(W) = ⊕_W ∏present (Lean Having.witness_identity, which
170 // needs idempotence only; absorptivity further collapses the sum to the
171 // minimal worlds, Having.witness_minimal, which is what the upset prune
172 // exploits).
173 auto combine_exhaustive_worlds =
174 [&](const std::vector<mask_t> &worlds,
175 const std::vector<typename SemiringT::value_type> &kvals,
176 bool upset, bool monotone) -> typename SemiringT::value_type {
177 if (worlds.empty())
178 return S.zero();
179
180 if (certifiable_contributors(kvals)) {
181 std::vector<typename SemiringT::value_type> disjuncts;
182 disjuncts.reserve(worlds.size());
183 for (const auto &mask : worlds) {
184 std::vector<typename SemiringT::value_type> present, missing;
186 for (size_t i = 0; i < kvals.size(); ++i)
187 (mask[i] ? present : missing).push_back(kvals[i]);
188 disjuncts.push_back(S.certified_world_term(present, missing));
189 }
190 return S.certified_exclusive_plus(disjuncts);
191 }
192
193 std::vector<typename SemiringT::value_type> disjuncts;
194 disjuncts.reserve(worlds.size());
195 const size_t n = kvals.size();
196 const bool no_monus = upset || (monotone && S.idempotent());
197
198 for (const auto &mask : worlds) {
199 std::vector<typename SemiringT::value_type> present, missing;
200 present.reserve(n);
201 missing.reserve(n);
203
204 for (size_t i = 0; i < n; ++i) {
205 if (mask[i]) {
206 if (kvals[i] != S.one())
207 present.push_back(kvals[i]);
208 } else if (!no_monus) {
209 if (kvals[i] != S.zero())
210 missing.push_back(kvals[i]);
211 }
212 }
213
214 auto present_prod = S.times(present);
215
216 if (missing.empty()) {
217 disjuncts.push_back(std::move(present_prod));
218 } else {
219 auto monus_factor = S.monus(S.one(), S.plus(missing));
220 auto term = monus_factor;
221 if (present_prod != S.one())
222 term = S.times(std::vector<typename SemiringT::value_type>{
223 present_prod, monus_factor});
224 disjuncts.push_back(std::move(term));
225 }
226 }
227
228 return S.plus(disjuncts);
229 };
230
231 // Single-scan closed form for MIN / MAX against a constant in an
232 // absorptive m-semiring. Writing L, L', G, G', E for the ⊕-sums of
233 // the contributors whose value is <, <=, >=, >, = C, the possible-world
234 // provenance of MIN(a) op C is
235 // MIN < C : L MIN >= C : (1 ⊖ L) ⊗ G
236 // MIN <= C : L' MIN > C : (1 ⊖ L') ⊗ G'
237 // MIN = C : (1 ⊖ L) ⊗ E MIN <> C : L ⊕ (1 ⊖ L') ⊗ G'
238 // and MAX is the mirror image (exchange < and >). The existential
239 // comparisons (MIN <, <=; MAX >, >=) hold in the worlds meeting the set
240 // of witnesses, an upward-closed family whose minimal elements are the
241 // singletons: the monus cancels from the possible-world sum and
242 // absorptivity alone makes the ⊕-sum over the witnesses exact (Lean
243 // Having.sum_ann_meet, HavingMonotone.minLe_site_rewrite and its three
244 // siblings). The other comparisons carry the 1 ⊖ factor excluding
245 // every world containing a spoiler, and their closed form is proved
246 // only when ⊗ moreover distributes over ⊖, which combines that factor
247 // with the witnesses by one ⊗ (Lean Having.minScan_correct /
248 // Having.maxScan_correct); without distributivity they are not
249 // proved, and not taken. The empty world never satisfies the
250 // comparison (MIN / MAX of an empty group is NULL), so scalar
251 // aggregation needs no special case.
252 auto min_max_scan =
253 [&](const std::vector<long> &mvals, long C,
254 const std::vector<typename SemiringT::value_type> &kvals,
256 AggregationOperator agg_kind) -> typename SemiringT::value_type {
257 using V = typename SemiringT::value_type;
258 std::vector<V> lt, le, ge, gt, eq;
259 for (size_t i = 0; i < kvals.size(); ++i) {
260 if (kvals[i] == S.zero()) continue;
261 if (mvals[i] < C) lt.push_back(kvals[i]);
262 if (mvals[i] <= C) le.push_back(kvals[i]);
263 if (mvals[i] >= C) ge.push_back(kvals[i]);
264 if (mvals[i] > C) gt.push_back(kvals[i]);
265 if (mvals[i] == C) eq.push_back(kvals[i]);
266 }
267 auto sum = [&](const std::vector<V> &v) -> V {
268 return v.empty() ? S.zero() : S.plus(v);
269 };
270 // (1 ⊖ ⊕spoilers) ⊗ ⊕witnesses
271 auto guarded = [&](const std::vector<V> &spoilers,
272 const std::vector<V> &witnesses) -> V {
273 if (witnesses.empty()) return S.zero();
274 V w = S.plus(witnesses);
275 if (spoilers.empty()) return w;
276 return S.times(std::vector<V>{S.monus(S.one(), S.plus(spoilers)), w});
277 };
278
279 // The MAX table is the MIN table with < and > exchanged: flip the
280 // operator and swap the roles of the below / above sets.
281 const bool is_max = (agg_kind == AggregationOperator::MAX);
282 const std::vector<V> &below = is_max ? gt : lt; // strictly on the "losing" side
283 const std::vector<V> &below_eq = is_max ? ge : le; // losing side or equal
284 const std::vector<V> &above = is_max ? lt : gt; // strictly on the "winning" side
285 const std::vector<V> &above_eq = is_max ? le : ge; // winning side or equal
286 if (is_max) op = flip_op(op);
287
288 switch (op) {
289 case ComparisonOperator::LT: return sum(below);
290 case ComparisonOperator::LE: return sum(below_eq);
291 case ComparisonOperator::GE: return guarded(below, above_eq);
292 case ComparisonOperator::GT: return guarded(below_eq, above);
293 case ComparisonOperator::EQ: return guarded(below, eq);
295 V a = sum(below);
296 V b = guarded(below_eq, above);
297 if (a == S.zero()) return b;
298 if (b == S.zero()) return a;
299 return S.plus(std::vector<V>{a, b});
300 }
301 }
302 return S.zero();
303 };
304
305 // Provenance of a predicate decided by the *first present* occurrence:
306 // the valid worlds partition into fibers, one per candidate first
307 // occurrence i, each fixing i present, a set A_i of occurrences absent
308 // (for choose(): every occurrence before i; for bool_or / bool_and: the
309 // earlier candidates and the class that must be wholly absent) and
310 // leaving the rest free. In an absorptive m-semiring whose ⊗
311 // distributes over ⊖ the free suffix sums to 𝟙 and each fiber is
312 // (1 ⊖ ⊕_{A_i} k) ⊗ k_i (Lean Having.firstScan_correct; the same
313 // hypotheses as the MIN / MAX scan). Elsewhere -- Why, Which, How,
314 // Formula, counting, the security semiring -- the free part does not
315 // collapse, so every world of every fiber is enumerated and annotated
316 // ∏present ⊗ (1 ⊖ ⊕missing), exponential in the number of free
317 // occurrences; @p monotone says the union of the fibers is closed under
318 // supersets (no class has to be wholly absent), which lets an
319 // idempotent semiring drop the monus factors.
320 using fiber_t = std::pair<size_t, std::vector<size_t>>; // (present, absent set)
321 auto first_present_provenance =
322 [&](const std::vector<fiber_t> &fibers,
323 const std::vector<typename SemiringT::value_type> &kvals,
324 bool monotone) -> typename SemiringT::value_type {
325 using V = typename SemiringT::value_type;
326 if (fibers.empty()) return S.zero();
327
328 if (S.absorptive() && S.mul_sub_left_distributive()) {
329 std::vector<V> terms;
330 for (const auto &fb : fibers) {
331 const V &k = kvals[fb.first];
332 if (k == S.zero()) continue;
333 std::vector<V> absent;
334 for (size_t j : fb.second)
335 if (kvals[j] != S.zero()) absent.push_back(kvals[j]);
336 if (absent.empty()) { terms.push_back(k); continue; }
337 V guard = S.monus(S.one(), S.plus(absent));
338 terms.push_back(k == S.one() ? guard : S.times(std::vector<V>{guard, k}));
339 }
340 return terms.empty() ? S.zero() : S.plus(terms);
341 }
342
343 const size_t n = kvals.size();
344 std::vector<mask_t> worlds;
345 for (const auto &fb : fibers) {
346 std::vector<bool> fixed(n, false);
347 fixed[fb.first] = true;
348 for (size_t j : fb.second) fixed[j] = true;
349 std::vector<size_t> free_idx;
350 for (size_t j = 0; j < n; ++j)
351 if (!fixed[j]) free_idx.push_back(j);
352 const size_t m = free_idx.size();
353 check_world_count(m >= 63 ? size_t(-1)
354 : worlds.size() + (size_t(1) << m));
355 for (size_t sub = 0; sub < (size_t(1) << m); ++sub) {
356 mask_t mask(n, false);
357 mask[fb.first] = true;
358 for (size_t b = 0; b < m; ++b)
359 if (sub & (size_t(1) << b)) mask[free_idx[b]] = true;
360 worlds.push_back(std::move(mask));
361 }
362 }
363 return combine_exhaustive_worlds(worlds, kvals, /*upset=*/false, monotone);
364 };
365
366 // One comparison, or several over the same contributors combined by a
367 // Boolean predicate (a conjunction, a disjunction of HAVING atoms on one
368 // group), resolved over the worlds of those contributors: in each, every
369 // comparison is read and the predicate decides whether the world counts.
370 // Numeric aggregates (SUM, COUNT, AVG, MIN, MAX, choose()) and arithmetic
371 // over them; at most 24 contributors.
372auto build_joint = [&](const std::vector<JointAtom> &atoms,
373 const std::function<bool(const std::vector<bool> &)>
374 &pred,
375 typename SemiringT::value_type &pw_out) -> bool {
376 struct AggInfo {
378 bool is_int; // integer-typed result?
379 bool is_scalar; // aggregation without GROUP BY?
380 std::vector<std::pair<int, double> > contribs; // (distinct-K index, value)
381 };
382 // A decimal text denotes an integer iff it has no fractional/exponent part.
383 auto text_is_int = [](const std::string &s) -> bool {
384 if (s.empty()) return false;
385 for (char ch : s)
386 if (!((ch >= '0' && ch <= '9') || ch == '+' || ch == '-'))
387 return false;
388 return true;
389 };
390 std::map<gate_t, AggInfo> aggs;
391 std::map<gate_t, int> kindex;
392 std::vector<gate_t> kgates;
393
394 // A number, the whole text of it: a date such as 2022-08-05 is not
395 // 2022.
396 auto parse_number = [](const std::string &s, double &out) -> bool {
397 try {
398 std::size_t pos = 0;
399 out = std::stod(s, &pos);
400 return pos == s.size();
401 } catch (...) {
402 return false;
403 }
404 };
405
406 std::function<bool(gate_t)> collect = [&](gate_t gx) -> bool {
407 gate_type gt = c.getGateType(gx);
408 if (gt == gate_agg) {
409 if (aggs.count(gx))
410 return true;
411 AggInfo ai;
412 ai.kind = getAggregationOperator(c.getInfos(gx).first);
413 ai.is_int = aggtype_is_integer(c.getInfos(gx).second & PROVSQL_AGG_TYPE_MASK);
414 ai.is_scalar =
415 (c.getInfos(gx).second & PROVSQL_AGG_SCALAR_FLAG) != 0;
416 // Only the kinds eval reads a value of: any other declines the
417 // route here, rather than reading there as "no value" in every
418 // world -- which is a comparison that never holds, a probability of
419 // zero with nothing to say so. bool_and / bool_or / array_agg were
420 // kept out only by their values failing to parse as numbers.
421 switch (ai.kind) {
428 break;
429 default:
430 return false;
431 }
432 for (gate_t ch : c.getWires(gx)) {
433 if (c.getGateType(ch) != gate_semimod)
434 return false;
435 std::string ms;
436 gate_t kg{};
437 if (!semimod_extract_string_and_K(c, ch, ms, kg))
438 return false;
439 int idx;
440 auto it = kindex.find(kg);
441 if (it == kindex.end()) {
442 idx = static_cast<int>(kgates.size());
443 kindex[kg] = idx;
444 kgates.push_back(kg);
445 } else
446 idx = it->second;
447 double m;
448 if (!parse_number(ms, m)) return false;
449 ai.contribs.emplace_back(idx, m);
450 }
451 aggs.emplace(gx, std::move(ai));
452 return true;
453 }
454 if (gt == gate_arith) {
455 for (gate_t ch : c.getWires(gx))
456 if (!collect(ch))
457 return false;
458 return true;
459 }
460 if (gt == gate_value)
461 return true;
462 if (gt == gate_semimod) { // a constant threshold: semimod(1, value)
463 std::string ms;
464 gate_t kg{};
465 if (!semimod_extract_string_and_K(c, gx, ms, kg))
466 return false;
467 return c.getGateType(kg) == gate_one;
468 }
469 return false;
470 };
471
472 for (const JointAtom &a : atoms)
473 if (!collect(a.L) || !collect(a.R))
474 return false;
475 if (aggs.empty())
476 return false;
477 const size_t n = kgates.size();
478 if (n > 24) // 2^n enumeration: keep it bounded
479 return false;
480
481 // Numeric value of a subexpression in a given world, tracking whether it
482 // is integer-valued so that division floors as SQL does (NULL -> false).
483 std::function<bool(gate_t, uint64_t, double &, bool &)> eval =
484 [&](gate_t gx, uint64_t world, double &out, bool &is_int) -> bool {
485 gate_type gt = c.getGateType(gx);
486 if (gt == gate_value) {
487 std::string s = c.getExtra(gx);
488 if (!parse_number(s, out)) return false;
489 is_int = text_is_int(s);
490 return true;
491 }
492 if (gt == gate_semimod) { // constant threshold
493 std::string ms; gate_t kg{};
494 if (!semimod_extract_string_and_K(c, gx, ms, kg)) return false;
495 if (!parse_number(ms, out)) return false;
496 is_int = text_is_int(ms);
497 return true;
498 }
499 if (gt == gate_agg) {
500 const AggInfo &ai = aggs.at(gx);
501 double acc = 0, mn = 0, mx = 0, fst = 0;
502 long cnt = 0;
503 bool first = true;
504 for (const auto &pr : ai.contribs)
505 if (world & (uint64_t(1) << pr.first)) {
506 double m = pr.second;
507 acc += m; ++cnt;
508 if (first) { mn = mx = fst = m; first = false; }
509 else { mn = std::min(mn, m); mx = std::max(mx, m); }
510 }
511 is_int = ai.is_int;
512 // An aggregate with no surviving contributor in this world declines
513 // the world (returning false), which the caller reads as "the
514 // comparison does not hold here". Two situations produce cnt == 0
515 // and both want that answer: the group has no row present, so the
516 // group's row does not exist; or the group is non-empty but every
517 // contributed value was NULL, so the aggregate is SQL NULL and the
518 // comparison is NULL, hence false. (A NULL-valued row never reaches
519 // contribs -- the aggregation rewriting drops it -- which is why the
520 // two are indistinguishable here, and why they need not be.)
521 //
522 // COUNT is the exception: an empty set genuinely counts 0, so the
523 // world has a value whenever a row exists to carry it -- which is
524 // the case for a scalar aggregation, and not for a grouped one whose
525 // empty group is no row at all. The gate records COUNT for both
526 // count(*) and count(expr) (see make_aggregation_expression), so no
527 // guessing from the values is needed here.
528 switch (ai.kind) {
529 case AggregationOperator::SUM: if (cnt == 0) return false; out = acc; return true;
530 case AggregationOperator::COUNT: // values 1 or 0/1
531 if (cnt == 0 && !ai.is_scalar) return false;
532 out = acc; return true;
533 case AggregationOperator::AVG: if (cnt == 0) return false; out = acc / cnt; return true;
534 case AggregationOperator::MIN: if (cnt == 0) return false; out = mn; return true;
535 case AggregationOperator::MAX: if (cnt == 0) return false; out = mx; return true;
536 // choose() is PICKFIRST: the value of the first present contributor,
537 // in the order of the gate's wires (see ChooseAgg).
538 case AggregationOperator::CHOOSE: if (cnt == 0) return false; out = fst; return true;
539 default:
540 // collect admits no other kind: one reaching here would read as
541 // "no value" in every world, so it raises instead.
542 throw CircuitException(
543 "having_semantics: aggregate kind not read per world");
544 }
545 }
546 if (gt == gate_arith) {
547 const auto &w = c.getWires(gx);
548 unsigned aop = static_cast<unsigned>(c.getInfos(gx).first);
549 if (aop == PROVSQL_ARITH_PLUS || aop == PROVSQL_ARITH_TIMES) {
550 double r = (aop == PROVSQL_ARITH_PLUS) ? 0 : 1;
551 bool all_int = true;
552 for (gate_t ch : w) {
553 double v; bool vi;
554 if (!eval(ch, world, v, vi)) return false;
555 if (aop == PROVSQL_ARITH_PLUS) r += v; else r *= v;
556 all_int = all_int && vi;
557 }
558 out = r; is_int = all_int; return true;
559 }
560 if (aop == PROVSQL_ARITH_MINUS) {
561 if (w.size() != 2) return false;
562 double a, b; bool ai, bi;
563 if (!eval(w[0], world, a, ai) || !eval(w[1], world, b, bi)) return false;
564 out = a - b; is_int = ai && bi; return true;
565 }
566 if (aop == PROVSQL_ARITH_DIV || aop == PROVSQL_ARITH_INTDIV) {
567 if (w.size() != 2) return false;
568 double a, b; bool ai, bi;
569 if (!eval(w[0], world, a, ai) || !eval(w[1], world, b, bi)) return false;
570 if (b == 0) return false;
571 if (aop == PROVSQL_ARITH_INTDIV) { // SQL division of integers
572 out = std::trunc(a / b);
573 is_int = true;
574 } else {
575 /* A real division, whatever the operands happen to be in this
576 * world. Which of the two divisions SQL means is the gate's to
577 * say -- the rewriting emits INTDIV exactly where the
578 * expression's type is an integer one -- and deciding it again
579 * from the values truncated a division the query wrote over
580 * numbers: count(*) OVER w / count(*) OVER w0 came out 1 or 0
581 * per world, so a comparison over it answered the probability
582 * that the two counts are equal. The other five evaluators
583 * (Monte Carlo, RangeCheck, Expectation, the simplifier, the
584 * collapsed moment) all read the op and not the values. */
585 out = a / b;
586 is_int = false;
587 }
588 return true;
589 }
590 if (aop == PROVSQL_ARITH_NEG) {
591 if (w.size() != 1) return false;
592 double a; bool ai;
593 if (!eval(w[0], world, a, ai)) return false;
594 out = -a; is_int = ai; return true;
595 }
596 if (aop == PROVSQL_ARITH_ASFLOAT8 ||
597 aop == PROVSQL_ARITH_ASFLOAT4) {
598 /* The value read in its own type: a double is what this carries,
599 * and a real rounds it to seven digits. */
600 double a;
601 bool ai;
602 if (w.size() != 1 || !eval(w[0], world, a, ai)) return false;
603 out = aop == PROVSQL_ARITH_ASFLOAT8
604 ? a : static_cast<double>(static_cast<float>(a));
605 is_int = ai;
606 return true;
607 }
608 if (aop == PROVSQL_ARITH_ROUND || aop == PROVSQL_ARITH_FLOOR ||
609 aop == PROVSQL_ARITH_CEIL || aop == PROVSQL_ARITH_ABS) {
610 /* Read in the world, on the value the world gives: rounding and
611 * absolute value of a value, never of an expectation. */
612 double a;
613 bool ai;
614 if (w.empty() || !eval(w[0], world, a, ai)) return false;
615 if (aop == PROVSQL_ARITH_FLOOR) out = std::floor(a);
616 else if (aop == PROVSQL_ARITH_CEIL) out = std::ceil(a);
617 else if (aop == PROVSQL_ARITH_ABS) out = std::fabs(a);
618 else if (w.size() == 1) out = std::round(a);
619 else {
620 double d;
621 bool di;
622 if (!eval(w[1], world, d, di)) return false;
623 const double f = std::pow(10.0, d);
624 out = std::round(a * f) / f;
625 }
626 /* An integer in, an integer out, except a rounding to digits of a
627 * value that was not one. */
628 is_int = ai || aop != PROVSQL_ARITH_ROUND || w.size() == 1;
629 return true;
630 }
631 if (aop == PROVSQL_ARITH_POW || aop == PROVSQL_ARITH_LN ||
632 aop == PROVSQL_ARITH_EXP) {
633 /* The transform of the value this world gives. Without these
634 * three the switch fell through to "no value in this world", which
635 * the caller reads as "the comparison does not hold here" -- in
636 * every world, so a HAVING over sqrt(sum(x)) (a POW of one half),
637 * over ln or exp, or over an expression holding one, answered
638 * probability 0 whatever the threshold. The other five evaluators
639 * read them, or decline the shape and leave it to this one.
640 *
641 * Where the transform is undefined ON the value the world gives --
642 * the logarithm of a nonpositive number, a negative base raised to
643 * a fraction -- the world has no value, the reading a divisor of
644 * zero gets (see the DIV arm) rather than the error SQL raises
645 * there: raising in one world would take every other world's
646 * answer with it. A NaN operand (a NaN in the data) is a value,
647 * and gives NaN, as in SQL. */
648 double a;
649 bool ai;
650
651 if (w.empty() || !eval(w[0], world, a, ai)) return false;
652 bool nan_operand = std::isnan(a);
653 if (aop == PROVSQL_ARITH_LN) {
654 if (!nan_operand && !(a > 0)) return false;
655 out = std::log(a);
656 } else if (aop == PROVSQL_ARITH_EXP) {
657 out = std::exp(a);
658 } else {
659 double e;
660 bool ei;
661
662 if (w.size() != 2 || !eval(w[1], world, e, ei)) return false;
663 nan_operand = nan_operand || std::isnan(e);
664 out = std::pow(a, e);
665 if (std::isnan(out) && !nan_operand) return false;
666 }
667 if (!nan_operand && !std::isfinite(out)) return false;
668 is_int = false;
669 return true;
670 }
671 if (aop == PROVSQL_ARITH_MAX || aop == PROVSQL_ARITH_MIN) {
672 if (w.empty()) return false;
673 double r = 0; bool all_int = true, first = true;
674 for (gate_t ch : w) {
675 double v; bool vi;
676 if (!eval(ch, world, v, vi)) return false;
677 /* In PostgreSQL's order of floats, NaN the greatest. */
678 if (first) { r = v; first = false; }
679 else if (aop == PROVSQL_ARITH_MAX ? sql_less(r, v)
680 : sql_less(v, r))
681 r = v;
682 all_int = all_int && vi;
683 }
684 out = r; is_int = all_int; return true;
685 }
686 if (aop == PROVSQL_ARITH_PERCENTILE) {
687 /* A continuous percentile over the group's rows: the wires are
688 * interleaved [ind_1, x_1, ...] with ind_i the row's 0/1 presence,
689 * and the fraction is the gate's own text. The values the world
690 * holds are sorted and interpolated at the fraction, as
691 * MonteCarloSampler reads them; a world holding none of them has no
692 * value, like an aggregate with no contributing row. No comparison
693 * reaches this today -- the gate is built for percentile_cont over
694 * a random variable, whose circuits the sampler reads -- so it is
695 * written to the sampler's reading rather than to a measurement. */
696 std::vector<double> members;
697 double fraction, pos, fp;
698 std::size_t lo;
699
700 if (w.empty() || w.size() % 2 != 0) return false;
701 try {
702 fraction = std::stod(c.getExtra(gx));
703 } catch (const std::exception &) {
704 return false;
705 }
706 for (std::size_t i = 0; i < w.size(); i += 2) {
707 double ind, x;
708 bool ii, xi;
709
710 if (!eval(w[i], world, ind, ii)) return false;
711 if (ind < 0.5) continue; /* the row is not here */
712 /* A row with no value is skipped, as SQL skips a NULL. */
713 if (!eval(w[i + 1], world, x, xi)) continue;
714 members.push_back(x);
715 }
716 if (members.empty()) return false;
717 std::sort(members.begin(), members.end(), sql_less<double>);
718 pos = fraction * static_cast<double>(members.size() - 1);
719 lo = static_cast<std::size_t>(pos);
720 fp = pos - static_cast<double>(lo);
721 out = (lo + 1 < members.size())
722 ? members[lo] + fp * (members[lo + 1] - members[lo])
723 : members[lo];
724 is_int = false;
725 return true;
726 }
727 /* An arithmetic this evaluator does not know. Falling through to
728 * "this world has no value" is what made a HAVING over sqrt, ln or
729 * exp answer probability 0 in every world, silently and with
730 * confidence, for as long as those three arms were missing: the
731 * caller reads no value as "the comparison does not hold here". An
732 * unimplemented operator has to be told apart from a world that
733 * genuinely has no value, so it raises, as every other evaluator's
734 * default does (MonteCarloSampler, Expectation). A new gate_arith
735 * operator therefore fails loudly here until it is read. */
736 throw CircuitException(
737 "having_semantics: unknown gate_arith operator tag: " +
738 std::to_string(aop));
739 }
740 return false;
741 };
742
743 std::vector<typename SemiringT::value_type> kval(n);
744 for (size_t i = 0; i < n; ++i)
745 kval[i] = c.evaluate<SemiringT>(kgates[i], mapping, S);
746
747 // The joint enumeration below is over complete worlds already:
748 // certify the disjuncts when the semiring and contributors allow.
749 const bool certify = certifiable_contributors(kval);
750
751 // Whether the world in which no contributor is present is itself a
752 // valid world. For a grouped aggregation it is not: an empty group is
753 // no row, so there is nothing for the comparison to hold of. A scalar
754 // aggregation always yields its single row, empty input included, so
755 // that world is real and a predicate true on it (count(*) = 0, and
756 // anything the empty-input values satisfy) must pick it up. Mixed
757 // shapes follow the grouped reading: whichever side is grouped has no
758 // row there, so the joined row does not exist either.
759 const bool empty_world_valid =
760 !aggs.empty() &&
761 std::all_of(aggs.begin(), aggs.end(),
762 [](const std::pair<const gate_t, AggInfo> &e) {
763 return e.second.is_scalar;
764 });
765 // No contributor at all: the empty world is the only one, and it is
766 // only a world for scalar aggregations (a window frame that may be
767 // empty while its row exists).
768 if (n == 0 && !empty_world_valid)
769 return false;
770
771 std::vector<typename SemiringT::value_type> disjuncts;
772 const uint64_t total = uint64_t(1) << n;
773 for (uint64_t world = empty_world_valid ? 0 : 1; world < total; ++world) {
774 std::vector<bool> truth(atoms.size(), false);
775 for (size_t ai = 0; ai < atoms.size(); ++ai) {
776 double lv, rv;
777 bool lint, rint;
778 if (!eval(atoms[ai].L, world, lv, lint) ||
779 !eval(atoms[ai].R, world, rv, rint))
780 continue; // NULL comparison: false
781 /* In PostgreSQL's order of floats: NaN equals NaN and is above
782 * every number. */
783 const bool lt = sql_less(lv, rv), gt = sql_less(rv, lv);
784 switch (atoms[ai].op) {
785 case ComparisonOperator::EQ: truth[ai] = !lt && !gt; break;
786 case ComparisonOperator::NE: truth[ai] = lt || gt; break;
787 case ComparisonOperator::LT: truth[ai] = lt; break;
788 case ComparisonOperator::LE: truth[ai] = !gt; break;
789 case ComparisonOperator::GT: truth[ai] = gt; break;
790 case ComparisonOperator::GE: truth[ai] = !lt; break;
791 }
792 }
793 /* A comparison that is NULL in the world counts as false: exact for a
794 * conjunction and a disjunction, which keep a row only where they are
795 * true, and there is no negation among them. */
796 if (!pred(truth))
797 continue;
798
799 std::vector<typename SemiringT::value_type> present, missing;
800 for (size_t i = 0; i < n; ++i) {
801 if (world & (uint64_t(1) << i)) {
802 if (certify || kval[i] != S.one()) present.push_back(kval[i]);
803 } else {
804 if (certify || kval[i] != S.zero()) missing.push_back(kval[i]);
805 }
806 }
807 if (certify) {
808 disjuncts.push_back(S.certified_world_term(present, missing));
809 continue;
810 }
811 auto present_prod = S.times(present);
812 if (missing.empty())
813 disjuncts.push_back(std::move(present_prod));
814 else {
815 auto monus_factor = S.monus(S.one(), S.plus(missing));
816 disjuncts.push_back(
817 present_prod == S.one()
818 ? monus_factor
819 : S.times(std::vector<typename SemiringT::value_type>{
820 present_prod, monus_factor}));
821 }
822 }
823
824 pw_out = disjuncts.empty() ? S.zero()
825 : certify ? S.certified_exclusive_plus(disjuncts)
826 : S.plus(disjuncts);
827 return true;
828 };
829
830 auto pw_from_cmp_gate = [&](gate_t cmp_gate, typename SemiringT::value_type &pw_out) -> bool {
831 const auto &cw = c.getWires(cmp_gate);
832 if (cw.size() != 2) return false;
833
834 gate_t L = cw[0];
835 gate_t R = cw[1];
836
837 bool okop = false;
838 ComparisonOperator op = map_cmp_op(c, cmp_gate, okop);
839 if (!okop) return false;
840
841 auto build_from = [&](gate_t agg_side, gate_t const_side, ComparisonOperator effective_op) -> bool {
842 if (c.getGateType(agg_side) != gate_agg) return false;
843
844 // info2 of the gate_agg is the aggregate's result type -- the
845 // comparison domain (int / numeric / float / text) -- in its low 31 bits;
846 // the high bit is the scalar-aggregation flag, masked off here.
847 const unsigned aggtype = c.getInfos(agg_side).second & PROVSQL_AGG_TYPE_MASK;
848 const bool is_scalar =
849 (c.getInfos(agg_side).second & PROVSQL_AGG_SCALAR_FLAG) != 0;
850 AggregationOperator agg_kind = getAggregationOperator(c.getInfos(agg_side).first);
851 const auto &children = c.getWires(agg_side);
852
853 // ---- Value-as-text domain: choose() over a non-numeric scalar constant.
854 // Covers text and any other type whose values round-trip through
855 // their text representation (bool, date, uuid, enum, ...); numeric
856 // choose() goes to the numeric domain below (which also supports the
857 // ordering comparisons). Only = / <> are exposed here. ----
858 if ((aggtype_is_text(aggtype) &&
859 agg_kind != AggregationOperator::MIN &&
860 agg_kind != AggregationOperator::MAX) ||
861 (agg_kind == AggregationOperator::CHOOSE &&
862 !aggtype_is_numeric(aggtype))) {
863 std::string C_str;
864 if (!extract_constant_string(c, const_side, C_str)) return false;
865
866 std::vector<std::string> mvals_str;
867 std::vector<typename SemiringT::value_type> kvals;
868 mvals_str.reserve(children.size());
869 kvals.reserve(children.size());
870 for (gate_t ch : children) {
871 if (c.getGateType(ch) != gate_semimod) return false;
872 std::string m_str;
873 gate_t k_gate{};
874 if (!semimod_extract_string_and_K(c, ch, m_str, k_gate)) return false;
875 mvals_str.push_back(m_str);
876 kvals.push_back(c.evaluate<SemiringT>(k_gate, mapping, S));
877 }
878
879 // Only choose() is supported (the only text-valued aggregate whose
880 // possible-world value is decided occurrence-by-occurrence), and
881 // only = / <> are exposed for text.
882 if (agg_kind != AggregationOperator::CHOOSE)
883 throw std::runtime_error(
884 "comparing an aggregate with a text constant in HAVING "
885 "is only implemented for choose()");
886 if (effective_op != ComparisonOperator::EQ &&
887 effective_op != ComparisonOperator::NE)
888 throw std::runtime_error(
889 "only = and <> are supported when comparing choose() "
890 "with a text constant");
891
892 // choose() is PICKFIRST: in a world W its value is that of the
893 // lowest-index present element. So choose(W) op C holds iff the
894 // first present element matches: one fiber per matching index i,
895 // with every occurrence before i absent and the suffix free.
896 //
897 // The fibers are mutually exclusive by construction (they differ
898 // on the first present index): when the semiring certifies
899 // enumerations, build them as certified world terms under a
900 // certified deterministic OR instead.
901 if (certifiable_contributors(kvals)) {
902 std::vector<typename SemiringT::value_type> disjuncts;
903 std::vector<typename SemiringT::value_type> before;
904 for (size_t i = 0; i < kvals.size(); ++i) {
905 bool match = (effective_op == ComparisonOperator::EQ)
906 ? (mvals_str[i] == C_str)
907 : (mvals_str[i] != C_str);
908 if (match)
909 disjuncts.push_back(S.certified_world_term(
910 std::vector<typename SemiringT::value_type>{kvals[i]},
911 before));
912 before.push_back(kvals[i]);
913 }
914 pw_out = disjuncts.empty() ? S.zero()
915 : S.certified_exclusive_plus(disjuncts);
916 return true;
917 }
918 std::vector<fiber_t> fibers;
919 std::vector<size_t> before;
920 for (size_t i = 0; i < kvals.size(); ++i) {
921 bool match = (effective_op == ComparisonOperator::EQ)
922 ? (mvals_str[i] == C_str)
923 : (mvals_str[i] != C_str);
924 if (match) fibers.emplace_back(i, before);
925 before.push_back(i);
926 }
927 pw_out = first_present_provenance(fibers, kvals, /*monotone=*/false);
928 return true;
929 }
930
931 // ---- Boolean comparison domain: bool_or / bool_and (and the every
932 // alias for bool_and) compared with a boolean constant. A boolean
933 // aggregate has only two possible values, so the worlds yielding the
934 // wanted value are characterised directly in the m-semiring rather
935 // than by a 2^n enumeration. The rows partition by their value into
936 // a class that must have at least one present member ("someE") and a
937 // class that must be wholly absent ("noneF"):
938 // bool_or = true : someE = true-rows (false free)
939 // bool_or = false : someE = false-rows, noneF = true-rows
940 // bool_and = true : someE = true-rows, noneF = false-rows
941 // bool_and = false : someE = false-rows (true free)
942 // "at least one of someE present" splits by the first present
943 // someE index (the choose pattern), each fiber also requiring
944 // every noneF row absent; see first_present_provenance for when
945 // that is a closed form and when it is enumerated. Non-empty
946 // groups are enforced by someE being non-empty. ----
947 if (aggtype_is_boolean(aggtype)) {
948 if (agg_kind != AggregationOperator::OR &&
949 agg_kind != AggregationOperator::AND)
950 return false;
951 if (effective_op != ComparisonOperator::EQ &&
952 effective_op != ComparisonOperator::NE)
953 throw std::runtime_error(
954 "only = and <> are supported when comparing a boolean aggregate "
955 "(bool_or / bool_and / every) with a constant in HAVING");
956
957 auto parse_bool = [](const std::string &s, bool &ok) -> bool {
958 ok = true;
959 if (s == "t" || s == "true" || s == "1") return true;
960 if (s == "f" || s == "false" || s == "0") return false;
961 ok = false; return false;
962 };
963
964 std::string C_str;
965 if (!extract_constant_string(c, const_side, C_str)) return false;
966 bool okc = false;
967 const bool C = parse_bool(C_str, okc);
968 if (!okc) return false;
969 // The aggregate value the satisfying worlds must produce.
970 const bool target = (effective_op == ComparisonOperator::EQ) ? C : !C;
971
972 std::vector<bool> vals;
973 std::vector<typename SemiringT::value_type> kvals;
974 vals.reserve(children.size());
975 kvals.reserve(children.size());
976 for (gate_t ch : children) {
977 if (c.getGateType(ch) != gate_semimod) return false;
978 std::string m_str;
979 gate_t k_gate{};
980 if (!semimod_extract_string_and_K(c, ch, m_str, k_gate)) return false;
981 bool okv = false;
982 const bool b = parse_bool(m_str, okv);
983 if (!okv) return false;
984 vals.push_back(b);
985 kvals.push_back(c.evaluate<SemiringT>(k_gate, mapping, S));
986 }
987
988 const bool want_or = (agg_kind == AggregationOperator::OR);
989 std::vector<size_t> someE; // at least one of these must be present
990 std::vector<size_t> noneF; // all of these must be absent
991 if (want_or == target) {
992 // bool_or=true / bool_and=false: one trigger row suffices, the other
993 // class is free.
994 for (size_t i = 0; i < vals.size(); ++i)
995 if (vals[i] == want_or) someE.push_back(i);
996 } else {
997 // bool_or=false / bool_and=true: the trigger class must be wholly
998 // absent and the opposite class must have at least one present row.
999 for (size_t i = 0; i < vals.size(); ++i)
1000 (vals[i] == want_or ? noneF : someE).push_back(i);
1001 }
1002
1003 if (someE.empty()) { pw_out = S.zero(); return true; }
1004
1005 if (certifiable_contributors(kvals)) {
1006 std::vector<typename SemiringT::value_type> disjuncts;
1007 std::vector<typename SemiringT::value_type> before; // someE rows before i
1008 for (size_t e : someE) {
1009 std::vector<typename SemiringT::value_type> missing = before;
1010 for (size_t f : noneF) missing.push_back(kvals[f]);
1011 disjuncts.push_back(S.certified_world_term(
1012 std::vector<typename SemiringT::value_type>{kvals[e]}, missing));
1013 before.push_back(kvals[e]);
1014 }
1015 pw_out = S.certified_exclusive_plus(disjuncts);
1016 return true;
1017 }
1018
1019 // With no class to exclude (bool_or = true, bool_and = false) the
1020 // predicate is existential: it holds in the worlds meeting someE,
1021 // an upward-closed family whose minimal elements are the
1022 // singletons, so in an absorptive semiring the ⊕-sum of the
1023 // someE annotations is exact, with no monus and no distributivity
1024 // (Lean Having.sum_ann_meet, the MIN <= C argument). An
1025 // idempotent semiring still enumerates the family but, it being
1026 // monotone, without the monus factors.
1027 if (noneF.empty() && S.absorptive()) {
1028 std::vector<typename SemiringT::value_type> witnesses;
1029 for (size_t e : someE)
1030 if (kvals[e] != S.zero()) witnesses.push_back(kvals[e]);
1031 pw_out = witnesses.empty() ? S.zero() : S.plus(witnesses);
1032 return true;
1033 }
1034
1035 std::vector<fiber_t> fibers;
1036 std::vector<size_t> absent = noneF; // grows with the earlier someE rows
1037 for (size_t e : someE) {
1038 fibers.emplace_back(e, absent);
1039 absent.push_back(e);
1040 }
1041 pw_out = first_present_provenance(fibers, kvals,
1042 /*monotone=*/noneF.empty());
1043 return true;
1044 }
1045
1046 // ---- Array comparison domain: array_agg(x) against a constant array.
1047 // No aggregate-specific optimization (the general pipeline): scan the
1048 // non-empty worlds whose ordered present elements equal (=) or differ
1049 // (<>) from the constant array, then combine those worlds in the
1050 // m-semiring. Elements are compared as their text representations,
1051 // so any element type works. ----
1052 if (agg_kind == AggregationOperator::ARRAY_AGG) {
1053 if (effective_op != ComparisonOperator::EQ &&
1054 effective_op != ComparisonOperator::NE)
1055 throw std::runtime_error(
1056 "only = and <> are supported when comparing array_agg() with a "
1057 "constant array in HAVING");
1058
1059 std::string C_str;
1060 if (!extract_constant_string(c, const_side, C_str)) return false;
1061 std::vector<std::string> target;
1062 if (!parse_array_literal(C_str, target)) return false;
1063
1064 std::vector<std::string> vals;
1065 std::vector<typename SemiringT::value_type> kvals;
1066 vals.reserve(children.size());
1067 kvals.reserve(children.size());
1068 for (gate_t ch : children) {
1069 if (c.getGateType(ch) != gate_semimod) return false;
1070 std::string m_str;
1071 gate_t k_gate{};
1072 if (!semimod_extract_string_and_K(c, ch, m_str, k_gate)) return false;
1073 // A NULL input of the aggregate: its value gate is gate_null().
1074 if (c.getUUID(c.getWires(ch)[1]) == GATE_NULL_UUID)
1075 m_str = array_null_element();
1076 vals.push_back(m_str);
1077 kvals.push_back(c.evaluate<SemiringT>(k_gate, mapping, S));
1078 }
1079
1080 // Boolean elements: the row values carry the scalar bool text
1081 // ('true'/'false') while the constant array's elements come back in
1082 // PostgreSQL's array form ('t'/'f'). Canonicalise both sides so the
1083 // text comparison below sees the same representation.
1084 if (aggtype_elem_is_boolean(aggtype)) {
1085 auto canon_bool = [](std::string &s) {
1086 if (s == "t" || s == "true" || s == "1") s = "true";
1087 else if (s == "f" || s == "false" || s == "0") s = "false";
1088 };
1089 for (auto &e : target) canon_bool(e);
1090 for (auto &v : vals) canon_bool(v);
1091 }
1092
1093 auto worlds = enumerate_array_agg_worlds(
1094 vals, target, effective_op == ComparisonOperator::EQ);
1095 pw_out = combine_exhaustive_worlds(worlds, kvals, /*upset=*/false,
1096 /*monotone=*/false);
1097 return true;
1098 }
1099
1100 // The possible worlds of an aggregate over integer-mapped values
1101 // compared with an integer threshold: the closed forms, or the
1102 // enumeration.
1103 auto finish_domain = [&](const std::vector<long> &mvals, long C,
1104 const std::vector<typename SemiringT::value_type> &kvals)
1105 -> bool {
1106 // A certified enumeration needs the *complete* valid worlds (every
1107 // contributor present or explicitly negated): the upset shortcut
1108 // and the monotone MIN/MAX skips below produce overlapping,
1109 // non-exclusive disjuncts, sound for absorptive evaluation but
1110 // unmarkable. When certifying, request the full enumeration --
1111 // the same one non-absorptive semirings already use.
1112 const bool certify = certifiable_contributors(kvals);
1113
1114 // MIN / MAX in an absorptive semiring: the single-scan closed form
1115 // replaces the 2^n world enumeration -- for the existential
1116 // comparisons (MIN below, MAX above the constant) in every
1117 // absorptive semiring, for the others only when ⊗ distributes over
1118 // ⊖ (see min_max_scan). A certifying semiring keeps the
1119 // enumeration, whose exclusive world terms its certificate needs.
1120 if ((agg_kind == AggregationOperator::MIN ||
1121 agg_kind == AggregationOperator::MAX) &&
1122 S.absorptive() && !certify) {
1123 const bool existential =
1124 (agg_kind == AggregationOperator::MIN)
1125 ? (effective_op == ComparisonOperator::LT ||
1126 effective_op == ComparisonOperator::LE)
1127 : (effective_op == ComparisonOperator::GT ||
1128 effective_op == ComparisonOperator::GE);
1129 if (existential || S.mul_sub_left_distributive()) {
1130 pw_out = min_max_scan(mvals, C, kvals, effective_op, agg_kind);
1131 return true;
1132 }
1133 }
1134
1135 bool upset = false;
1136 auto worlds = enumerate_valid_worlds(mvals, C, effective_op, agg_kind,
1137 certify ? false : S.absorptive(),
1138 upset, is_scalar);
1139
1140 // Comparisons preserved as the group grows, whose valid worlds are
1141 // therefore closed under supersets: MIN below and MAX above the
1142 // constant, COUNT above it (count(col) carries 0/1 values), SUM
1143 // above it when no contributor is negative.
1144 const bool above = (effective_op == ComparisonOperator::GT ||
1145 effective_op == ComparisonOperator::GE);
1146 const bool below = (effective_op == ComparisonOperator::LT ||
1147 effective_op == ComparisonOperator::LE);
1148 bool monotone = false;
1149 switch (agg_kind) {
1150 case AggregationOperator::MIN: monotone = below; break;
1151 case AggregationOperator::MAX: monotone = above; break;
1152 case AggregationOperator::COUNT: monotone = above; break;
1154 monotone = above &&
1155 std::all_of(mvals.begin(), mvals.end(), [](long v) { return v >= 0; });
1156 break;
1157 default: break;
1158 }
1159
1160 pw_out = combine_exhaustive_worlds(worlds, kvals, upset, monotone);
1161 return true;
1162 };
1163
1164 // ---- Ordered domain: MIN / MAX over a type that is not numeric (text,
1165 // date, timestamp, ...). Their value in a world only depends on
1166 // the order of the values, so values and threshold are mapped to
1167 // their ranks under the type's own comparison function (with its
1168 // default collation, for text), and the integer machinery below
1169 // applies. ----
1170 if (!aggtype_is_numeric(aggtype) &&
1171 (agg_kind == AggregationOperator::MIN ||
1172 agg_kind == AggregationOperator::MAX)) {
1173 std::string C_str;
1174 if (!extract_constant_string(c, const_side, C_str)) return false;
1175 std::vector<std::string> m_strs;
1176 std::vector<typename SemiringT::value_type> kvals;
1177 for (gate_t ch : children) {
1178 if (c.getGateType(ch) != gate_semimod) return false;
1179 std::string m_str;
1180 gate_t k_gate{};
1181 if (!semimod_extract_string_and_K(c, ch, m_str, k_gate)) return false;
1182 m_strs.push_back(m_str);
1183 kvals.push_back(c.evaluate<SemiringT>(k_gate, mapping, S));
1184 }
1185 std::vector<long> ranks;
1186 long C_rank = 0;
1187 if (!rank_values_by_type(aggtype, m_strs, C_str, ranks, C_rank))
1188 return false;
1189 return finish_domain(ranks, C_rank, kvals);
1190 }
1191
1192 // ---- Numeric comparison domain (int / numeric / float): unify by
1193 // scaling every value and the threshold to a common integer
1194 // grid by their decimal text, so a numeric(p,d) / finite-decimal
1195 // float column is evaluated exactly and fractional thresholds
1196 // work. Integer is the scale-0 case. ----
1197 std::string C_str;
1198 if (!extract_constant_string(c, const_side, C_str)) return false;
1199 long C_mant = 0; int C_scale = 0;
1200 if (!parse_decimal_scaled(C_str, C_mant, C_scale)) return false;
1201
1202 std::vector<long> m_mant;
1203 std::vector<int> m_scale;
1204 std::vector<typename SemiringT::value_type> kvals;
1205 m_mant.reserve(children.size());
1206 m_scale.reserve(children.size());
1207 kvals.reserve(children.size());
1208 for (gate_t ch : children) {
1209 if (c.getGateType(ch) != gate_semimod) return false;
1210 std::string m_str;
1211 gate_t k_gate{};
1212 if (!semimod_extract_string_and_K(c, ch, m_str, k_gate)) return false;
1213 long mm = 0; int ms = 0;
1214 if (!parse_decimal_scaled(m_str, mm, ms)) return false;
1215 m_mant.push_back(mm);
1216 m_scale.push_back(ms);
1217 kvals.push_back(c.evaluate<SemiringT>(k_gate, mapping, S));
1218 }
1219
1220 // Common scale: rescale every value and the threshold to integers.
1221 int target_scale = C_scale;
1222 for (int ms : m_scale) target_scale = std::max(target_scale, ms);
1223 long C = 0;
1224 if (!rescale_to(C_mant, C_scale, target_scale, C)) return false;
1225 std::vector<long> mvals(m_mant.size());
1226 for (size_t i = 0; i < m_mant.size(); ++i)
1227 if (!rescale_to(m_mant[i], m_scale[i], target_scale, mvals[i])) return false;
1228
1229 return finish_domain(mvals, C, kvals);
1230 };
1231
1232 // General possible-worlds evaluation for a comparison over an *arithmetic
1233 // expression of one or more aggregates* (sum(x)*sum(y) > k, sum(x) > sum(y),
1234 // 100/sum(x) > 5, ...), which the single-aggregate path above cannot fold.
1235 // We enumerate the joint possible worlds over the union of the aggregates'
1236 // contributors, evaluate the arithmetic numerically in each world, and
1237 // combine the worlds where the comparison holds in the semiring exactly as
1238 // the single-aggregate path does (present_prod ⊗ (1 ⊖ missing_sum)). This
1239 // is exponential in the number of distinct contributors, so it bails out
1240 // (returning false, leaving the gate unresolved) beyond a small bound.
1241 auto build_general = [&](gate_t Lx, gate_t Rx,
1242 ComparisonOperator opx) -> bool {
1243 return build_joint(std::vector<JointAtom>{JointAtom{Lx, Rx, opx}},
1244 [](const std::vector<bool> &t) { return t[0]; },
1245 pw_out);
1246 };
1247
1248 // ---- Two array_agg() aggregates compared with each other (a join on
1249 // two aggregated arrays): the worlds of the tuples of both, which
1250 // may be shared, where the arrays are equal (=) or differ (<>).
1251 // Elements are compared as their texts, as against a constant. ----
1252 auto build_array_pair = [&](gate_t Lx, gate_t Rx,
1253 ComparisonOperator opx) -> bool {
1255 return false;
1256 std::map<gate_t, std::size_t> bit;
1257 std::vector<typename SemiringT::value_type> kvals;
1258 std::vector<std::size_t> bits[2];
1259 std::vector<std::string> vals[2];
1260 const gate_t sides[2] = {Lx, Rx};
1261
1262 for (int side = 0; side < 2; ++side) {
1263 if (getAggregationOperator(c.getInfos(sides[side]).first) !=
1265 return false;
1266 for (gate_t ch : c.getWires(sides[side])) {
1267 if (c.getGateType(ch) != gate_semimod) return false;
1268 std::string m_str;
1269 gate_t k_gate{};
1270 if (!semimod_extract_string_and_K(c, ch, m_str, k_gate)) return false;
1271 if (c.getUUID(c.getWires(ch)[1]) == GATE_NULL_UUID)
1272 m_str = array_null_element();
1273 auto it = bit.find(k_gate);
1274 if (it == bit.end()) {
1275 if (kvals.size() >= 20)
1276 return false; // 2^n enumeration: keep it bounded
1277 it = bit.emplace(k_gate, kvals.size()).first;
1278 kvals.push_back(c.evaluate<SemiringT>(k_gate, mapping, S));
1279 }
1280 bits[side].push_back(it->second);
1281 vals[side].push_back(m_str);
1282 }
1283 }
1284 if (kvals.empty())
1285 return false;
1286
1287 auto worlds = enumerate_array_agg_pair_worlds(
1288 bits[0], vals[0], bits[1], vals[1], kvals.size(),
1289 opx == ComparisonOperator::EQ);
1290 pw_out = combine_exhaustive_worlds(worlds, kvals, /*upset=*/false,
1291 /*monotone=*/false);
1292 return true;
1293 };
1294
1295 if (c.getGateType(L) == gate_agg && build_from(L, R, op))
1296 return true;
1297 if (c.getGateType(R) == gate_agg && build_from(R, L, flip_op(op)))
1298 return true;
1299 if (c.getGateType(L) == gate_agg && c.getGateType(R) == gate_agg &&
1300 build_array_pair(L, R, op))
1301 return true;
1302
1303 return build_general(L, R, op);
1304 };
1305
1306 // Several conditions over one group -- HAVING count(*) >= 3 AND
1307 // sum(price) <= 4 -- have as provenance one sum over the worlds of the
1308 // group, of the worlds where the whole predicate holds. The circuit holds
1309 // the product (or sum) of the conditions, which is that only in a semiring
1310 // exclusive with an idempotent product (product_is_joint): elsewhere a
1311 // product or a sum whose children include conditions over the same
1312 // contributors has them resolved together, in one enumeration, and replaced
1313 // by a gate carrying the result. Visited from the root down, so that a
1314 // combination nested in another over the same group is resolved with it.
1315 // A Boolean combination of conditions over one family: its tree, with
1316 // the conditions numbered in the order of @c atoms.
1317 struct FNode {
1318 int kind; // 0 condition, 1 and, 2 or
1319 size_t atom;
1320 std::vector<FNode> kids;
1321 };
1322 // A conjunction of comparisons of one count(*) with constants is a range
1323 // C <= count <= D, whose provenance is S_C ⊖ S_{D+1}, S_j the sum over
1324 // the worlds of exactly j occurrences of the products of their
1325 // annotations (Lean G_eq_S_monus_S): in a semiring absorptive with ⊗
1326 // distributing over ⊖, in O(n·D) rather than an enumeration of 2^n
1327 // worlds, and past the enumeration's bound on n.
1328 auto count_range = [&](const std::vector<JointAtom> &atoms,
1329 const FNode &root,
1330 typename SemiringT::value_type &out) -> bool {
1331 if (!S.absorptive() || !S.mul_sub_left_distributive())
1332 return false;
1333 std::function<bool(const FNode &)> all_and = [&](const FNode &n) {
1334 if (n.kind == 0) return true;
1335 if (n.kind != 1) return false;
1336 for (const FNode &k : n.kids)
1337 if (!all_and(k)) return false;
1338 return true;
1339 };
1340 if (!all_and(root))
1341 return false;
1342 long lo = 0, hi = -1; // hi < 0: no upper bound
1343 bool scalar = false;
1344 std::vector<gate_t> ks;
1345 for (size_t ai = 0; ai < atoms.size(); ++ai) {
1346 gate_t agg = atoms[ai].L, cst = atoms[ai].R;
1347 ComparisonOperator op = atoms[ai].op;
1348 if (c.getGateType(agg) != gate_agg) {
1349 std::swap(agg, cst);
1350 op = flip_op(op);
1351 }
1352 if (c.getGateType(agg) != gate_agg ||
1353 getAggregationOperator(c.getInfos(agg).first) !=
1355 return false;
1356 std::string cs;
1357 if (!extract_constant_string(c, cst, cs))
1358 return false;
1359 long v;
1360 try {
1361 std::size_t pos = 0;
1362 v = std::stol(cs, &pos);
1363 if (pos != cs.size()) return false;
1364 } catch (...) {
1365 return false;
1366 }
1367 scalar = (c.getInfos(agg).second & PROVSQL_AGG_SCALAR_FLAG) != 0;
1368 std::vector<gate_t> these;
1369 for (gate_t ch : c.getWires(agg)) {
1370 std::string ms;
1371 gate_t kg{};
1372 if (c.getGateType(ch) != gate_semimod ||
1373 !semimod_extract_string_and_K(c, ch, ms, kg) || ms != "1")
1374 return false; // count(*): every occurrence counts one
1375 these.push_back(kg);
1376 }
1377 if (ai == 0)
1378 ks = these;
1379 else if (these != ks)
1380 return false;
1381 switch (op) {
1382 case ComparisonOperator::GE: lo = std::max(lo, v); break;
1383 case ComparisonOperator::GT: lo = std::max(lo, v + 1); break;
1384 case ComparisonOperator::LE: hi = hi < 0 ? v : std::min(hi, v); break;
1385 case ComparisonOperator::LT: hi = hi < 0 ? v - 1 : std::min(hi, v - 1); break;
1387 lo = std::max(lo, v);
1388 hi = hi < 0 ? v : std::min(hi, v);
1389 break;
1390 default:
1391 return false;
1392 }
1393 }
1394 if (!scalar && lo < 1)
1395 lo = 1; // an empty group is no row
1396 const long n = static_cast<long>(ks.size());
1397 if ((hi >= 0 && hi < lo) || lo > n) {
1398 out = S.zero();
1399 return true;
1400 }
1401 const long top = (hi >= 0 && hi + 1 <= n) ? hi + 1 : lo;
1402 std::vector<typename SemiringT::value_type> Sj(top + 1, S.zero());
1403 Sj[0] = S.one();
1404 for (long i = 0; i < n; ++i) {
1405 auto a = c.evaluate<SemiringT>(ks[i], mapping, S);
1406 for (long j = std::min(top, i + 1); j >= 1; --j)
1407 Sj[j] = S.plus(std::vector<typename SemiringT::value_type>{
1408 Sj[j], S.times(std::vector<typename SemiringT::value_type>{
1409 Sj[j - 1], a})});
1410 }
1411 out = (hi >= 0 && hi + 1 <= n) ? S.monus(Sj[lo], Sj[hi + 1]) : Sj[lo];
1412 return true;
1413 };
1414
1415 if (!S.product_is_joint()) {
1416 std::set<gate_t> cmpset(cmp_gates.begin(), cmp_gates.end());
1417
1418 // The contributors a condition reads: the row tokens under its aggregates.
1419 std::function<void(gate_t, std::set<gate_t> &)> family_walk =
1420 [&](gate_t x, std::set<gate_t> &fam) {
1421 gate_type t = c.getGateType(x);
1422 if (t == gate_agg) {
1423 for (gate_t ch : c.getWires(x)) {
1424 std::string ms;
1425 gate_t kg{};
1426 if (c.getGateType(ch) == gate_semimod &&
1427 semimod_extract_string_and_K(c, ch, ms, kg))
1428 fam.insert(kg);
1429 }
1430 } else if (t == gate_arith || t == gate_cmp)
1431 for (gate_t ch : c.getWires(x))
1432 family_walk(ch, fam);
1433 };
1434
1435 std::function<bool(gate_t, std::set<gate_t> &, bool &, FNode &,
1436 std::vector<JointAtom> &)> as_combination =
1437 [&](gate_t x, std::set<gate_t> &fam, bool &fam_set, FNode &out,
1438 std::vector<JointAtom> &atoms) -> bool {
1439 if (cmpset.count(x)) {
1440 const auto &w = c.getWires(x);
1441 bool okop = false;
1442 ComparisonOperator op = map_cmp_op(c, x, okop);
1443 std::set<gate_t> f;
1444 if (w.size() != 2 || !okop)
1445 return false;
1446 family_walk(x, f);
1447 if (f.empty())
1448 return false;
1449 if (!fam_set) {
1450 fam = f;
1451 fam_set = true;
1452 } else if (fam != f)
1453 return false;
1454 out.kind = 0;
1455 out.atom = atoms.size();
1456 atoms.push_back(JointAtom{w[0], w[1], op});
1457 return true;
1458 }
1459 gate_type t = c.getGateType(x);
1460 if (t != gate_times && t != gate_plus)
1461 return false;
1462 out.kind = t == gate_times ? 1 : 2;
1463 for (gate_t ch : c.getWires(x)) {
1464 FNode k;
1465 if (!as_combination(ch, fam, fam_set, k, atoms))
1466 return false;
1467 out.kids.push_back(std::move(k));
1468 }
1469 return !out.kids.empty();
1470 };
1471 std::function<bool(const FNode &, const std::vector<bool> &)> holds =
1472 [&](const FNode &n, const std::vector<bool> &t) -> bool {
1473 if (n.kind == 0)
1474 return t[n.atom];
1475 for (const FNode &k : n.kids) {
1476 bool v = holds(k, t);
1477 if (n.kind == 1 && !v) return false;
1478 if (n.kind == 2 && v) return true;
1479 }
1480 return n.kind == 1;
1481 };
1482
1483 std::set<gate_t> seen;
1484 std::vector<gate_t> todo{g};
1485 /* Once per statement, as each row's token is evaluated on its own. */
1486 static TimestampTz warned_at = 0;
1487 bool warned = warned_at == GetCurrentStatementStartTimestamp();
1488 while (!todo.empty()) {
1489 gate_t p = todo.back();
1490 todo.pop_back();
1491 if (!seen.insert(p).second)
1492 continue;
1493 gate_type pt = c.getGateType(p);
1494 if (pt == gate_times || pt == gate_plus) {
1495 // The children that are combinations of conditions, by family.
1496 std::map<std::set<gate_t>, std::vector<std::pair<gate_t, FNode>>> groups;
1497 for (gate_t ch : c.getWires(p)) {
1498 std::set<gate_t> fam;
1499 bool fam_set = false;
1500 FNode n;
1501 std::vector<JointAtom> scratch;
1502 if (as_combination(ch, fam, fam_set, n, scratch))
1503 groups[fam].emplace_back(ch, FNode());
1504 }
1505 for (auto &grp : groups) {
1506 if (grp.second.size() < 2)
1507 continue;
1508 std::vector<JointAtom> atoms;
1509 FNode root;
1510 root.kind = pt == gate_times ? 1 : 2;
1511 std::set<gate_t> fam;
1512 bool fam_set = false, ok = true;
1513 for (auto &m : grp.second) {
1514 FNode k;
1515 if (!as_combination(m.first, fam, fam_set, k, atoms)) {
1516 ok = false;
1517 break;
1518 }
1519 root.kids.push_back(std::move(k));
1520 }
1521 typename SemiringT::value_type joint;
1522 if (!ok ||
1523 (!count_range(atoms, root, joint) &&
1524 !build_joint(atoms,
1525 [&](const std::vector<bool> &t) {
1526 return holds(root, t);
1527 },
1528 joint))) {
1529 if (!warned) {
1530 warned = true;
1531 warned_at = GetCurrentStatementStartTimestamp();
1533 "conditions on aggregates of one group are combined as the "
1534 "product of their provenances, which is not the provenance "
1535 "of their combination in this semiring: these aggregates are "
1536 "not resolved jointly");
1537 }
1538 continue;
1539 }
1540 /* The group's conditions give way to one gate holding their joint
1541 * provenance. */
1542 gate_t n = c.addGate();
1543 mapping[n] = std::move(joint);
1544 std::vector<gate_t> wires;
1545 std::set<gate_t> replaced;
1546 for (auto &m : grp.second)
1547 replaced.insert(m.first);
1548 for (gate_t ch : c.getWires(p))
1549 if (!replaced.count(ch))
1550 wires.push_back(ch);
1551 wires.push_back(n);
1552 c.getWires(p) = wires;
1553 }
1554 }
1555 for (gate_t ch : c.getWires(p))
1556 if (!cmpset.count(ch))
1557 todo.push_back(ch);
1558 }
1559 }
1560
1561 // Each comparison gate is resolved on its own: its possible-world
1562 // enumeration reads the circuit and writes only its own mapping entry, so
1563 // one gate the enumeration cannot handle -- an agg-vs-agg shape past the
1564 // contributor cap, an unsupported aggregate -- says nothing about the
1565 // others. Skip it and carry on rather than abandoning the gates that
1566 // follow: those are left for the semiring's own cmp() to deal with, which
1567 // renders them (Formula) or raises, and a gate this loop could have
1568 // resolved should not be demoted to that just because of its position in
1569 // collect_sp_cmp_gates' traversal.
1570 // What the joint resolution replaced is no longer read.
1571 std::set<gate_t> reachable;
1572 {
1573 std::vector<gate_t> st{g};
1574 while (!st.empty()) {
1575 gate_t x = st.back();
1576 st.pop_back();
1577 if (!reachable.insert(x).second)
1578 continue;
1579 for (gate_t ch : c.getWires(x))
1580 st.push_back(ch);
1581 }
1582 }
1583 for (gate_t cmp_gate : cmp_gates) {
1584 typename SemiringT::value_type pw;
1585 if (!reachable.count(cmp_gate))
1586 continue;
1587 /* A single count(*) against a constant is the range of one bound. */
1588 if (!S.product_is_joint()) {
1589 const auto &w = c.getWires(cmp_gate);
1590 bool okop = false;
1591 ComparisonOperator op = map_cmp_op(c, cmp_gate, okop);
1592 FNode one;
1593 one.kind = 0;
1594 one.atom = 0;
1595 if (w.size() == 2 && okop &&
1596 count_range(std::vector<JointAtom>{JointAtom{w[0], w[1], op}}, one,
1597 pw)) {
1598 mapping[cmp_gate] = std::move(pw);
1599 continue;
1600 }
1601 }
1602 if (!pw_from_cmp_gate(cmp_gate, pw))
1603 continue;
1604
1605 mapping[cmp_gate] = std::move(pw);
1606 }
1607}
1608
1609#endif
AggregationOperator getAggregationOperator(Oid oid)
Map a PostgreSQL aggregate function OID to an AggregationOperator.
Typed aggregation value, operator, and aggregator abstractions.
AggregationOperator
SQL aggregation functions tracked by ProvSQL.
Definition Aggregation.h:52
@ OR
Boolean OR aggregate.
Definition Aggregation.h:59
@ MAX
MAX → input type.
Definition Aggregation.h:56
@ COUNT
COUNT(*) or COUNT(expr) → integer.
Definition Aggregation.h:53
@ AND
Boolean AND aggregate.
Definition Aggregation.h:58
@ SUM
SUM → integer or float.
Definition Aggregation.h:54
@ ARRAY_AGG
Array aggregation.
Definition Aggregation.h:61
@ MIN
MIN → input type.
Definition Aggregation.h:55
@ CHOOSE
Arbitrary selection (pick one element).
Definition Aggregation.h:60
@ AVG
AVG → float.
Definition Aggregation.h:57
ComparisonOperator
SQL comparison operators used in gate_cmp circuit gates.
Definition Aggregation.h:40
@ LT
Less than (<).
Definition Aggregation.h:44
@ GT
Greater than (>).
Definition Aggregation.h:46
@ LE
Less than or equal (<=).
Definition Aggregation.h:43
@ NE
Not equal (<>).
Definition Aggregation.h:42
@ GE
Greater than or equal (>=).
Definition Aggregation.h:45
bool sql_less(T a, T b)
The order PostgreSQL gives numbers: for floats, NaN equals NaN and is greater than every other value ...
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Template implementation of GenericCircuit::evaluate().
Exception type thrown by circuit operations on invalid input.
Definition Circuit.h:382
A refusal by design, or a known gap, rather than an error.
Definition Circuit.h:409
std::vector< gate_t > & getWires(gate_t g)
Return a mutable reference to the child-wire list of gate g.
Definition Circuit.h:311
gateType getGateType(gate_t g) const
Return the type of gate g.
Definition Circuit.h:301
uuid getUUID(gate_t g) const
Return the UUID string associated with gate g.
Definition Circuit.hpp:65
const S::value_type & evaluate(gate_t g, std::unordered_map< gate_t, typename S::value_type > &provenance_mapping, S semiring) const
Evaluate the sub-circuit rooted at gate g over semiring semiring.
gate_t addGate() override
Allocate a new gate with a default-initialised type.
std::string getExtra(gate_t g) const
Return the string extra for gate g.
std::pair< unsigned, unsigned > getInfos(gate_t g) const
Return the integer annotation pair for gate g.
static Datum semimod_gate(const pg_uuid_t *value_token, const pg_uuid_t *token)
The semimod gate value_token ⊗ token.
void provsql_having(GenericCircuit &c, gate_t g, MapT &mapping, SemiringT S=SemiringT{})
Rewrite HAVING comparison gates in the circuit into their possible-world provenance (world enumeratio...
bool rescale_to(long mantissa, int scale, int target_scale, long &out)
bool aggtype_is_text(unsigned oid)
bool aggtype_is_numeric(unsigned oid)
bool aggtype_is_integer(unsigned oid)
bool parse_array_literal(const std::string &s, std::vector< std::string > &out)
ComparisonOperator flip_op(ComparisonOperator op)
bool rank_values_by_type(unsigned typoid, const std::vector< std::string > &vals, const std::string &threshold, std::vector< long > &ranks, long &threshold_rank)
bool aggtype_elem_is_boolean(unsigned oid)
std::vector< gate_t > collect_sp_cmp_gates(GenericCircuit &c, gate_t start)
bool parse_decimal_scaled(const std::string &s, long &mantissa, int &scale)
ComparisonOperator map_cmp_op(GenericCircuit &c, gate_t cmp_gate, bool &ok)
bool aggtype_is_boolean(unsigned oid)
bool semimod_extract_string_and_K(GenericCircuit &c, gate_t semimod_gate, std::string &m_out, gate_t &k_gate_out)
bool extract_constant_string(GenericCircuit &c, gate_t x, std::string &C_out)
#define PROVSQL_GAP
#define provsql_warning(fmt,...)
Emit a ProvSQL warning message (execution continues).
void provsql_poll_interrupt()
Throw where an evaluation is to stop, its query cancelled.
Core types, constants, and utilities shared across ProvSQL.
@ PROVSQL_ARITH_PERCENTILE
continuous percentile (order-statistic aggregate): wires are interleaved [ind_1, x_1,...
@ PROVSQL_ARITH_DIV
binary, child0 / child1
@ PROVSQL_ARITH_ASFLOAT8
unary, child0 as double precision
@ PROVSQL_ARITH_LN
unary, natural logarithm of child0 (a negative draw raises at evaluation)
@ PROVSQL_ARITH_ROUND
child0 rounded half away from zero, to child1 decimal digits where a second child is given (SQL round...
@ PROVSQL_ARITH_PLUS
n-ary, sum of children
@ PROVSQL_ARITH_POW
binary, child0 ^ child1 (real branch only: a negative base drawn with a non-integer exponent raises a...
@ PROVSQL_ARITH_ABS
unary, |child0|
@ PROVSQL_ARITH_FLOOR
unary, greatest integer <= child0
@ PROVSQL_ARITH_NEG
unary, -child0
@ PROVSQL_ARITH_INTDIV
binary, child0 / child1 truncated toward zero: SQL's division of two integers
@ PROVSQL_ARITH_MINUS
binary, child0 - child1
@ PROVSQL_ARITH_CEIL
unary, least integer >= child0
@ PROVSQL_ARITH_EXP
unary, e^child0
@ PROVSQL_ARITH_TIMES
n-ary, product of children
@ PROVSQL_ARITH_MIN
n-ary, min of children (order statistic; least / min aggregate)
@ PROVSQL_ARITH_MAX
n-ary, max of children (order statistic; greatest / max aggregate)
@ PROVSQL_ARITH_ASFLOAT4
unary, child0 as real reads it
#define PROVSQL_AGG_TYPE_MASK
@ gate_arith
n-ary arithmetic gate over scalar-valued children (info1 holds operator tag)
#define PROVSQL_GATE_NULL_UUID
UUID of the constant value gate standing for the NULL value, the result of gate_null().
#define PROVSQL_AGG_SCALAR_FLAG
Scalar-aggregation flag, stored in the upper bit of a gate_agg's info2 (whose low 31 bits hold the ag...
std::vector< mask_t > enumerate_array_agg_pair_worlds(const std::vector< std::size_t > &lbits, const std::vector< std::string > &lvals, const std::vector< std::size_t > &rbits, const std::vector< std::string > &rvals, std::size_t nbits, bool want_equal)
Enumerate the worlds where the arrays of two array_agg() aggregates are equal (want_equal) or differ.
Definition subset.cpp:494
void check_world_count(std::size_t count)
Throw if count worlds of a group, held for enumeration, are more than provsql.max_worlds allows.
Definition subset.cpp:40
std::vector< mask_t > enumerate_valid_worlds(const std::vector< long > &values, long constant, ComparisonOperator op, AggregationOperator agg_kind, bool absorptive, bool &upset, bool is_scalar)
Enumerate all subsets of n tuples satisfying an aggregate predicate.
Definition subset.cpp:454
std::vector< mask_t > enumerate_array_agg_worlds(const std::vector< std::string > &vals, const std::vector< std::string > &target, bool want_equal)
Enumerate the non-empty worlds whose ordered present elements equal (want_equal true) or differ from ...
Definition subset.cpp:526
Enumerate tuple subsets satisfying an aggregate HAVING predicate.
std::vector< bool > mask_t
A bitmask over tuples representing one possible world.
Definition subset.hpp:29