Indexes

“When a reader requests a list of posts, HopPress must return the published posts.” The application must run a database query. The query is to get all rows in the posts table where the state column is equal to published.

The database, by default, reads every row in the table and keeps the ones that match the filtering condition. That is called a full table scan. The scan gets slower as the number of posts increases. A university news site accumulates tens of thousands of posts over a few years, and each reader visit would read all of them to find the published ones. The cost of the list depends on how big the table is, not on how many posts come back.

An index is a separate structure the database keeps next to a table. It holds the values of one or more columns, sorted, with a pointer from each value to the row it came from. The name comes from the index at the back of a book, and it works the same way: to find rows where state is published, the database looks up published in the index and follows the pointers. It does not read the rows that do not match. The lookup cost grows with the size of the index, and it grows slowly. It does not grow with the size of the table.

Primary keys are already indexed, because looking up a single row by its primary key is a common pattern. That is why getting one post by its post_id is fast. Columns declared unique are indexed as well, because the database needs the index to check uniqueness. Every other index is a design decision. You create the index on a column yourself, and the database keeps the index up to date on every write.

The way to decide is to list the reads the application performs and the column each one filters on.

The first and last rows are already indexed. The post_id is the primary key of posts, and idp_subject is unique in users. The rest need indexes. (Note that some databases automatically index foreign keys like author_id, editor_id, and post_id in post_state_changes, but most do not. Check what your database does before assuming.)

posts
  index on (state)
  index on (author_id)
  index on (editor_id)

post_state_changes
  index on (post_id)

You can also create an index on multiple columns. That is useful when the application filters on one column and sorts on another. For example, we may want the list of published posts sorted by published_at, so the newest appears first. The database can use an index on (state, published_at) to find the published rows and read them in published_at order without sorting.

posts
  index on (state, published_at)
  index on (author_id, created_at)
  index on (editor_id, created_at)

post_state_changes
  index on (post_id, occurred_at)

An index has a cost. Every insert, update, or delete that touches an indexed column must update the index as well, so each index makes writes slower. Each index also takes space. So you should not index every column. Index the columns the application frequently filters and sorts on. This is the same trade-off we made for denormalization: make writes slower to make reads faster.