java-topology/defects/mariadb/unit/MariadbTest.java

package unit;

import java.util.*;

/**
 * MariadbTest — CWE-407 benchmarks for MariaDB defects.
 *
 * mariadb-0001: setup_order/setup_group — O(O*S) find_item_in_list per ORDER item
 *               vs O(S + O) with pre-built HashMap
 *
 * mariadb-0002: setup_new_fields — O(N*S) find_item_in_list per new_field
 *               vs O(S + N) with pre-built HashMap
 *
 * No JUnit. Prints N/N PASS.
 */
public class MariadbTest {

    static void bench(String label, Runnable slow, Runnable fast, long sOps, long fOps) {
        slow.run(); fast.run();
        long t0 = System.nanoTime(); slow.run(); long sMs = (System.nanoTime() - t0) / 1_000_000;
        long t1 = System.nanoTime(); fast.run(); long fMs = (System.nanoTime() - t1) / 1_000_000;
        System.out.printf("  %-60s  slow:%4dms (%,d ops)  fast:%4dms (%,d ops)  speedup:%.0fx%n",
                label, sMs, sOps, fMs, fOps, fOps > 0 ? (double) sOps / fOps : 0);
    }

    // -----------------------------------------------------------------------
    // mariadb-0001 — setup_order/setup_group: O(O*S) vs O(S+O)
    //
    // Models sql/sql_select.cc:28873-28876 and 28950-28953
    //   Outer loop: O ORDER BY / GROUP BY items
    //   Inner: find_item_in_list = O(S) linear scan over List<Item> SELECT fields
    //   Total: O(O * S)
    //
    // Fix: build HashMap<name, position> before outer loop — O(S) setup + O(O) lookups
    // -----------------------------------------------------------------------
    static long setupOrderSlow(int O, int S) {
        // SELECT list: S field names
        List<String> selectFields = new ArrayList<>(S);
        for (int i = 0; i < S; i++) selectFields.add("field_" + i);

        // ORDER BY: O items, each matching a SELECT field by name
        List<String> orderItems = new ArrayList<>(O);
        for (int i = 0; i < O; i++) orderItems.add("field_" + (i % S));

        long ops = 0;
        for (String orderItem : orderItems) {
            // O(S) linear scan — models List_iterator<Item> in find_item_in_list
            for (String sel : selectFields) {
                ops++;
                if (sel.equals(orderItem)) break;
            }
        }
        return ops;
    }

    static long setupOrderFast(int O, int S) {
        List<String> selectFields = new ArrayList<>(S);
        for (int i = 0; i < S; i++) selectFields.add("field_" + i);

        List<String> orderItems = new ArrayList<>(O);
        for (int i = 0; i < O; i++) orderItems.add("field_" + (i % S));

        long ops = 0;
        // Build name->index map once — O(S)
        Map<String, Integer> nameIndex = new HashMap<>(S * 2);
        for (int i = 0; i < S; i++) {
            nameIndex.put(selectFields.get(i), i);
            ops++; // map insertion cost
        }

        for (String orderItem : orderItems) {
            ops++; // O(1) hash lookup
            nameIndex.get(orderItem);
        }
        return ops;
    }

    // -----------------------------------------------------------------------
    // mariadb-0002 — setup_new_fields: O(N*S) vs O(S+N)
    //
    // Models sql/sql_select.cc:29060-29064
    //   Loop over N new_field ORDER entries, each calls find_item_in_list O(S)
    //   Total: O(N * S)
    //
    // Fix: pre-build name->Item** map once, O(1) lookup per new_field
    // -----------------------------------------------------------------------
    static long setupNewFieldsSlow(int N, int S) {
        List<String> fields = new ArrayList<>(S);
        for (int i = 0; i < S; i++) fields.add("col_" + i);

        List<String> newFields = new ArrayList<>(N);
        for (int i = 0; i < N; i++) newFields.add("col_" + (i % S));

        long ops = 0;
        for (String nf : newFields) {
            for (String f : fields) {
                ops++;
                if (f.equals(nf)) break;
            }
        }
        return ops;
    }

    static long setupNewFieldsFast(int N, int S) {
        List<String> fields = new ArrayList<>(S);
        for (int i = 0; i < S; i++) fields.add("col_" + i);

        List<String> newFields = new ArrayList<>(N);
        for (int i = 0; i < N; i++) newFields.add("col_" + (i % S));

        long ops = 0;
        Map<String, Integer> fieldIndex = new HashMap<>(S * 2);
        for (int i = 0; i < S; i++) { fieldIndex.put(fields.get(i), i); ops++; }

        for (String nf : newFields) {
            ops++;
            fieldIndex.get(nf);
        }
        return ops;
    }

