provenance_evaluate_compiled.cpp

Go to the documentation of this file.

/**
 * @file provenance_evaluate_compiled.cpp
 * @brief SQL function @c provsql.provenance_evaluate_compiled() – C++ semiring evaluation.
 *
 * Implements the compiled (C++ generic) variant of provenance circuit
 * evaluation.  Unlike @c provenance_evaluate() (which calls user-supplied
 * PostgreSQL functions for each semiring operation), this function
 * evaluates the circuit using one of the built-in C++ semiring
 * implementations from the @c semiring/ directory.
 *
 * Supported semirings (selected by the @p semiring argument):
 * - @c "boolean"   → @c semiring::Boolean
 * - @c "counting"  → @c semiring::Counting
 * - @c "formula"   → @c semiring::Formula (symbolic representation as a formula)
 * - @c "how"       → @c semiring::How (canonical polynomial provenance ℕ[X])
 * - @c "why"       → @c semiring::Why (witness sets)
 * - @c "which"     → @c semiring::Which (lineage)
 * - @c "boolexpr"  → @c semiring::BoolExpr (Boolean circuit for probability)
 * - @c "tropical"  → @c semiring::Tropical (min-plus, shortest-cost)
 * - @c "viterbi"   → @c semiring::Viterbi (max-times, most-likely derivation)
 * - @c "lukasiewicz" → @c semiring::Lukasiewicz (Łukasiewicz fuzzy t-norm)
 * - @c "interval_union" → @c semiring::IntervalUnion (multirange union, PG14+)
 *   for any of <tt>tstzmultirange</tt>, <tt>nummultirange</tt>,
 *   <tt>int4multirange</tt>; selected by the result type of the call
 * - @c "minmax" / @c "maxmin" → @c semiring::MinMax over any user-defined
 *   PostgreSQL enum type, selected by @c get_typtype() == @c TYPTYPE_ENUM
 *
 * Each compiled semiring exposes @c parse_leaf() and (for text-valued
 * carriers) @c to_text() member functions, so this file is purely a
 * dispatcher: it picks the right semiring instance from the
 * (result-type, semiring-name) pair, then calls the @c pec() template
 * which runs the same four-step pipeline for every semiring (build leaf
 * mapping, evaluate HAVING sub-circuits, evaluate the main circuit,
 * encode the result as a Datum).
 */
extern "C" {
#include "postgres.h"
#include "fmgr.h"
#include "catalog/pg_type.h"
#include "utils/uuid.h"
#include "utils/builtins.h"
#include "utils/lsyscache.h"
#include "provsql_utils.h"
#include "provsql_mmap.h"
 
PG_FUNCTION_INFO_V1(provenance_evaluate_compiled);
PG_FUNCTION_INFO_V1(plain_truth);
}
 
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
 
#include "Expectation.h"
#include "having_semantics.hpp"
#include "provenance_evaluate_compiled.hpp"
#include "semiring/Boolean.h"
#include "semiring/Counting.h"
#include "semiring/Formula.h"
#include "semiring/How.h"
#include "semiring/Why.h"
#include "semiring/Which.h"
#include "semiring/BoolExpr.h"
#include "semiring/Tropical.h"
#include "semiring/Viterbi.h"
#include "semiring/Lukasiewicz.h"
#include "semiring/IntervalUnion.h"
#include "semiring/MinMax.h"
 
const char *drop_temp_table = "DROP TABLE IF EXISTS tmp_uuids;";
 
