Hash and Specialised Indexes

Jr Codex DBMS Notes

Level: Intermediate Prerequisites: Chapter 2: B+ Tree Indexes; DSA Notes, Module 8 Time to complete: ~20 minutes

Table of Contents

1. Hash Indexes
2. Composite Indexes
3. Covering Indexes
4. Partial and Expression Indexes
5. Full-Text and Specialised Types
6. Choosing an Index Type
7. Summary & Next Steps

1. Hash Indexes

The DSA Notes built hash maps for O(1) lookup. On disk they exist, and are used far less than you would expect.

CREATE INDEX idx_students_email_hash ON students USING HASH (email);   -- PostgreSQL

Hash vs B+ Tree
─────────────────────────────────────────
                       HASH      B+ TREE
  ─────────────────────────────────────────
  Equality (=)         O(1)      O(log n)
  Range (<, BETWEEN)   ✗ NO      ✓ yes
  ORDER BY             ✗ NO      ✓ free
  MIN / MAX            ✗ NO      ✓ O(log n)
  Prefix LIKE 'a%'     ✗ NO      ✓ yes
  Size                 smaller   larger
─────────────────────────────────────────

Why B+ Trees Win Anyway
─────────────────────────────────────────
  A hash index is faster at exactly ONE thing, by a
  small constant factor — O(1) versus a 3-level
  descent that is usually cached anyway.

  It cannot do ANY of the other five.

  So a B+ tree serves every query pattern including
  equality, at negligible extra cost. Adding a hash
  index means maintaining a second index that
  handles a strict subset of queries.

  Use a hash index only when: the column is large
  (long URLs), you ONLY ever do equality, and you
  have measured that it matters.
─────────────────────────────────────────

2. Composite Indexes

An index on several columns, in a specified order. The order is everything.

CREATE INDEX idx_students_city_marks ON students (city, marks);

The Sort Order It Creates
─────────────────────────────────────────
  Entries are sorted by city FIRST, then by marks
  within each city:

    ('Delhi', 74) ('Delhi', 82)
    ('Mumbai', 65)
    ('Pune', 88) ('Pune', 91)

  It behaves exactly like sorting a spreadsheet by
  column A, then column B.
─────────────────────────────────────────

THE LEFTMOST PREFIX RULE
─────────────────────────────────────────
  An index on (a, b, c) can serve queries filtering
  on:

    ✓ a
    ✓ a, b
    ✓ a, b, c
    ✗ b            — cannot skip a
    ✗ c            — cannot skip a and b
    ✗ b, c         — cannot skip a

  WHY: entries are sorted by `a` first. Without a
  value for `a`, the b-values are scattered across
  the whole index — there is nothing to seek to.

  Same reason a phone book sorted by (surname,
  forename) cannot find everyone called "James".
─────────────────────────────────────────

-- Which of these use idx_students_city_marks (city, marks)?
SELECT * FROM students WHERE city = 'Pune';                    -- ✓ prefix
SELECT * FROM students WHERE city = 'Pune' AND marks > 80;     -- ✓ full use
SELECT * FROM students WHERE marks > 80;                       -- ✗ skips `city`
SELECT * FROM students WHERE city = 'Pune' ORDER BY marks;     -- ✓ AND no sort needed

Ordering the Columns
─────────────────────────────────────────
  1. EQUALITY columns first, RANGE columns last.
     An index stops being useful for further
     columns after the first range condition.

       WHERE city = ? AND marks > ?
       ──► index (city, marks). Not (marks, city).

  2. Most SELECTIVE first among equality columns —
     it narrows the search fastest.

  3. Match your ORDER BY, to get sorting free.
─────────────────────────────────────────

3. Covering Indexes

An index containing every column a query needs, so the table is never touched.

CREATE INDEX idx_cover ON students (city, marks, name);
 
SELECT name, marks FROM students WHERE city = 'Pune';
-- All three columns are IN the index ──► INDEX-ONLY SCAN. The heap is never read.

Why This Is Such a Large Win
─────────────────────────────────────────
  A normal index scan is TWO steps:
    1. find matching entries in the index
    2. for EACH, fetch the row from the heap
       ── a RANDOM page read per row

  Step 2 usually dominates. 1,000 matching rows can
  mean 1,000 random reads.

  A covering index eliminates step 2 entirely. This
  is frequently a 10x improvement, and the single
  most effective index tuning technique.
─────────────────────────────────────────

-- INCLUDE: carry extra columns in the LEAVES only, not in the sort key.
CREATE INDEX idx_cover2 ON students (city, marks) INCLUDE (name);
-- Smaller internal nodes (higher fanout) while still covering the query.

