Query Rewrites & SARGability - Unnesting, NOT IN vs NOT EXISTS, OR to UNION, Keyset Pagination & ORM N+1

-- Page 6: how query shape decides what the optimizer can do.
\pset footer off
SET client_min_messages = warning;
DROP SCHEMA IF EXISTS p6 CASCADE;
CREATE SCHEMA p6;
SET search_path = p6;
SET max_parallel_workers_per_gather = 0;
CREATE TABLE users AS SELECT g AS id, 'u' || g || '@example.com' AS email FROM generate_series(1, 50000) g;
ALTER TABLE users ADD PRIMARY KEY (id);
CREATE TABLE orders AS
  SELECT g AS id,
         CASE WHEN g % 50000 = 0 THEN NULL ELSE 1 + (g * 13) % 40000 END AS user_id,   -- one NULL user_id
         timestamptz '2026-01-01' + (g || ' minutes')::interval AS created_at,
         'SKU-' || (g % 900) AS sku
  FROM generate_series(1, 200000) g;
ALTER TABLE orders ADD PRIMARY KEY (id);
CREATE INDEX orders_created_idx ON orders (created_at);
CREATE INDEX orders_user_idx ON orders (user_id);
CREATE INDEX orders_sku_idx ON orders (sku);
VACUUM ANALYZE users; VACUUM ANALYZE orders;
-- 1) EXISTS / IN are unnested into a Semi Join; NOT EXISTS into an Anti Join
EXPLAIN (COSTS OFF) SELECT count(*) FROM users u WHERE EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id);
EXPLAIN (COSTS OFF) SELECT count(*) FROM users u WHERE NOT EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id);
-- 2) NOT IN cannot become an anti join (NULL semantics) and, worse, one NULL makes it return nothing
SELECT count(*) AS not_exists_count FROM users u WHERE NOT EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id);
SELECT count(*) AS not_in_count FROM users u WHERE u.id NOT IN (SELECT o.user_id FROM orders o);
EXPLAIN (COSTS OFF) SELECT count(*) FROM users u WHERE u.id NOT IN (SELECT o.user_id FROM orders o);
-- 3) SARGability: a function on the indexed column hides it from the index; a half-open range does not
EXPLAIN (COSTS OFF) SELECT count(*) FROM orders WHERE date_trunc('day', created_at) = timestamptz '2026-02-01';
EXPLAIN (COSTS OFF) SELECT count(*) FROM orders
WHERE created_at >= timestamptz '2026-02-01' AND created_at < timestamptz '2026-02-02';
-- 4) Casting the column (often what an ORM or a mismatched parameter type does) has the same effect
EXPLAIN (COSTS OFF) SELECT * FROM users WHERE id::text = '4242';
EXPLAIN (COSTS OFF) SELECT * FROM users WHERE id = '4242';    -- literal is coerced to int instead: index usable
-- 5) OR across different columns: PostgreSQL can BitmapOr two indexes (MySQL index_merge, or rewrite to UNION)
EXPLAIN (COSTS OFF) SELECT count(*) FROM orders WHERE user_id = 7 OR sku = 'SKU-5';
-- 6) Deep OFFSET pagination reads and throws away rows; keyset (seek) pagination starts at the right place
CREATE INDEX orders_created_id_idx ON orders (created_at, id);   -- same index serves both queries
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
SELECT id, created_at FROM orders ORDER BY created_at, id OFFSET 150000 LIMIT 20;
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
SELECT id, created_at FROM orders
WHERE (created_at, id) > (timestamptz '2026-04-15 04:00:00+00', 150000)
ORDER BY created_at, id LIMIT 20;

SET max_parallel_workers_per_gather = 0;
EXPLAIN (COSTS OFF) SELECT count(*) FROM users u WHERE EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id);
                  QUERY PLAN                  
----------------------------------------------
 Aggregate
   ->  Hash Join
         Hash Cond: (u.id = o.user_id)
         ->  Seq Scan on users u
         ->  Hash
               ->  HashAggregate
                     Group Key: o.user_id
                     ->  Seq Scan on orders o

EXPLAIN (COSTS OFF) SELECT count(*) FROM users u WHERE NOT EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id);
              QUERY PLAN               
---------------------------------------
 Aggregate
   ->  Hash Right Anti Join
         Hash Cond: (o.user_id = u.id)
         ->  Seq Scan on orders o
         ->  Hash
               ->  Seq Scan on users u

SELECT count(*) AS not_exists_count FROM users u WHERE NOT EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id);
 not_exists_count 
------------------
            10000

SELECT count(*) AS not_in_count FROM users u WHERE u.id NOT IN (SELECT o.user_id FROM orders o);
 not_in_count 
--------------
            0

EXPLAIN (COSTS OFF) SELECT count(*) FROM users u WHERE u.id NOT IN (SELECT o.user_id FROM orders o);
                         QUERY PLAN                         
------------------------------------------------------------
 Aggregate
   ->  Seq Scan on users u
         Filter: (NOT (ANY (id = (hashed SubPlan 1).col1)))
         SubPlan 1
           ->  Seq Scan on orders o

