4 Indexes
This chapter covers
- Exploring index types
- Understanding query execution plans
- Optimizing query performance
- Reducing the number of table lookups
- Indexing a subset of data
- Indexing the result of a function or expression
Indexes are often the first optimization technique that comes to mind when dealing with a long-running query or a slow database operation. They’ve proven so effective in many scenarios that we sometimes overlook other optimization methods, turning to indexes right away. As a result, indexes may be the second most common database object we create and use, right after tables.
Let’s explore Postgres's indexing capabilities as we build a multiplayer online game played by people around the world. We’ll learn how and when to use various index types to keep the gamers’ experience smooth and uninterrupted even during peak hours.
4.1 Why are indexes so popular?
Suppose we have a table with 100 records, and we ask Postgres to return a record with ID equal to 5. The algorithmic complexity of this search operation, expressed in Big O notation, is O(N), where N is the number of records in the table. O(N) describes linear search complexity, meaning that the more records we have, the longer it will take for Postgres to find the requested record or confirm that it doesn’t exist because the database will have to linearly search through potentially the entire N records.