Indexing in DBMS — Missing Foreign Key Broke Checkout

-- ============================================================
-- 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

-- ============================================================
-- Show how column order in a composite index affects query plans.
-- Example: an orders table with department and order_date.
-- ============================================================

CREATE TABLE orders100k (
    order_id       SERIAL PRIMARY KEY,
    department_id  INT NOT NULL,
    order_date     DATE NOT NULL,
    amount         DECIMAL(10,2),
    status         VARCHAR(20)
);

-- Insert sample data (100k rows, 10 departments, 1000 dates)
INSERT INTO orders100k (department_id, order_date, amount, status)
SELECT
    (RANDOM() * 9 + 1)::INT,
    '2025-01-01'::DATE + (RANDOM() * 365)::INT,
    (RANDOM() * 1000)::DECIMAL(10,2),
    CASE WHEN RANDOM() < 0.5 THEN 'completed' ELSE 'pending' END
FROM generate_series(1, 100000);

-- Index A: department_id first, order_date second
CREATE INDEX idx_dept_date ON orders100k (department_id, order_date);

-- Query 1: filter on leading column only → efficient
EXPLAIN ANALYZE
SELECT COUNT(*)
FROM   orders100k
WHERE  department_id = 3;
-- Plan: Index Only Scan on idx_dept_date — excellent

-- Query 2: filter on both → still efficient
EXPLAIN ANALYZE
SELECT COUNT(*)
FROM   orders100k
WHERE  department_id = 3
  AND  order_date BETWEEN '2025-06-01' AND '2025-06-30';
-- Plan: Index Only Scan — even better because range is narrowed

-- Query 3: filter on second column only → NOT efficient
EXPLAIN ANALYZE
SELECT COUNT(*)
FROM   orders100k
WHERE  order_date BETWEEN '2025-06-01' AND '2025-06-30';
-- Plan: Seq Scan (reads whole table) — index cannot help because leading column is missing

-- To support Query 3, you'd need an index on (order_date) alone
CREATE INDEX idx_date ON orders100k (order_date);

-- io.thecodeforge
-- Simulating multilevel index behavior in PostgreSQL
-- Outer index (level 1) points to inner index blocks (level 2)

CREATE TABLE orders (
    order_id BIGSERIAL PRIMARY KEY,
    customer_id INT NOT NULL,
    order_date TIMESTAMP NOT NULL,
    total DECIMAL(10,2)
);

-- PostgreSQL automatically creates a B-Tree index on primary key
-- For multilevel, the engine stores index pages in blocks
-- Inspect index depth using pg_stat_user_indexes

SELECT
    indexrelid::regclass AS index_name,
    idx_scan,
    idx_tup_read,
    idx_tup_fetch
FROM pg_stat_user_indexes
WHERE tablename = 'orders'
ORDER BY idx_scan DESC;

-- Real-world: a 10M row index typically has depth 3-4
-- You can estimate depth with:
SELECT pg_relation_size('orders_pkey') AS index_size_bytes;
-- Divide by 8192 (page size) to get number of leaf pages
-- Then take log base (fill factor * page entries) to estimate levels

-- io.thecodeforge
-- Force different access patterns in SQL Server

CREATE TABLE events (
    event_id BIGINT IDENTITY(1,1) PRIMARY KEY,
    event_type VARCHAR(50) NOT NULL,
    recorded_at DATETIME2 NOT NULL
);

-- Non-clustered index supporting both seek and scan
CREATE NONCLUSTERED INDEX idx_events_recorded_at 
ON events (recorded_at)
INCLUDE (event_type);

-- Query 1: Seek plan (high selectivity)
SELECT * FROM events 
WHERE recorded_at = '2025-01-15 14:30:00';
-- Estimated rows: ~1, plan shows Index Seek

-- Query 2: Scan plan (low selectivity)
SELECT * FROM events 
WHERE recorded_at >= '2025-01-01' 
  AND recorded_at < '2025-02-01';
-- Estimated rows: ~150K, plan shows Index Scan

-- Check actual execution plan
SET STATISTICS XML ON;
GO
-- Run your query, then examine XML for:
-- <PhysicalOp>Index Seek</PhysicalOp> vs <PhysicalOp>Index Scan</PhysicalOp>