Indexing

Chapter 32: Indexing Strategies

Advanced Database Indexing Techniques

---

32.1 Index Fundamentals

Indexes are data structures that improve query performance by providing fast lookup paths.

                    How Indexes Work
    ================================================================================

    Without Index (Table Scan):
    +----------------------------------------------------------+
    | Row 1 | Row 2 | Row 3 | Row 4 | Row 5 | ... | Row 1000000 |
    +----------------------------------------------------------+
                              Sequential Scan
                              O(n) complexity

    With Index (B-Tree):
                         +--------+
                         | Root   |
                         +--------+
                            /    \
                     +--------+  +--------+
                     | Node   |  | Node   |
                     +--------+  +--------+
                       /    \       /    \
                    [Data] [Data] [Data] [Data]

                    O(log n) complexity

    ================================================================================

---

32.2 Index Types in TypeORM

Single Column Index

// Entity-level index
@Entity()
@Index(['email'])
export class User {
  @PrimaryGeneratedColumn()
  id: number;

  @Column()
  email: string;
}

// Column-level index
@Entity()
export class User {
  @PrimaryGeneratedColumn()
  id: number;

  @Index()
  @Column()
  email: string;
}

// Multiple indexes on same entity
@Entity()
@Index(['email'])
@Index(['username'])
export class User {
  @Column()
  email: string;

  @Column()
  username: string;
}

Composite Index

// Index on multiple columns
@Entity()
@Index(['firstName', 'lastName'])
export class User {
  @Column()
  firstName: string;

  @Column()
  lastName: string;
}

// Query that uses this index
const users = await userRepository
  .createQueryBuilder('user')
  .where('user.firstName = :firstName', { firstName: 'John' })
  .andWhere('user.lastName = :lastName', { lastName: 'Doe' })
  .getMany();

// Also uses index (leftmost prefix)
const users = await userRepository
  .createQueryBuilder('user')
  .where('user.firstName = :firstName', { firstName: 'John' })
  .getMany();

// Does NOT use index (lastName is not leftmost)
const users = await userRepository
  .createQueryBuilder('user')
  .where('user.lastName = :lastName', { lastName: 'Doe' })
  .getMany();

Unique Index

// Unique index
@Entity()
@Index(['email'], { unique: true })
export class User {
  @Column()
  email: string;
}

// Column-level unique
@Entity()
export class User {
  @Column({ unique: true })
  email: string;
}

// Composite unique index
@Entity()
@Index(['userId', 'postId'], { unique: true })
export class UserPost {
  @Column()
  userId: number;

  @Column()
  postId: number;
}

---

32.3 Specialized Index Types

Full-Text Index

// PostgreSQL full-text search
@Entity()
export class Post {
  @PrimaryGeneratedColumn()
  id: number;

  @Column('text')
  title: string;

  @Column('text')
  content: string;
}

// Create full-text index via migration
export class AddFullTextIndex1700000001 implements MigrationInterface {
  public async up(queryRunner: QueryRunner): Promise<void> {
    // Create GIN index for full-text search
    await queryRunner.query(`
      CREATE INDEX IDX_POST_FULLTEXT
      ON posts
      USING GIN (to_tsvector('english', title || ' ' || content))
    `);
  }

  public async down(queryRunner: QueryRunner): Promise<void> {
    await queryRunner.query(`DROP INDEX IDX_POST_FULLTEXT`);
  }
}

// Full-text search query
const posts = await dataSource
  .createQueryBuilder(Post, 'post')
  .where(
    `to_tsvector('english', post.title || ' ' || post.content) @@ to_tsquery(:query)`,
    { query: 'typescript & tutorial' }
  )
  .getMany();

JSON Index

// Entity with JSON column
@Entity()
export class Product {
  @PrimaryGeneratedColumn()
  id: number;

  @Column('jsonb')
  attributes: Record<string, any>;
}

// GIN index for JSON (PostgreSQL)
export class AddJsonIndex1700000001 implements MigrationInterface {
  public async up(queryRunner: QueryRunner): Promise<void> {
    await queryRunner.query(`
      CREATE INDEX IDX_PRODUCT_ATTRIBUTES
      ON products USING GIN (attributes)
    `);
  }

  public async down(queryRunner: QueryRunner): Promise<void> {
    await queryRunner.query(`DROP INDEX IDX_PRODUCT_ATTRIBUTES`);
  }
}