namespace {
 
/**
 * @brief Wrap a @c std::string in a Postgres @c text Datum.
 */
Datum text_datum(const std::string &s) {
  text *result = (text *) palloc(VARHDRSZ + s.size());
  SET_VARSIZE(result, VARHDRSZ + s.size());
  memcpy(VARDATA(result), s.c_str(), s.size());
  return PointerGetDatum(result);
}
 
// to_datum overloads: encode a semiring's evaluation result as a Postgres Datum.
Datum to_datum(const semiring::Boolean &, bool v)         { return BoolGetDatum(v); }
Datum to_datum(const semiring::Counting &, unsigned v)    { return Int32GetDatum(static_cast<int32>(v)); }
Datum to_datum(const semiring::Tropical &, double v)      { return Float8GetDatum(v); }
Datum to_datum(const semiring::Viterbi &, double v)       { return Float8GetDatum(v); }
Datum to_datum(const semiring::Lukasiewicz &, double v)   { return Float8GetDatum(v); }
Datum to_datum(const semiring::Formula &sr, const std::string &v) { return text_datum(sr.to_text(v)); }
Datum to_datum(const semiring::Why &sr, const semiring::why_provenance_t &v)     { return text_datum(sr.to_text(v)); }
Datum to_datum(const semiring::How &sr, const semiring::how_provenance_t &v)     { return text_datum(sr.to_text(v)); }
Datum to_datum(const semiring::Which &sr, const semiring::which_provenance_t &v) { return text_datum(sr.to_text(v)); }
#if PG_VERSION_NUM >= 140000
Datum to_datum(const semiring::IntervalUnion &, Datum v)  { return v; }
#endif
Datum to_datum(const semiring::MinMax &, Datum v)         { return v; }
 
/**
 * @brief Run the four-step compiled-evaluation pipeline for a semiring.
 *
 * 1. Build the input-gate → leaf-value mapping by parsing each leaf via
 *    @c sr.parse_leaf().
 * 2. Rewrite HAVING comparison gates in @p c via @c provsql_having().
 * 3. Evaluate the main circuit at @p g.
 * 4. Encode the result as a Postgres Datum via @c to_datum(sr, ...).
 *
 * @tparam Sem        The compiled semiring class.
 * @param constants   Extension OID cache.
 * @param c           Generic circuit to evaluate.
 * @param g           Root gate.
 * @param sr          Semiring instance.
 * @param drop_table  Whether the temporary UUID table should be dropped.
 * @return            The semiring evaluation result encoded as a Datum.
 */
template <typename Sem>
Datum pec(
  const constants_t &constants,
  GenericCircuit &c,
  gate_t g,
  const Sem &sr,
  bool drop_table)
{
  using V = typename Sem::value_type;
  std::unordered_map<gate_t, V> mapping;
  initialize_provenance_mapping<V>(constants, c, mapping,
    [&sr](const char *v) { return sr.parse_leaf(v); }, drop_table);
 
  provsql_having(c, g, mapping, sr);
  V out = c.evaluate<Sem>(g, mapping, sr);
  return to_datum(sr, std::move(out));
}
 
/**
 * @brief Evaluate the BoolExpr semiring; bypasses the GenericCircuit pipeline.
 *
 * With @p labels, each input gate renders as its mapped label; without,
 * leaves render as the default @c x@<id@> placeholders.
 */
Datum pec_boolexpr(
  BooleanCircuit &bc,
  gate_t root,
  const std::unordered_map<gate_t, std::string> *labels)
{
  return text_datum(labels ? bc.toString(root, *labels) : bc.toString(root));
}
 
} // namespace
 
/**
 * @brief Join a provenance mapping table with a set of UUIDs using SPI.
 * @param table  OID of the provenance mapping relation.
 * @param uuids  List of UUID strings to join against.
 * @return       @c true if a temporary table was created (caller must drop it).
 */
