ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
CaseCmpExpander.cpp
Go to the documentation of this file.
1/**
2 * @file CaseCmpExpander.cpp
3 * @brief Implementation of @c runCaseCmpExpander. See @c CaseCmpExpander.h.
4 */
5#include "CaseCmpExpander.h"
6
7#include <string>
8#include <vector>
9
10#include "having_semantics.hpp" // extract_constant_string, map_cmp_op, parse_decimal_scaled
11#include "Circuit.hpp" // Circuit<>::getUUID, used on the circuit
12
13extern "C" {
14#include "provsql_utils.h" // gate_type enum
15}
16
17namespace provsql {
18
19namespace {
20
21/// Whether @p op holds of a pair whose comparison has sign @p sign.
22bool op_holds(ComparisonOperator op, int sign)
23{
24 switch (op) {
25 case ComparisonOperator::EQ: return sign == 0;
26 case ComparisonOperator::NE: return sign != 0;
27 case ComparisonOperator::LT: return sign < 0;
28 case ComparisonOperator::LE: return sign <= 0;
29 case ComparisonOperator::GT: return sign > 0;
30 case ComparisonOperator::GE: return sign >= 0;
31 }
32 return false;
33}
34
35/**
36 * @brief The constant an operand carries, where it carries one.
37 *
38 * An arm of a lowered @c CASE is a bare @c gate_value; the other side of a
39 * comparison the rewriter builds is the @c semimod(𝟙, value) of a value of
40 * the row. @p is_null says the constant is SQL's NULL, which no comparison
41 * holds of.
42 */
43bool constant_of(GenericCircuit &gc, gate_t g, std::string &out, bool &is_null)
44{
45 const gate_type t = gc.getGateType(g);
46
47 if (t == gate_value)
48 out = gc.getExtra(g);
49 else if (t == gate_semimod) {
51 return false;
52 } else
53 return false;
54
55 is_null = out.empty() || out == "NULL" ||
56 gc.getUUID(g) == provsql_having_detail::GATE_NULL_UUID;
57 return true;
58}
59
60/// Decide a comparison between two constants, if both are decimal numbers.
61bool decide_constant_cmp(GenericCircuit &gc, gate_t l, gate_t r,
62 ComparisonOperator op, bool &holds)
63{
64 std::string ls, rs;
65 bool lnull = false, rnull = false;
66 long lm = 0, rm = 0;
67 int lscale = 0, rscale = 0, scale;
68
69 if (!constant_of(gc, l, ls, lnull) || !constant_of(gc, r, rs, rnull))
70 return false;
71 if (lnull || rnull) {
72 holds = false; /* unknown, and an unknown guard does not hold */
73 return true;
74 }
77 return false;
78 scale = lscale > rscale ? lscale : rscale;
79 if (!provsql_having_detail::rescale_to(lm, lscale, scale, lm) ||
80 !provsql_having_detail::rescale_to(rm, rscale, scale, rm))
81 return false;
82 holds = op_holds(op, lm < rm ? -1 : (lm > rm ? 1 : 0));
83 return true;
84}
85
86/**
87 * @brief Expand one comparison whose operand at @p side is a @c gate_case.
88 *
89 * The cmp gate itself becomes the @c gate_plus of the arm terms, keeping its
90 * id (and so every parent that reads it).
91 */
92void expand(GenericCircuit &gc, gate_t cmp, unsigned side, gate_t one)
93{
94 /* Copy before creating gates: the wire vectors may move. */
95 const std::vector<gate_t> cw = gc.getWires(cmp);
96 const gate_t selection = cw[side], other = cw[1 - side];
97 const std::vector<gate_t> aw = gc.getWires(selection);
98 const std::pair<unsigned, unsigned> infos = gc.getInfos(cmp);
99 const std::size_t n = aw.size(), arms = (n - 1) / 2;
100 bool okop = false;
102 std::vector<gate_t> terms;
103
104 for (std::size_t i = 0; i <= arms; ++i) {
105 const bool is_default = (i == arms);
106 const gate_t value = is_default ? aw[n - 1] : aw[2 * i + 1];
107 const gate_t l = (side == 0) ? value : other;
108 const gate_t r = (side == 0) ? other : value;
109 std::vector<gate_t> factors;
110 gate_t arm_cmp;
111 bool holds = false;
112
113 /* The comparison of this arm, in the operand order of the original. */
114 if (okop && decide_constant_cmp(gc, l, r, op, holds)) {
115 if (!holds)
116 continue; /* the term is 𝟘: the arm never satisfies the comparison */
117 arm_cmp = gc.addAnonymousGate(gate_one, {});
118 } else {
119 arm_cmp = gc.addAnonymousGate(gate_cmp, {l, r});
120 gc.setInfos(arm_cmp, infos.first, infos.second);
121 }
122
123 /* The arm is selected where its guard holds and none before it does. */
124 for (std::size_t j = 0; j < i; ++j)
125 factors.push_back(gc.addAnonymousGate(gate_monus, {one, aw[2 * j]}));
126 if (!is_default)
127 factors.push_back(aw[2 * i]);
128 factors.push_back(arm_cmp);
129 terms.push_back(factors.size() == 1
130 ? factors[0]
131 : gc.addAnonymousGate(gate_times, std::move(factors)));
132 }
133
134 if (terms.empty())
135 gc.resolveGateToZero(cmp); /* no arm ever satisfies it */
136 else
137 gc.resolveToPlus(cmp, std::move(terms));
138}
139
140/**
141 * @brief Hoist the guarded selections out of the arithmetic a comparison
142 * reads, one level per call.
143 *
144 * @c "x + CASE WHEN g THEN a ELSE b END" is, world by world,
145 * @c "CASE WHEN g THEN x + a ELSE x + b END": an arithmetic gate with a
146 * @c gate_case child becomes, in place, the @c gate_case of the same guards
147 * whose values are the arithmetic over each arm. Only the arithmetic a
148 * comparison reads, directly or through other arithmetic, is rewritten --
149 * that is where the expansion below needs the selection outermost; a
150 * selection nested in the arithmetic of a GREATEST's arm, as an @c ntile
151 * written without conditions of its own has, is otherwise left for no
152 * evaluator to read.
153 *
154 * @return Whether a gate was rewritten.
155 */
156bool hoist_cases_out_of_arith(GenericCircuit &gc)
157{
158 std::vector<gate_t> stack;
159 std::vector<bool> seen(gc.getNbGates(), false);
160 std::vector<gate_t> todo;
161
162 for (std::size_t i = 0; i < gc.getNbGates(); ++i) {
163 const auto g = static_cast<gate_t>(i);
164 if (gc.getGateType(g) != gate_cmp || gc.getWires(g).size() != 2)
165 continue;
166 for (gate_t c : gc.getWires(g))
167 stack.push_back(c);
168 }
169 while (!stack.empty()) {
170 const gate_t g = stack.back();
171 stack.pop_back();
172 if (seen[static_cast<std::size_t>(g)] || gc.getGateType(g) != gate_arith)
173 continue;
174 seen[static_cast<std::size_t>(g)] = true;
175 bool has_case = false;
176 for (gate_t c : gc.getWires(g)) {
177 if (gc.getGateType(c) == gate_case) {
178 const std::size_t n = gc.getWires(c).size();
179 if (n >= 1 && n % 2 == 1)
180 has_case = true;
181 } else
182 stack.push_back(c);
183 }
184 if (has_case)
185 todo.push_back(g);
186 }
187
188 for (gate_t g : todo) {
189 /* Copy before creating gates: the wire vectors may move. */
190 const std::vector<gate_t> gw = gc.getWires(g);
191 const std::pair<unsigned, unsigned> infos = gc.getInfos(g);
192 std::size_t k = 0;
193 while (k < gw.size() && !(gc.getGateType(gw[k]) == gate_case &&
194 gc.getWires(gw[k]).size() % 2 == 1))
195 ++k;
196 if (k == gw.size())
197 continue;
198 const std::vector<gate_t> aw = gc.getWires(gw[k]);
199 const std::size_t n = aw.size();
200 std::vector<gate_t> nw;
201 for (std::size_t i = 0; i < n; ++i) {
202 if (i % 2 == 0 && i != n - 1) { /* a guard */
203 nw.push_back(aw[i]);
204 continue;
205 }
206 std::vector<gate_t> operands = gw;
207 operands[k] = aw[i];
208 nw.push_back(gc.addAnonymousArithGate(
209 static_cast<provsql_arith_op>(infos.first), std::move(operands)));
210 }
211 gc.resolveToCase(g, std::move(nw));
212 }
213 return !todo.empty();
214}
215
216/**
217 * @brief Rewrite a comparison between two expressions, one of them arithmetic
218 * or a guarded selection, as the comparison of their difference with 0.
219 *
220 * @c "a > b" over numbers is @c "a - b > 0", world by world. A comparison
221 * with a constant is what the resolution below knows how to read, and the
222 * guard of a GREATEST over two expressions -- the two terms of an @c ntile --
223 * compares one with the other. Comparisons between two plain aggregates,
224 * which the resolution reads as they are, are left alone.
225 *
226 * @return Whether a gate was rewritten.
227 */
228bool subtract_expression_comparisons(GenericCircuit &gc, gate_t &zero,
229 bool &have_zero)
230{
231 std::vector<gate_t> todo;
232
233 for (std::size_t i = 0; i < gc.getNbGates(); ++i) {
234 const auto g = static_cast<gate_t>(i);
235 if (gc.getGateType(g) != gate_cmp || gc.getWires(g).size() != 2)
236 continue;
237 const auto &w = gc.getWires(g);
238 std::string ignored;
239 bool is_null = false;
240 if (constant_of(gc, w[0], ignored, is_null) ||
241 constant_of(gc, w[1], ignored, is_null))
242 continue;
243 const gate_type t0 = gc.getGateType(w[0]), t1 = gc.getGateType(w[1]);
244 if (t0 == gate_arith || t0 == gate_case || t1 == gate_arith ||
245 t1 == gate_case)
246 todo.push_back(g);
247 }
248 if (todo.empty())
249 return false;
250 if (!have_zero) {
251 zero = gc.addAnonymousValueGate("0");
252 have_zero = true;
253 }
254 for (gate_t g : todo) {
255 const std::vector<gate_t> w = gc.getWires(g);
256 const gate_t diff =
258 gc.getWires(g) = {diff, zero};
259 }
260 return true;
261}
262
263} // namespace
264
266{
267 unsigned decided = 0;
268
269 for (std::size_t i = 0; i < gc.getNbGates(); ++i) {
270 const auto g = static_cast<gate_t>(i);
271 bool okop = false, holds = false;
272 if (gc.getGateType(g) != gate_cmp || gc.getWires(g).size() != 2)
273 continue;
275 const gate_t l = gc.getWires(g)[0], r = gc.getWires(g)[1];
276 if (!okop || !decide_constant_cmp(gc, l, r, op, holds))
277 continue;
278 if (holds)
279 gc.resolveGateToOne(g);
280 else
281 gc.resolveGateToZero(g);
282 ++decided;
283 }
284 return decided;
285}
286
288{
289 unsigned expanded = 0;
290 gate_t one{}, zero{};
291 bool have_one = false, have_zero = false;
292
293 /* A comparison between two guarded selections takes one round per side, a
294 * nested selection one per level; the bound is a guard against a circuit
295 * that would build them without end. */
296 for (unsigned round = 0; round < 32; ++round) {
297 std::vector<std::pair<gate_t, unsigned>> todo;
298
299 /* A comparison between two expressions becomes one with 0, and a
300 * selection under the arithmetic a comparison reads comes up, a level per
301 * round, so that the expansion below reaches it. */
302 bool rewritten = false;
303 if (subtract_expression_comparisons(gc, zero, have_zero)) {
304 ++expanded;
305 rewritten = true;
306 }
307 if (hoist_cases_out_of_arith(gc)) {
308 ++expanded;
309 rewritten = true;
310 }
311 const auto nb = gc.getNbGates();
312
313 for (std::size_t i = 0; i < nb; ++i) {
314 const auto g = static_cast<gate_t>(i);
315 if (gc.getGateType(g) != gate_cmp)
316 continue;
317 const auto &w = gc.getWires(g);
318 if (w.size() != 2)
319 continue;
320 /* The wires of a gate_case are (guard, value)* followed by the
321 * default, so an odd number of them, at least one. */
322 for (unsigned side = 0; side < 2; ++side)
323 if (gc.getGateType(w[side]) == gate_case) {
324 const std::size_t n = gc.getWires(w[side]).size();
325 if (n >= 1 && n % 2 == 1)
326 todo.emplace_back(g, side);
327 break;
328 }
329 }
330 if (todo.empty()) {
331 if (rewritten)
332 continue; /* a selection came up a level: the next round reads it */
333 break;
334 }
335
336 if (!have_one) {
337 one = gc.addAnonymousGate(gate_one, {});
338 have_one = true;
339 }
340 for (const auto &t : todo) {
341 if (gc.getGateType(t.first) != gate_cmp)
342 continue; /* defensive: already rewritten */
343 expand(gc, t.first, t.second, one);
344 ++expanded;
345 }
346 }
347 return expanded;
348}
349
350} // namespace provsql
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
Expansion of a comparison one of whose operands is a guarded selection (gate_case) into the compariso...
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Out-of-line template method implementations for Circuit<gateType>.
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
std::vector< gate_t >::size_type getNbGates() const
Return the total number of gates in the circuit.
Definition Circuit.h:252
void resolveToPlus(gate_t g, std::vector< gate_t > w)
Rewrite an arbitrary gate as a gate_plus over w.
void resolveGateToZero(gate_t g)
Replace an arbitrary gate (typically gate_times) by gate_zero.
void resolveGateToOne(gate_t g)
Rewrite a gate as gate_one, the event that holds in every world.
void resolveToCase(gate_t g, std::vector< gate_t > w)
Rewrite a gate as the gate_case over w (guards and values, then the default).
gate_t addAnonymousArithGate(provsql_arith_op op, std::vector< gate_t > wires_)
Allocate a fresh gate_arith gate with operator tag op and the given wires.
gate_t addAnonymousValueGate(const std::string &text)
Allocate a fresh gate_value gate carrying the textual scalar text.
void setInfos(gate_t g, unsigned info1, unsigned info2)
Set the integer annotation pair for gate g.
std::string getExtra(gate_t g) const
Return the string extra for gate g.
gate_t addAnonymousGate(gate_type type, std::vector< gate_t > wires_)
Allocate a fresh gate of type type over wires_.
std::pair< unsigned, unsigned > getInfos(gate_t g) const
Return the integer annotation pair for gate g.
Provenance evaluation helper for HAVING-clause circuits.
bool rescale_to(long mantissa, int scale, int target_scale, long &out)
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 extract_constant_string(GenericCircuit &c, gate_t x, std::string &C_out)
unsigned runConstantCmpDecider(GenericCircuit &gc)
Decide every comparison between two constants.
unsigned runCaseCmpExpander(GenericCircuit &gc)
Expand every gate_cmp with a gate_case operand in gc.
Core types, constants, and utilities shared across ProvSQL.
provsql_arith_op
Arithmetic operator tags used by gate_arith.
@ PROVSQL_ARITH_MINUS
binary, child0 - child1
@ gate_case
N-ary guarded selection over scalar (RV) children: wires are [guard_1, value_1, .....
@ gate_arith
n-ary arithmetic gate over scalar-valued children (info1 holds operator tag)