Database Indexing: Making Queries Fast

Database Indexing: The Key to Query Performance

A table with a million rows is slow to search. Scanning every row to find one record is torture. Indexes solve this. An index is a data structure that enables fast lookups, similar to a book's index: you don't read every page to find a topic, you check the index, then jump directly to relevant pages. Without an index, SELECT * FROM users WHERE email = 'alice@example.com'; scans all million rows. With an index on email, it's found in milliseconds. Let's understand how indexes work. B-trees are the most common index structure. They're balanced trees maintaining sorted order. A B-tree with three levels can index 100 million+ rows. Each step of traversal eliminates many rows. Searching is logarithmic: O(log n) operations instead of O(n) linear scans. Creating an index: CREATE INDEX idx_users_email ON users(email);. This creates a B-tree index on the email column. Queries using email are now fast. Primary key indexes are created automatically. Every table should have a primary key: CREATE TABLE users (id INT PRIMARY KEY, name VARCHAR(100));. id is indexed for fast lookups. Multiple-column indexes (composite indexes) are powerful: CREATE INDEX idx_orders_user_date ON orders(user_id, created_at);. This indexes both columns. Queries filtering by user_id or (user_id AND created_at) benefit. Queries filtering by just created_at don't use this index (leftmost prefix must match). Index selectivity matters. Columns with many distinct values (email, username) are good index candidates. Columns with few values (gender with M/F/Other) are poor candidates. Indexes cost space and write time. When you insert or update rows, indexes must be updated too. Too many indexes slow down writes. Balance is key. EXPLAIN shows how queries execute: EXPLAIN SELECT * FROM users WHERE email = 'alice@example.com';. Output shows whether an index is used. Index scan means the full index was searched. Seq scan means a full table scan (slow). Covering indexes include all columns needed for the query: CREATE INDEX idx_users_email_name ON users(email, name);. SELECT name FROM users WHERE email = 'abc'; uses the index without touching the table. Index-only scans are incredibly fast. Partial indexes index only rows matching a condition: CREATE INDEX idx_active_users ON users(email) WHERE status = 'active';. This is smaller and faster than indexing all users. Useful for filtering active records while ignoring inactive ones. Database optimization follows a pattern. First, identify slow queries using slow query logs or performance monitoring. EXPLAIN reveals missing indexes. Add indexes strategically. Profile again. Some queries remain slow despite indexes. Query optimization matters too. SELECT * FROM orders WHERE YEAR(created_at) = 2024; uses a function, preventing index use. Rewrite as: SELECT * FROM orders WHERE created_at >= '2024-01-01' AND created_at < '2025-01-01';. Now the index is used. Avoiding full table scans is the goal. Sometimes they're unavoidable. But minimizing them improves performance dramatically. Understanding indexing is essential for database performance. Learn it early, and you'll design fast queries. Discover indexing late, and you'll spend nights optimizing sluggish systems. Master this skill.

Under the Hood: Database Indexing: Making Queries Fast

Here is what separates someone who merely USES technology from someone who UNDERSTANDS it: knowing what happens behind the screen. When you tap "Send" on a WhatsApp message, do you know what journey that message takes? When you search something on Google, do you know how it finds the answer among billions of web pages in less than a second? When UPI processes a payment, what makes sure the money goes to the right person?

Understanding Database Indexing: Making Queries Fast gives you the ability to answer these questions. More importantly, it gives you the foundation to BUILD things, not just use things other people built. India's tech industry employs over 5 million people, and companies like Infosys, TCS, Wipro, and thousands of startups are all built on the concepts we are about to explore.

This is not just theory for exams. This is how the real world works. Let us get into it.

Database Design: Normalisation and Relationships

Good database design prevents data duplication and inconsistency. This is called normalisation. Consider an e-commerce database:

-- BAD design (denormalised — data repeated everywhere)
-- If customer moves city, you must update EVERY order row!

-- GOOD design (normalised — each fact stored once)
CREATE TABLE customers (
    id   SERIAL PRIMARY KEY,
    name TEXT NOT NULL,
    email TEXT UNIQUE,
    city  TEXT
);

CREATE TABLE products (
    id    SERIAL PRIMARY KEY,
    name  TEXT NOT NULL,
    price DECIMAL(10,2),
    category TEXT
);

CREATE TABLE orders (
    id          SERIAL PRIMARY KEY,
    customer_id INTEGER REFERENCES customers(id),
    product_id  INTEGER REFERENCES products(id),
    quantity    INTEGER,
    order_date  TIMESTAMP DEFAULT NOW()
);

-- JOIN to reconstruct the full picture
SELECT c.name, p.name AS product, o.quantity,
       (p.price * o.quantity) AS total
FROM orders o
JOIN customers c ON o.customer_id = c.id
JOIN products p ON o.product_id = p.id
WHERE o.order_date > '2025-01-01';

The REFERENCES keyword creates a foreign key — a link between tables. This is a relational database: data is stored in related tables, and JOINs combine them. The tradeoff: normalised databases are consistent and space-efficient, but JOINs can be slow on very large datasets. This is why companies like Flipkart use a mix of SQL databases (for transactions) and NoSQL databases like MongoDB or Cassandra (for product catalogs and recommendations).

Real-World System Design: Swiggy's Architecture

