Index with Sort #

-- A query that triggers filesort
EXPLAIN SELECT id, title, created_at
FROM articles
WHERE status = 'published'
ORDER BY created_at DESC
LIMIT 20;

-- If the only existing index is: INDEX (status)
-- +------+-------+---------------+------+---------+--------------------------+
-- | type | key   | possible_keys | rows | filtered | Extra                   |
-- +------+-------+---------------+------+---------+--------------------------+
-- | ref  | idx_  | idx_status    | 85000| 100.00  | Using where; Using      |
-- |      | status|               |      |         | filesort                |
-- +------+-------+---------------+------+---------+--------------------------+

-- "Using where" → the status filter is used
-- "Using filesort" → the database collects 85,000 rows,
--   then sorts all of them to take the top 20
-- LIMIT 20 doesn't help reduce the sort cost!

-- Create a composite index covering WHERE and ORDER BY
CREATE INDEX idx_articles_status_created
    ON articles (status, created_at DESC);

-- The same query now:
EXPLAIN SELECT id, title, created_at
FROM articles
WHERE status = 'published'
ORDER BY created_at DESC
LIMIT 20;

-- +-------+-----------------------------+------+---------+-----------------------+
-- | type  | key                         | rows | filtered | Extra                |
-- +-------+-----------------------------+------+---------+-----------------------+
-- | range | idx_articles_status_created |   20 | 100.00  | Using index condition |
-- +-------+-----------------------------+------+---------+-----------------------+

-- rows = 20  ← the database only reads 20 rows!
-- No "Using filesort"
-- Extra: "Using index condition" → an index scan with a condition

-- Query: published articles from a specific category, newest first
SELECT id, title, created_at
FROM articles
WHERE status = 'published'
  AND category_id = 5
ORDER BY created_at DESC
LIMIT 20;

-- ANTI-PATTERN 1: sort column before equality columns
CREATE INDEX idx_wrong_1 ON articles (created_at DESC, status, category_id);
-- → The database can't use the index for the status and category_id filters
--   because they aren't index prefixes
-- → Filesort appears

-- ANTI-PATTERN 2: sort column in the middle of equality columns
CREATE INDEX idx_wrong_2 ON articles (status, created_at DESC, category_id);
-- → The database can use status, but after hitting created_at (the sort column)
--   it can't continue to category_id in the next position
-- → category_id can't be used through this index
-- → Filesort can appear

-- CORRECT: all equality columns first, sort column last
CREATE INDEX idx_correct ON articles (status, category_id, created_at DESC);
-- → The database: seek to (status='published', category_id=5)
-- → In that position, rows are already sorted by created_at DESC
-- → Take 20, done — no filesort

-- Query: articles created in the last 7 days, newest first
SELECT id, title, created_at
FROM articles
WHERE status = 'published'
  AND created_at >= NOW() - INTERVAL 7 DAY  -- ← range condition
ORDER BY created_at DESC
LIMIT 20;

-- Index: (status, created_at DESC)
-- What happens?
-- The database seeks to status='published', created_at >= [threshold]
-- Within that range, the data is ALREADY sorted by created_at DESC
-- → No filesort! A range on the same sort column isn't a problem.

-- But if the range isn't on the sort column:
SELECT id, title, created_at
FROM articles
WHERE status = 'published'
  AND price BETWEEN 100000 AND 500000  -- ← a range on ANOTHER column
ORDER BY created_at DESC
LIMIT 20;

-- Ideal index: (status, price, created_at DESC)
-- Problem: after finding rows within the price range,
-- those rows are NO LONGER sorted by created_at
-- The database still must sort → filesort appears
-- This is a fundamental B-Tree index limitation

-- MySQL 8.0+: per-column descending indexes
CREATE INDEX idx_articles_price_created
    ON articles (price ASC, created_at DESC);

-- The query leveraging this:
SELECT id, title, price, created_at
FROM articles
WHERE status = 'published'
ORDER BY price ASC, created_at DESC
LIMIT 20;

-- EXPLAIN in MySQL 8.0+:
-- Extra: "Using index condition"  ← no filesort!

