Understanding Table Joins and Relationships
An index is extra information stored by a database to enable faster lookups on a specific column without scanning every row.
The Search Problem
Imagine a music database with millions of artist records. A user asks for all tracks by Frank Sinatra. The database must first find the matching row or rows in the Artist table, then use those results when it joins to the Track table. The central question is how the database should find the artist: should it inspect every row, or should it have a faster route to the matching name?
An index is extra information stored by a database to enable faster lookups on a specific column without scanning every row.
What do you think happens?
A table contains millions of artist rows, and the database needs rows whose name is Frank Sinatra. Which search strategy normally examines fewer rows?
Reveal answer
Answer: An index lookup
A full table scan checks rows one by one. An index stores a mapping from column values to row locations, allowing the database to go directly to relevant rows.
Two Lookup Paths
Without an index, the database performs a full table scan. It starts at the first row and checks rows one by one until it has found the requested matches. In a table with millions of rows, this may require examining millions of rows. With an index, the database uses its stored structure to locate the relevant rows and examines only those rows needed for the search.
| Search method | What the database does | Effect on a large table |
|---|---|---|
| Full table scan | Checks rows one by one, potentially through the entire table | Can be slow when the table contains millions of rows |
| Index lookup | Uses the indexed value to locate matching rows | Can examine only the relevant rows, especially for a unique or rare value |
Value to Row Mapping
An index does not store a copy of all the data in the table. Instead, it stores a mapping from each value in the indexed column to the location of the row containing that value. When the database searches for Frank Sinatra in an indexed name column, the index helps it find the matching row location, after which the database retrieves the full row.
Finding an artist before joining tracks
Locate the artist named Frank Sinatra and then use the matching artist result when working with the Track table.
Search the indexed column: The database searches the Artist.name value for Frank Sinatra.
Use the stored mapping: The index identifies the location of the matching Artist row or rows.
Retrieve the artist data: The database retrieves the full artist row from the identified location.
Join to tracks: The matching artist result is then used when the query joins the Artist and Track tables to find the requested tracks.
The database avoids scanning every Artist row merely to find the requested name, while the query can still obtain related track information.
Logical Keys and Joins
A logical key is a text column that represents a real-world identifier and is used in a WHERE clause to find rows. In the music example, Artist.name is a logical key because people search for artists by name. In a user database, an email address can be a logical key because users log in with their email address.
Logical keys differ from primary keys because they carry semantic meaning. A primary key is usually a numeric ID assigned by the database, while a logical key is meaningful to people and reflects how they naturally identify or search for records. In the music example, the database searches Artist.name and then joins the matching artist result to the Track table.
Creating the Index
SQL uses the CREATE INDEX statement to add an index. The statement specifies an index name, the table being indexed, and the column whose values should be indexed. Choose a descriptive index name that reflects the table and column.
| Part | Meaning |
|---|---|
| artist_name | The descriptive name given to the index |
| Artist | The table being indexed |
| name | The text column whose values are indexed |
Parts of the CREATE INDEX statement
After the statement executes, the database builds the index structure for Artist.name. Existing queries do not need to be rewritten, and the query syntax does not change. The database can automatically use the index for queries that search the Artist.name column.
Automatic Use and Maintenance
The database automatically maintains an index as data changes. It also uses the index transparently when it can speed up a query that searches the indexed column. You do not add special index syntax to every SELECT statement, and you do not need to rewrite an existing query after creating the index.
Choosing Useful Indexes
Index a logical key when the table is large, queries frequently use that column in WHERE clauses, the column contains text, and the column is relatively selective. A selective column is one where a search usually returns a small fraction of the table rather than half of its rows. These conditions make the work of maintaining the index more likely to be justified by faster lookups.
| Situation | Indexing guidance | Reason |
|---|---|---|
| Large table with frequent searches on a text logical key | Usually beneficial | The index can avoid checking every row repeatedly |
| Searches usually return a small fraction of rows | Usually beneficial | The lookup can focus on relatively few matching rows |
| Small table | May not be worthwhile | Index maintenance overhead can outweigh the lookup benefit |
| Column is rarely searched | Usually unnecessary | The index would provide little lookup benefit |
| Search usually returns about half the table | Use caution | The column is not relatively selective |
Common Indexing Mistakes
Assuming every column should have an index.
Indexes consume storage and require maintenance as data changes. A rarely used index may not provide enough lookup benefit to justify that overhead.
Fix:
Prioritize large tables and frequently searched, relatively selective text columns.Confusing a logical key with a primary key.
A logical key carries real-world meaning, while a primary key is usually a numeric ID assigned by the database.
Fix:
Identify the column people use to find records, then consider whether frequent searches on that column justify an index.Rewriting every query after creating an index.
The database uses indexes transparently for suitable searches, so the existing query syntax does not need to change.
Fix:
Create the index and continue using the existing query syntax.Thinking an index contains a complete second copy of the table.
The index stores a mapping from indexed values to row locations rather than a copy of all table data.
Fix:
Understand the index as a route from a searched value to the matching row location.
Practice the Decision
A user database contains millions of rows. Users frequently log in by email address, and each search normally returns one user. Decide whether email is a logical key and whether it is a strong candidate for an index. Then write a CREATE INDEX statement using a descriptive index name.
Hints
- Ask whether email represents a real-world identifier used to find a record.
- Check whether the table is large, the column is frequently searched, and searches return a small fraction of rows.
- Use the pattern CREATE INDEX index_name ON table_name(column_name).
Practice solution
Choose whether to index the email column in a large user table where users frequently log in with their email address.
Identify the logical key: Email is a logical key because it is a real-world identifier used to find users.
Evaluate the conditions: The table is large, searches use the column frequently, the column contains text, and each search returns a small fraction of the table.
Write the statement: Use a descriptive index name, the User table, and the email column.
CREATE INDEX user_email ON User(email);
Key Takeaways
- An index stores extra information that maps values in a column to row locations, helping the database avoid a full table scan.
- A logical key is a meaningful real-world identifier, such as an artist name or email address, that is used to find rows.
- CREATE INDEX specifies an index name, a table, and the column to index.
- The database automatically maintains indexes as data changes and can use them without changes to existing query syntax.
- Indexes are most useful when large tables are frequently searched through a selective text column, so they should be created strategically.
Key Takeaways
- An index provides a faster lookup path by mapping column values to row locations.
- A full table scan checks rows one by one, while an index can focus the search on matching rows.
- Logical keys such as artist names and email addresses are useful indexing candidates when they are frequently searched.
- CREATE INDEX adds the structure, and the database maintains and uses it transparently.
- Index selectively because indexes consume storage and create maintenance overhead.