bool join_with_temp_uuids(Oid table, const std::vector<std::string> &uuids) {
  if (SPI_connect() != SPI_OK_CONNECT)
    throw CircuitException("SPI_connect failed");
 
  // No mapping given: run an empty join, so the provenance mapping stays
  // empty and every leaf falls back to the semiring's one (the
  // absent-mapping convention).
  if (!OidIsValid(table)) {
    if (SPI_exec("SELECT ''::text AS value, NULL::uuid AS provenance WHERE false",
                 0) != SPI_OK_SELECT) {
      SPI_finish();
      throw CircuitException("Join query failed");
    }
    return false;
  }
 
  char *table_name = get_rel_name(table);
  if (!table_name) {
    SPI_finish();
    throw CircuitException("Invalid OID: no such table");
  }
  // Schema-qualify so the lookup works regardless of search_path.
  // get_rel_name alone would resolve unqualified, which fails when the
  // mapping lives in a schema not on search_path (e.g. provsql_test in
  // the regression DB, or any user schema reached via Studio with the
  // default "public, provsql" search_path).
  const char *qualified = quote_qualified_identifier(
    get_namespace_name(get_rel_namespace(table)), table_name);
 
  constexpr size_t nb_max_uuid_value = 10000000;
 
  StringInfoData join_query;
  initStringInfo(&join_query);
  bool drop_table = false;
 
  // Two different mechanisms to implement the join (unless there are no
  // UUIDs):
  // if there are less than nb_max_uuid_value UUIDs, we do a join
  // with a VALUES() list;
  // otherwise we create a temporary table where we dump the inserts
  // and join with it.
  if(uuids.size() == 0) {
    appendStringInfo(&join_query,
                     "SELECT value, provenance FROM %s WHERE 'f'", qualified);
  } else if(uuids.size() <= nb_max_uuid_value) {
    appendStringInfo(&join_query,
                     "SELECT value, provenance FROM %s t JOIN (VALUES", qualified);
    bool first=true;
    for(auto u: uuids) {
      appendStringInfo(&join_query, "%s('%s'::uuid)", first?"":",", u.c_str());
      first=false;
    }
 
    appendStringInfo(&join_query, ") AS u(id) ON t.provenance=u.id");
  } else {
    const char *create_temp_table = "CREATE TEMP TABLE tmp_uuids(id uuid);";
    if (SPI_exec(create_temp_table, 0) != SPI_OK_UTILITY) {
      SPI_finish();
      throw CircuitException("Failed to create temporary table");
    }
    drop_table = true;
 
    constexpr size_t batch_size = 1000;
 
    for (size_t offset = 0; offset < uuids.size(); offset += batch_size) {
      StringInfoData insert_query;
      initStringInfo(&insert_query);
      appendStringInfo(&insert_query, "INSERT INTO tmp_uuids VALUES ");
 
      size_t end = std::min(offset + batch_size, uuids.size());
      for (size_t i = offset; i < end; ++i) {
        appendStringInfo(&insert_query, "('%s')%s", uuids[i].c_str(), (i + 1 == end) ? "" : ",");
      }
 
      int retval=SPI_exec(insert_query.data, 0);
      pfree(insert_query.data);
 
      if(retval != SPI_OK_INSERT) {
        SPI_exec(drop_temp_table, 0);
        SPI_finish();
        throw CircuitException("Batch insert into temp table failed");
      }
    }
 
    appendStringInfo(&join_query,
                     "SELECT value, provenance FROM %s t JOIN tmp_uuids u ON t.provenance = u.id", qualified);
  }
 
  if (SPI_exec(join_query.data, 0) != SPI_OK_SELECT) {
    if(drop_table)
      SPI_exec(drop_temp_table, 0);
    SPI_finish();
    throw CircuitException("Join query failed");
  }
 
  return drop_table;
}
 
/**
 * @brief Core implementation of compiled provenance evaluation.
 * @param token    UUID of the root provenance gate.
 * @param table    OID of the provenance mapping relation.
 * @param semiring Name of the semiring to evaluate over.
 * @param type     OID of the result element type.
 * @return         Datum containing the semiring evaluation result.
 */