When you order food on Swiggy, here is what happens behind the scenes in about 2 seconds: your location is geocoded (algorithms), nearby restaurants are queried from a spatial index (data structures), menu prices are pulled from a database (SQL), delivery time is estimated using ML models trained on historical data (AI), the order is placed in a distributed message queue (Kafka), a delivery partner is assigned using a matching algorithm (optimization), and real-time tracking begins using WebSocket connections (networking). EVERY concept in your CS curriculum is being used simultaneously to deliver your biryani.

Algorithm Complexity and Big-O Notation

Big-O notation describes how an algorithm's performance scales with input size. This is THE most important concept for coding interviews:

  BIG-O COMPARISON (n = 1,000,000 elements):

  O(1)        Constant     1 operation          Hash table lookup
  O(log n)    Logarithmic  20 operations        Binary search
  O(n)        Linear       1,000,000 ops        Linear search
  O(n log n)  Linearithmic 20,000,000 ops       Merge sort, Quick sort
  O(n²)       Quadratic    1,000,000,000,000    Bubble sort, Selection sort
  O(2ⁿ)       Exponential  ∞ (universe dies)    Brute force subset

  Time at 1 billion ops/sec:
  O(n log n): 0.02 seconds    ← Perfectly usable
  O(n²):      11.5 DAYS       ← Completely unusable!
  O(2ⁿ):      Longer than the age of the universe

  # Python example: Merge Sort (O(n log n))
  def merge_sort(arr):
      if len(arr) <= 1:
          return arr
      mid = len(arr) // 2
      left = merge_sort(arr[:mid])      # Sort left half
      right = merge_sort(arr[mid:])     # Sort right half
      return merge(left, right)         # Merge sorted halves

  def merge(left, right):
      result = []
      i = j = 0
      while i < len(left) and j < len(right):
          if left[i] <= right[j]:
              result.append(left[i]); i += 1
          else:
              result.append(right[j]); j += 1
      result.extend(left[i:])
      result.extend(right[j:])
      return result

This matters in the real world. India's Aadhaar system must search through 1.4 billion biometric records for every authentication request. At O(n), that would take seconds per request. With the right data structures (hash tables, B-trees), it takes milliseconds. The algorithm choice is the difference between a working system and an unusable one.

Production Engineering: Database Indexing: Making Queries Fast at Scale

Understanding database indexing: making queries fast at an academic level is necessary but not sufficient. Let us examine how these concepts manifest in production environments where failure has real consequences.

Consider India's UPI system processing 10+ billion transactions monthly. The architecture must guarantee: atomicity (a transfer either completes fully or not at all — no half-transfers), consistency (balances always add up correctly across all banks), isolation (concurrent transactions on the same account do not interfere), and durability (once confirmed, a transaction survives any failure). These are the ACID properties, and violating any one of them in a payment system would cause financial chaos for millions of people.

At scale, you also face the thundering herd problem: what happens when a million users check their exam results at the same time? (CBSE result day, anyone?) Without rate limiting, connection pooling, caching, and graceful degradation, the system crashes. Good engineering means designing for the worst case while optimising for the common case. Companies like NPCI (the organisation behind UPI) invest heavily in load testing — simulating peak traffic to identify bottlenecks before they affect real users.

Monitoring and observability become critical at scale. You need metrics (how many requests per second? what is the 99th percentile latency?), logs (what happened when something went wrong?), and traces (how did a single request flow through 15 different microservices?). Tools like Prometheus, Grafana, ELK Stack, and Jaeger are standard in Indian tech companies. When Hotstar streams IPL to 50 million concurrent users, their engineering team watches these dashboards in real-time, ready to intervene if any metric goes anomalous.

The career implications are clear: engineers who understand both the theory (from chapters like this one) AND the practice (from building real systems) command the highest salaries and most interesting roles. India's top engineering talent earns ₹50-100+ LPA at companies like Google, Microsoft, and Goldman Sachs, or builds their own startups. The foundation starts here.

Key Vocabulary

Here are important terms from this chapter that you should know:

💡 Interview-Style Problem

Here is a problem that frequently appears in technical interviews at companies like Google, Amazon, and Flipkart: "Design a URL shortener like bit.ly. How would you generate unique short codes? How would you handle millions of redirects per second? What database would you use and why? How would you track click analytics?"

Think about: hash functions for generating short codes, read-heavy workload (99% redirects, 1% creates) suggesting caching, database choice (Redis for cache, PostgreSQL for persistence), and horizontal scaling with consistent hashing. Try sketching the system architecture on paper before looking up solutions. The ability to think through system design problems is the single most valuable skill for senior engineering roles.

Where This Takes You

The knowledge you have gained about database indexing: making queries fast is directly applicable to: competitive programming (Codeforces, CodeChef — India has the 2nd largest competitive programming community globally), open-source contribution (India is the 2nd largest contributor on GitHub), placement preparation (these concepts form 60% of technical interview questions), and building real products (every startup needs engineers who understand these fundamentals).

India's tech ecosystem offers incredible opportunities. Freshers at top companies earn ₹15-50 LPA; experienced engineers at FAANG companies in India earn ₹50-1 Cr+. But more importantly, the problems being solved in India — digital payments for 1.4 billion people, healthcare AI for rural areas, agricultural tech for 150 million farmers — are some of the most impactful engineering challenges in the world. The fundamentals you are building will be the tools you use to tackle them.

Crafted for Class 7–9 • Databases • Aligned with NEP 2020 & CBSE Curriculum