-- In MySQL 5.7 or older:
-- DESC in indexes is ignored, everything is stored ASC
-- The query ORDER BY price ASC, created_at DESC will trigger filesort
-- because the index doesn't store created_at in DESC order

-- Check whether the index is really stored as DESC
SHOW CREATE TABLE articles;
-- Look for DESC in the index definition:
-- KEY `idx_articles_price_created` (`price`,`created_at` DESC)

-- PostgreSQL: specify the direction per column
CREATE INDEX idx_articles_price_created
    ON articles (price ASC NULLS LAST, created_at DESC NULLS FIRST);

-- NULLS FIRST / NULLS LAST determines NULL value positions in sorting
-- Important for preventing "sort mismatches" that still trigger runtime sorts

-- Query:
SELECT id, title, price, created_at
FROM articles
WHERE status = 'published'
ORDER BY price ASC NULLS LAST, created_at DESC NULLS FIRST
LIMIT 20;

-- EXPLAIN ANALYZE:
-- -> Index Scan using idx_articles_price_created on articles
--    (cost=0.43..95.23 rows=20 width=44) (actual time=0.028..0.089 rows=20 loops=1)
-- No Sort node → the index scan directly produces the right order

-- Index: (status, created_at) — implicitly ASC
CREATE INDEX idx_articles_status_created ON articles (status, created_at);

-- ASC query: forward scan
SELECT id FROM articles
WHERE status = 'published'
ORDER BY created_at ASC
LIMIT 20;
-- → Scans the index from the front: efficient

-- DESC query: backward scan
SELECT id FROM articles
WHERE status = 'published'
ORDER BY created_at DESC
LIMIT 20;
-- → Scans the index from the back: almost equally efficient
-- EXPLAIN Extra: "Backward index scan" (MySQL 8.0+)
-- or "Index Scan Backward" (PostgreSQL)
-- No filesort!

-- A frequently run query: the latest articles list with minimal data
SELECT id, title, status, created_at
FROM articles
WHERE status = 'published'
ORDER BY created_at DESC
LIMIT 20;

-- A regular index: (status, created_at DESC)
-- The database: uses the index for the seek and sort
-- But still needs to read the table for the 'title' and 'id' columns
-- Extra: "Using index condition" (still a table lookup)

-- Covering index: add all SELECT columns
CREATE INDEX idx_articles_covering
    ON articles (status, created_at DESC, title, id);
-- Or more concisely since 'id' is the primary key always in the index:
CREATE INDEX idx_articles_covering
    ON articles (status, created_at DESC, title);

-- Now:
-- Extra: "Using index"  ← index-only scan, no table lookup
-- Rows read: exactly 20 — no more

-- Performance comparison:
-- Without covering:  read 20 index entries + 20 table lookups
-- With covering: read 20 index entries only — 2× faster for heavy reads

-- Query: the 20 latest activities from one user
SELECT id, type, message, created_at
FROM activity_logs
WHERE user_id = 42
ORDER BY created_at DESC
LIMIT 20;

-- ANTI-PATTERN: an index only on user_id
CREATE INDEX idx_logs_user ON activity_logs (user_id);
-- → user_id filter: ✓ (maybe 50,000 logs for this user)
-- → created_at sort: ✗ (filesort over 50,000 rows)

-- CORRECT: a composite index of user_id + created_at
CREATE INDEX idx_logs_user_created ON activity_logs (user_id, created_at DESC);
-- → Seek to user_id=42, rows already sorted by created_at DESC
-- → Take 20, done — zero filesort
-- → rows in EXPLAIN: 20 (not 50,000)

-- Query: the latest orders with status and tenant filters
SELECT id, order_number, total, created_at
FROM orders
WHERE tenant_id = 'abc123'
  AND status    = 'pending'
ORDER BY created_at DESC
LIMIT 20;

-- Index: (tenant_id, status, created_at DESC)
-- ✓ Equality: tenant_id
-- ✓ Equality: status
-- ✓ Sort: created_at DESC — in the last position, correct

-- Verify with EXPLAIN:
EXPLAIN SELECT id, order_number, total, created_at
FROM orders
WHERE tenant_id = 'abc123' AND status = 'pending'
ORDER BY created_at DESC LIMIT 20;