    // -----------------------------------------------------------------------
    // Main
    // -----------------------------------------------------------------------
    public static void main(String[] args) {
        System.out.println("mariadb CWE-407 benchmarks");
        System.out.println("=".repeat(100));

        int failures = 0;
        int total = 0;

        // --- mariadb-0001 setup_order ---
        {
            int O = 500, S = 500;
            long[] slowOps = new long[1], fastOps = new long[1];
            Runnable slow = () -> slowOps[0] = setupOrderSlow(O, S);
            Runnable fast = () -> fastOps[0] = setupOrderFast(O, S);

            slow.run(); fast.run();
            long t0 = System.nanoTime(); slow.run(); long sMs = (System.nanoTime() - t0) / 1_000_000;
            long t1 = System.nanoTime(); fast.run(); long fMs = (System.nanoTime() - t1) / 1_000_000;
            double speedup = fastOps[0] > 0 ? (double) slowOps[0] / fastOps[0] : 0;
            System.out.printf("  %-60s  slow:%4dms (%,d ops)  fast:%4dms (%,d ops)  speedup:%.1fx%n",
                    "mariadb-0001 setup_order O(O*S) vs O(S+O)", sMs, slowOps[0], fMs, fastOps[0], speedup);

            total++;
            // slow: O(O*S) = O*S/2 avg; fast: O(S+O); ratio ~= O*S/(2*(S+O)) ~ O/4 at O=S=500 ~ 125x
            boolean pass = slowOps[0] > fastOps[0] * 10L;
            if (!pass) {
                System.out.printf("    FAIL: slowOps=%,d fastOps=%,d (expected slowOps > 10x fastOps)%n",
                        slowOps[0], fastOps[0]);
                failures++;
            }
        }

        // --- mariadb-0001 setup_group (same algorithm, same fix) ---
        {
            int O = 500, S = 500;
            long[] slowOps = new long[1], fastOps = new long[1];
            Runnable slow = () -> slowOps[0] = setupOrderSlow(O, S);
            Runnable fast = () -> fastOps[0] = setupOrderFast(O, S);

            slow.run(); fast.run();
            long t0 = System.nanoTime(); slow.run(); long sMs = (System.nanoTime() - t0) / 1_000_000;
            long t1 = System.nanoTime(); fast.run(); long fMs = (System.nanoTime() - t1) / 1_000_000;
            double speedup = fastOps[0] > 0 ? (double) slowOps[0] / fastOps[0] : 0;
            System.out.printf("  %-60s  slow:%4dms (%,d ops)  fast:%4dms (%,d ops)  speedup:%.1fx%n",
                    "mariadb-0001 setup_group O(O*S) vs O(S+O)", sMs, slowOps[0], fMs, fastOps[0], speedup);

            total++;
            boolean pass = slowOps[0] > fastOps[0] * 10L;
            if (!pass) {
                System.out.printf("    FAIL: slowOps=%,d fastOps=%,d (expected slowOps > 10x fastOps)%n",
                        slowOps[0], fastOps[0]);
                failures++;
            }
        }

        // --- mariadb-0002 setup_new_fields ---
        {
            int N = 500, S = 500;
            long[] slowOps = new long[1], fastOps = new long[1];
            Runnable slow = () -> slowOps[0] = setupNewFieldsSlow(N, S);
            Runnable fast = () -> fastOps[0] = setupNewFieldsFast(N, S);

            slow.run(); fast.run();
            long t0 = System.nanoTime(); slow.run(); long sMs = (System.nanoTime() - t0) / 1_000_000;
            long t1 = System.nanoTime(); fast.run(); long fMs = (System.nanoTime() - t1) / 1_000_000;
            double speedup = fastOps[0] > 0 ? (double) slowOps[0] / fastOps[0] : 0;
            System.out.printf("  %-60s  slow:%4dms (%,d ops)  fast:%4dms (%,d ops)  speedup:%.1fx%n",
                    "mariadb-0002 setup_new_fields O(N*S) vs O(S+N)", sMs, slowOps[0], fMs, fastOps[0], speedup);

            total++;
            boolean pass = slowOps[0] > fastOps[0] * 10L;
            if (!pass) {
                System.out.printf("    FAIL: slowOps=%,d fastOps=%,d (expected slowOps > 10x fastOps)%n",
                        slowOps[0], fastOps[0]);
                failures++;
            }
        }

        System.out.println("=".repeat(100));
        System.out.printf("%d/%d %s%n", total - failures, total, failures == 0 ? "PASS" : "FAIL");
        if (failures > 0) System.exit(1);
    }
}