Indexing in DBMS Explained — Types, Trade-offs and Real-World Usage

-- ============================================================
-- Demonstrate the cost difference between a full scan
-- and an index seek on a large orders table.
-- Run EXPLAIN (or EXPLAIN ANALYZE in PostgreSQL) to see the plan.
-- ============================================================

-- Step 1: Create a realistic orders table
CREATE TABLE orders (
    order_id      SERIAL PRIMARY KEY,
    customer_id   INT            NOT NULL,
    product_name  VARCHAR(200)   NOT NULL,
    order_total   DECIMAL(10,2)  NOT NULL,
    created_at    TIMESTAMP      NOT NULL DEFAULT NOW()
);

-- Step 2: Seed 1 million rows (simulate a production-sized table)
INSERT INTO orders (customer_id, product_name, order_total, created_at)
SELECT
    (RANDOM() * 100000)::INT,              -- 100k unique customers
    'Product_' || (RANDOM() * 500)::INT,   -- 500 unique products
    (RANDOM() * 500 + 5)::DECIMAL(10,2),   -- order value $5 - $505
    NOW() - (RANDOM() * INTERVAL '2 years') -- orders from last 2 years
FROM generate_series(1, 1000000);

-- Step 3: Query WITHOUT an index — watch the execution plan
EXPLAIN ANALYZE
SELECT order_id, product_name, order_total
FROM   orders
WHERE  customer_id = 4821;
-- Expected plan: "Seq Scan on orders" — reads ALL 1M rows
-- Typical cost on spinning disk: 800ms - 3000ms

-- Step 4: Create a B-Tree index on customer_id
CREATE INDEX idx_orders_customer_id
    ON orders (customer_id);
-- This builds the index structure — one-time cost, usually seconds

-- Step 5: Run the SAME query — the planner now uses the index
EXPLAIN ANALYZE
SELECT order_id, product_name, order_total
FROM   orders
WHERE  customer_id = 4821;
-- Expected plan: "Index Scan using idx_orders_customer_id"
-- Typical cost: 0.5ms - 3ms — a 1000x improvement

-- ============================================================
-- Compare B-Tree vs Hash index behaviour on a products table.
-- PostgreSQL syntax — MySQL uses ENGINE=MEMORY for Hash indexes.
-- ============================================================

CREATE TABLE products (
    product_id    SERIAL PRIMARY KEY,
    sku           VARCHAR(50)    NOT NULL,   -- unique product code
    category      VARCHAR(100)   NOT NULL,   -- e.g. 'electronics'
    price         DECIMAL(10,2)  NOT NULL,
    in_stock      BOOLEAN        NOT NULL DEFAULT TRUE
);

-- ── B-TREE INDEX ─────────────────────────────────────────────
-- Best for: equality, range queries, ORDER BY, LIKE 'prefix%'
CREATE INDEX idx_products_price_btree
    ON products USING BTREE (price);

-- This query USES the B-Tree index efficiently (range query)
EXPLAIN SELECT product_id, sku
FROM   products
WHERE  price BETWEEN 50.00 AND 150.00;  -- range scan ✓

-- ── HASH INDEX ───────────────────────────────────────────────
-- Best for: exact equality lookups ONLY — useless for ranges
CREATE INDEX idx_products_sku_hash
    ON products USING HASH (sku);

-- This query USES the Hash index efficiently (exact match)
EXPLAIN SELECT product_id, price
FROM   products
WHERE  sku = 'ELEC-4K-TV-001';          -- equality lookup ✓

-- This query CANNOT use the Hash index — falls back to seq scan
EXPLAIN SELECT product_id, price
FROM   products
WHERE  sku LIKE 'ELEC%';               -- range/pattern — hash fails ✗

-- ── PARTIAL INDEX (a B-Tree power move) ─────────────────────
-- Index ONLY the rows you actually query — smaller, faster index
CREATE INDEX idx_products_instock_price
    ON products (price)
    WHERE in_stock = TRUE;              -- only index in-stock items
-- Result: index is a fraction of the size but covers the hot query path

-- ============================================================
-- Illustrate clustered index layout vs non-clustered,
-- and the power of a COVERING index to eliminate key lookups.
-- SQL Server syntax — concepts identical in MySQL/PostgreSQL.
-- ============================================================