// Query JSON field
const products = await productRepository
  .createQueryBuilder('product')
  .where(`product.attributes->>'color' = :color`, { color: 'red' })
  .getMany();

Partial Index

// Index only active users
@Entity()
@Index(
  ['email'],
  { where: 'isActive = true' }
)
export class User {
  @Column()
  email: string;

  @Column()
  isActive: boolean;
}

// Via migration
export class AddPartialIndex1700000001 implements MigrationInterface {
  public async up(queryRunner: QueryRunner): Promise<void> {
    await queryRunner.query(`
      CREATE INDEX IDX_USER_ACTIVE_EMAIL
      ON users (email)
      WHERE isActive = true
    `);
  }

  public async down(queryRunner: QueryRunner): Promise<void> {
    await queryRunner.query(`DROP INDEX IDX_USER_ACTIVE_EMAIL`);
  }
}

---

32.4 Index Design Strategies

Selectivity-Based Indexing

                    Index Selectivity
    ================================================================================

    Selectivity = Distinct Values / Total Rows

    High Selectivity (Good for indexing):
    - Email (unique): 1.0
    - Username (unique): 1.0
    - Phone number: 0.99

    Low Selectivity (Poor for indexing):
    - Gender: 0.0001 (2 values)
    - Boolean flags: 0.0001 (2 values)
    - Status with few values: 0.001

    Rule of Thumb:
    - Index columns with selectivity > 0.1
    - Combine low-selectivity columns with high-selectivity ones

    ================================================================================

Covering Index

// Covering index includes all queried columns
@Entity()
@Index(['userId', 'status', 'createdAt'])
export class Order {
  @Column()
  userId: number;

  @Column()
  status: string;

  @CreateDateColumn()
  createdAt: Date;
}

// Query that can be satisfied entirely by index
const orders = await orderRepository
  .createQueryBuilder('order')
  .select(['order.userId', 'order.status', 'order.createdAt'])
  .where('order.userId = :userId', { userId: 1 })
  .getMany();

// PostgreSQL: INCLUDE clause for covering index
export class AddCoveringIndex1700000001 implements MigrationInterface {
  public async up(queryRunner: QueryRunner): Promise<void> {
    await queryRunner.query(`
      CREATE INDEX IDX_ORDER_COVERING
      ON orders (userId, status)
      INCLUDE (createdAt, total)
    `);
  }

  public async down(queryRunner: QueryRunner): Promise<void> {
    await queryRunner.query(`DROP INDEX IDX_ORDER_COVERING`);
  }
}

Index Order Strategy

                    Composite Index Column Order
    ================================================================================

    Rules for Column Order:
    1. Equality columns first
    2. Range columns last
    3. Sort columns after equality
    4. High selectivity first (when no equality)

    Example Query:
    SELECT * FROM orders
    WHERE userId = 1          -- Equality
    AND status = 'pending'    -- Equality
    AND createdAt > '2024-01-01'  -- Range
    ORDER BY total DESC       -- Sort

    Optimal Index:
    @Index(['userId', 'status', 'createdAt', 'total'])

    Why this order:
    - userId: Equality, high selectivity
    - status: Equality, lower selectivity
    - createdAt: Range (must come after equality)
    - total: Sort (can use index for sorting)

    ================================================================================

---

32.5 Index Maintenance

Analyze Index Usage

-- PostgreSQL: Find unused indexes
SELECT
    schemaname,
    relname as table_name,
    indexrelname as index_name,
    idx_scan as index_scans,
    idx_tup_read as tuples_read,
    idx_tup_fetch as tuples_fetched
FROM pg_stat_user_indexes
ORDER BY idx_scan ASC;

-- PostgreSQL: Find index size
SELECT
    relname as table_name,
    indexrelname as index_name,
    pg_size_pretty(pg_relation_size(indexrelid)) as index_size
FROM pg_stat_user_indexes
ORDER BY pg_relation_size(indexrelid) DESC;

-- PostgreSQL: Find duplicate indexes
SELECT
    pg_size_pretty(sum(pg_relation_size(idx))::bigint) as size,
    (array_agg(idx))[1] as idx1,
    (array_agg(idx))[2] as idx2,
    (array_agg(idx))[3] as idx3,
    (array_agg(idx))[4] as idx4
