Post-Mortem: How a Single MySQL Index Broke GitHub

Database indexing is one of the most critical levers for optimizing query execution in relational databases. However, operating at hyper-scale means that even small, seemingly benign schema changes—such as altering the sort order of a column in a composite index—can trigger severe outages.

In one incident, GitHub engineers executed a database migration intended to flip the sort direction of an index. Instead of speeding up queries, the migration resulted in over an hour of downtime for github.com. This incident offers a masterclass in MySQL indexing internals, the hidden costs of ORMs (Object-Relational Mapping), query optimizer behavior, and how database degradation cascades across microservices.

---

1. Anatomy of the Outage: The Official Incident Report

Despite GitHub’s brief, two-paragraph incident summary, the core technical trigger was clearly identified:

“This incident was caused by a database migration to flip the order of an index. Reversing the index caused a full table scan since there was a missed dependency on the changed index by a generated Active Record query.”

To understand why reversing an index caused a global service disruption, we must first break down how MySQL handles indexes, sorting, and multi-column scan directions.

---

2. MySQL Index Ordering Mechanics

Ascending vs. Descending Indexes

In a standard B-Tree index, index keys are stored sequentially in sorted order on disk. By default, MySQL constructs indexes in ascending order (ASC).

If you have a single-column index on user_id:

CREATE INDEX idx_user_id ON users(user_id);

MySQL stores the leaf nodes sorted as 1, 2, 3, ... N. If a query requests records ordered in reverse (ORDER BY user_id DESC), MySQL can traverse the B-tree in reverse order. For a single column, scanning forward or backward is trivial.

The Multi-Column (Composite) Ordering Problem

The complexity compounds when dealing with composite indexes involving two or more columns where sort directions differ. Consider a typical social coding query: fetching commits for a repository ordered by date descending, but for commits on the same day, ordered by author ascending.

SELECT * FROM commits 
WHERE repo_id = 42 
ORDER BY commit_date DESC, author_id ASC;

If the index is defined with default ascending behavior:

CREATE INDEX idx_date_author ON commits(commit_date ASC, author_id ASC);

• MySQL can read the index forward (ASC, ASC).
• MySQL can read the index backward (DESC, DESC).
• MySQL cannot read this index directly to satisfy (DESC, ASC) without sorting.

Index on Disk: (Date ASC, Author ASC)
(2023-01-01, Alice) -> (2023-01-01, Bob) -> (2023-01-02, Alice) -> (2023-01-02, Charlie)

Desired Order: (Date DESC, Author ASC)
(2023-01-02, Alice) -> (2023-01-02, Charlie) -> (2023-01-01, Alice) -> (2023-01-01, Bob)

Because the disk order does not match the desired hybrid sort pattern, the MySQL optimizer is forced to resort to a filesort.

What is a filesort?

Despite its name, a filesort does not necessarily mean sorting on disk, but rather that MySQL must evaluate rows and sort them in an in-memory buffer (sort_buffer_size). However, if the result set exceeds the buffer limit, it dumps temporary chunks to disk and performs an external merge sort.

At scale, frequent filesort executions cause:

• Severe memory and CPU pressure.
• Extensive disk I/O thrashing.
• Thread contention inside the storage engine (InnoDB).

The Introduction of Descending Indexes in MySQL 8.0

Prior to MySQL 8.0, specifying DESC in index definitions was parsed by the syntax parser but ignored by the storage engine—all indexes were built ASC. Starting with MySQL 8.0, genuine descending indexes became supported:

CREATE INDEX idx_date_author_flipped 
ON commits(commit_date DESC, author_id ASC);

GitHub needed to flip an index’s column order to eliminate a costly filesort on a high-throughput endpoint.

---

3. How Flipping an Index Triggered a Full Table Scan

When GitHub deployed the migration to reverse the index order, an unexpected regression occurred: queries that previously used the old index suddenly triggered full table scans.

There are two primary reasons why this happens in real-world systems:

Scenario A: Unidentified Query Dependencies (The ORM Blind Spot)

GitHub runs a large monolithic Ruby on Rails application using Active Record as its Object-Relational Mapper (ORM). ORMs generate dynamic SQL queries under the hood.

1. While Team A wanted to optimize Query X (requiring DESC, ASC), an unmonitored high-traffic Query Y (generated elsewhere in the Rails monolith) relied directly on the old index (ASC, ASC).
2. When the index was migrated or flipped, Query Y could no longer use index-ordered scans.
3. Because Query Y occurred with far greater frequency than anticipated, dropping or altering the old index caused Query Y to execute full table scans across massive dataset partitions.

flowchart TD
    Migration[Flip Index to DESC, ASC] --> NewIndex[New Index Built]
    OldIndex[Old Index ASC, ASC Dropped/Replaced] --> QueryY[Existing Active Record Query Y]
    QueryY -->|Cannot use DESC, ASC index| FTS[Full Table Scan]
    FTS --> DiskIO[Massive Disk I/O & Latency Spike]