static Datum provenance_evaluate_compiled_internal
  (pg_uuid_t token, Oid table, const std::string &semiring, Oid type)
{
  constants_t constants = get_constants(true);
 
  // boolexpr without a mapping has nothing to fetch from SPI: skip the
  // GenericCircuit build + temp-UUID join and read the BooleanCircuit
  // directly. Every other case (including boolexpr WITH a mapping)
  // shares the prelude below.
  if(semiring=="boolexpr" && !OidIsValid(table)) {
    gate_t root;
    BooleanCircuit bc = getBooleanCircuit(token, root);
    return pec_boolexpr(bc, root, nullptr);
  }
 
  // The expectation evaluator reads its leaves directly from the
  // gate_rv / gate_value extra fields; no leaf-mapping table is
  // involved.  Bypass the SPI prelude.
  if(semiring=="expectation") {
    if(type != constants.OID_TYPE_FLOAT)
      throw CircuitException(
              "Unknown element type for expectation: must be float8");
    GenericCircuit gc = getGenericCircuit(token);
    auto root = gc.getGate(uuid2string(token));
    return Float8GetDatum(provsql::compute_expectation(gc, root));
  }
 
  GenericCircuit c = getGenericCircuit(token);
  auto g = c.getGate(uuid2string(token));
  auto inputs = c.getInputs();
 
  std::vector<std::string> inputs_uuid;
  std::transform(inputs.begin(), inputs.end(), std::back_inserter(inputs_uuid), [&c](auto x) {
    return c.getUUID(x);
  });
  bool drop_table = join_with_temp_uuids(table, inputs_uuid);
 
  if(semiring=="boolexpr") {
    // boolexpr with a mapping: build the gate-to-label map on the
    // GenericCircuit (the mapping table is keyed by input UUIDs that
    // don't survive translation to BooleanCircuit gate ids), then
    // translate keys to bc gates via gc_to_bc so bc.toString can label
    // each leaf with its mapped value.
    gate_t root;
    std::unordered_map<gate_t, std::string> gc_labels;
    initialize_provenance_mapping<std::string>(constants, c, gc_labels, [](const char *v) {
      return std::string(v);
    }, drop_table);
 
    std::unordered_map<gate_t, gate_t> gc_to_bc;
    BooleanCircuit bc = getBooleanCircuit(c, token, root, gc_to_bc);
 
    std::unordered_map<gate_t, std::string> bc_labels;
    bc_labels.reserve(gc_labels.size());
    for(const auto &kv : gc_labels) {
      auto it = gc_to_bc.find(kv.first);
      if(it != gc_to_bc.end())
        bc_labels[it->second] = kv.second;
    }
    return pec_boolexpr(bc, root, &bc_labels);
  }
 
  if (type == constants.OID_TYPE_VARCHAR)
  {
    if (semiring == "formula") return pec(constants, c, g, semiring::Formula{}, drop_table);
    if (semiring == "why")     return pec(constants, c, g, semiring::Why{}, drop_table);
    if (semiring == "how")     return pec(constants, c, g, semiring::How{}, drop_table);
    if (semiring == "which")   return pec(constants, c, g, semiring::Which{}, drop_table);
    throw CircuitException("Unknown semiring for type varchar: " + semiring);
  }
  if (type == constants.OID_TYPE_INT) {
    if (semiring == "counting") return pec(constants, c, g, semiring::Counting{}, drop_table);
    throw CircuitException("Unknown semiring for type int: " + semiring);
  }
  if (type == constants.OID_TYPE_FLOAT) {
    if (semiring == "tropical")    return pec(constants, c, g, semiring::Tropical{}, drop_table);
    if (semiring == "tropical_nonneg")
      return pec(constants, c, g, semiring::TropicalNonneg{}, drop_table);
    if (semiring == "viterbi")     return pec(constants, c, g, semiring::Viterbi{}, drop_table);
    if (semiring == "lukasiewicz") return pec(constants, c, g, semiring::Lukasiewicz{}, drop_table);
    throw CircuitException("Unknown semiring for type float: " + semiring);
  }
  if (type == constants.OID_TYPE_BOOL) {
    if (semiring == "boolean") return pec(constants, c, g, semiring::Boolean{}, drop_table);
    throw CircuitException("Unknown semiring for type bool: " + semiring);
  }
#if PG_VERSION_NUM >= 140000
  if (type == constants.OID_TYPE_TSTZMULTIRANGE) {
    if (semiring != "temporal" && semiring != "interval_union")
      throw CircuitException("Unknown semiring for type tstzmultirange: " + semiring);
    return pec(constants, c, g, semiring::IntervalUnion(constants.OID_TYPE_TSTZMULTIRANGE), drop_table);
  }
  if (type == constants.OID_TYPE_NUMMULTIRANGE) {
    if (semiring != "interval_union")
      throw CircuitException("Unknown semiring for type nummultirange: " + semiring);
    return pec(constants, c, g, semiring::IntervalUnion(constants.OID_TYPE_NUMMULTIRANGE), drop_table);
  }
  if (type == constants.OID_TYPE_INT4MULTIRANGE) {
    if (semiring != "interval_union")
      throw CircuitException("Unknown semiring for type int4multirange: " + semiring);
    return pec(constants, c, g, semiring::IntervalUnion(constants.OID_TYPE_INT4MULTIRANGE), drop_table);
  }
#endif
  if (get_typtype(type) == TYPTYPE_ENUM) {
    if (semiring == "minmax") return pec(constants, c, g, semiring::MinMax(type, false), drop_table);
    if (semiring == "maxmin") return pec(constants, c, g, semiring::MinMax(type, true), drop_table);
    throw CircuitException("Unknown semiring for enum type: " + semiring);
  }
  throw CircuitException("Unknown element type for provenance_evaluate_compiled");
}
 
