The index that was one column out

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

/**
 * Solution: the index that was one column out.
 *
 * The original index named all three filtered columns and the plan showed it
 * being used, which is why the review passed it. It was still wrong:
 *
 *     (tenant_id, created_at, event_type)
 *                 ^^^^^^^^^^ a RANGE, in the middle
 *
 * Seeking stops at the first range column. tenant_id narrows, created_at
 * narrows, and then the entries within that time window are ordered by time
 * rather than grouped by event_type — so every entry in the window is read
 * and event_type is checked one at a time. The index "uses" three columns and
 * only two of them do any narrowing.
 *
 * Moving the range column last puts both equality columns in front of it:
 *
 *     (tenant_id, event_type, created_at)
 *
 * Now all three narrow the scan, and the entries read are the entries
 * returned. That reordering is the entire performance fix — no new index, no
 * extra write cost, the same three columns.
 *
 * Then user_id is appended so the query never fetches a row. A wider index
 * costs the same ONE write per insert as a narrow one, because write cost is
 * per index and not per column, which is why widening usually beats adding.
 *
 * The rule, in the order to apply it:
 *   1. every equality column first, in any order among themselves
 *   2. the range or ORDER BY column next
 *   3. the selected columns after that, to cover
 */
public class Solution {

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

    /** equality: compared with =. range: compared with > or BETWEEN, or null. */
    record Query(String name, List<String> equality, String range, List<String> selected) { }

    static final List<Index> INDEXES = List.of(
        Index.of("idx_events", "tenant_id", "event_type", "created_at", "user_id"));

    static final Query DASHBOARD = new Query(
        "logins for a tenant, last 24h",
        List.of("tenant_id", "event_type"),
        "created_at",
        List.of("id", "user_id"));

    /* ─────────── the rules ─────────── */

    /**
     * How many leading index columns actually narrow the scan.
     * Equality columns count while they keep matching from the left; the first
     * range column counts and then everything stops.
     */
    static int usefulPrefix(Index index, Query query) {
        int used = 0;
        for (String column : index.columns()) {
            if (query.equality().contains(column)) { used++; continue; }
            if (column.equals(query.range())) { used++; }
            break;
        }
        return used;
    }

    /** True when every column the query reads is in the index. */
    static boolean covers(Index index, Query query) {
        Set<String> have = new HashSet<>(index.columns());
        have.add("id");
        return have.containsAll(query.selected());
    }

    /** Entries the scan must examine, given how much of the index narrowed it. */
    static long entriesExamined(Index index, Query query) {
        long total = 1_000_000;
        for (int i = 0; i < usefulPrefix(index, query); i++) {
            String column = index.columns().get(i);
            total /= column.equals(query.range()) ? 24 : selectivityOf(column);
        }
        return Math.max(total, matchingRows());
    }

    static int selectivityOf(String column) {
        return switch (column) {
            case "tenant_id" -> 50;
            case "event_type" -> 20;
            default -> 1;
        };
    }

    static long matchingRows() { return 1_000_000 / 50 / 24 / 20; }

    public static void main(String[] args) {
        boolean ok = true;
        Index index = INDEXES.get(0);

        long examined = entriesExamined(index, DASHBOARD);
        long returned = matchingRows();
        int prefix = usefulPrefix(index, DASHBOARD);

        System.out.println("── " + DASHBOARD.name() + " ──");
        System.out.println("  index            : " + index.name() + " " + index.columns());
        System.out.println("  equality columns : " + DASHBOARD.equality());
        System.out.println("  range column     : " + DASHBOARD.range());
        System.out.println("  columns that narrow the scan : " + prefix + " of " + index.columns().size()
            + " " + index.columns().subList(0, prefix));
        System.out.println("  entries examined : " + examined);
        System.out.println("  rows returned    : " + returned);
        System.out.println("  read amplification : " + (examined / returned) + "x");
        System.out.println("  covering?        : " + covers(index, DASHBOARD));
        System.out.println();

        ok &= check("every filtered column narrows the scan",
            prefix == DASHBOARD.equality().size() + 1);
        ok &= check("read amplification is under 5x", examined / returned < 5);
        ok &= check("the query is covered by the index", covers(index, DASHBOARD));

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

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