FROM (
    SELECT indexrelid::regclass as idx, indrelid::regclass as table,
           array_to_string(indkey, ' ') as cols,
           indpred is not null as partial
    FROM pg_index
) sub
GROUP BY table, cols, partial
HAVING count(*) > 1;

Rebuild Indexes

// Reindex via migration
export class ReindexTables1700000001 implements MigrationInterface {
  public async up(queryRunner: QueryRunner): Promise<void> {
    // Reindex specific table
    await queryRunner.query(`REINDEX TABLE users`);

    // Reindex specific index
    await queryRunner.query(`REINDEX INDEX IDX_USER_EMAIL`);

    // Reindex entire database (run as superuser)
    // await queryRunner.query(`REINDEX DATABASE mydb`);
  }

  public async down(queryRunner: QueryRunner): Promise<void> {
    // No down needed for REINDEX
  }
}

// Concurrent reindex (doesn't lock table)
export class ConcurrentReindex1700000001 implements MigrationInterface {
  public async up(queryRunner: QueryRunner): Promise<void> {
    await queryRunner.query(`REINDEX TABLE CONCURRENTLY users`);
  }

  public async down(queryRunner: QueryRunner): Promise<void> {}
}

---

32.6 Index Anti-Patterns

Common Mistakes

                    Index Anti-Patterns
    ================================================================================

    1. Over-Indexing
       - Too many indexes slow down writes
       - Each index adds storage overhead
       - Rule: One index per query pattern, not per column

    2. Redundant Indexes
       @Index(['userId'])           -- Redundant
       @Index(['userId', 'status']) -- Covers both cases

    3. Low-Selectivity Indexes
       @Index(['isActive'])  -- Only 2 values, poor selectivity

    4. Wrong Column Order
       @Index(['status', 'userId'])  -- Wrong order
       @Index(['userId', 'status'])  -- Correct order

    5. Not Indexing Foreign Keys
       @ManyToOne(() => User)
       @JoinColumn({ name: 'authorId' })
       author: User;  // Should have index on authorId

    6. Function on Indexed Column
       WHERE LOWER(email) = 'test@example.com'  -- Won't use index
       WHERE email = 'TEST@EXAMPLE.COM'         -- Will use index

    ================================================================================

Fixing Anti-Patterns

// Bad: Multiple single-column indexes
@Entity()
@Index(['userId'])
@Index(['status'])
@Index(['createdAt'])
export class Order {
  @Column()
  userId: number;

  @Column()
  status: string;

  @CreateDateColumn()
  createdAt: Date;
}

// Good: Composite index based on query patterns
@Entity()
@Index(['userId', 'status', 'createdAt'])
export class Order {
  @Column()
  userId: number;

  @Column()
  status: string;

  @CreateDateColumn()
  createdAt: Date;
}

// Bad: Function on indexed column
const users = await userRepository
  .createQueryBuilder('user')
  .where('LOWER(user.email) = :email', { email: 'test@example.com' })
  .getMany();

// Good: Use citext type or normalize before query
const users = await userRepository
  .createQueryBuilder('user')
  .where('user.email ILIKE :email', { email: 'test@example.com' })
  .getMany();

---

32.7 Index Monitoring Service

src/database/index-monitor.service.ts

import { Injectable, InjectDataSource } from '@nestjs/common';
import { DataSource } from 'typeorm';

interface IndexStats {
  tableName: string;
  indexName: string;
  scans: number;
  size: string;
  isUnused: boolean;
}

@Injectable()
export class IndexMonitorService {
  constructor(
    @InjectDataSource()
    private dataSource: DataSource,
  ) {}

  async getIndexStats(): Promise<IndexStats[]> {
    const stats = await this.dataSource.query(`
      SELECT
        relname as table_name,
        indexrelname as index_name,
        idx_scan as scans,
        pg_size_pretty(pg_relation_size(indexrelid)) as size,
        idx_scan = 0 as is_unused
      FROM pg_stat_user_indexes
      ORDER BY idx_scan ASC
    `);

    return stats;
  }

  async getUnusedIndexes(): Promise<IndexStats[]> {
    const stats = await this.getIndexStats();
    return stats.filter(s => s.isUnused);
  }