EXPLAIN (COSTS OFF) SELECT count(*) FROM orders WHERE date_trunc('day', created_at) = timestamptz '2026-02-01';
                                                 QUERY PLAN                                                 
------------------------------------------------------------------------------------------------------------
 Aggregate
   ->  Seq Scan on orders
         Filter: (date_trunc('day'::text, created_at) = '2026-02-01 00:00:00-06'::timestamp with time zone)

EXPLAIN (COSTS OFF) SELECT count(*) FROM orders
WHERE created_at >= timestamptz '2026-02-01' AND created_at < timestamptz '2026-02-02';
                                                                           QUERY PLAN                                                                           
----------------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate
   ->  Index Only Scan using orders_created_idx on orders
         Index Cond: ((created_at >= '2026-02-01 00:00:00-06'::timestamp with time zone) AND (created_at < '2026-02-02 00:00:00-06'::timestamp with time zone))

EXPLAIN (COSTS OFF) SELECT * FROM users WHERE id::text = '4242';
              QUERY PLAN               
---------------------------------------
 Seq Scan on users
   Filter: ((id)::text = '4242'::text)

EXPLAIN (COSTS OFF) SELECT * FROM users WHERE id = '4242';
              QUERY PLAN              
--------------------------------------
 Index Scan using users_pkey on users
   Index Cond: (id = 4242)

EXPLAIN (COSTS OFF) SELECT count(*) FROM orders WHERE user_id = 7 OR sku = 'SKU-5';
                           QUERY PLAN                           
----------------------------------------------------------------
 Aggregate
   ->  Bitmap Heap Scan on orders
         Recheck Cond: ((user_id = 7) OR (sku = 'SKU-5'::text))
         ->  BitmapOr
               ->  Bitmap Index Scan on orders_user_idx
                     Index Cond: (user_id = 7)
               ->  Bitmap Index Scan on orders_sku_idx
                     Index Cond: (sku = 'SKU-5'::text)

CREATE INDEX orders_created_id_idx ON orders (created_at, id);
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
SELECT id, created_at FROM orders ORDER BY created_at, id OFFSET 150000 LIMIT 20;
                                        QUERY PLAN                                        
------------------------------------------------------------------------------------------
 Limit (actual rows=20 loops=1)
   ->  Index Only Scan using orders_created_id_idx on orders (actual rows=150020 loops=1)
         Heap Fetches: 0

EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
SELECT id, created_at FROM orders
WHERE (created_at, id) > (timestamptz '2026-04-15 04:00:00+00', 150000)
ORDER BY created_at, id LIMIT 20;
                                                 QUERY PLAN                                                  
-------------------------------------------------------------------------------------------------------------
 Limit (actual rows=20 loops=1)
   ->  Index Only Scan using orders_created_id_idx on orders (actual rows=20 loops=1)
         Index Cond: (ROW(created_at, id) > ROW('2026-04-14 23:00:00-05'::timestamp with time zone, 150000))
         Heap Fetches: 0

"""Query rewrites you can verify in any Python install (stdlib sqlite3, real EXPLAIN QUERY PLAN output).

1) NOT IN vs NOT EXISTS with a NULL in the subquery.
2) SARGability: function on an indexed column vs an equivalent range.
3) Type mismatches: literal coerced (fine) vs column cast (index lost).
4) OFFSET vs keyset pagination: rows the engine has to step over.
"""
import sqlite3

db = sqlite3.connect(":memory:")
db.executescript("""
CREATE TABLE users(id INTEGER PRIMARY KEY, email TEXT);
CREATE TABLE orders(id INTEGER PRIMARY KEY, user_id INTEGER, created_at TEXT, phone TEXT);
CREATE INDEX orders_created ON orders(created_at);
CREATE INDEX orders_phone ON orders(phone);
""")
db.executemany("INSERT INTO users VALUES (?, ?)", [(i, f"u{i}@example.com") for i in range(1, 1001)])
db.executemany("INSERT INTO orders VALUES (?, ?, ?, ?)",
               [(i, None if i == 500 else 1 + i % 800,                       # exactly one NULL user_id
                 f"2026-{1 + i % 12:02d}-{1 + i % 28:02d} 10:00:00", f"555{i:04d}") for i in range(1, 5001)])
db.execute("ANALYZE")

def plan(sql):
    return " | ".join(row[3] for row in db.execute("EXPLAIN QUERY PLAN " + sql))

print("sqlite", sqlite3.sqlite_version)
# 1) NULL trap: x NOT IN (..., NULL) is never TRUE (it is NULL or FALSE), so the filter drops every row
q_not_in = "SELECT count(*) FROM users WHERE id NOT IN (SELECT user_id FROM orders)"
q_not_exists = "SELECT count(*) FROM users u WHERE NOT EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id)"
print("NOT IN     ->", db.execute(q_not_in).fetchone()[0])
print("NOT EXISTS ->", db.execute(q_not_exists).fetchone()[0])
print("NOT IN + IS NOT NULL ->", db.execute(q_not_in.replace("FROM orders)", "FROM orders WHERE user_id IS NOT NULL)")).fetchone()[0])