The Trade
─────────────────────────────────────────
  Covering indexes are WIDER, so:
    - the index is bigger, and evicts more from the
      buffer pool (Chapter 5)
    - every UPDATE to any included column must
      update the index

  Cover the columns your hot query needs. Do not
  cover everything — at that point you have
  duplicated the table.
─────────────────────────────────────────

4. Partial and Expression Indexes

-- PARTIAL: index only the rows you actually query.
CREATE INDEX idx_active_orders ON orders (created_at)
WHERE status = 'pending';

Why Partial Indexes Are Underused
─────────────────────────────────────────
  A table holds 10,000,000 orders; 5,000 are
  pending.

  Full index    ──► 10,000,000 entries
  Partial index ──►      5,000 entries

  Two thousand times smaller, so it stays entirely
  in memory, and every write to a non-pending row
  does not touch it at all.

  Any column with a skewed, frequently-filtered
  value — status, is_deleted, is_active — is a
  candidate.
─────────────────────────────────────────

-- EXPRESSION: index the result of a function.
CREATE INDEX idx_lower_email ON students (LOWER(email));
 
SELECT * FROM students WHERE LOWER(email) = 'asha@example.com';    -- ✓ uses it

The Rule This Illustrates
─────────────────────────────────────────
  A plain index on `email` CANNOT serve
  WHERE LOWER(email) = ?

  The index stores the original values; the
  database has no way to know which of them lower-
  case to the target without checking every one.

  Wrapping an indexed column in ANY function
  disables its index. Chapter 4 calls this
  "non-sargable" and lists the common cases.
─────────────────────────────────────────

5. Full-Text and Specialised Types

Beyond B+ Trees
─────────────────────────────────────────
  FULL-TEXT (GIN)
    Inverted index: word ──► list of rows.
    Real text search with stemming and ranking.
    Solves the LIKE '%word%' problem from Module 3,
    Chapter 2.

  GIN
    For "contains" queries on composite values:
    arrays, JSONB, tsvector.

  GiST
    Extensible; geometric and range types.
    Nearest-neighbour and overlap queries.

  BRIN
    Block Range INdex. Stores min/max per block
    range. TINY, and only works when the data is
    physically ordered by that column — perfect for
    append-only time-series.

  SPATIAL (R-tree)
    Two-dimensional "within this bounding box".
─────────────────────────────────────────

-- Full-text search, properly.
ALTER TABLE articles ADD COLUMN search_vector tsvector
    GENERATED ALWAYS AS (to_tsvector('english', title || ' ' || body)) STORED;
 
CREATE INDEX idx_articles_fts ON articles USING GIN (search_vector);
 
SELECT title, ts_rank(search_vector, query) AS rank
FROM articles, to_tsquery('english', 'database & index') AS query
WHERE search_vector @@ query
ORDER BY rank DESC;

BRIN, Because the Numbers Are Striking
─────────────────────────────────────────
  A 100GB append-only events table, indexed on
  timestamp:

    B+ tree index   ~20 GB
    BRIN index      ~few MB

  BRIN records only the min and max timestamp for
  each range of blocks. To find a time window it
  skips every block range that cannot contain it.

  Requires physical ordering to match the column —
  which append-only time-series data has for free.
─────────────────────────────────────────

6. Choosing an Index Type

Decision Guide
─────────────────────────────────────────
  Default, anything ordered, ranges, sorting
      ──► B+ TREE. Start here, essentially always.

  Several columns filtered together
      ──► COMPOSITE, equality columns first

  A hot query reading few columns
      ──► COVERING, or B+ tree with INCLUDE

  Filtering on a skewed flag
      ──► PARTIAL. Often a dramatic win.

  Filtering on a function's result
      ──► EXPRESSION index on that expression

  Searching words inside text
      ──► FULL-TEXT / GIN. Never LIKE '%x%'.

  Arrays or JSONB containment
      ──► GIN

  Huge append-only table ordered by time
      ──► BRIN

  Equality only, on a large column, measured
      ──► HASH
─────────────────────────────────────────

7. Summary & Next Steps

Key Takeaways

• Hash indexes beat B+ trees only at equality and by a small constant, while losing ranges, ordering, MIN/MAX and prefix matching — which is why B+ trees are the default.
• A composite index is sorted left to right, so it can only serve queries that use a leftmost prefix; put equality columns before range columns.
• A covering index removes the random heap fetch per matching row, and is usually the single largest index-tuning win available.
• Partial indexes on skewed flags can be thousands of times smaller than a full index, and wrapping a column in a function disables its index entirely.

Concept Check

1. An index exists on (city, marks). Explain why WHERE marks > 80 cannot use it.
2. What two steps does a normal index scan perform, and which one does a covering index eliminate?
3. Why can a plain index on email not serve WHERE LOWER(email) = ?, and what fixes it?

Next Chapter

→ Chapter 4: Choosing Indexes

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index