ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
subset.cpp
Go to the documentation of this file.
1/**
2 * @file subset.cpp
3 * @brief Valid-world enumeration for aggregate HAVING predicates.
4 *
5 * Implements @c enumerate_valid_worlds() declared in @c subset.hpp.
6 *
7 * For a list of @f$n@f$ tuples with individual values, the function
8 * iterates over all @f$2^n@f$ possible worlds (bitmasks), computes the
9 * aggregate of the present tuples' values using the requested
10 * @c AggregationOperator, and tests the comparison predicate. All
11 * valid worlds are collected and returned.
12 *
13 * The @c upset output flag is set to @c true when the set of valid
14 * worlds is upward-closed (every superset of a valid world is also
15 * valid), which is the case for monotone aggregation predicates (e.g.
16 * SUM ≥ k). This information is used to optimise the evaluation of
17 * monotone HAVING clauses.
18 *
19 * Internal helpers in an anonymous namespace:
20 * - @c increment(): advance a bitmask to the next possible world.
21 * - @c compute_agg(): compute the aggregate value for one bitmask.
22 */
23#include "subset.hpp"
24#include <algorithm>
25#include <cstddef>
26#include <cstdint>
27#include <limits>
28#include <vector>
29#include <stdexcept>
30#include <cassert>
31
32#include "provsql_interrupt.h"
33#include <string>
34
35extern "C" {
36/** @c provsql.max_worlds (0: no limit). */
37extern int provsql_max_worlds;
38}
39
40void check_world_count(std::size_t count)
41{
42 if (provsql_max_worlds > 0 && count > (std::size_t)provsql_max_worlds)
44 "world-limit",
45 ("a condition on an aggregate of a group needs more than "
46 "provsql.max_worlds (" + std::to_string(provsql_max_worlds) +
47 ") of its possible worlds enumerated").c_str(),
48 "Raise provsql.max_worlds, or set it to 0 for no limit.");
49}
50
51namespace {
52/** @brief The next world after @p v, or @c false after the last one; a
53 * cancelled query stops the enumeration here. */
54static bool increment(mask_t &v)
55{
57 for(size_t i=0; i<v.size(); ++i)
58 {
59 v[i]=!v[i];
60 if(v[i])
61 return true;
62 }
63 return false;
64}
65
66static std::vector<mask_t> all_worlds(const std::vector<long> &values)
67{
68 std::vector<mask_t> worlds;
69 mask_t mask(values.size());
70 // Skip empty world
71 while(increment(mask)) {
72 worlds.push_back(mask);
73 check_world_count(worlds.size());
74 }
75 return worlds;
76}
77
78static void append_range(std::vector<mask_t> &out,
79 const std::vector<std::vector<mask_t> > &dp,
80 long long lo,
81 long long hi)
82{
83 if (dp.empty()) return;
84 const long long J = static_cast<long long>(dp.size())-1;
85 lo = std::max(lo, 0LL);
86 hi = std::min(hi, J);
87 if (lo>hi) return;
88
89 for (long long j = lo; j <= hi; ++j) {
90 out.insert(out.end(), dp[j].begin(), dp[j].end());
91 check_world_count(out.size());
92 }
93}
94
95class DPException : public std::exception {};
96
97/** @brief Return the minimum of two values. */
98#define MIN(x,y) ((x)<(y)?(x):(y))
99
100static std::vector<mask_t> sum_dp(const std::vector<long> &values, long C, ComparisonOperator op, bool absorptive, bool &upset, bool keep_empty=false)
101{
102 const std::size_t n = values.size();
103
104 std::vector<mask_t> R;
105
106 // We first deal with NEQ by combining LT and GT
107 if(op == ComparisonOperator::NE) {
108 std::vector<mask_t> lt= sum_dp(values, C, ComparisonOperator::LT, absorptive, upset, keep_empty);
109 std::vector<mask_t> gt= sum_dp(values, C, ComparisonOperator::GT, absorptive, upset, keep_empty);
110 R.reserve(lt.size()+gt.size());
111 R.insert(R.end(),lt.begin(),lt.end());
112 R.insert(R.end(),gt.begin(),gt.end());
113 return R;
114 }
115
116 long long T=0;
117 for (long w: values) {
118 if (w < 0)
119 throw DPException();
120 T+=w;
121 }
122
123 //no valid worlds case
124 if (op == ComparisonOperator::GT && C>=T) return {};
125 if (op == ComparisonOperator::GE && C>T) return {};
126 if (op == ComparisonOperator::LT && C<=0) return {};
127 if (op == ComparisonOperator::LE && C<0) return {};
128 if (op == ComparisonOperator::EQ && (C>T || C<0)) return {};
129
130 //tautology cases
131 if (op == ComparisonOperator::GT && C<0) return all_worlds(values);
132 if (op == ComparisonOperator::GE && C<=0) return all_worlds(values);
133 if (op == ComparisonOperator::LT && C>T) return all_worlds(values);
134 if (op == ComparisonOperator::LE && C>=T) return all_worlds(values);
135
136 long long J=0;
138 J=T;
139 else if (op==ComparisonOperator::LT)
140 J=MIN(C-1,T);
141 else
142 J=MIN(C,T);
143
144 assert(J>=0);
145
146 // The DP is pseudo-polynomial: it allocates one bucket per integer in
147 // [0, J]. A large J (huge aggregate values, or a high-scale decimal grid)
148 // would make that array impractical -- bail out so the caller falls back to
149 // exact subset enumeration, which is magnitude-independent.
150 static const long long SUM_DP_MAX_J = 10000000LL;
151 if (J > SUM_DP_MAX_J)
152 throw DPException();
153
154 std::vector<std::vector<mask_t> > dp(static_cast<std::size_t>(J) + 1);
155 dp[0].push_back(mask_t(n)); // dp[0] <- {emptyset}
156 std::size_t held = 1; // masks in all the dp entries
157
158 long long pref_sum=0;
159
160 for (std::size_t i=0; i<n; ++i)
161 {
162 const long w=values[i];
163 pref_sum+=w;
164 const long long j_max=MIN(J,pref_sum);
165
166 for (long long j = j_max; j >= w; --j) {
167 const long long p = j - w;
168 if(absorptive && ((op==ComparisonOperator::GT && p>C) ||
169 (op==ComparisonOperator::GE && p>=C))) {
170 upset=true;
171 continue;
172 }
173 size_t s=dp[p].size();
174 for(size_t k=0; k<s; ++k) {
175 mask_t m = dp[p][k];
176 m[i] = true;
177 dp[j].push_back(m);
178 check_world_count(++held);
179 }
180 }
181 }
182
183 switch(op){
185 append_range(R,dp,C,C);
186 break;
187
189 append_range(R,dp,C+1,J);
190 break;
191
192
194 append_range(R,dp,0,C-1);
195 break;
196
198 append_range(R,dp,C,J);
199 break;
200
202 append_range(R,dp,0,C);
203 break;
204
205 case ComparisonOperator::NE: // case already processed
206 assert(false);
207 }
208
209 // dp[0] holds the empty world together with every non-empty world whose
210 // present tuples all sum to 0 (value 0 being SUM's additive identity). A
211 // HAVING predicate is never satisfied by the empty group, but those value-0
212 // worlds are legitimate non-empty worlds and must be kept -- cf. the ValidSum
213 // proof, which removes only the single world {emptyset} from the selected
214 // range. So the <, <= (and =, when C=0) ranges above include dp[0], and we
215 // drop only the all-absent mask here. Skipping all of dp[0] instead (the old
216 // `lo=1`) silently dropped, e.g., a BID-block choice of a value-0 tuple under
217 // `sum < k`.
218 R.erase(std::remove_if(R.begin(), R.end(),
219 [](const mask_t &m) {
220 for(size_t i=0; i<m.size(); ++i) if(m[i]) return false;
221 return true;
222 }),
223 R.end());
224
225 // keep_empty marks a SCALAR COUNT enumerated through this value-aware DP
226 // (count(col) with NULL contributors, whose 0/1 values make COUNT a SUM of
227 // indicators). Unlike a genuine SUM -- empty group SQL NULL, so the empty
228 // world never satisfies -- a COUNT's empty group has the real value 0, so the
229 // all-absent world is a legitimate possible world: re-add it exactly when 0
230 // satisfies the predicate (a true-on-empty bound: = 0, < k, <= k, <> k!=0).
231 if (keep_empty) {
232 bool zero_sat = false;
233 switch(op) {
234 case ComparisonOperator::EQ: zero_sat = (C == 0); break;
235 case ComparisonOperator::NE: zero_sat = (C != 0); break;
236 case ComparisonOperator::LT: zero_sat = (0 < C); break;
237 case ComparisonOperator::LE: zero_sat = (0 <= C); break;
238 case ComparisonOperator::GT: zero_sat = (0 > C); break;
239 case ComparisonOperator::GE: zero_sat = (0 >= C); break;
240 }
241 if (zero_sat)
242 R.push_back(mask_t(n));
243 }
244
245 return R;
246}
247
248//generate k-subsets form an n-set
249static void combinations(std::size_t start,
250 int k_left,
251 mask_t mask,
252 std::vector<mask_t> &out)
253{
254 const size_t n = mask.size();
255
256 if (k_left == 0) {
257 out.push_back(mask);
258 check_world_count(out.size());
259 return;
260 }
261
262 if (start >= n) return;
263
264 const std::size_t remaining = n - start;
265 if (remaining < static_cast<std::size_t>(k_left)) return;
266
267 combinations(start + 1, k_left, mask, out);
268
269 mask[start]=true;
270 combinations(start + 1, k_left - 1, mask, out);
271}
272
273static std::vector<mask_t> count_enum(const std::vector<long> &values, long m, ComparisonOperator op, bool absorptive, bool &upset, bool is_scalar)
274{
275 const int n = static_cast<int>(values.size());
276 std::vector<mask_t> out;
277
278 auto add_exact_k = [&](long k) {
279 if (k < 0 || k > n) return;
280 combinations(0, static_cast<int>(k), mask_t(n), out);
281 };
282
283 /* The lowest count a group can have: 1 for a grouped aggregate (the empty
284 * group is no row, so a HAVING predicate is never evaluated on it -- the
285 * count >= 0 / count > -K family collapses to "non-empty" rather than to a
286 * tautology), but 0 for a SCALAR aggregate (no GROUP BY), whose single result
287 * row always exists with the empty input contributing count 0. Folding the
288 * empty world into each branch's bound (rather than appending it afterwards)
289 * keeps it consistent with the upset / minimal-witness structure: for the GE
290 * upset, count >= 0 then has minimal witness {} and is correctly a tautology;
291 * the empty subset is annotated by the caller as one ⊗ (𝟙 ⊖ ⊕(tuples)). */
292 const long lo = is_scalar ? 0 : 1;
293
294 switch (op)
295 {
297 if (m >= lo) add_exact_k(m);
298 break;
299
301 ++m;
302 [[fallthrough]];
304 /* count >= m : minimal present count is max(m, lo). */
305 const long mink = std::max(m, lo);
306 if (absorptive) {
307 upset = true;
308 add_exact_k(mink);
309 } else
310 for (long k = mink; k <= n; ++k) add_exact_k(k);
311 break;
312 }
313
315 --m;
316 [[fallthrough]];
318 /* count <= m : worlds k in [lo, m] (empty world k=0 included for a scalar
319 * aggregate iff m >= 0). */
320 for (long k = lo; k <= m; ++k) add_exact_k(k);
321 break;
322
324 /* count != m : every world in [lo, n] except k = m (the scalar empty world
325 * k=0 is included iff m != 0). */
326 for (long k = lo; k <= n; ++k)
327 if (k != m) add_exact_k(k);
328 break;
329 }
330
331 return out;
332}
333
334}
335
336/**
337 * @brief Apply a comparison operator to two values.
338 * @tparam I Type of the left operand.
339 * @tparam J Type of the right operand.
340 * @param a Left operand.
341 * @param op Comparison operator.
342 * @param b Right operand.
343 * @return Result of the comparison.
344 */
345template<typename I, typename J>
346static bool compare(I a, ComparisonOperator op, J b) {
347 switch (op) {
348 case ComparisonOperator::EQ: return a == b;
349 case ComparisonOperator::NE: return a != b;
350 case ComparisonOperator::GT: return a > b;
351 case ComparisonOperator::LT: return a < b;
352 case ComparisonOperator::GE: return a >= b;
353 case ComparisonOperator::LE: return a <= b;
354 }
355 return false;
356}
357
358/**
359 * @brief Evaluate whether the aggregation of @p values masked by @p mask satisfies @p op @p constant.
360 * @param values Input values to aggregate.
361 * @param mask Boolean mask selecting which values to include.
362 * @param constant Right-hand side constant of the comparison.
363 * @param op Comparison operator.
364 * @param aggregator Aggregator to apply to the selected values.
365 * @return @c true if the aggregate result satisfies the comparison.
366 */
367bool evaluate(const std::vector<long>& values,
368 const std::vector<bool>& mask,
369 long constant, ComparisonOperator op,
370 std::unique_ptr<Aggregator> aggregator)
371{
372 for (std::size_t i = 0; i < values.size(); ++i) {
373 if (mask[i]) aggregator->add(AggValue {values[i]});
374 }
375 auto res = aggregator->finalize();
376 switch(aggregator->resultType()) {
377 case ValueType::INT:
378 return compare(std::get<long>(res.v), op, constant);
380 return compare(std::get<bool>(res.v), op, constant);
381 case ValueType::FLOAT:
382 return compare(std::get<double>(res.v), op, constant);
383 default:
384 throw std::runtime_error("Cannot compare this kind of value");
385 }
386}
387
389 const std::vector<long> &values,
390 const mask_t &present,
391 long constant,
393 AggregationOperator agg_kind)
394{
395 // Empty-group exclusion: an all-absent group does not exist, so HAVING is
396 // never satisfied on it (the one edge convention a sampler must reproduce to
397 // match the expansion).
398 bool any = false;
399 for (bool b : present)
400 if (b) { any = true; break; }
401 if (!any)
402 return false;
403
404 return evaluate(values, present, constant, op,
405 makeAggregator(agg_kind, ValueType::INT));
406}
407
408/**
409 * @brief Enumerate all subsets satisfying a HAVING predicate by exhaustive search.
410 * @param values Input values.
411 * @param constant Constant for the comparison.
412 * @param op Comparison operator.
413 * @param agg_kind Aggregation function to apply.
414 * @param absorptive Whether the semiring is absorptive.
415 * @param upset Set to @c true if the result set forms an upset (monotone).
416 * @return Vector of satisfying subset masks.
417 */
418std::vector<mask_t> enumerate_exhaustive(
419 const std::vector<long> &values,
420 long constant,
422 AggregationOperator agg_kind,
423 bool absorptive,
424 bool &upset)
425{
426 const size_t n = values.size();
427
428 std::vector<mask_t> worlds;
429 mask_t mask(n);
430
431 bool all_worlds = true;
432
433 while(increment(mask)) { // Skipping empty world (handled by agg_cmp_holds_in_world too)
434 if(agg_cmp_holds_in_world(values, mask, constant, op, agg_kind)) {
435 worlds.push_back(mask);
436 check_world_count(worlds.size());
437 } else
438 all_worlds=false;
439 }
440
441 if(all_worlds && absorptive)
442 {
443 worlds.clear();
444
445 // In that case, the result is equivalent to the upset generated by
446 // the single-tuple possible worlds
447 combinations(0, 1, mask_t(n), worlds);
448 upset=true;
449 }
450
451 return worlds;
452}
453
454std::vector<mask_t> enumerate_valid_worlds(
455 const std::vector<long> &values,
456 long constant,
458 AggregationOperator agg_kind,
459 bool absorptive,
460 bool &upset,
461 bool is_scalar
462 )
463{
464 if (agg_kind == AggregationOperator::COUNT) {
465 /* count(*) (every contributor's value is the unit 1) is pure cardinality:
466 * count_enum enumerates by subset size and folds the scalar empty world via
467 * its lo bound. count(col) keeps the COUNT identity but carries per-row 0/1
468 * values (0 for a NULL-valued / null-padded row that still keeps the group
469 * alive); cardinality would wrongly count the 0-valued rows, so route it to
470 * the value-aware sum_dp -- with keep_empty=is_scalar, since a scalar
471 * count(col)'s empty group is the real value 0 (not SQL NULL like a sum). */
472 bool all_one = true;
473 for (long v : values) if (v != 1) { all_one = false; break; }
474 if (all_one)
475 return count_enum(values,constant,op, absorptive, upset, is_scalar);
476 try {
477 return sum_dp(values, constant, op, absorptive, upset, /*keep_empty=*/is_scalar);
478 } catch(DPException &e) {
479 // 0/1 values are non-negative, so this never throws; fall back defensively.
480 return enumerate_exhaustive(values, constant, op, agg_kind, absorptive, upset);
481 }
482 }
483
484 if(agg_kind == AggregationOperator::SUM)
485 try {
486 return sum_dp(values, constant, op, absorptive, upset);
487 } catch(DPException &e) {
488 // We will use the default implementation of the enumeration
489 }
490
491 return enumerate_exhaustive(values, constant, op, agg_kind, absorptive, upset);
492}
493
495 const std::vector<std::size_t> &lbits,
496 const std::vector<std::string> &lvals,
497 const std::vector<std::size_t> &rbits,
498 const std::vector<std::string> &rvals,
499 std::size_t nbits,
500 bool want_equal)
501{
502 std::vector<mask_t> worlds;
503 mask_t mask(nbits);
504 const auto side = [](const std::vector<std::size_t> &bits,
505 const std::vector<std::string> &vals,
506 const mask_t &m) {
507 std::vector<std::string> present;
508 for(std::size_t i = 0; i < vals.size(); ++i)
509 if(m[bits[i]]) present.push_back(vals[i]);
510 return present;
511 };
512
513 while(increment(mask)) {
514 std::vector<std::string> l = side(lbits, lvals, mask);
515 if(l.empty()) continue; // NULL: no comparison holds
516 std::vector<std::string> r = side(rbits, rvals, mask);
517 if(r.empty()) continue;
518 if((l == r) == want_equal) {
519 worlds.push_back(mask);
520 check_world_count(worlds.size());
521 }
522 }
523 return worlds;
524}
525
526std::vector<mask_t> enumerate_array_agg_worlds(
527 const std::vector<std::string> &vals,
528 const std::vector<std::string> &target,
529 bool want_equal)
530{
531 const size_t n = vals.size();
532 std::vector<mask_t> worlds;
533 mask_t mask(n);
534
535 // increment() starts from the all-absent mask and never yields it, so the
536 // empty group (which never satisfies a HAVING clause) is excluded for free.
537 while(increment(mask)) {
538 std::vector<std::string> present;
539 present.reserve(n);
540 for(size_t i = 0; i < n; ++i)
541 if(mask[i]) present.push_back(vals[i]);
542 if((present == target) == want_equal) {
543 worlds.push_back(mask);
544 check_world_count(worlds.size());
545 }
546 }
547 return worlds;
548}
std::unique_ptr< Aggregator > makeAggregator(AggregationOperator op, ValueType t)
Create a concrete Aggregator for the given operator and value type.
AggregationOperator
SQL aggregation functions tracked by ProvSQL.
Definition Aggregation.h:52
@ COUNT
COUNT(*) or COUNT(expr) → integer.
Definition Aggregation.h:53
@ SUM
SUM → integer or float.
Definition Aggregation.h:54
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
@ INT
Signed 64-bit integer.
@ BOOLEAN
Boolean.
@ FLOAT
Double-precision float.
int provsql_max_worlds
Possible worlds of a group that a condition on its aggregate may have enumerated before the evaluatio...
Definition provsql.c:132
void provsql_limit_exceeded(const char *tag, const char *message, const char *hint)
Stop the evaluation at a resource limit (provsql.max_memory, provsql.max_worlds): throws,...
Cancellation of the long C++ evaluation loops.
void provsql_poll_interrupt()
Throw where an evaluation is to stop, its query cancelled.
A dynamically-typed aggregate value.
bool evaluate(const std::vector< long > &values, const std::vector< bool > &mask, long constant, ComparisonOperator op, std::unique_ptr< Aggregator > aggregator)
Evaluate whether the aggregation of values masked by mask satisfies op constant.
Definition subset.cpp:367
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
#define MIN(x, y)
Return the minimum of two values.
Definition subset.cpp:98
static bool compare(I a, ComparisonOperator op, J b)
Apply a comparison operator to two values.
Definition subset.cpp:346
bool agg_cmp_holds_in_world(const std::vector< long > &values, const mask_t &present, long constant, ComparisonOperator op, AggregationOperator agg_kind)
Canonical per-world decision: does agg(present) op constant hold in the world where exactly the prese...
Definition subset.cpp:388
std::vector< mask_t > enumerate_exhaustive(const std::vector< long > &values, long constant, ComparisonOperator op, AggregationOperator agg_kind, bool absorptive, bool &upset)
Enumerate all subsets satisfying a HAVING predicate by exhaustive search.
Definition subset.cpp:418
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