Using an Index

Indexing for Joins

IN CLASS – Why would an index make joins faster?

Imagine a table containing 32 million ratings.

SELECT *
FROM hw3_ratings
WHERE userId = 10;

Without an index, MySQL might scan millions of records to find those belonging to user 10.

With an index, it can navigate a B-tree to find the relevant range.

A B-tree index maintains search keys in an ordered structure that MySQL can navigate efficiently.

In InnoDB:

• The primary key defines the clustered index, with the full row stored in its leaf pages.
• Secondary indexes contain indexed values plus the primary-key values needed to find the row.
• An index might be used just to determine whether a matching row exists, without retrieving other columns.

SHOW INDEX FROM hw3_ratings;
SHOW INDEX FROM hw3_movies;

Your hw3_ratings table has two indexes:

PRIMARY KEY (userId, movieId)
KEY idx_ratings_movie (movieId)

Why two indexes? Isn’t movieId already indexed?

Query A — Find all ratings by a user

EXPLAIN SELECT *
FROM hw3_ratings
WHERE userId = 10;

Query B — Find all ratings for a movie

EXPLAIN SELECT *
FROM hw3_ratings
WHERE movieId = 1;

Query C — Find a user’s rating for one movie

EXPLAIN SELECT *
FROM hw3_ratings
WHERE userId = 10 AND movieId = 1;

Which index each query will use?

Query	Expected index
A	PRIMARY
B	idx_ratings_movie
C	PRIMARY

The B-tree for (userId, movieId) is ordered conceptually like this:

userId   movieId
----------------
10       1
10       2
10       5
11       1
11       7
12       2

If you know userId, you can navigate to that user’s records. If you know only movieId, matching values are scattered across different users.

That’s why column order matters.

What happens if we reverse the primary key to (movieId, userId)?

Movie-specific lookups become efficient through that key, but user-specific lookups no longer have the same leading-column advantage.

An important nuance for MySQL 8.0: the optimizer sometimes supports index skip scans, so the leftmost-prefix rule is a very useful general principle, not an absolute claim that a later column can never be used.

EXPLAIN SELECT *
FROM hw3_imdb_principals
WHERE tconst = 'tt0114709';

EXPLAIN SELECT *
FROM hw3_imdb_principals
WHERE ordering = 1;

How much faster is an indexed lookup?

EXPLAIN SELECT * FROM lecture_links
WHERE movieId = 1;

EXPLAIN SELECT * FROM lecture_links_noidx
WHERE movieId = 1;

Which one scans the whole table? Which uses a B-tree lookup?

EXPLAIN ANALYZE
SELECT * FROM lecture_links
WHERE movieId = 1;

EXPLAIN ANALYZE
SELECT * FROM lecture_links_noidx
WHERE movieId = 1;

Can we fix the unindexed table?

CREATE INDEX idx_movie
ON lecture_links_noidx(movieId);

EXPLAIN ANALYZE
SELECT * FROM lecture_links_noidx
WHERE movieId = 1;

Why might the optimizer deliberately ignore an index?

Almost all movie IDs are positive. If nearly every row qualifies, reading the entire table may be cheaper than navigating a secondary index and fetching every matching row.

Indexing for Joins

First, join the unindexed copy of hw3_links with the indexed hw3_movies.

EXPLAIN ANALYZE
SELECT COUNT(*)
FROM lecture_links_noidx L
JOIN hw3_movies M
  ON L.movieId = M.movieId;

Since we just created an index on lecture_links_noidx, this query now has indexes available on both sides.

Which table is read first? Which index is used? Does MySQL actually use both indexes?

DROP INDEX idx_movie ON lecture_links_noidx;

EXPLAIN ANALYZE
SELECT COUNT(*)
FROM lecture_links_noidx L
JOIN hw3_movies M
  ON L.movieId = M.movieId;

Is this necessarily much slower?

No! An index on the inner, lookup side of a join can be sufficient. MySQL may scan the unindexed table and use the primary key on hw3_movies to find each matching row.

What if neither table has an index?

Create a second unindexed copy:

DROP TABLE IF EXISTS lecture_links_noidx2;

CREATE TABLE lecture_links_noidx2 AS
SELECT movieId, tconst
FROM hw3_links;

Compare:

EXPLAIN ANALYZE
SELECT COUNT(*)
FROM lecture_links_noidx L
JOIN lecture_links_noidx2 R
  ON L.movieId = R.movieId;

Do we have time for sorted:

CREATE TABLE lecture_links_sorted AS
SELECT movieId, tconst
FROM hw3_links
ORDER BY movieId;

SHOW INDEX FROM lecture_links_sorted;

Lets try:

EXPLAIN ANALYZE
SELECT * FROM lecture_links_sorted
WHERE movieId = 1;

Compare:

EXPLAIN ANALYZE
SELECT * FROM lecture_links
WHERE movieId = 1;

What about order by?

EXPLAIN
SELECT movieId
FROM lecture_links
ORDER BY movieId
LIMIT 10;

EXPLAIN
SELECT movieId
FROM lecture_links_noidx
ORDER BY movieId
LIMIT 10;

In the indexed table, MySQL can walk the B-tree in order. In the unindexed table, it may need a sort.

Costs:

SELECT
    table_name,
    table_rows,
    ROUND(data_length / 1024 / 1024, 1) AS data_mb,
    ROUND(index_length / 1024 / 1024, 1) AS index_mb
FROM information_schema.tables
WHERE table_schema = DATABASE()
  AND table_name IN
  ('hw3_ratings', 'hw3_imdb_principals');

Table	Data	Secondary indexes
hw3_ratings	2,819 MB	476 MB
hw3_imdb_principals	6,509 MB	5,890 MB

These are approximate InnoDB storage statistics.

Why does hw3_imdb_principals have nearly 6 GB of secondary indexes?

It has about 101 million rows. Every entry in a secondary index requires storage for its key and the corresponding primary-key columns, plus B-tree overhead.

Question: Why not index every column?

Indexes have three major costs:

1. They consume storage.
2. Inserts and deletes must maintain the indexes.
3. Updates to indexed columns may require additional index work.

Index-only queries

An index sometimes contains everything the query needs.

For example, the secondary index on hw3_ratings(movieId) also contains the primary-key columns, including userId.

EXPLAIN
SELECT movieId, userId
FROM hw3_ratings
WHERE movieId = 1;