ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
RvHistogram.cpp
Go to the documentation of this file.
1/**
2 * @file RvHistogram.cpp
3 * @brief SQL function `provsql.rv_histogram(token, bins)`.
4 *
5 * Returns an empirical histogram of the scalar values produced by the
6 * sub-circuit rooted at @c token, binned into @p bins equal-width
7 * intervals between the observed minimum and maximum. The sample
8 * count is taken from @c provsql.rv_mc_samples; pinning
9 * @c provsql.monte_carlo_seed makes the result reproducible.
10 *
11 * Output: a jsonb array of objects @c {bin_lo, bin_hi, count}, one per
12 * non-empty bin (zero-count bins are still emitted so the client can
13 * draw a flat baseline). Returning jsonb rather than @c SETOF record
14 * keeps the C++ side free of SRF / FuncCallContext mechanics and
15 * matches the pattern used by @c simplified_circuit_subgraph.
16 *
17 * Accepted root gate types:
18 * - @c gate_value: degenerate Dirac at the constant. Emits a single
19 * bin at @c (v, v) with count equal to the would-be sample count,
20 * so the client can normalise to a probability mass without a
21 * special case.
22 * - @c gate_rv: sampled from the leaf's distribution.
23 * - @c gate_arith: sampled by recursing through the arithmetic DAG,
24 * reusing @c gate_rv draws within an iteration so shared leaves
25 * are correctly correlated.
26 * - @c gate_mixture: sampled by recursing through the mixture's
27 * Bernoulli (gate_input) wire and the selected scalar branch,
28 * reusing per-iteration caches so a shared p_token across the
29 * circuit produces coupled draws.
30 * - @c gate_agg: sampled per Monte Carlo iteration by walking the
31 * gate_semimod children, applying their Boolean filter, and
32 * finalising the chosen aggregator (COUNT / SUM / AVG / MIN /
33 * MAX). Same machinery probability evaluation uses for HAVING
34 * under MC; see @c MonteCarloSampler::evalScalar.
35 * - @c gate_semimod: a bare per-row contribution interpreted as
36 * value · 1_{k fires}, i.e. zero in worlds where the row's
37 * Boolean filter does not fire and the scalar value otherwise.
38 *
39 * Any other gate type still raises: Boolean-valued gates fall under
40 * @c probability_evaluate, and unsupported scalar shapes (delta…)
41 * have no defined sampling semantics.
42 */
43extern "C" {
44#include "postgres.h"
45#include "fmgr.h"
46#include "utils/jsonb.h"
47#include "utils/fmgrprotos.h"
48#include "utils/uuid.h"
49#include "provsql_utils.h"
50#include "provsql_error.h"
51
52PG_FUNCTION_INFO_V1(rv_histogram);
53}
54
55#include "CircuitFromMMap.h"
56#include "Expectation.h"
57#include "GenericCircuit.h"
58#include "MonteCarloSampler.h"
59#include "RandomVariable.h"
60#include "RangeCheck.h"
61#include "provsql_utils_cpp.h"
62
63#include <algorithm>
64#include <cmath>
65#include <iomanip>
66#include <optional>
67#include <sstream>
68#include <string>
69#include <tuple>
70#include <utility>
71#include <vector>
72#include "provsql_interrupt.h"
73
74namespace {
75
76void emit_bin(std::ostringstream &out, bool &first,
77 double lo, double hi, double count)
78{
79 if (!first) out << ',';
80 first = false;
81 out << "{\"bin_lo\":" << lo
82 << ",\"bin_hi\":" << hi
83 << ",\"count\":" << count << '}';
84}
85
86} // namespace
87
88extern "C" Datum
89rv_histogram(PG_FUNCTION_ARGS)
90{
91 pg_uuid_t *root_arg = (pg_uuid_t *) PG_GETARG_POINTER(0);
92 int bins = PG_GETARG_INT32(1);
93 pg_uuid_t *prov_arg = (pg_uuid_t *) PG_GETARG_POINTER(2);
94
95 if (bins <= 0)
96 provsql_error("rv_histogram: bins must be positive (got %d)", bins);
97
98 std::ostringstream out;
99 /* setprecision(17) preserves full double round-trip through the
100 * jsonb_in parser, so the client sees the same bin edges that the
101 * sampler produced. */
102 out << std::setprecision(17);
103 out << '[';
104 bool first = true;
105
106 try {
107 provsql_interrupt_scope interrupt_scope;
108 /* Always go through getJointCircuit: when prov is gate_one() the
109 * joint loader still produces a valid single-root closure (the
110 * gate_one leaf is just an extra disconnected node). This keeps
111 * a single code path for shared-leaf coupling between the
112 * indicator (event_gate) and the value (root_gate) in the
113 * conditional case. */
114 gate_t root_gate, event_gate;
116 try {
117 gc = getJointCircuit(*root_arg, *prov_arg, root_gate, event_gate);
118 } catch (const CircuitException &) {
119 out << ']';
120 Datum json = DirectFunctionCall1(
121 jsonb_in, CStringGetDatum(pstrdup(out.str().c_str())));
122 PG_RETURN_DATUM(json);
123 }
124
125 /* gate_one event = unconditional. */
126 std::optional<gate_t> event_opt;
127 if (gc.getGateType(event_gate) != gate_one) event_opt = event_gate;
128 /* A stored "X | C" arrives as a conditioned root: peel it to the bare
129 * scalar target and fold the condition into the event, so the histogram
130 * is of the conditional (truncated) distribution. */
131 root_gate = provsql::lift_conditioning(gc, root_gate, event_opt);
132 const bool conditional = event_opt.has_value();
133
134 const gate_type t = gc.getGateType(root_gate);
135
136 if (t == gate_value) {
137 /* Dirac: parse the literal, emit one degenerate bin. Count
138 * mirrors rv_mc_samples (or 1 if MC is disabled) so the client
139 * can compute relative mass the same way for every gate kind. */
140 const double v = provsql::parseDoubleStrict(gc.getExtra(root_gate));
141 const unsigned n = provsql_rv_mc_samples > 0
142 ? static_cast<unsigned>(provsql_rv_mc_samples)
143 : 1u;
144 emit_bin(out, first, v, v, n);
145 } else if (t == gate_rv || t == gate_arith || t == gate_mixture
146 || t == gate_agg || t == gate_semimod || t == gate_case) {
147 std::vector<double> samples;
148 /* Exact analytical histogram: when the (peeled) root matches a
149 * closed-form distribution -- a (truncated) Gaussian, a sum of
150 * Normals, a mixture of bare RVs -- the per-bin probability mass is
151 * cdf(hi) - cdf(lo), exact and sampling-free. This is the right
152 * answer whatever provsql.rv_mc_samples is (in particular 0):
153 * truncating a Gaussian has an exact distribution. Composites with
154 * no closed form (general gate_arith, gate_agg) fall through to
155 * Monte Carlo below. */
156 auto shape = provsql::matchClosedFormDistribution(gc, root_gate, event_opt);
157 std::optional<std::vector<std::tuple<double, double, double>>> ahist;
158 if (shape) ahist = provsql::analyticalHistogram(*shape, bins);
159
160 if (ahist) {
161 for (const auto &[bl, bh, mass] : *ahist)
162 emit_bin(out, first, bl, bh, mass);
163 } else if (provsql_rv_mc_samples <= 0) {
164 /* No closed form and sampling disabled: empty histogram rather
165 * than an error, so a distribution-profile composed with the
166 * closed-form support / moments still succeeds. */
167 ereport(NOTICE,
168 (errmsg("rv_histogram: no closed-form shape and "
169 "provsql.rv_mc_samples = 0; returning an empty "
170 "histogram")));
171 } else {
172 const unsigned N = static_cast<unsigned>(provsql_rv_mc_samples);
173
174 if (conditional) {
175 /* Closed-form truncation fast path: when the root is a bare
176 * gate_rv of a supported family and the event reduces to an
177 * interval on it, draw exactly @c N samples from the truncated
178 * distribution. 100% acceptance, so the "accepted 0 of N"
179 * error below no longer fires on tight events that previously
180 * starved the MC rejection path. */
182 gc, root_gate, *event_opt, N);
183 if (direct) {
184 samples = std::move(*direct);
185 } else {
187 gc, root_gate, *event_opt, N);
188 if (cs.accepted.empty())
190 "rv_histogram: conditional MC accepted 0 of %u samples; "
191 "raise provsql.rv_mc_samples or check that the event is "
192 "satisfiable",
193 cs.attempted);
194 samples = provsql::definedDraws(cs.accepted);
195 }
196 } else {
197 samples = provsql::definedDraws(
198 provsql::monteCarloScalarSamples(gc, root_gate, N));
199 }
200 } /* end: rv_mc_samples > 0 */
201
202 /* A NaN drawn (a NaN in the data) has no place on the axis. */
203 samples.erase(std::remove_if(samples.begin(), samples.end(),
204 [](double x) { return std::isnan(x); }),
205 samples.end());
206 if (!samples.empty()) {
207 /* Pick the bin range per side: when @c compute_support proves
208 * a finite support endpoint we use it verbatim (Uniform / sums
209 * of Uniforms / mixtures of bounded RVs / Exponential's lower
210 * end at 0 / etc.), because the analytical bound is tighter
211 * than any sample-based estimate. When the support is open
212 * on a side (Normal, sums involving Normal, the upper tail of
213 * Exponential / Erlang) the raw empirical extreme would be
214 * an outlier draw -- ~±4σ for a Normal at rv_mc_samples = 10000
215 * -- which stretches the histogram so the bulk of the mass
216 * concentrates in middle bins and the edge bins look empty.
217 * Trim the outermost 0.1% of samples on that side; samples
218 * outside the trimmed range still get pooled into the edge
219 * bin (the clamp below), so total counts stay conserved. */
220 std::sort(samples.begin(), samples.end());
221 const std::size_t n = samples.size();
222 const std::size_t lo_idx = n / 1000; /* 0.1% */
223 const std::size_t hi_idx = n - 1 - lo_idx;
224 auto support = provsql::compute_support(gc, root_gate, event_opt);
225 double smin = std::isfinite(support.first)
226 ? support.first
227 : samples[lo_idx];
228 double smax = std::isfinite(support.second)
229 ? support.second
230 : samples[hi_idx];
231 if (smin == smax) {
232 /* Degenerate: trimmed range collapsed to a point (every
233 * non-tail draw is the same value, or the simplifier
234 * elided everything but a single point-mass leaf). */
235 emit_bin(out, first, smin, smax,
236 static_cast<unsigned>(samples.size()));
237 } else {
238 std::vector<unsigned> counts(bins, 0);
239 const double width = (smax - smin) / bins;
240 for (double x : samples) {
241 int b = static_cast<int>((x - smin) / width);
242 if (b < 0) b = 0;
243 if (b >= bins) b = bins - 1;
244 counts[b] += 1;
245 }
246 for (int i = 0; i < bins; ++i) {
247 const double lo = smin + i * width;
248 const double hi = (i == bins - 1) ? smax : lo + width;
249 emit_bin(out, first, lo, hi, counts[i]);
250 }
251 }
252 }
253 } else {
254 const char *type_name = (t < nb_gate_types)
255 ? gate_type_name[t] : "invalid";
257 "rv_histogram: root gate type '%s' is not a scalar "
258 "(expected gate_value, gate_rv, gate_arith, gate_mixture, "
259 "gate_agg, gate_semimod, or gate_case)",
260 type_name);
261 }
262 } catch (const std::exception &e) {
264 provsql_error("rv_histogram: %s", e.what());
265 } catch (...) {
267 provsql_error("rv_histogram: unknown exception");
268 }
269
270 out << ']';
271 Datum json = DirectFunctionCall1(
272 jsonb_in, CStringGetDatum(pstrdup(out.str().c_str())));
273 PG_RETURN_DATUM(json);
274}
GenericCircuit getJointCircuit(const std::vector< pg_uuid_t > &tokens, std::vector< gate_t > &gates)
Multi-root variant of getJointCircuit.
Build in-memory circuits from the mmap-backed persistent store.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Analytical expectation / variance / moment evaluator over RV circuits.
Semiring-agnostic in-memory provenance circuit.
Monte Carlo sampling over a GenericCircuit, RV-aware.
Continuous random-variable helpers (distribution parsing, moments).
Support-based bound check for continuous-RV comparators.
Datum rv_histogram(PG_FUNCTION_ARGS)
Exception type thrown by circuit operations on invalid input.
Definition Circuit.h:382
gateType getGateType(gate_t g) const
Return the type of gate g.
Definition Circuit.h:301
std::string getExtra(gate_t g) const
Return the string extra for gate g.
The SIGINT handler installed for the lifetime of the object, the previous one restored as it ends (a ...
std::pair< double, double > compute_support(const GenericCircuit &gc, gate_t root, std::optional< gate_t > event_root)
Compute the [lo, hi] support interval of a scalar sub-circuit rooted at root.
std::optional< ClosedFormShape > matchClosedFormDistribution(const GenericCircuit &gc, gate_t root, std::optional< gate_t > event_root)
Detect any of the closed-form shapes supported by rv_analytical_curves.
std::vector< std::optional< double > > monteCarloScalarSamples(const GenericCircuit &gc, gate_t root, unsigned samples)
Sample a scalar sub-circuit samples times and return the draws.
gate_t lift_conditioning(GenericCircuit &gc, gate_t root, std::optional< gate_t > &event_opt)
Lift conditioning out of a scalar arithmetic expression.
std::optional< std::vector< std::tuple< double, double, double > > > analyticalHistogram(const ClosedFormShape &shape, int bins)
Exact histogram (bin_lo, bin_hi, probability mass) of a closed-form shape, in bins equal-width bins o...
double parseDoubleStrict(const std::string &s)
Strictly parse s as a double.
ConditionalScalarSamples monteCarloConditionalScalarSamples(const GenericCircuit &gc, gate_t root, gate_t event_root, unsigned samples)
Rejection-sample root conditioned on event_root.
std::optional< std::vector< double > > try_truncated_closed_form_sample(const GenericCircuit &gc, gate_t root, gate_t event_root, unsigned n)
Try to draw n exact samples from the conditional distribution of root given event_root via closed-for...
std::vector< double > definedDraws(const std::vector< std::optional< double > > &samples)
The draws of samples that have a value, in order.
int provsql_rv_mc_samples
Default sample count for analytical-evaluator MC fallbacks; 0 disables fallback (callers raise instea...
Definition provsql.c:126
Uniform error-reporting macros for ProvSQL.
#define provsql_error(fmt,...)
Report a fatal ProvSQL error and abort the current transaction.
void provsql_cancel_if_interrupted(void)
Raise PG's cancel if the evaluation stopped for one; nothing otherwise.
Cancellation of the long C++ evaluation loops.
const char * gate_type_name[]
Names of gate types.
Core types, constants, and utilities shared across ProvSQL.
@ gate_rv
Continuous random-variable leaf (extra encodes distribution).
@ gate_case
N-ary guarded selection over scalar (RV) children: wires are [guard_1, value_1, .....
@ gate_mixture
Probabilistic mixture: three wires [p_token (gate_input Bernoulli), x_token, y_token]; samples x when...
@ gate_arith
n-ary arithmetic gate over scalar-valued children (info1 holds operator tag)
C++ utility functions for UUID manipulation.