russell@unturf.com
0a580b313d
Authors: russell@unturf.com · brackishbert@gmail.com · foxhop.net · TimeHexOn.com Patches, unit tests, benchmarks, whitepaper, and outreach briefs. Public domain — no copyright claimed. Use freely.
220 lines
8.8 KiB
Java
220 lines
8.8 KiB
Java
package support;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* PostgresqlVarDedupAlgorithm — models preptlist.c sites postgresql-0002.
|
||
*
|
||
* DEFECT (CWE-407): tlist_member() walks the entire target list calling
|
||
* structural equal() on each entry to check if a Var is already present.
|
||
* As the list grows, each check takes longer. Building a tlist of N unique
|
||
* Vars from a pool of M candidates costs O(M × N) — quadratic when M ≈ N.
|
||
*
|
||
* Sites in PostgreSQL source (preptlist.c):
|
||
* :180 — MERGE action targetList/qual Var collection
|
||
* :206 — mergeJoinCondition Var collection
|
||
* :316 — RETURNING clause Var collection
|
||
*
|
||
* Defective C pattern (all three sites identical):
|
||
*
|
||
* vars = pull_var_clause(..., PVC_INCLUDE_PLACEHOLDERS);
|
||
* foreach(l, vars) {
|
||
* Var *var = (Var *) lfirst(l);
|
||
* if (IsA(var, Var) && var->varno == result_relation)
|
||
* continue; // skip target-rel vars
|
||
* if (tlist_member((Expr *) var, tlist)) // O(n) — THE DEFECT
|
||
* continue;
|
||
* tlist = lappend(tlist, makeTargetEntry(...));
|
||
* }
|
||
*
|
||
* Fix (Path B — no nodeHash() required):
|
||
* Maintain a HashSet<Var> (C: Bitmapset keyed on encoded varno×varattno)
|
||
* alongside the tlist. Check/update the set instead of scanning tlist.
|
||
* Reduces per-var check from O(n) to O(1). Total: O(n) instead of O(n²).
|
||
*
|
||
* C encoding: bms_member(varno * 3200 + varattno + 1600)
|
||
* Safe for varno ≤ 65001 (INNER_VAR) and varattno in [-1600, 1600].
|
||
*
|
||
* Comparison counts:
|
||
* defective: 0+1+2+...+(N-1) = N*(N-1)/2 (N unique vars, each checked
|
||
* against all previously added entries)
|
||
* fixed: N (one O(1) hash check per var)
|
||
*
|
||
* Growth when N doubles: defective ≈4× (quadratic), fixed ≈2× (linear).
|
||
*/
|
||
public class PostgresqlVarDedupAlgorithm {
|
||
|
||
// ── Var: models PostgreSQL Var node ──────────────────────────────────────
|
||
//
|
||
// A Var represents a column reference: (varno=relation, varattno=column,
|
||
// varlevelsup=query nesting depth). PostgreSQL equal() on Vars compares
|
||
// all three fields plus vartype and several others. We model the minimum
|
||
// set needed to reproduce the defect: varno + varattno + varlevelsup.
|
||
|
||
public static final class Var {
|
||
public final int varno; // relation index (1-based)
|
||
public final int varattno; // column number (negative = system col)
|
||
public final int varlevelsup; // query nesting (0 = current query)
|
||
|
||
public Var(int varno, int varattno, int varlevelsup) {
|
||
this.varno = varno;
|
||
this.varattno = varattno;
|
||
this.varlevelsup = varlevelsup;
|
||
}
|
||
|
||
/** Structural equality — models PostgreSQL equal() for Var nodes. */
|
||
@Override
|
||
public boolean equals(Object o) {
|
||
if (!(o instanceof Var v)) return false;
|
||
return varno == v.varno && varattno == v.varattno
|
||
&& varlevelsup == v.varlevelsup;
|
||
}
|
||
|
||
@Override
|
||
public int hashCode() { return Objects.hash(varno, varattno, varlevelsup); }
|
||
|
||
@Override
|
||
public String toString() {
|
||
return "Var(" + varno + "," + varattno + "," + varlevelsup + ")";
|
||
}
|
||
}
|
||
|
||
// ── TargetEntry: wraps an expression in the target list ──────────────────
|
||
|
||
public static final class TargetEntry {
|
||
public final Var expr;
|
||
public final int resno; // position in tlist (1-based)
|
||
|
||
public TargetEntry(Var expr, int resno) {
|
||
this.expr = expr;
|
||
this.resno = resno;
|
||
}
|
||
}
|
||
|
||
// ── Result ────────────────────────────────────────────────────────────────
|
||
|
||
public static final class Result {
|
||
public final List<TargetEntry> tlist;
|
||
/** Number of element-level equality checks performed. */
|
||
public final long comparisons;
|
||
|
||
public Result(List<TargetEntry> tlist, long comparisons) {
|
||
this.tlist = tlist;
|
||
this.comparisons = comparisons;
|
||
}
|
||
}
|
||
|
||
// ── Defective: tlist_member scan — O(n) per var ──────────────────────────
|
||
//
|
||
// Exact port of the defective PostgreSQL pattern.
|
||
// Each call to tlist_member() walks the existing tlist, calling equal()
|
||
// on each entry's expr until it finds a match or exhausts the list.
|
||
|
||
public static Result defectiveBuildTlist(List<Var> vars, int resultRelation) {
|
||
List<TargetEntry> tlist = new ArrayList<>();
|
||
long comparisons = 0;
|
||
|
||
for (Var var : vars) {
|
||
if (var.varno == resultRelation)
|
||
continue; // skip: belongs to target relation
|
||
|
||
// tlist_member: scan tlist, call equal() on each expr
|
||
boolean found = false;
|
||
for (TargetEntry te : tlist) {
|
||
comparisons++;
|
||
if (te.expr.equals(var)) {
|
||
found = true;
|
||
break;
|
||
}
|
||
}
|
||
if (found) continue;
|
||
|
||
tlist.add(new TargetEntry(var, tlist.size() + 1));
|
||
}
|
||
|
||
return new Result(tlist, comparisons);
|
||
}
|
||
|
||
// ── Fixed: HashSet on Var identity — O(1) per var ────────────────────────
|
||
//
|
||
// Maintain a HashSet<Var> alongside the tlist.
|
||
// C equivalent: Bitmapset keyed on (varno * 3200 + varattno + 1600).
|
||
// Does NOT require nodeHash() — Var identity is three plain integers.
|
||
|
||
public static Result fixedBuildTlist(List<Var> vars, int resultRelation) {
|
||
List<TargetEntry> tlist = new ArrayList<>();
|
||
Set<Var> seen = new HashSet<>();
|
||
long comparisons = 0;
|
||
|
||
for (Var var : vars) {
|
||
if (var.varno == resultRelation)
|
||
continue;
|
||
|
||
comparisons++; // one O(1) hash table lookup
|
||
if (seen.contains(var)) continue;
|
||
|
||
tlist.add(new TargetEntry(var, tlist.size() + 1));
|
||
seen.add(var);
|
||
}
|
||
|
||
return new Result(tlist, comparisons);
|
||
}
|
||
|
||
// ── Self-test ─────────────────────────────────────────────────────────────
|
||
|
||
public static void main(String[] args) {
|
||
System.out.println("PostgresqlVarDedupAlgorithm — postgresql-0002 (preptlist.c)");
|
||
System.out.println("Defect: tlist_member O(n) check per var while building junk tlist");
|
||
System.out.println("Fix: HashSet<Var> / Bitmapset — O(1) per check");
|
||
System.out.println();
|
||
|
||
// Simulate a MERGE with multiple actions referencing many columns.
|
||
// resultRelation=1, source table=2, many columns referenced.
|
||
int[] sizes = {10, 20, 50, 100, 200, 500};
|
||
System.out.printf("%-8s %-14s %-10s %-10s %s%n",
|
||
"N vars", "Defective ops", "Fixed ops", "Speedup", "Tlist size");
|
||
System.out.println("─".repeat(62));
|
||
|
||
for (int n : sizes) {
|
||
List<Var> vars = buildVarPool(n, /*resultRelation=*/1, /*duplicates=*/n / 2);
|
||
Result def = defectiveBuildTlist(vars, 1);
|
||
Result fix = fixedBuildTlist(vars, 1);
|
||
|
||
// Sanity: both versions must produce the same tlist
|
||
assert def.tlist.size() == fix.tlist.size()
|
||
: "tlist size mismatch at N=" + n;
|
||
|
||
System.out.printf("%-8d %-14d %-10d %-10.1fx %d%n",
|
||
vars.size(),
|
||
def.comparisons,
|
||
fix.comparisons,
|
||
(double) def.comparisons / Math.max(1, fix.comparisons),
|
||
def.tlist.size());
|
||
}
|
||
|
||
System.out.println();
|
||
System.out.println("Exact defective count = N*(N-1)/2 (triangular number).");
|
||
System.out.println("Fixed count = N (one hash lookup per unique var).");
|
||
}
|
||
|
||
/** Builds a pool of vars mixing unique entries and duplicates. */
|
||
public static List<Var> buildVarPool(int uniqueVars, int resultRelation, int extraDuplicates) {
|
||
List<Var> pool = new ArrayList<>();
|
||
// unique vars from relation 2
|
||
for (int att = 1; att <= uniqueVars; att++) {
|
||
pool.add(new Var(2, att, 0));
|
||
}
|
||
// duplicates (already in pool — trigger the O(n) scan)
|
||
Random rng = new Random(42);
|
||
for (int i = 0; i < extraDuplicates; i++) {
|
||
int att = rng.nextInt(uniqueVars) + 1;
|
||
pool.add(new Var(2, att, 0));
|
||
}
|
||
// result relation vars (filtered out by both versions)
|
||
for (int att = 1; att <= 5; att++) {
|
||
pool.add(new Var(resultRelation, att, 0));
|
||
}
|
||
Collections.shuffle(pool, rng);
|
||
return pool;
|
||
}
|
||
}
|