java-topology/defects/starrocks/unit/MvTableRelationAlgorithm.java

package unit;

import java.util.*;
import java.util.stream.*;

/**
 * Standalone unit test for starrocks-0001:
 * MaterializedViewRewriter.getTableToRelationid — List.contains() in column-ref loop → O(N×T).
 *
 * Simulates getTableToRelationid():
 *   for each column-ref → table entry, test membership in tableList.
 *
 * Compile: javac -d . MvTableRelationAlgorithm.java
 * Run:     java unit.MvTableRelationAlgorithm
 */
public class MvTableRelationAlgorithm {

    // ── Minimal stubs ────────────────────────────────────────────────────────

    static class Table {
        final String name;
        Table(String name) { this.name = name; }
        @Override public boolean equals(Object o) {
            return o instanceof Table && name.equals(((Table) o).name);
        }
        @Override public int hashCode() { return name.hashCode(); }
        @Override public String toString() { return name; }
    }

    static class ColRef {
        final int id;
        ColRef(int id) { this.id = id; }
        @Override public int hashCode() { return id; }
        @Override public boolean equals(Object o) {
            return o instanceof ColRef && id == ((ColRef) o).id;
        }
    }

    // ── Result ───────────────────────────────────────────────────────────────

    static class Result {
        final Map<Table, Set<Integer>> tableToRelationId;
        final long ns;
        Result(Map<Table, Set<Integer>> m, long ns) { this.tableToRelationId = m; this.ns = ns; }
    }

    // ── Defective: List<Table>.contains() O(T) per column ref ────────────────

    static class DefectiveAlgorithm {
        Result getTableToRelationid(
                Map<ColRef, Table> colRefToTable,
                Set<ColRef> validColumnRefs,
                List<Table> tableList) {             // List → O(T) .contains
            Map<Table, Set<Integer>> result = new HashMap<>();
            long t0 = System.nanoTime();
            for (Map.Entry<ColRef, Table> entry : colRefToTable.entrySet()) {
                if (!tableList.contains(entry.getValue())) {  // CWE-407 site
                    continue;
                }
                if (!validColumnRefs.contains(entry.getKey())) {
                    continue;
                }
                result.computeIfAbsent(entry.getValue(), k -> new HashSet<>())
                        .add(entry.getKey().id % 100);  // synthetic relation ID
            }
            return new Result(result, System.nanoTime() - t0);
        }
    }

    // ── Fixed: Set<Table>.contains() O(1) ────────────────────────────────────

    static class FixedAlgorithm {
        Result getTableToRelationid(
                Map<ColRef, Table> colRefToTable,
                Set<ColRef> validColumnRefs,
                List<Table> tableList) {
            Map<Table, Set<Integer>> result = new HashMap<>();
            long t0 = System.nanoTime();
            Set<Table> tableSet = new HashSet<>(tableList);   // O(T) once
            for (Map.Entry<ColRef, Table> entry : colRefToTable.entrySet()) {
                if (!tableSet.contains(entry.getValue())) {   // O(1)
                    continue;
                }
                if (!validColumnRefs.contains(entry.getKey())) {
                    continue;
                }
                result.computeIfAbsent(entry.getValue(), k -> new HashSet<>())
                        .add(entry.getKey().id % 100);
            }
            return new Result(result, System.nanoTime() - t0);
        }
    }

    // ── Test data helpers ────────────────────────────────────────────────────

    static Table[] makeTables(int T) {
        Table[] tables = new Table[T];
        for (int i = 0; i < T; i++) tables[i] = new Table("tbl_" + i);
        return tables;
    }

    static Map<ColRef, Table> makeColRefMap(int N, Table[] tables) {
        Map<ColRef, Table> m = new LinkedHashMap<>();
        for (int i = 0; i < N; i++) {
            m.put(new ColRef(i), tables[i % tables.length]);
        }
        return m;
    }

    // ── Assertions ───────────────────────────────────────────────────────────

    static void assertEquals(Object expected, Object actual, String msg) {
        if (!expected.equals(actual))
            throw new AssertionError(msg + ": expected=" + expected + " actual=" + actual);
    }

    static void assertTrue(boolean cond, String msg) {
        if (!cond) throw new AssertionError(msg);
    }

    public static void main(String[] args) {
        System.out.println("=== starrocks-0001: MvTableRelationAlgorithm ===");

        DefectiveAlgorithm defAlg = new DefectiveAlgorithm();
        FixedAlgorithm fixAlg = new FixedAlgorithm();

        // Small correctness test
        {
            int N = 50, T = 5;
            Table[] tables = makeTables(T);
            Map<ColRef, Table> colMap = makeColRefMap(N, tables);
            Set<ColRef> valid = new HashSet<>(colMap.keySet());
            List<Table> tableList = Arrays.asList(tables).subList(0, 3);

            Result dr = defAlg.getTableToRelationid(colMap, valid, new ArrayList<>(tableList));
            Result fr = fixAlg.getTableToRelationid(colMap, valid, new ArrayList<>(tableList));

            assertEquals(dr.tableToRelationId, fr.tableToRelationId, "tableToRelationId contents");
            System.out.println("PASS  correctness (N=50, T=5)");
        }

        // Benchmark
        {
            int N = 10000, T = 200;
            Table[] tables = makeTables(T);
            Map<ColRef, Table> colMap = makeColRefMap(N, tables);
            Set<ColRef> valid = new HashSet<>(colMap.keySet());
            // tableList covers only first 100 tables — forces full scan of list per entry
            List<Table> tableList = Arrays.asList(tables).subList(0, 100);

            // warm up
            for (int i = 0; i < 5; i++) {
                defAlg.getTableToRelationid(colMap, valid, new ArrayList<>(tableList));
                fixAlg.getTableToRelationid(colMap, valid, new ArrayList<>(tableList));
            }

            long defNs = 0, fixNs = 0;
            int reps = 30;
            for (int i = 0; i < reps; i++) {
                defNs += defAlg.getTableToRelationid(colMap, valid, new ArrayList<>(tableList)).ns;
                fixNs += fixAlg.getTableToRelationid(colMap, valid, new ArrayList<>(tableList)).ns;
            }
            defNs /= reps; fixNs /= reps;
            double ratio = (double) defNs / Math.max(1, fixNs);

            System.out.printf("BENCH N=%d T=%d (list size=%d) reps=%d%n", N, T, tableList.size(), reps);
            System.out.printf("  defective avg: %,d ns%n", defNs);
            System.out.printf("  fixed     avg: %,d ns%n", fixNs);
            System.out.printf("  speedup:       %.1fx%n", ratio);

            assertTrue(ratio >= 2.0, "Expected fixed >= 2x faster, got " + ratio + "x");
            System.out.println("PASS  speedup >= 2x");
        }

        System.out.println("=== ALL PASS ===");
    }
}