# 2) SARGable vs not
print("function on column:", plan("SELECT count(*) FROM orders WHERE substr(created_at, 1, 7) = '2026-03'"))
print("half-open range   :", plan("SELECT count(*) FROM orders WHERE created_at >= '2026-03-01' AND created_at < '2026-04-01'"))

# 3) Type mismatches. SQLite applies the column's TEXT affinity to the literal, so the index still works;
#    casting the *column* (what an ORM or a careless refactor does) hides it from the index.
#    (MySQL is stricter: string_column = 123 converts the column side and cannot use the index.)
print("phone = 5550042           :", plan("SELECT * FROM orders WHERE phone = 5550042"))
print("CAST(phone AS INT)=5550042:", plan("SELECT * FROM orders WHERE CAST(phone AS INTEGER) = 5550042"))

# 4) OFFSET vs keyset: count VM steps with a progress handler as a proxy for work done
def steps(sql):
    n = [0]
    def tick(): n[0] += 1; return 0
    db.set_progress_handler(tick, 10)        # callback every 10 VM instructions
    db.execute(sql).fetchall(); db.set_progress_handler(None, 0)
    return n[0] * 10
off = steps("SELECT id FROM orders ORDER BY id LIMIT 20 OFFSET 4000")
key = steps("SELECT id FROM orders WHERE id > 4000 ORDER BY id LIMIT 20")
print(f"OFFSET 4000 page: ~{off:,} VM steps | keyset page (id > 4000): ~{key:,} VM steps")

sqlite 3.46.1
NOT IN     -> 0
NOT EXISTS -> 200
NOT IN + IS NOT NULL -> 200
function on column: SCAN orders USING COVERING INDEX orders_created
half-open range   : SEARCH orders USING COVERING INDEX orders_created (created_at>? AND created_at<?)
phone = 5550042           : SEARCH orders USING INDEX orders_phone (phone=?)
CAST(phone AS INT)=5550042: SCAN orders
OFFSET 4000 page: ~8,110 VM steps | keyset page (id > 4000): ~80 VM steps

// Two app-side query-shape problems the optimizer cannot fix for you:
// 1) ORM N+1: one query for a list, then one query per row. Detect it by fingerprinting SQL
//    (strip literals) and counting repeats per request, the way pg_stat_statements groups queries.
// 2) OFFSET pagination: page k costs O(k * pageSize) rows read; keyset (seek) costs O(pageSize).
// The request log and table sizes are example values.

function fingerprint(sql: string): string {
  return sql
    .replace(/'(?:[^']|'')*'/g, "?")          // string literals
    .replace(/\b\d+(\.\d+)?\b/g, "?")         // numeric literals
    .replace(/\bin\s*\(\s*\?(\s*,\s*\?)*\s*\)/gi, "IN (?)") // collapse IN lists
    .replace(/\s+/g, " ")
    .trim();
}

function detectNPlusOne(log: string[], threshold = 5): Array<[string, number]> {
  const counts = new Map<string, number>();
  for (const q of log) counts.set(fingerprint(q), (counts.get(fingerprint(q)) ?? 0) + 1);
  return [...counts.entries()].filter(([, n]) => n >= threshold).sort((a, b) => b[1] - a[1]);
}

// One HTTP request rendering 25 posts with their authors, ORM lazy-loading style:
const requestLog: string[] = ["SELECT id, author_id, title FROM posts ORDER BY created_at DESC LIMIT 25"];
for (let i = 0; i < 25; i++) requestLog.push(`SELECT id, name FROM users WHERE id = ${100 + i}`);
console.log(`queries in request: ${requestLog.length}`);
for (const [fp, n] of detectNPlusOne(requestLog)) console.log(`N+1 suspect x${n}: ${fp}`);
// The fix is one set-based query (JOIN, or WHERE id IN (...) / = ANY($1) via eager loading):
const batched = `SELECT id, name FROM users WHERE id IN (${Array.from({ length: 25 }, (_, i) => 100 + i).join(", ")})`;
console.log(`after eager loading: 2 queries, second fingerprint = ${fingerprint(batched)}`);

// OFFSET vs keyset: rows the database must read (index entries walked) to serve page k
const pageSize = 20;
for (const page of [1, 100, 5_000, 50_000]) {
  const offsetRows = (page - 1) * pageSize + pageSize;   // walks and discards everything before the page
  const keysetRows = pageSize;                           // seeks to (last_created_at, last_id) and reads one page
  console.log(`page ${String(page).padStart(6)}: OFFSET reads ${offsetRows.toLocaleString("en-US").padStart(9)} rows, keyset reads ${keysetRows}`);
}

queries in request: 26
N+1 suspect x25: SELECT id, name FROM users WHERE id = ?
after eager loading: 2 queries, second fingerprint = SELECT id, name FROM users WHERE id IN (?)
page      1: OFFSET reads        20 rows, keyset reads 20
page    100: OFFSET reads     2,000 rows, keyset reads 20
page   5000: OFFSET reads   100,000 rows, keyset reads 20
page  50000: OFFSET reads 1,000,000 rows, keyset reads 20