Diff v2 → v3

  # Push Compute to the Datastore
  
  > **When to use it:** designing or reviewing a backend query, endpoint, or service
  > and deciding **where a computation should live** — app code, Postgres, or Redis.
  > Reach for it to kill an N+1 or an app-side loop, fix slow (OFFSET) pagination, add
  > aggregation / search / ranking / queues / rate-limiting / caching, or push
  > integrity down where it can't be bypassed. Keyword bait: "offload to the database",
  > "thin backend", "N+1", "keyset pagination", "window function", "SKIP LOCKED",
  > "rate limit", "leaderboard", "cache-aside", "materialized view".
  
  The one-line model: **the application layer orchestrates business *policy*; the
  datastore does the *data work*.** Filtering, sorting, joining, aggregating, ranking,
  de-duping, paginating, uniqueness, integrity, top-N, tree-walks are set operations the
  database already does in one indexed pass. Every `SELECT *` followed by an app-side loop
  re-implements — slowly, over the wire — what the engine does natively.
  
  But **climb the ladder; don't leap to the bottom.** "Offload everything to Redis" is as
  wrong as "loop in app code." The win is putting each computation on the *lowest rung that
  already solves it*. Postgres is already in your stack and is transactional and durable —
  reach for it first; add Redis only for what Postgres can't do cheaply. And measure the
  access pattern before optimizing it: offloading a query you haven't `EXPLAIN`ed is
  guessing. This is the "prefer the platform primitive over hand-rolled app code" instinct[^ponytail]
  applied to the backend.
  
  ## The ladder — climb until a rung solves it
  
  ```
  0. Understand + measure the access pattern      (EXPLAIN first, don't guess)
  1. Integrity           → DB constraints          (UNIQUE, FK, CHECK, NOT NULL, DEFAULT)
  2. Find / sort / page  → indexes                 (composite, covering, partial, expression; KEYSET not OFFSET)
  3. Shape / compute     → set-based SQL           (aggregates+FILTER, window fns, DISTINCT ON, LATERAL, CTEs, ON CONFLICT…RETURNING, SKIP LOCKED)
  4. Specialized engines → DB-native features      (FTS, pg_trgm, pgvector, PostGIS, materialized views, advisory locks)
  5. Ephemeral / cross-process / hot-path → Redis  (counters, rate-limits, leaderboards, cache, HLL, streams, locks)
  6. Branchy policy / CPU-heavy / must-be-testable → app code   (last resort — keep it thin)
  7. Outgrown Postgres+Redis (measured) → a specialized store   (search / OLAP / stream / graph / vector — last, and rederivable)
  ```
  
  ## 1. Integrity → constraints, not app checks
  
  An invariant enforced in app code holds only until a second writer (a migration, a job,
  another service, a `psql` session) bypasses it. A constraint holds always.[^ponytail]
  
  ```sql
  email        text    NOT NULL UNIQUE,
  price_cents  int     NOT NULL CHECK (price_cents > 0),
  author_id    bigint  NOT NULL REFERENCES users(id) ON DELETE CASCADE,
  id           uuid    DEFAULT gen_random_uuid(),
  created_at   timestamptz NOT NULL DEFAULT now()
  ```
  
  **Do** push uniqueness / FK / range / defaults into the schema. **Not** an
  `if exists?(email)` check before insert — it races, and the DB checks anyway. Pair
  `UNIQUE` with `INSERT … ON CONFLICT` (§3) so the app never round-trips to "check first".
  
  ## 2. Find / sort / paginate → the *right* indexes
  
  An index is the database's ability to *not* scan — but "it has an index" is not enough.[^luke]
  
  - **Composite column order: equality columns first, then the one range/sort column.**
    `WHERE tenant_id = ? AND created_at > ?` wants `(tenant_id, created_at)`. Reversed,
    `tenant_id` degrades from an *access predicate* (narrows the scan) to a *filter
    predicate* (scans, then discards). Everything after the first range/inequality column
    loses its narrowing power.[^luke]
  - **Never wrap an indexed column in a function** — `WHERE lower(email) = ?` can't use an
    index on `email`. Use an **expression index** `ON t (lower(email))` or a stored
    generated column.[^luke]
  - **Covering / index-only scans:** put read-only columns in the index so it never touches
    the heap — `CREATE INDEX … ON sales (subsidiary_id) INCLUDE (eur_value)`.[^luke]
  - **Partial indexes for hot subsets:** a queue table grows forever but you query only the
    unprocessed slice — `CREATE INDEX … ON jobs (created_at) WHERE status = 'pending'` stays
    small no matter how many `done` rows accumulate.[^luke]
  - **`ORDER BY` served by the index** (matching columns *and* direction) skips the sort step
    entirely — the biggest win with `LIMIT`.[^luke]
  
  ### 2b. Pagination: KEYSET (seek), never OFFSET at depth
  
  `LIMIT n OFFSET k` is defined as "produce the sorted result, then fetch and **discard** k
  rows." It is **O(k)** — page 1000 walks 10,000 rows to throw them away — *and* **incorrect**
  under concurrent inserts (a row added above the window shifts everything, so you skip or
  duplicate). Deep pagination that slows every page is this bug.[^luke]
  
  Keyset pagination passes the **last row's sort key** and asks for "rows after this",
  turning pagination into an indexed access predicate:
  
  ```sql
  -- index: (created_at DESC, id DESC)   ← unique tiebreaker (id) is mandatory for stable order
  -- first page:
  SELECT * FROM articles ORDER BY created_at DESC, id DESC FETCH FIRST 20 ROWS ONLY;
  -- next page: pass (created_at, id) of the LAST row shown
  SELECT * FROM articles
   WHERE (created_at, id) < (:last_created_at, :last_id)   -- row-value comparison = true access predicate
   ORDER BY created_at DESC, id DESC
   FETCH FIRST 20 ROWS ONLY;
  ```
  
  Trade-off to accept, not fight: you get next/prev, not "jump to page 47" — a bad UI anyway,
  and the wrong tool for infinite scroll / cursored APIs. (This is exactly why a cursored REST
  API encodes an opaque `sort_key:id` cursor instead of a page number.)
  
  ## 3. Shape / compute → one set-based query, not an app loop
  
  This rung kills the most app code. Each replaces "fetch rows, loop, tally":[^pg]
  
  | App-code impulse | Do this in SQL instead |
  |---|---|
  | Loop to bucket/sum by status; a 2nd query per bucket | `count(*) FILTER (WHERE status='refunded')`, `sum(x) FILTER (…)` in one pass |
  | Subtotals + grand total via 3 queries + UNION | `GROUP BY ROLLUP (a,b)` / `GROUPING SETS` / `CUBE` |
  | Sort rows in app for running total / rank / "vs previous row" | window fns: `sum(…) OVER (… ROWS UNBOUNDED PRECEDING)`, `rank() OVER(PARTITION BY …)`, `lag()` |
  | "Latest row per entity": pull all, keep first-seen per key | `SELECT DISTINCT ON (device_id) … ORDER BY device_id, recorded_at DESC` |
  | Top-3 per group (N+1 per parent) | `… CROSS JOIN LATERAL (SELECT … WHERE o.customer_id=c.id ORDER BY … LIMIT 3) o` |
  | Walk a tree/graph with a query per level (N+1) | `WITH RECURSIVE t AS (… UNION ALL …) SELECT * FROM t` |
  | SELECT-then-INSERT-or-UPDATE (races) + re-SELECT for the id | `INSERT … ON CONFLICT (k) DO UPDATE SET … RETURNING *` (atomic, one round trip) |
  | `for row in rows: UPDATE …` (N round trips) | set-based `UPDATE t SET … FROM other WHERE …` / `DELETE … USING …` |
  | A message broker just to hand one job to one worker | `SELECT id FROM jobs WHERE status='pending' ORDER BY … FOR UPDATE SKIP LOCKED LIMIT 1` then `UPDATE … RETURNING` |
  | Deserialize a JSON blob in app to filter/pluck a field | `WHERE payload @> '{"type":"signup"}'` with a `GIN` index; `payload->'user'->>'email'` |
  
  `RETURNING` on every write avoids the read-after-write round trip. CTE note (PG12+): a
  non-recursive CTE used once is inlined; add `AS MATERIALIZED` only to force the old
  optimization-fence behavior.[^pg]
  
  ## 4. Specialized engines → reach here before adding a new service
  
  Postgres has these built in; don't stand up Elasticsearch / a vector DB / a broker for
  moderate scale you haven't outgrown:[^pg]
  
  - **Full-text search:** a `tsvector` generated column + `GIN` index + `ts_rank`. Replaces
    `ILIKE '%…%'` scans and premature Elasticsearch.
  - **Fuzzy / typo-tolerant / substring:** `pg_trgm` (`gin_trgm_ops`, `similarity()`, `%`). Also
    the answer to "`LIKE '%foo'` can't use an index" — a leading wildcard has no access
    predicate; trigram indexing does.[^luke]
  - **Vector similarity (embeddings / RAG):** `pgvector` with an HNSW index (`<=>` cosine).
  - **Geo radius / proximity:** `PostGIS` (`ST_DWithin`) — not Haversine in a loop.
  - **Precomputed reports:** `MATERIALIZED VIEW` + `REFRESH MATERIALIZED VIEW CONCURRENTLY`
    (needs a `UNIQUE` index on the view). Replaces a cron job hand-writing a rollup table.
  - **Cross-process mutex without new infra:** `pg_advisory_xact_lock(hashtext('daily-report'))`.
  
  ## 4b. Match the storage model to the access pattern (row vs columnar)
  
  Postgres core is a **row store** (heap tables, MVCC): one page fetch returns every column
  of a row — ideal for OLTP point/range reads and high-churn single-row writes (helped by
  HOT updates + `fillfactor`; oversized values go out-of-line via TOAST; keep autovacuum
  healthy or dead-tuple bloat bites). But it's wrong for **analytics**: a `SELECT category,
  sum(amount) … GROUP BY category` over 50M rows still reads whole rows/pages to touch 2 of
  40 columns, evicting the OLTP working set from cache.[^storage]
  
  **Rule: "one row, all columns" → row store. "all rows, few columns, aggregated" →
  columnar.** Columnar stores each column contiguously — scans only the columns touched and
  compresses 3–10×.
  
  - **Columnar inside Postgres (maintained, 2026):** **Citus columnar** (`CREATE TABLE …
    USING columnar`, works single-node — but append-only: no `UPDATE`/`DELETE`);
    **TimescaleDB hypercore** (time-series: recent chunks stay row-store, old chunks compress
    to columnstore, + continuous aggregates); **pg_duckdb / pg_mooncake** (DuckDB's vectorized
    engine / Iceberg lakehouse for OLAP). Avoid the dead ends — `cstore_fdw`, ParadeDB
    `pg_analytics`, and Hydra are unmaintained.[^storage]
  - **BRIN index** for huge, naturally-ordered append-only tables (time-series): stores
    min/max per block range — megabytes where a B-tree is gigabytes. Useless on a column
    uncorrelated with physical order (UUIDs, randomly-updated status) — that's a B-tree's job.
  - **Partitioning** (range/list/hash) prunes whole partitions on the partition key (don't
    wrap it in a function, that defeats pruning) and makes retention cheap (`DROP TABLE` a
    partition, not a bulk `DELETE`). Composes with the above: partition by month → BRIN on the
    timestamp → compress cold partitions to columnar.
  
  **Route analytics off the OLTP primary.** A big aggregation steals shared buffer cache + CPU
  from transactional queries — the classic "random latency spike." In rising order of effort:
  **materialized view / continuous aggregate** (known recurring shape, staleness ok) →
  **columnar table/extension** (ad hoc aggregates over one append-mostly fact table) → **read
  replica** (live-ish full SQL without touching the primary's cache) → **dedicated warehouse**
  (ClickHouse / DuckDB / BigQuery / Snowflake) at org-scale BI.[^storage]
  
  ## 5. Redis → only for what Postgres can't do cheaply
  
  Redis is an **accelerant, never the system of record.** Reach for it when you need
  *ephemeral, cross-process state on the hot path* at a rate that would hammer Postgres:[^redis]
  
  | Need | Redis |
  |---|---|
  | Cross-instance counter / fixed-window rate limit | `INCR` + `EXPIRE … NX` (make it atomic) |
  | Sliding-window rate limit | sorted set: `ZREMRANGEBYSCORE` + `ZADD` + `ZCARD`, wrapped atomically |
  | Burst-tolerant limit (production default) | token bucket in a **Lua script** (read-decide-write must be atomic or tokens double-spend) |
  | Leaderboard / rank / top-N | sorted set: `ZADD`, `ZINCRBY`, `ZREVRANGE`, `ZREVRANK` (ordering is free) |
  | Priority queue across workers | sorted set + `BZPOPMIN` (atomic blocking pop) |
  | Unique visitors / huge cardinality | HyperLogLog `PFADD`/`PFCOUNT` — ~12 KB fixed, 0.81% error, vs a multi-GB `SET` |
  | Per-user daily flags / DAU / retention | bitmaps `SETBIT`/`BITCOUNT`/`BITOP AND` — 1 bit per user |
  | Event log / lightweight queue with acks & replay | Streams `XADD`/`XREADGROUP`/`XACK` + `XPENDING`/`XCLAIM` (at-least-once) |
  | Fire-and-forget broadcast | Pub/Sub (at-most-once; offline subscribers miss it — use Streams if that's not ok) |
  | Read cache in front of Postgres | cache-aside (see below) |
  
  **Redis rules that are easy to get fatally wrong:**[^redis]
  
  - **Multi-step = not atomic.** `ZADD` then `ZCARD` then decide is a race — two requests
    both pass the check. Wrap read-modify-write in a **Lua script** (`EVAL`; it blocks the
    server, so keep it tiny) or `MULTI/EXEC`. Token buckets and check-and-set *must* be Lua.
  - **Cache-aside:** read miss → load from Postgres → `SET … EX ttl`. On write, **`DEL` the
    key — do not `SET` it** (a `SET` races with an in-flight stale read that overwrites your
    fresh value). Always set a TTL even with explicit invalidation (TTL is the backstop). Add
    **jitter** so keys don't mass-expire, and guard recompute with a `SET NX PX` **mutex** so
    a popular expired key doesn't stampede the DB.
  - **Distributed lock:** `SET key <random-token> NX PX 30000` to acquire; release with a
    **Lua compare-token-then-DEL**, never a bare `DEL`. Redlock has real caveats (clock drift,
    GC-pause stalls — read Kleppmann vs antirez): fine as an *advisory* lock, but for
    correctness-critical exclusion add **fencing tokens** or use real consensus. Postgres
    advisory locks (§4) are often the simpler right answer.
  - **Not durable by default.** RDB loses seconds–minutes on crash; `MULTI/EXEC` has **no
    rollback**; memory is finite and eviction deletes data silently once `maxmemory` + an
    `lru/lfu/random` policy is set. Money, auth of record, and audit data live in Postgres;
    Redis holds a copy it can rebuild.
  
  ## 6. App code → the last rung, kept thin
  
  What genuinely belongs here: branchy **business policy** with many edge cases (pricing,
  eligibility, workflow) that needs unit tests and version-controlled diffs; **CPU-heavy**
  work (image/PDF/crypto/ML) that would steal CPU from the query workload; and anything a
  hard **portability** requirement forbids pushing into Postgres-specific SQL.[^pg] Rule of
  thumb: **offload set-based data operations; keep branchy policy and heavy compute in the app.**
  
  ## 7. Beyond Postgres/Redis → a specialized store, only when the pain is measured
  
  Don't add a datastore until you have **measured, current pain on a specific access pattern** —
  every new store is another backup/monitor/on-call/consistency surface and a second source of
  truth (a bug generator). There's almost always a cheaper step *inside* Postgres/Redis first, and
  you should run any specialized store as a **secondary, always-rederivable-from-Postgres** index,
  never the system of record. Signals you've genuinely outgrown it: search →
  Meilisearch/Typesense/Elasticsearch; OLAP → ClickHouse/DuckDB/warehouse; streaming →
  Kafka/Redpanda/NATS; graph → Neo4j (be skeptical — recursive CTEs go far); vector at scale →
- a dedicated vector DB. Details + thresholds in [[Redis Internals, Probabilistic Structures and Datastore Selection]].
+ a dedicated vector DB. Details + thresholds in [[redis-deep-dive-and-datastore-selection|Redis Internals & Datastore Selection]].
  
  ## Deep dives
  
  This is the operational hub. Each area has a companion when you need the depth:
  
- - [[Postgres Full-Text and Fuzzy Search]] — tsvector/`websearch_to_tsquery`, ranking, GIN/GiST/RUM, pg_trgm, hybrid FTS+vector (RRF), when to leave for Elasticsearch.
- - [[Postgres Query Planning and EXPLAIN]] — reading plans, statistics/extended stats, `work_mem` spills, the prepared-statement generic-plan trap.
- - [[Postgres Concurrency and Throughput]] — MVCC/vacuum/bloat, locking & deadlocks, isolation anomalies, connection pooling, COPY/`unnest` bulk writes, idempotency.
- - [[Postgres Scale-Out, Replication and Data Movement]] — replicas & read-your-writes, Citus sharding, CDC/outbox, FDW, partition-detach archival, denormalization.
- - [[Redis Internals, Probabilistic Structures and Datastore Selection]] — memory/encoding, Bloom/Count-Min/Top-K/t-digest, Cluster, and the specialized-store decision matrix.
+ - [[postgres-full-text-search|Postgres Full-Text & Fuzzy Search]] — tsvector/`websearch_to_tsquery`, ranking, GIN/GiST/RUM, pg_trgm, hybrid FTS+vector (RRF), when to leave for Elasticsearch.
+ - [[postgres-query-planning|Postgres Query Planning & EXPLAIN]] — reading plans, statistics/extended stats, `work_mem` spills, the prepared-statement generic-plan trap.
+ - [[postgres-concurrency-and-throughput|Postgres Concurrency & Throughput]] — MVCC/vacuum/bloat, locking & deadlocks, isolation anomalies, connection pooling, COPY/`unnest` bulk writes, idempotency.
+ - [[postgres-scale-out|Postgres Scale-Out & Replication]] — replicas & read-your-writes, Citus sharding, CDC/outbox, FDW, partition-detach archival, denormalization.
+ - [[redis-deep-dive-and-datastore-selection|Redis Internals & Datastore Selection]] — memory/encoding, Bloom/Count-Min/Top-K/t-digest, Cluster, and the specialized-store decision matrix.
  
  ## The escape valve — mark a deliberate non-offload
  
  Premature offloading is real. When you consciously leave compute in the app (or accept an
  N+1 at current scale), leave a breadcrumb with a trigger for when to revisit:[^ponytail]
  
  ```python
  # thin-backend: N+1 accepted — <100 rows per request. Switch to a LATERAL join if this
  # endpoint serves lists >1k, or if p95 crosses 200ms.
  ```
  
  ## Verify — offloading only wins if the DB does it efficiently
  
  - `EXPLAIN (ANALYZE, BUFFERS) <query>` — watch for a seq scan where you expected an index,
    `Rows Removed by Filter` ≫ rows returned, high `shared read` (I/O-bound), and
    actual-vs-estimated row blowups (stale stats → `ANALYZE`).[^pg]
  - `pg_stat_statements` — find the queries that are actually expensive in production.
  - Index cost is real: every index slows writes (one index can make an INSERT ~100× slower).
    Index what you query, drop speculative indexes, don't over-index write-heavy tables.[^luke]
  
  ## See also
  
  - [[Scaling Rails: Vertical & Horizontal]] — "the real bottleneck is almost always the
    database"; this skill is how you relieve it.
  - [[Clean Architecture]] — keep the datastore-specific SQL behind a boundary so the thin
    app layer stays testable and the offloading doesn't leak into business policy.
  
  [^ponytail]: Ponytail (DietrichGebert) — "the best code is the code you never wrote";
      prefer platform/DB primitives (`UNIQUE`/`FOREIGN KEY`/`CHECK`, window functions,
      recursive CTEs) over app-level re-implementations. <https://github.com/DietrichGebert/ponytail>
  [^luke]: Markus Winand, *Use The Index, Luke!* — B-tree access vs filter predicates,
      composite-index ordering (equality before range), expression/covering/partial indexes,
      and the OFFSET-vs-keyset pagination chapter. <https://use-the-index-luke.com/>
  [^pg]: PostgreSQL 16/17 docs — aggregate `FILTER`, window functions, `DISTINCT ON`,
      `LATERAL`, recursive CTEs, `INSERT … ON CONFLICT … RETURNING`, `FOR UPDATE SKIP LOCKED`,
      generated columns, materialized views, `EXPLAIN`. <https://www.postgresql.org/docs/current/>
  [^redis]: Redis docs — sorted sets, HyperLogLog, bitmaps, Streams, Lua/`EVAL` atomicity,
      cache-aside, distributed locks (+ Kleppmann/antirez Redlock debate), persistence &
      eviction caveats. <https://redis.io/docs/latest/>
  [^storage]: PostgreSQL storage internals (heap/TOAST/HOT, BRIN, declarative partitioning)
      <https://www.postgresql.org/docs/current/storage.html>; columnar landscape verified
      2026 — Citus columnar (`USING columnar`), TimescaleDB hypercore, pg_duckdb/pg_mooncake
      are maintained; cstore_fdw, ParadeDB pg_analytics, and Hydra are discontinued.