-- Relative price error of HashAggregate against Sort+GroupAggregate:
--
--     err = (cost_hash / cost_sort) / (ms_hash / ms_sort)
--
-- err = 1 is exact; err < 1 underprices hashing.  Each configuration is costed
-- twice from one set of timings: effective_cpu_cache_size = 0 reproduces
-- master's cost_agg(), 8MB applies the residency charge.
--
-- Usage:
--     psql -f cal_bias.sql
--     psql -v n=1000000 -v iters=7 -v full=1 -f cal_bias.sql
--
--     n      input rows per configuration     default 1000000
--     iters  timed repetitions, minimum taken default 3
--     full   also sweep two grouping columns  default 0
--
-- n must be large enough for the widest tables to exceed the CPU cache, and
-- work_mem large enough that neither arm spills and the charge is not capped
-- by hash_agg_set_limits().

\if :{?n}
\else
  \set n 1000000
\endif
\if :{?iters}
\else
  \set iters 3
\endif
\if :{?full}
\else
  \set full 0
\endif
\if :{?wm}
\else
  \set wm 256MB
\endif

\set ECHO none
SET max_parallel_workers_per_gather = 0;
SET jit = off;
SET work_mem = :'wm';

DO $$
BEGIN
    SET effective_cpu_cache_size = '8MB';
EXCEPTION WHEN undefined_object THEN
    RAISE EXCEPTION 'this script needs the costing patch: no effective_cpu_cache_size';
END $$;

CREATE TABLE bias_cfg AS
SELECT :n::bigint AS n, :iters::int AS iters, :full::int AS full;

CREATE OR REPLACE FUNCTION min_ms(q text, iters int)
RETURNS double precision LANGUAGE plpgsql AS $$
DECLARE
    t0 timestamptz;
    best double precision := 1e18;
    cur double precision;
BEGIN
    EXECUTE q;                       -- warm up, not counted
    FOR i IN 1..iters LOOP
        t0 := clock_timestamp();
        EXECUTE q;
        cur := extract(epoch FROM clock_timestamp() - t0) * 1000.0;
        IF cur < best THEN best := cur; END IF;
    END LOOP;
    RETURN best;
END $$;

CREATE OR REPLACE FUNCTION plan_total(q text)
RETURNS double precision LANGUAGE plpgsql AS $$
DECLARE j json;
BEGIN
    EXECUTE 'EXPLAIN (FORMAT JSON) ' || q INTO j;
    RETURN (j->0->'Plan'->>'Total Cost')::double precision;
END $$;

-- Returns the whole plan: fetching fields one at a time would re-execute the
-- query for each.
CREATE OR REPLACE FUNCTION exp_json(q text)
RETURNS text LANGUAGE plpgsql AS $$
DECLARE j text;
BEGIN
    EXECUTE 'EXPLAIN (ANALYZE, TIMING OFF, FORMAT JSON) ' || q INTO j;
    RETURN j;
END $$;

CREATE OR REPLACE FUNCTION num_in(j text, want text)
RETURNS double precision LANGUAGE plpgsql AS $$
DECLARE v text;
BEGIN
    SELECT (regexp_match(j, '"' || want || '": ?([0-9]+)'))[1] INTO v;
    RETURN coalesce(v::double precision, -1);
END $$;

CREATE TABLE bias_results (
    keytype   text,
    ncols     int,
    paylen    int,
    n         bigint,
    g_target  bigint,
    groups    bigint,
    width     int,
    hash_kb   double precision,
    sort_kb   double precision,
    hash_disk double precision,
    sort_ext  boolean,
    cost_hash_master  double precision,
    cost_hash_charged double precision,
    cost_sort double precision,
    ms_hash   double precision,
    ms_sort   double precision,
    hash_hashed boolean,      -- the hashed arm really hashed
    sort_sorted boolean       -- the sorted arm really sorted
);

-- Seeded: configurations that measure within a couple of percent have to be
-- identical between runs to be comparable.
SELECT setseed(0.42);

DO $$
DECLARE
    keytypes text[] := ARRAY['int', 'text'];
    paylens  int[]  := ARRAY[0, 120];
    ncolss   int[];
    gs       bigint[];
    n        bigint;
    it       int;
    isfull   int;

    kt text; nc int; pl int; gt bigint;
    g1 bigint;
    kexpr text; pexpr text; cols text;
    qb text; qc text;
    ng bigint; w int;
    hkb double precision; skb double precision; hdisk double precision;
    sext boolean; hhash boolean; ssort boolean;
    jh text; js text;
    chm double precision; chc double precision; cs double precision;
    mb double precision; mc double precision;