Scenario B: Optimizer Heuristic Traps and Missing Statistics

Relational database optimizers choose an execution plan based on cost estimates derived from table statistics (ANALYZE TABLE). When a new index is introduced:

• The optimizer may temporarily lack accurate histogram or cardinality statistics.
• If the cost estimation deems the new index less favorable than scanning or if it cannot resolve dynamic parameters, it falls back to a primary key scan or full table scan.
• Without explicit index pinning, the application is at the mercy of the optimizer’s heuristics.

---

4. The Cascading Failure Mechanism

A full table scan on a large production database rarely remains an isolated issue. It rapidly degrades into a distributed cascading failure across dependent microservices:

sequenceDiagram
    autonumber
    participant User as End User / Client
    participant Edge as Edge / API Gateway
    participant App as Application Service (Rails)
    participant DB as MySQL Database

    User->>Edge: HTTP Request
    Edge->>App: Forward Request
    App->>DB: Execute Active Record Query
    Note over DB: Index changed: Full Table Scan triggered!
    Note over DB: Disk I/O hits 100%, CPU spikes, locks held
    DB-->>App: Query delayed (exceeds timeout)
    Note over App: App workers block waiting on DB connections
    App--xEdge: Worker pool exhausted / Gateway Timeout (504)
    Edge--xUser: GitHub 500 / 504 Outage Page

Steps in the Collapse Chain

1. Database Saturation: The full table scan saturates disk I/O channels. InnoDB buffer pools get churned as cold data is read from disk into memory, evicting cached hot pages.
2. Connection Starvation: Because queries take seconds instead of milliseconds, connection pools between the application tier (Puma/Unicorn worker processes) and MySQL fill up completely.
3. Application Thread Exhaustion: Rails worker processes block waiting for database responses. Incoming web requests queue up at the reverse proxy (e.g., NGINX / Envoy).
4. Distributed Timeouts: Synchronously coupled upstream services (e.g., git authentication, webhooks, pull requests, issue trackers) encounter timeouts and drop traffic.
5. Complete Outage: The frontend API gateways throw 504 Gateway Timeouts or fallback error screens to end users.

---

5. Mitigation Strategies: Overriding the Optimizer

When a database optimizer refuses to choose the expected index, engineers can intervene using Index Hints.

1. USE INDEX

Informs MySQL to evaluate specific indexes among a restricted subset, but the optimizer retains the authority to fall back to a table scan if it calculates the index scan as more expensive.

SELECT * FROM commits 
USE INDEX (idx_date_author_flipped)
WHERE repo_id = 42 
ORDER BY commit_date DESC, author_id ASC;

2. FORCE INDEX

Forces the query optimizer to use the specified index unless there is strictly no physical way to traverse it. It tells the engine that a table scan is essentially infinitely expensive.

SELECT * FROM commits 
FORCE INDEX (idx_date_author_flipped)
WHERE repo_id = 42 
ORDER BY commit_date DESC, author_id ASC;

In high-scale systems where query execution paths must remain deterministic, critical queries often bypass ORM abstraction layers to leverage explicit hints.

---

6. Three Critical Engineering Takeaways

1. Never Blindly Trust an ORM

ORMs (Active Record, Hibernate, SQLAlchemy, Django ORM) accelerate early development by abstracting SQL into application-level code. However, abstractions leak at scale:

• ORMs can dynamically generate queries that bypass indexes (e.g., improper ordering, unintentional subqueries, missing composite constraints).
• Actionable Rule: Regularly audit ORM-generated SQL against the slow query log. Critical or high-throughput queries should be written as explicit raw SQL or prepared statements rather than dynamically assembled through ORM domain methods.

2. Continuously Validate Query Execution Plans (EXPLAIN)

Do not deploy schema or index alterations without evaluating the execution plan.

EXPLAIN FORMAT=TREE 
SELECT * FROM commits 
WHERE repo_id = 42 
ORDER BY commit_date DESC, author_id ASC;

• Automated Regression Auditing: In CI/CD or staging environments with production-like data shapes, run EXPLAIN on a catalog of common queries before and after running migrations.
• Diff the query execution plans: If an operation shifts from Index Range Scan or Index Scan to Full Table Scan or introduces an unexpected Using filesort, block the migration.

3. Maintain an Inventory of Queries and Index Dependencies

Large systems have thousands of queries interacting with shared tables. Flipping or dropping an index cannot be done safely without knowing every query that relies on it.

• Build an Index-Query Inventory: Track the bidirectional mapping between production queries and the indexes they touch.
• Verify Redundancy Before Deletion: When modifying index definitions, ensure the existing query patterns are satisfied either by retaining the existing index alongside the new one temporarily, or validating that all dependent queries maintain identical performance under the new index structure.
• Decouple Downstream Services: Implement circuit breakers, aggressive timeouts, and asynchronous processing to prevent a single degraded database table from pulling down the entire platform.