Indexing Strategy and Design Questions

Situation: You have events(event_id UUID PK, user_id UUID, event_type text, payload JSONB, occurred_at timestamptz) and must optimize for (a) recent per-user, (b) filtering by type + time range, (c) queries on payload keys.

Recommended schema/index choices and rationale:

1. Recent events per user (fast ORDER BY occurred_at DESC, LIMIT):

• B-tree composite index: CREATE INDEX ix_events_user_occurred_desc ON events (user_id, occurred_at DESC);
  • Rationale: supports WHERE user_id = ? ORDER BY occurred_at DESC LIMIT N with an index-only scan if needed columns are included. Put user_id first to allow equality lookup then ordered by time.

2. Filter by event_type and time range:

• B-tree composite: CREATE INDEX ix_events_type_occurred ON events (event_type, occurred_at);
  • Rationale: efficient for queries like WHERE event_type = 'X' AND occurred_at BETWEEN a AND b.
• Partial index for hot/common types or recent window:
  CREATE INDEX ix_events_type_purchase_recent ON events (occurred_at DESC) WHERE event_type = 'purchase' AND occurred_at >= now() - INTERVAL '90 days';
  • Rationale: smaller index tailored to high-traffic filters improves IO and cache hit; good for rolling-window queries.

3. Inspect specific keys inside payload:
   Choose index strategy by query shape:

• containment (@>) queries (e.g., payload @> '{"order_id":"123"}'):
  CREATE INDEX ix_events_payload_gin ON events USING GIN (payload jsonb_path_ops);
  • Rationale: jsonb_path_ops is compact and faster for containment, but only supports @> and not existence of arbitrary keys. If you need full text search inside values, use default jsonb_ops (slower, more general).
• existence / key lookup (payload ? 'key') or value comparisons on a specific key used often:
  • Expression b-tree index: CREATE INDEX ix_events_payload_orderid ON events ((payload->>'order_id'));
    • Rationale: supports WHERE payload->>'order_id' = '123' and ORDER BY on that expression; b-tree is good for equality/range on extracted scalar.
• JSON path queries: if using SQL/JSON path (jsonb_path_query), evaluate and consider functional indexes on the used expression.

Additional notes / trade-offs:

• Consider covering indexes: include frequently selected columns to enable index-only scans (Postgres INCLUDE clause).
• Partial indexes reduce maintenance cost but only match queries satisfying WHERE.
• GIN indexes are larger and slower to update (write cost). If writes are heavy, balance by indexing only high-value access patterns.
• Keep statistics up-to-date (ANALYZE), use pg_stat_statements to verify index usage, and monitor bloat (VACUUM/REINDEX as needed).

Example queries matched to indexes:

• Recent user events: SELECT * FROM events WHERE user_id = $1 ORDER BY occurred_at DESC LIMIT 50; -> ix_events_user_occurred_desc
• Type + time: SELECT * FROM events WHERE event_type='click' AND occurred_at > now() - INTERVAL '7 days'; -> ix_events_type_occurred (or partial)
• Payload key: SELECT * FROM events WHERE payload->>'order_id' = 'abc'; -> ix_events_payload_orderid (expression index) or payload @> '{"order_id":"abc"}' -> GIN

This mix balances read performance, write overhead, and storage; start with the composite B-tree indexes plus one GIN for general JSON containment and add expression/partial indexes for high-frequency queries after verifying with EXPLAIN.

1. Simple definition
   An index is a data structure that allows the database to locate rows quickly without scanning the full table. Think of it as a sorted lookup table (like an index in a book) mapping key values to row locations.

2. How B-tree vs Hash indexes work (step-by-step) and effects
   B-tree (balanced tree):

• Structure: root → internal nodes → leaf nodes; leaves hold key ranges and pointers to rows or row locations.
• Read lookup: traverse from root to leaf following key comparisons (O(log n) height). Range queries scan contiguous leaves efficiently.
• Write (insert/delete): find leaf, modify and rebalance/split or merge nodes; causes additional I/O and page writes.
• Effects: good for point lookups, range queries, ordered scans; moderately impacts write latency due to tree maintenance.

