Database indexes

-- SQLite 3.54: the same users, stored two ways
CREATE TABLE users_heap (email TEXT PRIMARY KEY, name TEXT, plan TEXT);
CREATE TABLE users_clustered (email TEXT PRIMARY KEY, name TEXT, plan TEXT) WITHOUT ROWID;
CREATE INDEX users_heap_plan ON users_heap (plan);
CREATE INDEX users_clustered_plan ON users_clustered (plan);

WITH RECURSIVE n(i) AS (SELECT 1 UNION ALL SELECT i + 1 FROM n WHERE i < 100000)
INSERT INTO users_heap
SELECT 'user' || i || '@example.com', 'User ' || i, CASE WHEN i % 10 = 0 THEN 'pro' ELSE 'free' END FROM n;
INSERT INTO users_clustered SELECT * FROM users_heap;

EXPLAIN QUERY PLAN SELECT name FROM users_heap WHERE email = 'user42@example.com';
-- SEARCH users_heap USING INDEX sqlite_autoindex_users_heap_1 (email=?)

EXPLAIN QUERY PLAN SELECT name FROM users_clustered WHERE email = 'user42@example.com';
-- SEARCH users_clustered USING PRIMARY KEY (email=?)

SELECT name, sum(pgsize) / 1024 AS kb FROM dbstat GROUP BY name;
-- users_heap                      4420  <- rows, keyed by rowid
-- sqlite_autoindex_users_heap_1   3196  <- email -> rowid
-- users_heap_plan                 1412  <- plan -> rowid
-- users_clustered                 4504  <- rows, keyed by email: no separate email index
-- users_clustered_plan            3340  <- plan -> email

-- PostgreSQL 18: 1 million orders from 20,000 customers; about 1% are still pending
CREATE TABLE orders (id bigint PRIMARY KEY, customer int, status text, total numeric);
INSERT INTO orders
SELECT i, i % 20000, CASE WHEN i % 97 = 0 THEN 'pending' ELSE 'shipped' END, i % 500
FROM generate_series(1, 1000000) AS i;

-- partial: index only the rows the app asks about
CREATE INDEX orders_status_all ON orders (status, customer);
CREATE INDEX orders_pending ON orders (customer) WHERE status = 'pending';

-- covering: the key to search on, plus a column to read without visiting the table
CREATE INDEX orders_customer ON orders (customer) INCLUDE (total);
VACUUM ANALYZE orders;  -- sets the visibility map, which index-only scans rely on

SELECT relname, pg_size_pretty(pg_relation_size(oid)) AS size
FROM pg_class WHERE relname LIKE 'orders%' ORDER BY relname;
-- orders 57 MB | orders_customer 30 MB | orders_pending 248 kB
-- orders_pkey 21 MB | orders_status_all 7328 kB

SET max_parallel_workers_per_gather = 0;
EXPLAIN (ANALYZE, BUFFERS, COSTS OFF)
SELECT id FROM orders WHERE status = 'pending' AND customer = 97;
-- Index Scan using orders_pending on orders (rows=1)
--   Index Cond: (customer = 97)
--   Buffers: shared hit=1 read=2

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF)
SELECT sum(total) FROM orders WHERE customer = 97;
-- Index Only Scan using orders_customer on orders (rows=50)
--   Heap Fetches: 0                         <- the table was never read
--   Buffers: shared hit=1 read=3

-- PostgreSQL 18: 1 million products with a name and a jsonb attributes column
CREATE EXTENSION pg_trgm;
CREATE TABLE products (id bigint PRIMARY KEY, name text, attrs jsonb);
INSERT INTO products
SELECT i, 'Widget ' || md5(i::text),
       jsonb_build_object('color', (ARRAY['red','green','blue','black'])[1 + i % 4],
                          'tags', jsonb_build_array('tag' || i % 1000, 'tag' || i % 7))
FROM generate_series(1, 1000000) AS i;

-- one entry per key and value, listing every row that contains it
CREATE INDEX products_attrs ON products USING gin (attrs jsonb_path_ops);
-- one entry per three-letter piece of the name
CREATE INDEX products_name_trgm ON products USING gin (name gin_trgm_ops);
VACUUM ANALYZE products;

SELECT relname, pg_size_pretty(pg_relation_size(oid)) AS size
FROM pg_class WHERE relname LIKE 'products%' ORDER BY relname;
-- products 135 MB | products_attrs 10 MB | products_name_trgm 114 MB | products_pkey 21 MB

SET max_parallel_workers_per_gather = 0;
EXPLAIN (ANALYZE, COSTS OFF)
SELECT count(*) FROM products WHERE attrs @> '{"tags": ["tag42"]}';
-- Bitmap Index Scan on products_attrs (rows=1000)
-- Execution Time: 18.717 ms      (sequential scan: 161.765 ms)

EXPLAIN (ANALYZE, COSTS OFF)
SELECT id, name FROM products WHERE name ILIKE '%c4ca42%';
-- Bitmap Index Scan on products_name_trgm (rows=4)
-- Bitmap Heap Scan on products (rows=2), Rows Removed by Index Recheck: 2
-- Execution Time: 0.940 ms       (sequential scan: 669.450 ms)