The index that made writes fall over

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

/**
 * Solution: the index that made writes fall over.
 *
 * Six indexes became two, and every query got faster rather than slower.
 *
 *   Three were never used at all. idx_status, idx_region and idx_total were
 *   each added for a query that no longer exists, or never matched the
 *   workload in the first place. They cost a write on every insert and
 *   returned nothing. Every database can list indexes with zero scans; that
 *   report is usually the shortest route to a faster write path.
 *
 *   One was redundant. idx_customer is a leftmost prefix of
 *   idx_customer_status, so any query the narrow one could serve, the wider
 *   one serves too. An index on (a) is always redundant beside one on (a, b);
 *   an index on (b) is not.
 *
 *   The hottest query — two million a day — was served but not COVERED, so
 *   every one of those lookups fetched the row separately. Widening the
 *   composite index to include the selected columns turns that into an
 *   index-only scan and removes a random read per row. That is the change
 *   that made reads faster while removing four indexes.
 *
 * Note the direction of the fix: the winning index is WIDER than the one it
 * replaced. Fewer indexes, each doing more, beats many narrow ones — because
 * the write cost is per index, not per column.
 */
public class Solution {

    record Index(String name, List<String> columns) {
        static Index of(String name, String... cols) {
            return new Index(name, List.of(cols));
        }
    }

    /** equality: columns compared with =, in any order. order: ORDER BY column, or null. */
    record Query(String name, List<String> equality, String order, List<String> selected, int perDay) { }

    static final List<Index> INDEXES = List.of(
        // Serves both customer queries, and COVERS the hot one.
        Index.of("idx_customer_status_total", "customer_id", "status", "total"),
        // Ordered by created_at, and carries customer_id so the scan is covered too.
        Index.of("idx_created_customer", "created_at", "customer_id"));

    static final List<Query> WORKLOAD = List.of(
        new Query("orders for a customer", List.of("customer_id"), null,
            List.of("id", "status", "total"), 2_000_000),
        new Query("open orders for a customer", List.of("customer_id", "status"), null,
            List.of("id", "total"), 400_000),
        new Query("recent orders", List.of(), "created_at",
            List.of("id", "customer_id"), 50_000));

    static final int WRITES_PER_DAY = 3_000_000;
    static final int WRITE_BUDGET = 15_000_000;

    /* ─────────── the two rules that decide everything ─────────── */

    /** Leftmost prefix: the index's leading columns must be the query's equality set. */
    static boolean serves(Index index, Query query) {
        List<String> cols = index.columns();
        int n = query.equality().size();
        if (cols.size() < n) return false;
        if (!new HashSet<>(cols.subList(0, n)).equals(new HashSet<>(query.equality()))) return false;
        if (query.order() == null) return true;
        return cols.size() > n ? cols.get(n).equals(query.order())
                               : query.equality().contains(query.order());
    }

    /** Covering: the index holds every column the query reads, so the row is never fetched. */
    static boolean covers(Index index, Query query) {
        if (!serves(index, query)) return false;
        Set<String> have = new HashSet<>(index.columns());
        have.add("id");                       // the row pointer is always there
        return have.containsAll(query.selected());
    }

    public static void main(String[] args) {
        boolean ok = true;

        System.out.println("── " + INDEXES.size() + " indexes, " + WORKLOAD.size() + " query shapes ──");
        for (Index i : INDEXES) {
            List<String> served = WORKLOAD.stream().filter(q -> serves(i, q)).map(Query::name).toList();
            System.out.println("  " + pad(i.name()) + i.columns()
                + (served.isEmpty() ? "  — serves nothing" : "  serves " + served));
        }

        List<Index> unused = INDEXES.stream()
            .filter(i -> WORKLOAD.stream().noneMatch(q -> serves(i, q))).toList();
        List<Index> redundant = INDEXES.stream().filter(Solution::isPrefixOfAnother).toList();
        Query hottest = WORKLOAD.stream().max(Comparator.comparingInt(Query::perDay)).orElseThrow();
        boolean hotCovered = INDEXES.stream().anyMatch(i -> covers(i, hottest));
        long writeOps = (long) WRITES_PER_DAY * (1 + INDEXES.size());

        System.out.println();
        System.out.println("  unused         : " + unused.stream().map(Index::name).toList());
        System.out.println("  redundant      : " + redundant.stream().map(Index::name).toList());
        System.out.println("  hottest query  : " + hottest.name() + " (" + hottest.perDay() + "/day)");
        System.out.println("  covered?       : " + hotCovered);
        System.out.println("  write ops/day  : " + writeOps + " (budget " + WRITE_BUDGET + ")");
        System.out.println();

        ok &= check("every index serves at least one query", unused.isEmpty());
        ok &= check("no index is a leftmost prefix of another", redundant.isEmpty());
        ok &= check("the hottest query is covered", hotCovered);
        ok &= check("write operations are within budget", writeOps <= WRITE_BUDGET);

        System.out.println();
        System.out.println(ok ? "PASS" : "FAIL");
    }

    static boolean isPrefixOfAnother(Index index) {
        return INDEXES.stream().anyMatch(other -> other != index
            && other.columns().size() > index.columns().size()
            && other.columns().subList(0, index.columns().size()).equals(index.columns()));
    }

    static String pad(String s) {
        return (s + "                              ").substring(0, 28);
    }

    static boolean check(String what, boolean passed) {
        System.out.println((passed ? "  ok    " : "  FAIL  ") + what);
        return passed;
    }
}