ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
ProbCache.cpp
Go to the documentation of this file.
1/**
2 * @file ProbCache.cpp
3 * @brief Cache of compiled d-DNNFs and folding of independent parts (implementation).
4 */
5#include "ProbCache.h"
6
7extern "C" {
8#include "provsql_utils.h"
9}
10
11#include <algorithm>
12#include <cassert>
13#include <numeric>
14
15namespace provsql {
16
17namespace {
18
19/// Budget of the cache, in bytes: @c provsql.prob_cache_size, and no more
20/// than a quarter of @c provsql.max_memory when that is set. What a
21/// statement adds to the cache counts in the memory its evaluations take,
22/// and the cache must not be what makes them pass the limit.
23size_t maxCacheBytes()
24{
25 size_t budget = static_cast<size_t>(provsql_prob_cache_size) * 1024;
26 if(provsql_max_memory > 0)
27 budget = std::min(budget,
28 static_cast<size_t>(provsql_max_memory) * 1024 * 1024 / 4);
29 return budget;
30}
31
32/// Largest entry worth keeping: beyond a quarter of the budget, storing
33/// one d-DNNF would push out most of the others.
34size_t maxEntryBytes()
35{
36 return maxCacheBytes() / 4;
37}
38
39constexpr unsigned MAX_FOLD_DEPTH = 64;
40
41size_t estimateEntryBytes(const dDNNF &dd, const ProbCache::Entry &e)
42{
43 size_t wires = 0, uuid_bytes = 0;
44 for(gate_t g{0}; g < dd.getNbGates(); ++g) {
45 wires += dd.getWires(g).size();
46 uuid_bytes += dd.getUUID(g).size();
47 }
48 // The form is held twice, as the key of the map and in the entry.
49 return 2 * e.form.size()
50 + dd.getNbGates() * 96
51 + wires * sizeof(gate_t)
52 + uuid_bytes * 2
53 + e.leaf_gate.size() * (sizeof(gate_t) + 1)
54 + 256;
55}
56
57std::string islandLeafUuid(size_t i)
58{
59 return "provsql:island:" + std::to_string(i);
60}
61
62double instantiateAndEvaluate(const ProbCache::Entry &e,
63 const std::vector<double> &leaf_probs)
64{
65 assert(leaf_probs.size() == e.leaf_gate.size());
66 dDNNF dd = e.dd;
67 for(size_t i = 0; i < leaf_probs.size(); ++i)
68 if(e.leaf_present[i])
69 dd.setProb(e.leaf_gate[i], leaf_probs[i]);
70 return dd.probabilityEvaluation();
71}
72
73void noteOnce(std::vector<std::string> &names, const std::string &name)
74{
75 if(std::find(names.begin(), names.end(), name) == names.end())
76 names.push_back(name);
77}
78
79void tryCacheCompiled(
80 ProbCache &cache, const CanonicalForm &key, dDNNF &dd,
81 const std::string &builder,
82 const std::function<std::string(const CanonicalLeaf &)> &leaf_uuid)
83{
85 e.form = key.form;
86 e.builder = builder;
87 e.leaf_gate.assign(key.leaves.size(), gate_t{0});
88 e.leaf_present.assign(key.leaves.size(), 0);
89
90 GateSet mapped;
91 for(size_t i = 0; i < key.leaves.size(); ++i) {
92 const std::string u = leaf_uuid(key.leaves[i]);
93 if(u.empty())
94 return;
95 if(!dd.hasGate(u))
96 continue;
97 gate_t g = dd.getGate(u);
98 if(dd.getGateType(g) != BooleanGate::IN)
99 return;
100 e.leaf_gate[i] = g;
101 e.leaf_present[i] = 1;
102 mapped.insert(g);
103 }
104
105 if(dd.getNbGates() > 0) {
106 std::vector<gate_t> stack{dd.getRoot()};
107 GateSet seen{dd.getRoot()};
108 while(!stack.empty()) {
109 gate_t g = stack.back();
110 stack.pop_back();
111 if(dd.getGateType(g) == BooleanGate::IN && !mapped.count(g))
112 return;
113 for(gate_t ch : dd.getWires(g))
114 if(seen.insert(ch).second)
115 stack.push_back(ch);
116 }
117 }
118
119 e.bytes=estimateEntryBytes(dd, e);
120 if(!cache.admits(e.bytes))
121 return;
122 e.dd = dd;
123 cache.insert(key, std::move(e));
124}
125
126gate_t materialiseComponent(
127 const BooleanCircuit &c, gate_t root, const GateSet *frontier,
128 const std::unordered_map<gate_t, size_t, hash_gate_t> &island_index,
129 const std::unordered_map<gate_t, double, hash_gate_t> &island_prob,
130 BooleanCircuit &out)
131{
132 GateSet nodes = reachableNodes(c, root, frontier);
133 std::unordered_map<gate_t, gate_t, hash_gate_t> old2new;
134 old2new.reserve(nodes.size());
135
136 auto isAbstract =[&](gate_t g) {
137 return g != root && frontier && frontier->count(g) != 0;
138 };
139
140 for(gate_t g : nodes) {
141 if(isAbstract(g))
142 old2new[g] = out.setGate(islandLeafUuid(island_index.at(g)),
143 BooleanGate::IN, island_prob.at(g));
144 else if(c.getGateType(g) == BooleanGate::IN)
145 old2new[g] = out.setGate(c.getUUID(g), BooleanGate::IN, c.getProb(g));
146 else
147 old2new[g] = out.setGate(c.getGateType(g));
148 }
149 for(gate_t g : nodes) {
150 if(isAbstract(g) || c.getGateType(g) == BooleanGate::IN)
151 continue;
152 for(gate_t u : c.getWires(g))
153 out.addWire(old2new.at(g), old2new.at(u));
154 }
155 return old2new.at(root);
156}
157
158}
159
161{
162 static ProbCache cache;
163 return cache;
164}
165
167 const std::string &builder)
168{
169 auto it = map_.find(key.form);
170 if(it == map_.end()
171 || (!builder.empty() && it->second->builder != builder)) {
172 ++stats_.misses;
173 return nullptr;
174 }
175 ++stats_.hits;
176 lru_.splice(lru_.begin(), lru_, it->second);
177 return &*it->second;
178}
179
180bool ProbCache::admits(size_t bytes)
181{
182 if(bytes <= maxEntryBytes())
183 return true;
184 ++stats_.rejections;
185 return false;
186}
187
188bool ProbCache::insert(const CanonicalForm &key, Entry entry)
189{
190 auto it = map_.find(key.form);
191 if(it != map_.end()) {
192 bytes_ -= it->second->bytes;
193 lru_.erase(it->second);
194 map_.erase(it);
195 }
196 bytes_ += entry.bytes;
197 lru_.push_front(std::move(entry));
198 map_[key.form] = lru_.begin();
199 ++stats_.inserts;
200 trim();
201 return true;
202}
203
205{
206 while(bytes_ > maxCacheBytes() && !lru_.empty()) {
207 bytes_ -= lru_.back().bytes;
208 map_.erase(lru_.back().form);
209 lru_.pop_back();
210 ++stats_.evictions;
211 }
212}
213
215{
216 lru_.clear();
217 map_.clear();
218 bytes_ = 0;
220}
221
223{
225 s.entries = lru_.size();
226 s.bytes = bytes_;
227 s.budget = maxCacheBytes();
228 return s;
229}
230
232{
233 for(gate_t g : reachableNodes(c, root)) {
234 switch(c.getGateType(g)) {
235 case BooleanGate::AND:
236 case BooleanGate::OR:
237 case BooleanGate::NOT:
238 break;
239 case BooleanGate::IN:
240 if(c.getUUID(g).empty())
241 return false;
242 break;
243 default:
244 return false;
245 }
246 }
247 return true;
248}
249
250namespace {
251
252/// Runs @p compile, recording the builder it used in the report.
253dDNNF compileNoted(const BooleanCircuit &c, gate_t root,
254 const ProbCacheCompileFn &compile, bool *ran_compiler,
255 const ProbCacheOptions &options, std::string &builder)
256{
257 if(ran_compiler)
258 *ran_compiler = true;
259 dDNNF dd = compile(c, root);
260 builder = options.last_builder ? options.last_builder() : std::string();
261 if(options.report)
262 noteOnce(options.report->built, builder);
263 return dd;
264}
265
266double cachedComponent(const BooleanCircuit &c, gate_t root,
267 const ProbCacheCompileFn &compile,
268 bool *ran_compiler, const ProbCacheOptions &options)
269{
271 cache.trim();
272 const auto lookup = [&](const CanonicalForm &cf) {
273 const ProbCache::Entry *e = cache.find(cf, options.required_builder);
274 if(e && options.report)
275 noteOnce(options.report->cached, e->builder);
276 return e;
277 };
278 std::string builder;
279 const IslandKey key = computeIslandKey(c, root);
280
281 std::unordered_map<gate_t, size_t, hash_gate_t> island_index;
282 for(size_t i = 0; i < key.island_roots.size(); ++i)
283 island_index[key.island_roots[i]] = i;
284
285 std::unordered_map<gate_t, double, hash_gate_t> island_prob;
286 for(size_t i = 0; i < key.islands.size(); ++i) {
287 const CanonicalForm &icf = key.islands[i];
288 const gate_t g = key.island_roots[i];
289 double p;
290 if(const auto *e = lookup(icf)) {
291 std::vector<double> probs;
292 probs.reserve(icf.leaves.size());
293 for(const CanonicalLeaf &leaf : icf.leaves)
294 probs.push_back(c.getProb(leaf.gate));
295 p = instantiateAndEvaluate(*e, probs);
296 } else {
297 BooleanCircuit island;
298 gate_t island_root = materialiseComponent(c, g, nullptr, {}, {}, island);
299 dDNNF dd = compileNoted(island, island_root, compile, ran_compiler,
300 options, builder);
301 tryCacheCompiled(cache, icf, dd, builder, [&](const CanonicalLeaf &leaf) {
302 return c.getUUID(leaf.gate);
303 });
304 p = dd.probabilityEvaluation();
305 }
306 island_prob[g] = p;
307 }
308
309 const CanonicalForm &rcf = key.residual;
310 std::vector<double> probs;
311 probs.reserve(rcf.leaves.size());
312 for(const CanonicalLeaf &leaf : rcf.leaves)
313 probs.push_back(leaf.is_abstract ? island_prob.at(leaf.gate)
314 : c.getProb(leaf.gate));
315
316 if(const auto *e = lookup(rcf))
317 return instantiateAndEvaluate(*e, probs);
318
319 auto residualLeafUuid = [&](const CanonicalLeaf &leaf) {
320 return leaf.is_abstract ? islandLeafUuid(island_index.at(leaf.gate))
321 : c.getUUID(leaf.gate);
322 };
323
324 if(key.island_roots.empty()) {
325 dDNNF dd = compileNoted(c, root, compile, ran_compiler, options, builder);
326 tryCacheCompiled(cache, rcf, dd, builder, residualLeafUuid);
327 return dd.probabilityEvaluation();
328 }
329
330 GateSet frontier(key.island_roots.begin(), key.island_roots.end());
331 BooleanCircuit res;
332 gate_t res_root = materialiseComponent(c, root, &frontier, island_index,
333 island_prob, res);
334 dDNNF dd = compileNoted(res, res_root, compile, ran_compiler, options,
335 builder);
336 tryCacheCompiled(cache, rcf, dd, builder, residualLeafUuid);
337 return dd.probabilityEvaluation();
338}
339
340double evaluateComponent(const BooleanCircuit &c, gate_t root,
341 const ProbCacheCompileFn &compile,
342 bool *ran_compiler, const ProbCacheOptions &options)
343{
344 if(options.use_cache)
345 return cachedComponent(c, root, compile, ran_compiler, options);
346 std::string builder;
347 return compileNoted(c, root, compile, ran_compiler, options, builder)
348 .probabilityEvaluation();
349}
350
351std::vector<std::vector<gate_t> > independentGroups(
352 const BooleanCircuit &c, const std::vector<gate_t> &children)
353{
354 std::vector<size_t> parent(children.size());
355 std::iota(parent.begin(), parent.end(), size_t{0});
356 auto find = [&parent](size_t x) {
357 while(parent[x] != x) {
358 parent[x] = parent[parent[x]];
359 x = parent[x];
360 }
361 return x;
362 };
363
364 std::unordered_map<gate_t, size_t, CanonicalGateHash> owner;
365 std::vector<gate_t> stack;
366 for(size_t i = 0; i < children.size(); ++i) {
367 stack.push_back(children[i]);
368 while(!stack.empty()) {
369 const gate_t g = stack.back();
370 stack.pop_back();
371 const auto &wires = c.getWires(g);
372 if(wires.empty() && c.getGateType(g) != BooleanGate::IN)
373 continue;
374 const auto entry = owner.emplace(g, i);
375 if(!entry.second) {
376 parent[find(i)] = find(entry.first->second);
377 continue;
378 }
379 stack.insert(stack.end(), wires.begin(), wires.end());
380 }
381 }
382
383 std::unordered_map<size_t, size_t> position;
384 std::vector<std::vector<gate_t> > groups;
385 for(size_t i = 0; i < children.size(); ++i) {
386 const auto entry = position.emplace(find(i), groups.size());
387 if(entry.second)
388 groups.emplace_back();
389 groups[entry.first->second].push_back(children[i]);
390 }
391 return groups;
392}
393
394gate_t materialiseGroup(const BooleanCircuit &c, BooleanGate type,
395 const std::vector<gate_t> &children,
396 BooleanCircuit &out)
397{
398 std::unordered_map<gate_t, gate_t, CanonicalGateHash> old2new;
399 std::vector<gate_t> nodes;
400 std::vector<gate_t> stack(children.begin(), children.end());
401 while(!stack.empty()) {
402 const gate_t g = stack.back();
403 stack.pop_back();
404 if(!old2new.emplace(g, gate_t{0}).second)
405 continue;
406 nodes.push_back(g);
407 const auto &wires = c.getWires(g);
408 stack.insert(stack.end(), wires.begin(), wires.end());
409 }
410 std::sort(nodes.begin(), nodes.end());
411
412 for(gate_t g : nodes)
413 old2new[g] = c.getGateType(g) == BooleanGate::IN
414 ? out.setGate(c.getUUID(g), BooleanGate::IN, c.getProb(g))
415 : out.setGate(c.getGateType(g));
416 for(gate_t g : nodes)
417 if(c.getGateType(g) != BooleanGate::IN)
418 for(gate_t u : c.getWires(g))
419 out.addWire(old2new.at(g), old2new.at(u));
420
421 const gate_t root = out.setGate(type);
422 for(gate_t child : children)
423 out.addWire(root, old2new.at(child));
424 return root;
425}
426
427double foldedProbability(const BooleanCircuit &c, gate_t g,
428 const ProbFoldEval &eval, unsigned depth)
429{
430 const BooleanGate type = c.getGateType(g);
431 if(type == BooleanGate::IN)
432 return c.getProb(g);
433
434 if(depth < MAX_FOLD_DEPTH
435 && (type == BooleanGate::AND || type == BooleanGate::OR)) {
436 std::vector<gate_t> children;
437 GateSet seen;
438 for(gate_t w : c.getWires(g))
439 if(seen.insert(w).second)
440 children.push_back(w);
441
442 const auto groups = independentGroups(c, children);
443 if(groups.size() != 1 || groups.front().size() == 1) {
444 double product = 1.;
445 for(const auto &group : groups) {
446 double p;
447 if(group.size() == 1) {
448 p = foldedProbability(c, group.front(), eval, depth + 1);
449 } else {
450 BooleanCircuit part;
451 const gate_t part_root = materialiseGroup(c, type, group, part);
452 p = eval.part(part, part_root, true);
453 }
454 product *= type == BooleanGate::AND ? p : 1. - p;
455 }
456 return type == BooleanGate::AND ? product : 1. - product;
457 }
458 }
459
460 if(depth == 0)
461 return eval.whole();
462
463 BooleanCircuit part;
464 const gate_t part_root = materialiseComponent(c, g, nullptr, {}, {}, part);
465 return eval.part(part, part_root, false);
466}
467
468}
469
471 const ProbFoldEval &eval)
472{
473 return foldedProbability(c, root, eval, 0);
474}
475
477 const ProbCacheCompileFn &compile,
478 bool *ran_compiler,
479 const ProbCacheOptions &options)
480{
481 if(ran_compiler)
482 *ran_compiler = false;
483 if(options.fold) {
484 ProbFoldEval eval;
485 bool whole = false;
486 eval.part = [&](BooleanCircuit &part, gate_t part_root, bool) {
487 return evaluateComponent(part, part_root, compile, ran_compiler,
488 options);
489 };
490 eval.whole = [&]() {
491 whole = true;
492 return evaluateComponent(c, root, compile, ran_compiler, options);
493 };
494 const double p = foldedProbability(c, root, eval, 0);
495 if(options.report)
496 options.report->folded = !whole;
497 return p;
498 }
499 return evaluateComponent(c, root, compile, ran_compiler, options);
500}
501
502std::string ProbCacheReport::describe() const
503{
504 std::string label;
505 const auto add = [&label](const std::string &name) {
506 if(!label.empty())
507 label += ",";
508 label += name;
509 };
510 if(folded)
511 add("fold");
512 for(const std::string &b : built)
513 if(!b.empty())
514 add(b);
515 for(const std::string &b : cached)
516 add(b.empty() ? "cache" : "cache:" + b);
517 return label;
518}
519
520}
BooleanGate
Gate types for a Boolean provenance circuit.
@ NOT
Logical negation of a single child gate.
@ OR
Logical disjunction of child gates.
@ AND
Logical conjunction of child gates.
@ IN
Input (variable) gate representing a base tuple.
static CircuitCache cache
Process-local singleton circuit gate cache.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Cache of compiled d-DNNFs, and folding of independent parts.
Boolean circuit for provenance formula evaluation.
void setProb(gate_t g, double p)
Set the probability for gate g and mark the circuit as probabilistic.
gate_t setGate(BooleanGate type) override
Allocate a new gate with type type and no UUID.
double getProb(gate_t g) const
Return the probability stored for gate g.
bool insert(const CircuitCacheInfos &infos)
Insert a new gate into the cache, evicting the oldest if necessary.
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
void addWire(gate_t f, gate_t t)
Add a directed wire from gate f (parent) to gate t (child).
Definition Circuit.hpp:195
uuid getUUID(gate_t g) const
Return the UUID string associated with gate g.
Definition Circuit.hpp:65
gate_t getGate(const uuid &u)
Return (or create) the gate associated with UUID u.
Definition Circuit.hpp:50
bool hasGate(const uuid &u) const
Test whether a gate with UUID u exists.
Definition Circuit.hpp:30
std::vector< gate_t >::size_type getNbGates() const
Return the total number of gates in the circuit.
Definition Circuit.h:252
A d-DNNF circuit supporting exact probabilistic and game-theoretic evaluation.
Definition dDNNF.h:71
double probabilityEvaluation() const
Compute the exact probability of the d-DNNF being true.
Definition dDNNF.cpp:141
gate_t getRoot() const
Return the root gate of this d-DNNF.
Definition dDNNF.h:120
The cache of compiled d-DNNFs of one backend.
Definition ProbCache.h:57
std::unordered_map< std::string, std::list< Entry >::iterator > map_
Definition ProbCache.h:99
void trim()
Drops the least recently used entries until the cache fits its budget (which the setting may have low...
static ProbCache & instance()
The cache of this backend.
bool insert(const CanonicalForm &key, Entry entry)
Stores entry under key, replacing an entry already there.
std::list< Entry > lru_
Definition ProbCache.h:98
const Entry * find(const CanonicalForm &key, const std::string &builder=std::string())
Looks key up.
void reset()
Empties the cache and its counters.
ProbCacheStats stats() const
The counters, with the current number and size of entries.
ProbCacheStats stats_
Definition ProbCache.h:101
bool admits(size_t bytes)
Whether an entry of bytes is small enough to be stored; counts a rejection otherwise.
double probFoldedProbability(const BooleanCircuit &c, gate_t root, const ProbFoldEval &eval)
Probability of the circuit below root, folding the independent groups of AND and OR gates from the ro...
std::function< dDNNF(const BooleanCircuit &, gate_t)> ProbCacheCompileFn
Compiles the circuit below a gate into a d-DNNF.
Definition ProbCache.h:105
GateSet reachableNodes(const BooleanCircuit &c, gate_t root, const GateSet *abstract_leaves)
Gates reachable from root.
double probCachedProbability(const BooleanCircuit &c, gate_t root, const ProbCacheCompileFn &compile, bool *ran_compiler, const ProbCacheOptions &options)
Probability of the circuit below root through the fold and the cache.
IslandKey computeIslandKey(const BooleanCircuit &c, gate_t root)
Splits the circuit below root into its outermost islands and the residual.
bool probCacheEligible(const BooleanCircuit &c, gate_t root)
Whether the circuit below root is one the cache and the fold handle: AND, OR and NOT gates over input...
std::unordered_set< gate_t, CanonicalGateHash > GateSet
Set of gates of one circuit.
int provsql_prob_cache_size
Byte budget, in kB, of the per-backend cache of compiled d-DNNFs; provsql.prob_cache_size GUC.
Definition provsql.c:140
int provsql_max_memory
Memory, in MB, that the evaluations of a statement may add to the backend's resident set,...
Definition provsql.c:131
Core types, constants, and utilities shared across ProvSQL.
Canonical form of a circuit below a root.
std::string form
The form, e.g. (OR (AND V V) (AND V #4)).
A leaf of a canonical form, in the order the form meets it.
A circuit split into its outermost islands and what remains.
What probCachedProbability may do, and what it reports back.
Definition ProbCache.h:121
bool fold
Fold the independent groups of the root first.
Definition ProbCache.h:123
ProbCacheReport * report
Definition ProbCache.h:129
bool folded
root split into independent groups
Definition ProbCache.h:111
std::vector< std::string > built
builders run on a miss
Definition ProbCache.h:112
std::string describe() const
Comma-separated label: "fold" if folded, the builders that ran, then "cache:<builder>" for each build...
std::vector< std::string > cached
builders of the entries served
Definition ProbCache.h:113
Counters of the cache since it was last emptied.
Definition ProbCache.h:38
size_t bytes
Estimated size of the entries held now.
Definition ProbCache.h:45
size_t budget
Size the entries may reach before some are dropped.
Definition ProbCache.h:46
size_t entries
Entries held now.
Definition ProbCache.h:44
A compiled d-DNNF and how its inputs match the leaves of its form.
Definition ProbCache.h:60
size_t bytes
Estimated size of the entry.
Definition ProbCache.h:67
std::string form
Canonical form the d-DNNF was compiled for.
Definition ProbCache.h:61
How probFoldedProbability evaluates what it cannot fold.
Definition ProbCache.h:133
std::function< double()> whole
Probability of the whole circuit, when its root has nothing to fold.
Definition ProbCache.h:139
std::function< double(BooleanCircuit &, gate_t, bool)> part
Probability of a part, given as a circuit of its own and its root; the flag tells a group of several ...
Definition ProbCache.h:137