45 (
"a condition on an aggregate of a group needs more than "
47 ") of its possible worlds enumerated").c_str(),
48 "Raise provsql.max_worlds, or set it to 0 for no limit.");
54static bool increment(
mask_t &v)
57 for(
size_t i=0; i<v.size(); ++i)
66static std::vector<mask_t> all_worlds(
const std::vector<long> &values)
68 std::vector<mask_t> worlds;
69 mask_t mask(values.size());
71 while(increment(mask)) {
72 worlds.push_back(mask);
78static void append_range(std::vector<mask_t> &out,
79 const std::vector<std::vector<mask_t> > &dp,
83 if (dp.empty())
return;
84 const long long J =
static_cast<long long>(dp.size())-1;
85 lo = std::max(lo, 0LL);
89 for (
long long j = lo; j <= hi; ++j) {
90 out.insert(out.end(), dp[j].begin(), dp[j].end());
95class DPException :
public std::exception {};
98#define MIN(x,y) ((x)<(y)?(x):(y))
100static std::vector<mask_t> sum_dp(
const std::vector<long> &values,
long C,
ComparisonOperator op,
bool absorptive,
bool &upset,
bool keep_empty=
false)
102 const std::size_t n = values.size();
104 std::vector<mask_t> R;
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());
117 for (
long w: values) {
150 static const long long SUM_DP_MAX_J = 10000000LL;
151 if (J > SUM_DP_MAX_J)
154 std::vector<std::vector<mask_t> > dp(
static_cast<std::size_t
>(J) + 1);
155 dp[0].push_back(
mask_t(n));
156 std::size_t held = 1;
158 long long pref_sum=0;
160 for (std::size_t i=0; i<n; ++i)
162 const long w=values[i];
164 const long long j_max=
MIN(J,pref_sum);
166 for (
long long j = j_max; j >= w; --j) {
167 const long long p = j - w;
173 size_t s=dp[p].size();
174 for(
size_t k=0; k<s; ++k) {
185 append_range(R,dp,C,C);
189 append_range(R,dp,C+1,J);
194 append_range(R,dp,0,C-1);
198 append_range(R,dp,C,J);
202 append_range(R,dp,0,C);
218 R.erase(std::remove_if(R.begin(), R.end(),
220 for(size_t i=0; i<m.size(); ++i) if(m[i]) return false;
232 bool zero_sat =
false;
249static void combinations(std::size_t start,
252 std::vector<mask_t> &out)
254 const size_t n = mask.size();
262 if (start >= n)
return;
264 const std::size_t remaining = n - start;
265 if (remaining <
static_cast<std::size_t
>(k_left))
return;
267 combinations(start + 1, k_left, mask, out);
270 combinations(start + 1, k_left - 1, mask, out);
273static std::vector<mask_t> count_enum(
const std::vector<long> &values,
long m,
ComparisonOperator op,
bool absorptive,
bool &upset,
bool is_scalar)
275 const int n =
static_cast<int>(values.size());
276 std::vector<mask_t> out;
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);
292 const long lo = is_scalar ? 0 : 1;
297 if (m >= lo) add_exact_k(m);
305 const long mink = std::max(m, lo);
310 for (
long k = mink; k <= n; ++k) add_exact_k(k);
320 for (
long k = lo; k <= m; ++k) add_exact_k(k);
326 for (
long k = lo; k <= n; ++k)
327 if (k != m) add_exact_k(k);
345template<
typename I,
typename J>
368 const std::vector<bool>& mask,
370 std::unique_ptr<Aggregator> aggregator)
372 for (std::size_t i = 0; i < values.size(); ++i) {
373 if (mask[i]) aggregator->add(
AggValue {values[i]});
375 auto res = aggregator->finalize();
376 switch(aggregator->resultType()) {
378 return compare(std::get<long>(res.v), op, constant);
380 return compare(std::get<bool>(res.v), op, constant);
382 return compare(std::get<double>(res.v), op, constant);
384 throw std::runtime_error(
"Cannot compare this kind of value");
389 const std::vector<long> &values,
399 for (
bool b : present)
400 if (b) { any =
true;
break; }
404 return evaluate(values, present, constant, op,
419 const std::vector<long> &values,
426 const size_t n = values.size();
428 std::vector<mask_t> worlds;
431 bool all_worlds =
true;
433 while(increment(mask)) {
435 worlds.push_back(mask);
441 if(all_worlds && absorptive)
447 combinations(0, 1,
mask_t(n), worlds);
455 const std::vector<long> &values,
473 for (
long v : values)
if (v != 1) { all_one =
false;
break; }
475 return count_enum(values,constant,op, absorptive, upset, is_scalar);
477 return sum_dp(values, constant, op, absorptive, upset, is_scalar);
478 }
catch(DPException &e) {
486 return sum_dp(values, constant, op, absorptive, upset);
487 }
catch(DPException &e) {
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,
502 std::vector<mask_t> worlds;
504 const auto side = [](
const std::vector<std::size_t> &bits,
505 const std::vector<std::string> &vals,
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]);
513 while(increment(mask)) {
514 std::vector<std::string> l = side(lbits, lvals, mask);
515 if(l.empty())
continue;
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);
527 const std::vector<std::string> &vals,
528 const std::vector<std::string> &target,
531 const size_t n = vals.size();
532 std::vector<mask_t> worlds;
537 while(increment(mask)) {
538 std::vector<std::string> present;
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);
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.
@ COUNT
COUNT(*) or COUNT(expr) → integer.
@ SUM
SUM → integer or float.
ComparisonOperator
SQL comparison operators used in gate_cmp circuit gates.
@ LE
Less than or equal (<=).
@ GE
Greater than or equal (>=).
@ INT
Signed 64-bit integer.
@ 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...
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.
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.
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.
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.
#define MIN(x, y)
Return the minimum of two values.
static bool compare(I a, ComparisonOperator op, J b)
Apply a comparison operator to two values.
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...
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.
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 ...
Enumerate tuple subsets satisfying an aggregate HAVING predicate.
std::vector< bool > mask_t
A bitmask over tuples representing one possible world.