/** @brief PostgreSQL-callable wrapper for provenance_evaluate_compiled(). */
Datum provenance_evaluate_compiled(PG_FUNCTION_ARGS)
{
  /* The sr_* SQL wrappers are STRICT, but the function itself is not:
   * guard the required arguments rather than rely on the wrappers.  The
   * mapping (argument 1) is legitimately NULL -- the no-mapping mode
   * renders anonymous leaves -- and reads as InvalidOid below. */
  if (PG_ARGISNULL(0) || PG_ARGISNULL(2))
    PG_RETURN_NULL();
 
  try {
    Datum token = PG_GETARG_DATUM(0);
 
    Oid table = PG_GETARG_OID(1);
 
    text *t = PG_GETARG_TEXT_P(2);
    std::string semiring(VARDATA(t),VARSIZE(t)-VARHDRSZ);
 
    Oid type = get_fn_expr_argtype(fcinfo->flinfo, 3);
 
    return provenance_evaluate_compiled_internal(*DatumGetUUIDP(token), table, semiring, type);
  } catch(const std::exception &e) {
    provsql_error("provenance_evaluate_compiled: %s", e.what());
  } catch(...) {
    provsql_error("provenance_evaluate_compiled: Unknown exception");
  }
 
  PG_RETURN_NULL();
}
 
