DBMS

Storage And Indexing

Hash and Specialised Indexes

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

JrCodex·8 min read

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