Hash index:

• Structure: hash table mapping hash(key) → bucket of pointers.
• Read lookup: compute hash and probe bucket (average O(1)). Exact-match queries are fast.
• Range queries: inefficient or impossible because hashing destroys order.
• Write: insert into bucket, may require resizing/re-hashing (expensive) but usually cheaper per-op than B-tree rebalancing.
• Effects: excellent for equality lookups, poor for ranges or ORDER BY; collision handling and resizing affect performance.

3. Real-world examples

• Primary key index: usually a unique B-tree on PK; enforces uniqueness and accelerates PK lookups.
• Composite index: index on (last_name, first_name). Useful when queries filter on last_name or both; can’t be used for first_name-only filters unless DB supports index skip scans.
• Covering index: index contains all columns needed by a query (e.g., INDEX(idx_col1, col2) for SELECT col2 WHERE col1=...). DB can return results from index alone (index-only scan) avoiding table lookups.

4. Trade-offs and why indexing matters

• Space: indexes consume disk and memory; many indexes increase storage and cache pressure.
• Write overhead: every insert/update/delete may need updating all relevant indexes, increasing latency.
• Selectivity: high-selectivity columns (many distinct values) yield big read speedups; low-selectivity (boolean, few values) offer little benefit.
• Maintenance complexity: composite vs single-column choice, index ordering, and statistics must be managed.
  Why it matters: Proper indexing can reduce query time from O(n) to O(log n) or O(1) for common operations, dramatically improving app responsiveness. Poor or excessive indexing harms write throughput and increases cost—choose indexes based on query patterns, selectivity, and read/write balance.

Approach: Explain left-prefix rule, equality vs range, and how ordering interacts with index physical order. Then recommend specific indexes with SQL and justify by selectivity and query patterns.

How composite indexes work (brief):

• A composite index on (a,b,c) is stored ordered by a then b then c. The optimizer can use the index for lookups that specify the leftmost columns (left-prefix rule).
• Equality predicates (=) on leading columns allow the optimizer to use the following columns for range scans or ordering. Once a range predicate appears, later columns can’t be used for index equality lookups.

Ordering implications:

• If you want ORDER BY created_at DESC without an extra sort, created_at must appear in the index after any equality columns and the index’s sort order must match the ORDER BY direction (many RDBMS like MySQL 8+ can store DESC order in the index; others ignore direction but can still scan backwards).

Recommended indexes for queries that filter by (user_id, status) and ORDER BY created_at DESC:

1. Primary recommendation (single index covers filter + order):
   CREATE INDEX idx_orders_user_status_createdat ON orders (user_id, status, created_at DESC);

   • Why: user_id and status are equality filters, so put them first (order between them is less important for equality-only filters). created_at last lets the DB scan the index in descending created_at order for matching (user_id,status) tuples—avoids filesort.
   • If you select other columns (e.g., id), include them to make it covering: (..., created_at DESC, id).

2. If status is low-selectivity (e.g., few distinct values) and user_id is high-selectivity, put user_id before status:
   CREATE INDEX idx_orders_user_createdat_status ON orders (user_id, status, created_at DESC);
   (Same as above; but if you had to choose single ordering, user_id first is typically better.)

Selectivity notes:

• High-selectivity column first improves index usefulness when predicates are mixed (inequalities). But for equality filters on both, order doesn’t materially affect ability to use index for filtering; it affects index cardinality and clustering efficiency.
• If you sometimes query only by user_id, ensure the index’s leftmost column is user_id so it can be used. An index (status, user_id, created_at) would not be usable for user_id-only queries because of left-prefix.

Trade-offs:

• Composite index saves CPU (no sort) and reduces I/O if it’s covering; cost is more write overhead and disk space.
• If you have many queries that filter only by status or only by created_at ranges, consider additional specialized indexes, but avoid excessive indexes.

Edge cases:

• If queries use ranges on created_at in WHERE, the optimizer can still use the index but might not be able to use created_at for ordering beyond the range.
• Test with EXPLAIN to confirm index usage and that filesort is avoided.