namespace {
 
/** Truth of the gates already met, in the database as it is: a gate never
 *  changes once created, nor does an input tuple's presence for the rows
 *  that read it.  Bounded, so that a long session does not grow it forever. */
std::unordered_map<std::string, bool> plain_truth_memo;
constexpr size_t plain_truth_memo_max = 1000000;
 
/** 1 / 0 for a gate whose truth follows from its type and its children's,
 *  -1 for one that needs the full evaluation (a comparison, ...). */
int quick_plain_truth(const pg_uuid_t &token, unsigned depth)
{
  std::string key = uuid2string(token);
  auto it = plain_truth_memo.find(key);
  if (it != plain_truth_memo.end())
    return it->second;
  if (depth > 64)
    return -1;
 
  unsigned nb_children = 0;
  pg_uuid_t *children = NULL;
  gate_type type = provsql_fetch_gate(&token, &nb_children, &children);
  int res = -1;
 
  switch (type) {
  case gate_input: case gate_mulinput: case gate_one:
    res = 1;
    break;
  case gate_zero:
    res = 0;
    break;
  case gate_times: case gate_plus: {
    bool is_times = type == gate_times;
    res = is_times ? 1 : 0;
    for (unsigned i = 0; i < nb_children; ++i) {
      int c = quick_plain_truth(children[i], depth + 1);
      if (c < 0) { res = -1; break; }
      if (is_times && !c) { res = 0; break; }
      if (!is_times && c) { res = 1; break; }
    }
    break;
  }
  case gate_monus:
    if (nb_children == 2) {
      int a = quick_plain_truth(children[0], depth + 1);
      int b = a == 1 ? quick_plain_truth(children[1], depth + 1) : 0;
      res = a < 0 || b < 0 ? -1 : (a && !b);
    }
    break;
  case gate_delta: case gate_project: case gate_eq: case gate_annotation:
  case gate_assumed:
    if (nb_children >= 1)
      res = quick_plain_truth(children[0], depth + 1);
    break;
  case gate_cmp: {
    /* A comparison of aggregate results holds, in the database as it is, by
     * the values its sides record there: agg_guard_holds reads them off the
     * gates.  Deciding it that way rather than over the Boolean semiring
     * matters, not merely for speed: the semiring reads a comparison through
     * the worlds of what it aggregates, which is 2^n terms for n
     * contributions, so a comparison over a few dozen rows -- one per row an
     * exploded aggregate value produces -- would not finish.  A comparison
     * whose sides record no value (a random variable, a text aggregate)
     * yields NULL and takes the evaluation below. */
    constants_t constants = get_constants(false);
    if (!constants.ok || !OidIsValid(constants.OID_FUNCTION_AGG_GUARD_HOLDS))
      break;
    {
      FmgrInfo flinfo;
      /* PostgreSQL 12 made the argument array variable-length, and with it
       * LOCAL_FCINFO and fcinfo->args[]; before that the call info is a plain
       * struct with fixed arg / argnull arrays. */
#if PG_VERSION_NUM >= 120000
      LOCAL_FCINFO(fcinfo, 1);
#else
      FunctionCallInfoData fcinfo_data;
      FunctionCallInfo fcinfo = &fcinfo_data;
#endif
      Datum d;
 
      fmgr_info(constants.OID_FUNCTION_AGG_GUARD_HOLDS, &flinfo);
      InitFunctionCallInfoData(*fcinfo, &flinfo, 1, InvalidOid, NULL, NULL);
#if PG_VERSION_NUM >= 120000
      fcinfo->args[0].value = UUIDPGetDatum(&token);
      fcinfo->args[0].isnull = false;
#else
      fcinfo->arg[0] = UUIDPGetDatum(&token);
      fcinfo->argnull[0] = false;
#endif
      d = FunctionCallInvoke(fcinfo);
      if (!fcinfo->isnull)
        res = DatumGetBool(d) ? 1 : 0;
    }
    break;
  }
  default:
    break;
  }
  free(children);
 
  if (res >= 0) {
    if (plain_truth_memo.size() >= plain_truth_memo_max)
      plain_truth_memo.clear();
    plain_truth_memo.emplace(std::move(key), res == 1);
  }
  return res;
}
 
} // namespace
 
/**
 * @brief Whether a token holds in the database as it is, every input tuple
 *        present: @c sr_boolean without a mapping.
 *
 * The rewriter filters by it the rows a displayed aggregate value reads, so
 * that the value is what plain SQL computes on the same data: a row kept only
 * for its provenance (the padding of a lowered outer join, a group a
 * @c HAVING rejects, a row beyond a rank-filtered @c LIMIT) does not count.
 * Gates whose truth follows from their children's (⊗, ⊕, ⊖, δ, ...) are
 * walked directly, through the backend's gate cache; a comparison is left to
 * the evaluation over the Boolean semiring, with no mapping to read.
 */
Datum plain_truth(PG_FUNCTION_ARGS)
{
  pg_uuid_t token;
 
  if (PG_ARGISNULL(0))
    PG_RETURN_BOOL(true);
  token = *PG_GETARG_UUID_P(0);
 
  int quick = quick_plain_truth(token, 0);
  if (quick >= 0)
    PG_RETURN_BOOL(quick == 1);
 
  /* A token the Boolean semiring cannot evaluate (a comparison on a random
   * variable, which has no value in the database as it is) holds: the row
   * counts, as it did before this filter. */
  bool res = true;
  try {
    GenericCircuit c = getGenericCircuit(token);
    gate_t g = c.getGate(uuid2string(token));
    semiring::Boolean sr;
    std::unordered_map<gate_t, bool> mapping;
    provsql_having(c, g, mapping, sr);
    res = c.evaluate<semiring::Boolean>(g, mapping, sr);
  } catch(const std::exception &) {
    res = true;
  }
  if (plain_truth_memo.size() >= plain_truth_memo_max)
    plain_truth_memo.clear();
  plain_truth_memo.emplace(uuid2string(token), res);
  PG_RETURN_BOOL(res);
}