CREATE TABLE employees (
    employee_id   INT           NOT NULL IDENTITY(1,1),
    department_id INT           NOT NULL,
    last_name     VARCHAR(100)  NOT NULL,
    first_name    VARCHAR(100)  NOT NULL,
    salary        DECIMAL(10,2) NOT NULL,
    hire_date     DATE          NOT NULL,

    -- PRIMARY KEY creates the CLUSTERED index by default in SQL Server
    -- Rows are physically sorted on disk by employee_id
    CONSTRAINT PK_employees PRIMARY KEY CLUSTERED (employee_id)
);

-- Non-clustered index on department_id
-- Stores: department_id → employee_id (pointer back to clustered index)
CREATE NONCLUSTERED INDEX idx_employees_department
    ON employees (department_id);

-- ── SCENARIO 1: Non-clustered causes a Key Lookup ────────────
-- The index has department_id but NOT salary or last_name.
-- Engine finds the pointer via the index, then looks up the main
-- table again for each matching row — expensive at scale.
SELECT employee_id, last_name, salary
FROM   employees
WHERE  department_id = 7;
-- Execution plan shows: Key Lookup (clustered) — one extra disk read per row

-- ── SCENARIO 2: Covering index eliminates the Key Lookup ─────
-- Include all columns the query needs directly in the index.
-- The INCLUDE clause adds columns to the leaf level of the B-Tree
-- without making them part of the sort key.
CREATE NONCLUSTERED INDEX idx_employees_dept_covering
    ON employees (department_id)          -- the WHERE / JOIN column
    INCLUDE (last_name, salary);           -- columns needed in SELECT

-- Now the SAME query never touches the main table at all
SELECT employee_id, last_name, salary
FROM   employees
WHERE  department_id = 7;
-- Execution plan shows: Index Only Scan — all data in the index ✓

-- ── PRO MOVE: Composite index column ORDER matters ────────────
-- For a query filtering on department_id AND sorting by hire_date:
CREATE NONCLUSTERED INDEX idx_employees_dept_hire
    ON employees (department_id, hire_date);  -- filter col first, sort col second
-- Putting hire_date first would make the department filter less selective

-- ============================================================
-- Demonstrate the measurable write cost of indexes on a
-- high-throughput event_log table (append-only pattern).
-- ============================================================

-- Version A: Over-indexed event log (common beginner mistake)
CREATE TABLE event_log_over_indexed (
    event_id      BIGSERIAL PRIMARY KEY,
    user_id       BIGINT        NOT NULL,
    session_id    UUID          NOT NULL,
    event_type    VARCHAR(100)  NOT NULL,
    page_url      TEXT          NOT NULL,
    metadata      JSONB,
    created_at    TIMESTAMP     NOT NULL DEFAULT NOW()
);
-- Beginner adds indexes on every column "just in case"
CREATE INDEX idx_event_user    ON event_log_over_indexed (user_id);
CREATE INDEX idx_event_session ON event_log_over_indexed (session_id);
CREATE INDEX idx_event_type    ON event_log_over_indexed (event_type);
CREATE INDEX idx_event_url     ON event_log_over_indexed (page_url);
CREATE INDEX idx_event_time    ON event_log_over_indexed (created_at);
-- 6 total structures to update on every INSERT — silent write killer

-- Version B: Lean, thoughtful indexing
CREATE TABLE event_log_lean (
    event_id      BIGSERIAL PRIMARY KEY,
    user_id       BIGINT        NOT NULL,
    session_id    UUID          NOT NULL,
    event_type    VARCHAR(100)  NOT NULL,
    page_url      TEXT          NOT NULL,
    metadata      JSONB,
    created_at    TIMESTAMP     NOT NULL DEFAULT NOW()
);
-- Only index what your actual queries need:
-- Hot query 1: "Show me all events for user X in the last 7 days"
CREATE INDEX idx_lean_user_time
    ON event_log_lean (user_id, created_at DESC);
-- Hot query 2: "Count events by type in the last hour"
CREATE INDEX idx_lean_type_time
    ON event_log_lean (event_type, created_at DESC);
-- Result: 3 structures updated per INSERT vs 6 — 50% write reduction

-- ── Measure index bloat on existing tables (PostgreSQL) ──────
SELECT
    schemaname,
    tablename,
    indexname,
    pg_size_pretty(pg_relation_size(indexrelid)) AS index_size,
    idx_scan   AS times_used,    -- indexes with 0 here are deadweight
    idx_tup_read,
    idx_tup_fetch
FROM   pg_stat_user_indexes
ORDER BY pg_relation_size(indexrelid) DESC;
-- Any index with idx_scan = 0 is costing you writes and giving nothing back