  async getIndexSize(): Promise<{ total: string; byTable: any[] }> {
    const result = await this.dataSource.query(`
      SELECT
        relname as table_name,
        pg_size_pretty(SUM(pg_relation_size(indexrelid))) as total_index_size
      FROM pg_stat_user_indexes
      GROUP BY relname
      ORDER BY SUM(pg_relation_size(indexrelid)) DESC
    `);

    const total = await this.dataSource.query(`
      SELECT pg_size_pretty(SUM(pg_relation_size(indexrelid))) as total
      FROM pg_stat_user_indexes
    `);

    return {
      total: total[0].total,
      byTable: result,
    };
  }

  async getDuplicateIndexes(): Promise<any[]> {
    return this.dataSource.query(`
      SELECT
        (array_agg(idx))[1] as index1,
        (array_agg(idx))[2] as index2,
        table
      FROM (
        SELECT
          indexrelid::regclass as idx,
          indrelid::regclass as table,
          array_to_string(indkey, ' ') as cols
        FROM pg_index
      ) sub
      GROUP BY table, cols
      HAVING count(*) > 1
    `);
  }
}

---

32.8 Complete Indexing Example

src/products/product.entity.ts

import {
  Entity,
  PrimaryGeneratedColumn,
  Column,
  Index,
  CreateDateColumn,
  UpdateDateColumn,
  ManyToOne,
  JoinColumn,
} from 'typeorm';
import { Category } from '../categories/category.entity';

@Entity()
@Index(['sku'], { unique: true })  // Unique SKU
@Index(['categoryId', 'isActive', 'createdAt'])  // Composite for listing
@Index(['name'])  // Search by name
@Index(['price', 'isActive'])  // Price filtering
export class Product {
  @PrimaryGeneratedColumn()
  id: number;

  @Column({ unique: true })
  sku: string;

  @Column()
  name: string;

  @Column('text')
  description: string;

  @Column('decimal', { precision: 10, scale: 2 })
  price: number;

  @Column({ default: true })
  isActive: boolean;

  @Column()
  categoryId: number;

  @Column('jsonb', { nullable: true })
  attributes: Record<string, any>;

  @Column({ default: 0 })
  viewCount: number;

  @CreateDateColumn()
  createdAt: Date;

  @UpdateDateColumn()
  updatedAt: Date;

  @ManyToOne(() => Category)
  @JoinColumn({ name: 'categoryId' })
  category: Category;
}

// Migration for additional indexes
export class AddProductIndexes1700000001 implements MigrationInterface {
  public async up(queryRunner: QueryRunner): Promise<void> {
    // Full-text search index
    await queryRunner.query(`
      CREATE INDEX IDX_PRODUCT_FULLTEXT
      ON products
      USING GIN (to_tsvector('english', name || ' ' || description))
    `);

    // JSON attributes index
    await queryRunner.query(`
      CREATE INDEX IDX_PRODUCT_ATTRIBUTES
      ON products USING GIN (attributes)
    `);

    // Partial index for active products
    await queryRunner.query(`
      CREATE INDEX IDX_PRODUCT_ACTIVE
      ON products (price, createdAt)
      WHERE isActive = true
    `);
  }

  public async down(queryRunner: QueryRunner): Promise<void> {
    await queryRunner.query(`DROP INDEX IDX_PRODUCT_ACTIVE`);
    await queryRunner.query(`DROP INDEX IDX_PRODUCT_ATTRIBUTES`);
    await queryRunner.query(`DROP INDEX IDX_PRODUCT_FULLTEXT`);
  }
}

---

32.9 Summary

                    Indexing Quick Reference
    +------------------------------------------------------------------+
    |                                                                   |
    |    Index Type         | Use Case                                  |
    |    -------------------|------------------------------------------|
    |    B-Tree            | Default, equality and range queries       |
    |    Unique            | Enforce uniqueness                        |
    |    Composite         | Multi-column queries                      |
    |    Partial           | Subset of rows                            |
    |    Full-Text         | Text search                               |
    |    GIN               | JSON, arrays, full-text                   |
    |                                                                   |
    |    Best Practices     | Description                              |
    |    -------------------|------------------------------------------|
    |    High selectivity  | Index columns with many unique values     |
    |    Query patterns    | Index based on actual queries             |
    |    Foreign keys      | Always index FK columns                   |
    |    Monitor usage     | Remove unused indexes                     |
    |    Test performance  | Verify index improves queries             |
    |                                                                   |
    +------------------------------------------------------------------+

---

Next Chapter

Chapter 33: Caching Strategies

---

Last Updated: February 2026