-- Expected:
-- type: range or ref
-- key: idx_orders_tenant_status_created
-- rows: ≈ 20 (not thousands)
-- Extra: "Using index condition" (no "Using filesort")

-- Query: active products sorted by featured_at (can be NULL)
-- featured_at NULL means the product isn't featured
SELECT id, name, featured_at
FROM products
WHERE status = 'active'
ORDER BY featured_at DESC  -- NULLs will be at the bottom
LIMIT 20;

-- Problem: NULLs in sorting can cause runtime sorts
-- In MySQL: NULL is considered the smallest (appears last in DESC)
-- In PostgreSQL: controllable with NULLS FIRST / NULLS LAST

-- The right index in MySQL:
CREATE INDEX idx_products_status_featured
    ON products (status, featured_at DESC);
-- NULLs will be at the end → featured products appear first

-- In PostgreSQL with NULLS LAST:
CREATE INDEX idx_products_status_featured
    ON products (status, featured_at DESC NULLS LAST);
-- Make sure the query uses ORDER BY featured_at DESC NULLS LAST
-- to match the index and avoid triggering runtime sorts

-- MySQL: enable the slow query log with minimal data
SET GLOBAL slow_query_log = 'ON';
SET GLOBAL long_query_time = 0.1;  -- log queries > 100ms
SET GLOBAL log_queries_not_using_indexes = 'ON';

-- Then analyze with:
-- mysqldumpslow -s t /var/log/mysql/slow.log
-- Look for queries with "filesort" in their EXPLAIN

-- PostgreSQL: pg_stat_statements for slow queries
SELECT query,
       calls,
       total_exec_time / calls AS avg_ms,
       rows / calls AS avg_rows
FROM pg_stat_statements
ORDER BY total_exec_time DESC
LIMIT 20;
-- Run EXPLAIN ANALYZE for each suspected query

-- Problem signals in MySQL EXPLAIN:
-- Extra: "Using filesort"           → runtime sort, not index sort
-- Extra: "Using temporary"         → the sort needs a temporary table (more expensive)
-- rows: a large number with a small LIMIT → scanning too many rows

-- Problem signals in PostgreSQL EXPLAIN:
-- -> Sort  (cost=...) → a Sort node exists → filesort
-- -> Seq Scan         → no index used at all

-- Good EXPLAIN targets:
-- MySQL: Extra contains "Using index" or "Using index condition",
--        does NOT contain "Using filesort"
-- PostgreSQL: no Sort node above an Index Scan

-- ✗ Anti-pattern 1: indexes only for filters, forgetting the sort
CREATE INDEX idx_orders_status ON orders (status);
-- Query: WHERE status = ? ORDER BY created_at DESC LIMIT 20
-- → The filter uses the index, but the sort is still a filesort
-- ✓ Solution: CREATE INDEX idx_orders_status_created ON orders (status, created_at DESC)

-- ✗ Anti-pattern 2: sort column before equality columns
CREATE INDEX idx_orders_created_status ON orders (created_at DESC, status);
-- Query: WHERE status = 'paid' ORDER BY created_at DESC
-- → The index isn't optimal because status isn't a prefix
-- ✓ Solution: (status, created_at DESC) — equality first

-- ✗ Anti-pattern 3: mixed ASC/DESC without database support
-- MySQL 5.7: ORDER BY price ASC, created_at DESC
CREATE INDEX idx_price_created ON products (price, created_at);
-- → created_at is stored ASC in the index, but the query asks for DESC
-- → Filesort appears even though the index exists
-- ✓ Solution: upgrade to MySQL 8.0+ and use (price ASC, created_at DESC)

-- ✗ Anti-pattern 4: functions in ORDER BY
ORDER BY DATE(created_at) DESC  -- functions kill index sorts
-- ✓ Solution: ORDER BY created_at DESC (use a range WHERE if a date filter is needed)

-- ✗ Anti-pattern 5: sorting without LIMIT on public endpoints
SELECT * FROM products WHERE status = 'active' ORDER BY created_at DESC;
-- → Filesorts the entire dataset to return it all
-- → Without LIMIT: the database sorts thousands/millions of rows
-- ✓ Solution: always add LIMIT, use pagination