BEGIN
    SELECT bias_cfg.n, bias_cfg.iters, bias_cfg.full
      INTO n, it, isfull FROM bias_cfg;

    ncolss := CASE WHEN isfull = 1 THEN ARRAY[1, 2] ELSE ARRAY[1] END;
    -- Spans well under the cache to several times over it.
    gs := ARRAY[n / 1000, n / 100, n / 10, n / 2, n];

    FOREACH kt IN ARRAY keytypes LOOP
    FOREACH nc IN ARRAY ncolss LOOP
    FOREACH pl IN ARRAY paylens LOOP
    FOREACH gt IN ARRAY gs LOOP
        -- Spread the target group count over the grouping columns.
        g1 := GREATEST(ceil(power(gt, 1.0 / nc))::bigint, 1);

        IF kt = 'int' THEN
            kexpr := format('(random() * %s)::int', g1);
        ELSE
            kexpr := format('md5(((random() * %s)::int)::text)', g1);
        END IF;

        cols := CASE WHEN nc = 1 THEN 'k1' ELSE 'k1, k2' END;

        IF pl = 0 THEN
            pexpr := '''''::text';
        ELSE
            pexpr := format('substr(repeat(md5(k1::text), 8), 1, %s)', pl);
        END IF;

        EXECUTE 'DROP TABLE IF EXISTS bias_t';
        IF nc = 1 THEN
            EXECUTE format(
                'CREATE TABLE bias_t AS
                   SELECT k1, %s AS p
                     FROM (SELECT %s AS k1 FROM generate_series(1, %s)) q',
                pexpr, kexpr, n);
        ELSE
            EXECUTE format(
                'CREATE TABLE bias_t AS
                   SELECT k1, k2, %s AS p
                     FROM (SELECT %s AS k1, %s AS k2
                             FROM generate_series(1, %s)) q',
                pexpr, kexpr, kexpr, n);
        END IF;
        EXECUTE 'ANALYZE bias_t';

        EXECUTE format('SELECT count(*) FROM (SELECT %s, p FROM bias_t
                            GROUP BY %s, p) z', cols, cols) INTO ng;
        SELECT avg(pg_column_size(t.*))::int INTO w FROM bias_t t;

        qb := format('SELECT count(*) FROM (SELECT %s, p FROM bias_t
                        GROUP BY %s, p) s', cols, cols);
        qc := qb;

        -- Each arm is pinned to its own strategy; an unpinned one would measure
        -- the sorted plan twice wherever the charge changed the decision.
        SET enable_hashagg = on;
        SET enable_groupagg = off;
        jh := exp_json(qb);
        hhash := jh LIKE '%Hashed%';
        hkb   := num_in(jh, 'Peak Memory Usage');
        hdisk := num_in(jh, 'Disk Usage');
        chc := plan_total(qb);
        SET effective_cpu_cache_size = 0;
        chm := plan_total(qb);
        SET effective_cpu_cache_size = '8MB';
        mb  := min_ms(qb, it);

        SET enable_hashagg = off;
        SET enable_groupagg = on;
        js := exp_json(qc);
        -- Group over Sort carries no Strategy field; the Sort identifies the arm.
        ssort := js LIKE '%"Node Type": "Sort"%' AND js NOT LIKE '%Hashed%';
        skb  := num_in(js, 'Sort Space Used');
        sext := js LIKE '%external%';
        cs   := plan_total(qc);
        mc   := min_ms(qc, it);

        SET enable_hashagg = on;
        SET enable_groupagg = on;

        INSERT INTO bias_results VALUES
            (kt, nc, pl, n, gt, ng, w, hkb, skb, hdisk, sext,
             chm, chc, cs, mb, mc, hhash, ssort);
    END LOOP;
    END LOOP;
    END LOOP;
    END LOOP;
END $$;


-- pg_settings.setting is unitless (kB here); current_setting() returns '8MB'
-- and will not cast.
CREATE OR REPLACE VIEW bias AS
SELECT *,
       hash_kb * 1024.0
           / ((SELECT setting::bigint FROM pg_settings
                WHERE name = 'effective_cpu_cache_size') * 1024.0)
           AS resident_ratio,
       (cost_hash_master  / cost_sort) / (ms_hash / ms_sort) AS err_master,
       (cost_hash_charged / cost_sort) / (ms_hash / ms_sort) AS err_patched,
       cost_hash_charged > cost_hash_master AS charged
FROM bias_results;

\echo ===== validity: any row here invalidates itself =====
SELECT keytype, ncols, paylen, groups, hash_disk, sort_ext,
       hash_hashed, sort_sorted, hash_kb
FROM bias_results
WHERE hash_disk > 0 OR sort_ext
   OR NOT hash_hashed OR NOT sort_sorted OR hash_kb < 0
ORDER BY keytype, ncols, paylen, groups;

\echo
\echo ===== the story: price error against hash table size =====
-- If the defect is a cache effect, err_master falls as resident_ratio rises
-- and err_patched stays flat.
SELECT CASE WHEN resident_ratio < 0.125 THEN 'a  <1/8x'
            WHEN resident_ratio < 0.5   THEN 'b  1/8-1/2x'
            WHEN resident_ratio < 1     THEN 'c  1/2-1x'
            WHEN resident_ratio < 4     THEN 'd  1-4x'
            WHEN resident_ratio < 16    THEN 'e  4-16x'
            ELSE                             'f  >16x' END AS table_vs_cache,
       count(*) AS configs,
       sum(CASE WHEN charged THEN 1 ELSE 0 END) AS charged,
       round(exp(avg(ln(err_master)))::numeric,  3) AS gmean_err_master,
       round(exp(avg(ln(err_patched)))::numeric, 3) AS gmean_err_patched
FROM bias GROUP BY 1 ORDER BY 1;

\echo
\echo ===== overall bias, all configurations =====
-- spread is exp(stddev(ln err)).
SELECT count(*) AS configs,
       sum(CASE WHEN charged THEN 1 ELSE 0 END) AS charged,
       round(exp(avg(ln(err_master)))::numeric,  3) AS gmean_master,
       round(exp(avg(ln(err_patched)))::numeric, 3) AS gmean_patched,
       round(exp(stddev_pop(ln(err_master)))::numeric,  3) AS spread_master,
       round(exp(stddev_pop(ln(err_patched)))::numeric, 3) AS spread_patched,
       sum(CASE WHEN abs(ln(err_patched)) < abs(ln(err_master))
                THEN 1 ELSE 0 END) AS moved_closer,
       sum(CASE WHEN abs(ln(err_patched)) > abs(ln(err_master))
                THEN 1 ELSE 0 END) AS moved_further
FROM bias;

\echo
\echo ===== bias among the configurations the charge actually reaches =====
SELECT count(*) AS configs,
       round(exp(avg(ln(err_master)))::numeric,  3) AS gmean_master,
       round(exp(avg(ln(err_patched)))::numeric, 3) AS gmean_patched,
       round(exp(stddev_pop(ln(err_master)))::numeric,  3) AS spread_master,
       round(exp(stddev_pop(ln(err_patched)))::numeric, 3) AS spread_patched,
       round(min(err_patched)::numeric, 3) AS min_patched,
       round(max(err_patched)::numeric, 3) AS max_patched,
       sum(CASE WHEN err_patched > 1 THEN 1 ELSE 0 END) AS overshot
FROM bias WHERE charged;

\echo
\echo ===== typical distance from the truth, in either direction =====
-- Geometric mean of the absolute log error: 1.00 is exact, 2.00 is off by a
-- factor of two on average, whichever way.
SELECT count(*) AS configs,
       round(exp(avg(abs(ln(err_master))))::numeric,  3) AS typ_off_master,
       round(exp(avg(abs(ln(err_patched))))::numeric, 3) AS typ_off_patched
FROM bias
UNION ALL
SELECT count(*),
       round(exp(avg(abs(ln(err_master))))::numeric,  3),
       round(exp(avg(abs(ln(err_patched))))::numeric, 3)
FROM bias WHERE charged;

\echo
\echo ===== by shape, to show the result is not one key type =====
SELECT keytype, ncols, paylen AS pay, count(*) AS configs,
       sum(CASE WHEN charged THEN 1 ELSE 0 END) AS charged,
       round(exp(avg(ln(err_master)))::numeric,  3) AS gmean_master,
       round(exp(avg(ln(err_patched)))::numeric, 3) AS gmean_patched
FROM bias GROUP BY keytype, ncols, paylen
ORDER BY keytype, ncols, paylen;

\echo
\echo ===== per configuration, ordered by table size against the cache =====
SELECT keytype AS kt, ncols AS nc, paylen AS pay, groups, width AS w,
       round(hash_kb::numeric, 0) AS hash_kb,
       round(resident_ratio::numeric, 3) AS vs_cache,
       round(ms_hash::numeric, 1) AS ms_hash,
       round(ms_sort::numeric, 1) AS ms_sort,
       round((ms_hash / ms_sort)::numeric, 3) AS meas_ratio,
       round(err_master::numeric,  3) AS err_master,
       round(err_patched::numeric, 3) AS err_patched,
       CASE WHEN NOT charged THEN '-'
            WHEN abs(ln(err_patched)) < abs(ln(err_master)) THEN 'closer'
            ELSE 'further' END AS moved
FROM bias ORDER BY resident_ratio;
