PostgreSQL's EXPLAIN command contains detailed information about many aspect of a query's execution plan. But one particular set of information is curiously absent.

EXPLAIN Quirks: PostgreSQL's Missing Index Usage Details


Here at Query Doctor (find us on [Discord](https://discord.gg/2K67GmPuva)) we are big fans of visualizations and of mental models. Together these two techniques allow complicated concepts to be easily understood. Applying this to indexes specifically is one of the superpowers that makes our doctors so effective.

A data structure known as a [B+ tree](https://en.wikipedia.org/wiki/B%2B_tree) is what the [majority of database indexes](https://en.wikipedia.org/wiki/B%2B_tree#Database_Systems) are built on today. The details of such data structures are interesting and there are many resources available online if you want to dive into them in full. As it turns out for our purposes though, there are only a few key facts about them that need to be known in order to build a robust model for using them. Those concepts are:

- The tree has a well-defined order which is declared when the index is created.
- All of the user data is available in the final layer of the index which we call the leaf nodes.
- The leaf nodes all point to their neighbors.

In "reality", a typical B+ tree may "look" like this:

![Standard (and static) B+ tree visualization](/posts-images/index-ray-intro/btree.png)

By contrast, here is how we think about the same structure:

<IxrEmbed
  data={{
     queryAst: {
      select: [
        'score',
        'gamerName'
      ],
      from: 'foo',
      where: [
        {
          id: '68363a0f-499f-4e9e-b586-d661175fb9eb',
          key: 'score',
          operator: '>',
          value: 8
        },
        {
          id: '571ff310-e668-4640-a9e7-d6721a4cebc2',
          key: 'official',
          operator: '=',
          value: true
        }
      ],
      orderBy: []
    },
    columns: [
      {
        name: 'gamerName',
        type: 'string',
        autofill: {
          dataType: 'first_name',
          randomnessPool: 'few'
        }
      },
      {
        name: 'score',
        type: 'number',
        autofill: {
          dataType: 'number',
          randomnessPool: 'few'
        }
      },
      {
        name: 'official',
        type: 'boolean',
        autofill: {
          dataType: 'boolean',
          randomnessPool: 'few'
        }
      }
    ],
    indexes: [
      {
        name: 'foos',
        columns: [
          {
            name: 'score',
            order: 'asc'
          },
        ]
      }
    ],
    data: [
      {
        _internal_id: 1,
        gamerName: 'Alice',
        score: 14,
        official: false
      },
      {
        _internal_id: 2,
        gamerName: 'Mary',
        score: 16,
        official: false
      },
      {
        _internal_id: 3,
        gamerName: 'Carol',
        score: 9,
        official: true
      },
      {
        _internal_id: 4,
        gamerName: 'Bob',
        score: 9,
        official: false
      },
      {
        _internal_id: 5,
        gamerName: 'Patricia',
        score: 2,
        official: true
      },
      {
        _internal_id: 6,
        gamerName: 'Alice',
        score: 2,
        official: false
      },
      {
        _internal_id: 7,
        gamerName: 'Mary',
        score: 14,
        official: true
      },
      {
        _internal_id: 8,
        gamerName: 'James',
        score: 2,
        official: false
      },
      {
        _internal_id: 9,
        gamerName: 'Barbara',
        score: 11,
        official: true
      }
    ],
    compare: { mode: "single-view", compared: [0, 1] },
  }}
/>

There are some obvious differences between these structures which we will explore momentarily. Despite those differences, notice that our model preserves the three critical components of B+ trees mentioned above. We can see, for example, that the values in the leaf nodes are ordered in the same way. 

So if these two representations are the same in those important ways, what is the point of offering an alternative at all? An example should help.

## Example: Finding High Scores

Consider the following query:

```sql
SELECT *
FROM games
WHERE score > 8 AND official = true
```

This query filters on two columns, `score` and `official`. One thing we could do is to create a compound index on both columns. 

### B+ Tree representation

Let's do so, placing `score` first since that's how it is listed in our query. Here is the B+ tree representation:

![B+ tree visualization of a compound index on the score and official columns](/posts-images/index-ray-intro/btree_num_bool_a.png)

We could instead swap the order and create the index with `official` first. Here is what that index would look like using the more direct B+ tree representation:

![B+ tree visualization of a compound index on the official and score columns](/posts-images/index-ray-intro/btree_bool_num_a.png)

This may make you wonder:

>Is one of these indexes better than the other for this query?  If so, which one and why?

The answer to that question is:

>The second index, which has `official` first, is absolutely better! 

How did we determine that? If we look at the two root nodes, for example, it isn't clear at all if the `( 09/T )` one would be any different than the `( F/16  T/09 )` one.

However when we look more broadly at what parts of the B+ tree are scanned when the query is executed the answer becomes much more apparent!

For the first index, that looks something like this:

![Traversal of the (score, official) B+ tree index](/posts-images/index-ray-intro/btree_num_bool_a_highlighted.png)

One of the important things to notice here is that the database scanned 6 out of the 9 total leaf nodes. Three of them, shown in yellow, did not match the query.

By contrast, the other index can be used by the database as follows:

![Traversal of the (official, score) B+ tree index](/posts-images/index-ray-intro/btree_bool_num_a_highlighted.png)

This time around we see that only the 3 leaf nodes that match the query are scanned. The reason it can do this is because the data we are interested in is all located together in one part of the index. We can determine this based on how the index was originally defined, specifically `(official, score)` in this case, but that is not at all _obvious_ when looking at the B+ tree representation.

### IndeX-Ray™ Representation

IndeX-Ray™ represents a better way to 'look' at and reason about these indexes.

Here is the first index of `(score, official)`:

<IxrEmbed
  data={{
     queryAst: {
      select: [
        'score',
        'gamerName'
      ],
      from: 'foo',
      where: [
        {
          id: '68363a0f-499f-4e9e-b586-d661175fb9eb',
          key: 'score',
          operator: '>',
          value: 8
        },
        {
          id: '571ff310-e668-4640-a9e7-d6721a4cebc2',
          key: 'official',
          operator: '=',
          value: true
        }
      ],
      orderBy: []
    },
    columns: [
      {
        name: 'gamerName',
        type: 'string',
        autofill: {
          dataType: 'first_name',
          randomnessPool: 'few'
        }
      },
      {
        name: 'score',
        type: 'number',
        autofill: {
          dataType: 'number',
          randomnessPool: 'few'
        }
      },
      {
        name: 'official',
        type: 'boolean',
        autofill: {
          dataType: 'boolean',
          randomnessPool: 'few'
        }
      }
    ],
    indexes: [
      {
        name: 'foos',
        columns: [
          {
            name: 'score',
            order: 'asc'
          },
          {
            name: 'official',
            order: 'asc'
          }
        ]
      }
    ],
    data: [
      {
        _internal_id: 1,
        gamerName: 'Alice',
        score: 14,
        official: false
      },
      {
        _internal_id: 2,
        gamerName: 'Mary',
        score: 16,
        official: false
      },
      {
        _internal_id: 3,
        gamerName: 'Carol',
        score: 9,
        official: true
      },
      {
        _internal_id: 4,
        gamerName: 'Bob',
        score: 9,
        official: false
      },
      {
        _internal_id: 5,
        gamerName: 'Patricia',
        score: 2,
        official: true
      },
      {
        _internal_id: 6,
        gamerName: 'Alice',
        score: 2,
        official: false
      },
      {
        _internal_id: 7,
        gamerName: 'Mary',
        score: 14,
        official: true
      },
      {
        _internal_id: 8,
        gamerName: 'James',
        score: 2,
        official: false
      },
      {
        _internal_id: 9,
        gamerName: 'Barbara',
        score: 11,
        official: true
      }
    ],
    compare: { mode: "single-view", compared: [0, 1] },
  }}
/>

As we mentioned in the intro, **the final layer of the index remains the same** in this representation. It is only the layers above that which have been shuffled around. In particular these internal layers now separate things out much more:

* A node does not contain multiple entries, such as both `11/T` and `14/F` as in `( 11/T 14/F )`
* Each column in the index, here `score` and `official`, has its own layer in the tree. So `11/T` would instead be a node with `11` which has a node with `T` as a child.

Together these changes result in the visualization having subtrees that are more meaningfully defined. We no longer have, for example, a node with `O9/T` underneath a parent node which has `( 11/T 14/F )`. Instead, the internal nodes always share the same values with leaf nodes that descend from them.

When we flip the index definition around to `(official, score)` we get the following:

<IxrEmbed
  data={{
     queryAst: {
      select: [
        'score',
        'gamerName'
      ],
      from: 'foo',
      where: [
        {
          id: '68363a0f-499f-4e9e-b586-d661175fb9eb',
          key: 'score',
          operator: '>',
          value: 8
        },
        {
          id: '571ff310-e668-4640-a9e7-d6721a4cebc2',
          key: 'official',
          operator: '=',
          value: true
        }
      ],
      orderBy: []
    },
    columns: [
      {
        name: 'gamerName',
        type: 'string',
        autofill: {
          dataType: 'first_name',
          randomnessPool: 'few'
        }
      },
      {
        name: 'score',
        type: 'number',
        autofill: {
          dataType: 'number',
          randomnessPool: 'few'
        }
      },
      {
        name: 'official',
        type: 'boolean',
        autofill: {
          dataType: 'boolean',
          randomnessPool: 'few'
        }
      }
    ],
    indexes: [
      {
        name: 'foos',
        columns: [
          {
            name: 'official',
            order: 'asc'
          },
          {
            name: 'score',
            order: 'asc'
          }
        ]
      }
    ],
    data: [
      {
        _internal_id: 1,
        gamerName: 'Alice',
        score: 14,
        official: false
      },
      {
        _internal_id: 2,
        gamerName: 'Mary',
        score: 16,
        official: false
      },
      {
        _internal_id: 3,
        gamerName: 'Carol',
        score: 9,
        official: true
      },
      {
        _internal_id: 4,
        gamerName: 'Bob',
        score: 9,
        official: false
      },
      {
        _internal_id: 5,
        gamerName: 'Patricia',
        score: 2,
        official: true
      },
      {
        _internal_id: 6,
        gamerName: 'Alice',
        score: 2,
        official: false
      },
      {
        _internal_id: 7,
        gamerName: 'Mary',
        score: 14,
        official: true
      },
      {
        _internal_id: 8,
        gamerName: 'James',
        score: 2,
        official: false
      },
      {
        _internal_id: 9,
        gamerName: 'Barbara',
        score: 11,
        official: true
      }
    ],
    compare: { mode: "single-view", compared: [0, 1] },
  }}
/>

We can see a much bigger change between the two IndeX-Ray™ representations than there was between the two B+ tree representations.

It should immediately be clear that the entire subtree of `F` (`false`) is not relevant to the query and **can be avoided altogether**. This is "why" the second index has the data grouped together in a manner that is better for the query. Being able to _see_ this makes it much easier to reason about the layout of indexes and how they can be used.

## Takeaways

This article introduced IndeX-Ray™, a technology that allows you to see the indexes inside of databases like never before.

This technology is a powerful tool used by anyone serious about query performance. It allows us to clearly "see" how indexes are used inside of databases. No longer having to guess about the layout of the information unlocks some powerful insights about how to best use them. **IndeX-Ray™ turns anyone into a Query Doctor!**

<ClosingSnippet />


Today we introduce IndeX-Ray™ which is a simple, intuitive, and powerful way to visualize indexes inside of databases!

IndeX-Ray™: Imaging Technology for Database Indexes


Indexes allow databases to efficiently find stored information. To do so they must contain an updated copy of the associated information from the records. Sometimes the information in the index alone is enough to respond to a query. This article takes a brief look at that additional optimization which is typically referred to as an _Index Only Scan_ or a _Covered Query_.

One quick note before we begin. The technique described here is pretty powerful but also quite specific. While all indexes are <LinkTodo>designed for queries</LinkTodo>, covering indexes usually limit flexibility even more. There are often ample other performance improvements that should be explored prior to covering, and relying on covering to reach performance goals can be a gamble that may not pay off.

---

## Setup

For this demonstration, consider a subset of our <LinkTodo>gaming schema</LinkTodo> populated with the following entries:

| ID  | gamerName | score |
| --- | --------- | ----- |
| 1   | Ice       | 0     |
| 2   | Sky       | 9     |
| 3   | Ray       | 3     |
| 4   | Ice       | 2     |
| 5   | Sky       | 1     |
| 6   | Ice       | 4     |
| 7   | Sky       | 2     |

When a user is logged in the application will need to retrieve the scores by that user from the database. The filtering conditions could be expressed as the following SQL query:

```sql
SELECT *
FROM GAMES
WHERE gamerName = 'Sky';
```

As we know, an [index can be used](what-is-an-index) to execute queries like this efficiently. Let's create one now on the `gamerName` column used by the query:

<IxrEmbed
  data={{
    queryAst: {
      select: [],
      from: "foo",
      where: [
        {
          id: "80a5cbec-9dee-4beb-8bb5-9eb39c4d552c",
          key: "gamerName",
          operator: "=",
          value: "Sky",
        },
      ],
      orderBy: [],
    },
    columns: [
      {
        name: "gamerName",
        type: "string",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
      {
        name: "score",
        type: "number",
        autofill: { dataType: "number", randomnessPool: "few" },
      },
    ],
    indexes: [{ name: "foos", columns: [{ name: "gamerName", order: "asc" }] }],
    data: [
      { _internal_id: 1, gamerName: "Ice", score: 0 },
      { _internal_id: 3, gamerName: "Sky", score: 9 },
      { _internal_id: 4, gamerName: "Ray", score: 3 },
      { _internal_id: 5, gamerName: "Ice", score: 2 },
      { _internal_id: 7, gamerName: "Sky", score: 1 },
      { _internal_id: 8, gamerName: "Ice", score: 4 },
      { _internal_id: 9, gamerName: "Sky", score: 2 },
    ],
    hovered: null,
    compare: {
      mode: "single-view",
      compared: [0, -1],
    },
  }}
/>

<IXRIntroSnippet />

The database did exactly as we were expecting, using the index in a targeted manner to read only the records that were of interest to us. Specifically it does a good job of removing unnecessary records from the table via the `WHERE` clause:

```
WHERE gamerName = 'Sky';
```

This query and index are designed in a way that will allow the database to scale successfully over time. This is pretty typical of what we might see in a real application and does not necessarily need any further attention. But while we are here, is there anything that we can do to optimize it evenmore?

## (Further) Narrowing the results

It turns out that there is more that we can do though by taking a look at the actual application requirements. Recall that we are just displaying the `score`s produced by the logged in user. This draws our attention to the beginning of the query:

```
SELECT *
```

The `*` here represents _all_ columns in the table, but the application only needs the value from a single one! While the purpose of this article is not to discuss <LinkTodo>discuss the `SELECT *` pattern</LinkTodo>, we certainly do not need the query to retrieve all of the columns. Based on this requirement, we can further narrow our results by removing extra information from the _records_ that get retrieved by the application. Adjusting the `SELECT` portion of the query slightly makes it:

```
SELECT score
FROM GAMES
WHERE gamerName = 'Sky';
```

Does this change execution at all?

<IxrEmbed
  data={{
    queryAst: {
      select: ["score"],
      from: "foo",
      where: [
        {
          id: "80a5cbec-9dee-4beb-8bb5-9eb39c4d552c",
          key: "gamerName",
          operator: "=",
          value: "Sky",
        },
      ],
      orderBy: [],
    },
    columns: [
      {
        name: "gamerName",
        type: "string",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
      {
        name: "score",
        type: "number",
        autofill: { dataType: "number", randomnessPool: "few" },
      },
    ],
    indexes: [{ name: "foos", columns: [{ name: "gamerName", order: "asc" }] }],
    data: [
      { _internal_id: 1, gamerName: "Ice", score: 0 },
      { _internal_id: 3, gamerName: "Sky", score: 9 },
      { _internal_id: 4, gamerName: "Ray", score: 3 },
      { _internal_id: 5, gamerName: "Ice", score: 2 },
      { _internal_id: 7, gamerName: "Sky", score: 1 },
      { _internal_id: 8, gamerName: "Ice", score: 4 },
      { _internal_id: 9, gamerName: "Sky", score: 2 },
    ],
    hovered: null,
    compare: {
      mode: "single-view",
      compared: [0, -1],
    },
  }}
/>

_Be sure to click the play button to see the database in action!_

Not yet in terms of the query execution plan itself. There are indeed _other_ benefits that come about from this change by itself, but determining what those are is an exercise left up to the reader (hint: some of them may be related to <LinkTodo>network traffic</LinkTodo>). That said, we are not done in terms of improving the query execution itself. Let's keep going!

When we look again at the final query, we can observe that there are only two columns, `gamerName` and `score`, are mentioned. The index already contains `gamerName`. This suggests that the database is _reading the entire record_ simply to retrieve the value of the one other column (`score`).

Can we help the database out by giving it that additional data in the index? Let's update the index to include the other column (`score`) and see what happens:

<IxrEmbed
  data={{
    queryAst: {
      select: ["score"],
      from: "foo",
      where: [
        {
          id: "80a5cbec-9dee-4beb-8bb5-9eb39c4d552c",
          key: "gamerName",
          operator: "=",
          value: "Sky",
        },
      ],
      orderBy: [],
    },
    columns: [
      {
        name: "gamerName",
        type: "string",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
      {
        name: "score",
        type: "number",
        autofill: { dataType: "number", randomnessPool: "few" },
      },
    ],
    indexes: [
      {
        name: "foos",
        columns: [
          { name: "gamerName", order: "asc" },
          { name: "score", order: "asc" },
        ],
      },
    ],
    data: [
      { _internal_id: 1, gamerName: "Ice", score: 0 },
      { _internal_id: 3, gamerName: "Sky", score: 9 },
      { _internal_id: 4, gamerName: "Ray", score: 3 },
      { _internal_id: 5, gamerName: "Ice", score: 2 },
      { _internal_id: 7, gamerName: "Sky", score: 1 },
      { _internal_id: 8, gamerName: "Ice", score: 4 },
      { _internal_id: 9, gamerName: "Sky", score: 2 },
    ],
    hovered: null,
    compare: {
      mode: "single-view",
      compared: [0, -1],
    },
  }}
/>

Ah now _there_ is a change!

The database scans the same number of leaf nodes (3) using this index as it did with the previous one. The differenc is that now the index alone contains both the `score` information needed for the `WHERE` clause as well as the `gamerName` information that should get returned to the client. This represents all of the information needed to process the query meaning that there is no reason for the database to retrieve and process the record itself. The database knows this and therefore removes that extra work from the query plan altogether. The result is this '_Index Only Scan_' or '_Covered Query_' seen above.

---

## Summary

Creating an index that fully covers a query can be a powerful optimization. Doing so allows the database to skip processing records altogether which is a direct reduction in the amount of work that the database and its host server are doing. Among others, one benefit is that such queries process faster.

This technique can be opportunistically pursued for queries that need to run as quickly as possible or for query and index pairs that are already close to being covered already. It should _not_, however, be the goal of all or even most queries. Indexes can, and should, <LinkTodo>support multiple queries</LinkTodo>. But every additional column that is added to an index definition typically makes it less flexible for supporting other operations. Those larger indexes also create incrementally more overhead which adds up over time.

So use covered queries, but do so responsibly.

<ClosingSnippet />


Indexes tell databases where to find information that it is looking for. Under the right circumstances, the index can save the database even more time by providing the requested information directly.

Covered Queries


Databases are able to quickly retrieve information seemingly regardless of how large they become. While they have many techniques that help them do so, none of them would be useful without indexes powering them underneath. This article takes a brief look at what an index is and why they can be so helpful for databases.

For this demonstration, consider the following data:

| ID  | name  | total |
| --- | ----- | ----- |
| 1   | Bob   | 0     |
| 2   | Carol | 9     |
| 3   | Alice | 3     |
| 4   | Bob   | 2     |
| 5   | Carol | 1     |
| 6   | Bob   | 4     |
| 7   | Carol | 2     |

Our user now wants to find a specific piece of information, namely the item that has a `name` of `'Bob'` and a `total` of `2`. In SQL, this would be expressed as:

```sql
SELECT *
FROM FOO
WHERE
    name = 'Bob'
    AND total = 2;
```

Without any indexes, the data will simply be sitting unorganized in the database. So in order for it to find the requested information, it must sequentially scan the records filtering for the values of interest:

<IxrEmbed
  data={{
    queryAst: {
      select: ["name", "total"],
      from: "foo",
      where: [
        { id: "abc", key: "name", operator: "=", value: "Bob" },
        { id: "d", key: "total", operator: "=", value: 2 },
      ],
      orderBy: [],
    },
    columns: [
      {
        name: "name",
        type: "string",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
      {
        name: "total",
        type: "number",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
    ],
    indexes: [],
    data: [
      { _internal_id: 1, name: "Bob", total: 0 },
      { _internal_id: 7, name: "Carol", total: 9 },
      { _internal_id: 1, name: "Alice", total: 3 },
      { _internal_id: 3, name: "Bob", total: 2 },
      { _internal_id: 5, name: "Carol", total: 1 },
      { _internal_id: 4, name: "Bob", total: 4 },
      { _internal_id: 6, name: "Carol", total: 2 },
    ],
    hovered: null,
    compare: {
      mode: "single-view",
      compared: [0, -1],
    },
  }}
/>

<IXRIntroSnippet />

What we see above is that the database spent time scanning all 7 records in the table but ended up discarding 6 of them since they did not match the query. Also notice here that even after the database found the single matching record it still had to continue its scan through the rest of the table. This is because it didn't _know_ that there weren't any other matching records that it might find later which the user would also be interested in. When looking through unorganized data, the items of interest could be anywhere.

Now let's create an index on the `name` column and see how things look:

<IxrEmbed
  data={{
    queryAst: {
      select: ["name", "total"],
      from: "foo",
      where: [
        { id: "abc", key: "name", operator: "=", value: "Bob" },
        { id: "d", key: "total", operator: "=", value: 2 },
      ],
      orderBy: [],
    },
    columns: [
      {
        name: "name",
        type: "string",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
      {
        name: "total",
        type: "number",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
    ],
    indexes: [
      {
        name: "foos",
        columns: [
          {
            name: "name",
            order: "asc",
          },
        ],
      },
    ],
    data: [
      { _internal_id: 1, name: "Bob", total: 0 },
      { _internal_id: 7, name: "Carol", total: 9 },
      { _internal_id: 1, name: "Alice", total: 3 },
      { _internal_id: 3, name: "Bob", total: 2 },
      { _internal_id: 5, name: "Carol", total: 1 },
      { _internal_id: 4, name: "Bob", total: 4 },
      { _internal_id: 6, name: "Carol", total: 2 },
    ],
    hovered: null,
    compare: {
      mode: "single-view",
      compared: [0, -1],
    },
  }}
/>

_Be sure to click the play button to see the database in action!_

Now that we have an index on the `name` column, the database is able to take a much different approach to finding the record of interest. No longer is it searching through all 7 records in the table, instead it focuses on only the 3 records which have a `name` of `'Bob'`. It does this by walking the index 'down and over':

- An index scan always starts at the `root` node of the tree and goes down to the specific section of the index where the first item of relevance to the query could be found.
- Once it reaches this bottom layer, which are known as leaf nodes, the database can then walk directly between neighboring nodes until it exits the section of relevance. In this example the database will scan along subsequent leaf nodes for those which contain a `name` of `'Bob'` stopping once it encounters the `'Carol'` node. Since the index is well-ordered the database can safely stop scanning for more records at this point knowing that there can be no other relevant records outside of this small section of the index.

We see one other interesting thing above which is that all 3 of the `'Bob'` records were scanned even though only 1 matched the query and belonged in the results. This is related to the fact that our query also included the following condition:

```sql
WHERE
    ...
    total = 2;
```

Since the `total` column is not part of this index, the database does not know what value the records have for that column without accessing them directly. All it can tell from reading the leaf nodes of the index is that there are some _candidate_ records which have the correct value for `name` (`'Bob'` in this example), but this index cannot say with certainty whether the record will match all of the query conditions or not. This is why the database had to scan the records which had `id`s of `1` and `4` even though it discarded them since they were not part of the result set.

You could similarly create an index on the `total` field instead, which would look as follows:

<IxrEmbed
  data={{
    queryAst: {
      select: ["name", "total"],
      from: "foo",
      where: [
        { id: "abc", key: "name", operator: "=", value: "Bob" },
        { id: "d", key: "total", operator: "=", value: 2 },
      ],
      orderBy: [],
    },
    columns: [
      {
        name: "name",
        type: "string",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
      {
        name: "total",
        type: "number",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
    ],
    indexes: [
      {
        name: "foos",
        columns: [
          {
            name: "total",
            order: "asc",
          },
        ],
      },
    ],
    data: [
      { _internal_id: 1, name: "Bob", total: 0 },
      { _internal_id: 7, name: "Carol", total: 9 },
      { _internal_id: 1, name: "Alice", total: 3 },
      { _internal_id: 3, name: "Bob", total: 2 },
      { _internal_id: 5, name: "Carol", total: 1 },
      { _internal_id: 4, name: "Bob", total: 4 },
      { _internal_id: 6, name: "Carol", total: 2 },
    ],
    hovered: null,
    compare: {
      mode: "single-view",
      compared: [0, -1],
    },
  }}
/>

As before, only one of the two columns being filtered on is present in the index, so it ends up scanning an extra record. It is a different extra record than before though, as it is `id: 6` which is a candidate based on its value of `2` for the indexed `total` column. How effective a single column index is depends on how selective the values in the column are as compared to any other filters that may also be present in the query.

But indexes are not just limited to a single column! Let's try creating a compound (also called multicolumn or composite) index using both of the columns from the `WHERE` clause:

<IxrEmbed
  data={{
    queryAst: {
      select: ["name", "total"],
      from: "foo",
      where: [
        { id: "abc", key: "name", operator: "=", value: "Bob" },
        { id: "d", key: "total", operator: "=", value: 2 },
      ],
      orderBy: [],
    },
    columns: [
      {
        name: "name",
        type: "string",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
      {
        name: "total",
        type: "number",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
    ],
    indexes: [
      {
        name: "foos",
        columns: [
          {
            name: "name",
            order: "asc",
          },
          {
            name: "total",
            order: "asc",
          },
        ],
      },
    ],
    data: [
      { _internal_id: 1, name: "Bob", total: 0 },
      { _internal_id: 7, name: "Carol", total: 9 },
      { _internal_id: 1, name: "Alice", total: 3 },
      { _internal_id: 3, name: "Bob", total: 2 },
      { _internal_id: 5, name: "Carol", total: 1 },
      { _internal_id: 4, name: "Bob", total: 4 },
      { _internal_id: 6, name: "Carol", total: 2 },
    ],
    hovered: null,
    compare: {
      mode: "single-view",
      compared: [0, -1],
    },
  }}
/>

Now the leaf nodes contain both of the columns being filtered against, so the database can scan just the single matching record. This is very efficient and can help the database scale very well over time.

<ClosingSnippet />


Indexes are the core component that drive efficient database performance. How do they do it?

What is an Index?


**Takeaway**: Indexes are incredible, but not magical. There are times when they should _not_ be used. Forcing a database to use one when it doesn’t naturally want to could cause performance to get worse.

**Why it matters**: The go-to advice when there is a query performance problem is ‘use an index’. While this is often correct, it is not always the solution. Having a basic understanding of when indexes are unable to improve the performance of a query will shift the focus toward more actionable steps.

---

## A Database Secret

Here’s one of the best kept secrets about databases:

> _Sometimes there is no index that will speed up a query._

On the surface, this may sound ridiculous if not down right blasphemous. Indexes can speed up a query by several orders of magnitude and the general guidance whenever a slow query is encountered is to [Use The Index](https://use-the-index-luke.com/). Indeed that is the proper rule of thumb and the same advice provided here. That doesn’t mean that it is _always_ the solution. Let’s take a look at why that is.

## Example Boolean Query

Consider the following query:

```sql
SELECT *
FROM FOO
WHERE active = true;
```

With conventional wisdom in mind, the first response after identifying this slow query may be to create the index of `(active)`. After doing so we observe that the optimizer is choosing not to use it! What is going on?

Given that index, the two basic approaches the database could pursue in order to execute this query would be:

1. Scan only the portion of the `(active)` index which contains `true` values and then fetch the associated records from the table
1. Scan every record in the table discarding all of those which do not contain a `true` value for the `active` column

### First Approach (Index Scan)

Let's confirm that the first approach, which scans an index, is doing what we expect:

<IxrEmbed
  data={{
    queryAst: {
      select: ["name", "value"],
      from: "foo",
      where: [
        {
          id: "94f384a3-69fc-498c-9b35-394f9ac0587b",
          key: "active",
          operator: "=",
          value: true,
        },
      ],
      orderBy: [],
    },
    columns: [
      {
        name: "name",
        type: "string",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
      {
        name: "value",
        type: "number",
        autofill: { dataType: "number", randomnessPool: "few" },
      },
      {
        name: "active",
        type: "boolean",
        autofill: { dataType: "boolean", randomnessPool: "few" },
      },
    ],
    indexes: [{ name: "foos", columns: [{ name: "active", order: "asc" }] }],
    data: [
      { _internal_id: 1, name: "Alice", value: 3, active: true },
      { _internal_id: 2, name: "Alice", value: 8, active: true },
      { _internal_id: 3, name: "Bob", value: 1, active: true },
      { _internal_id: 4, name: "Bob", value: 2, active: true },
      { _internal_id: 5, name: "Bob", value: 5, active: false },
      { _internal_id: 6, name: "Bob", value: 7, active: true },
      { _internal_id: 7, name: "Bob", value: 9, active: true },
      { _internal_id: 8, name: "Carol", value: 6, active: false },
      { _internal_id: 9, name: "Carol", value: 3, active: true },
    ],
    hovered: null,
    compare: { mode: "single-view", compared: [0, -1] },
  }}
/>

<IXRIntroSnippet />

Above we can see that the database was able to successfully limit its search to only the records of interest to the client (those that match `active=true`). This is great! The database did not have to waste any effort scanning excess records that the client was not interested in.

So why does the database seem to disagree and choose the other approach instead?

### Second Approach (Table Scan)

Let's take a look at the second option that the database has, which is to scan the full table:

<IxrEmbed
  data={{
    queryAst: {
      select: ["name", "value"],
      from: "foo",
      where: [
        {
          id: "94f384a3-69fc-498c-9b35-394f9ac0587b",
          key: "active",
          operator: "=",
          value: true,
        },
      ],
      orderBy: [],
    },
    columns: [
      {
        name: "name",
        type: "string",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
      {
        name: "value",
        type: "number",
        autofill: { dataType: "number", randomnessPool: "few" },
      },
      {
        name: "active",
        type: "boolean",
        autofill: { dataType: "boolean", randomnessPool: "few" },
      },
    ],
    indexes: [],
    data: [
      { _internal_id: 1, name: "Alice", value: 3, active: true },
      { _internal_id: 2, name: "Alice", value: 8, active: true },
      { _internal_id: 3, name: "Bob", value: 1, active: true },
      { _internal_id: 4, name: "Bob", value: 2, active: true },
      { _internal_id: 5, name: "Bob", value: 5, active: false },
      { _internal_id: 6, name: "Bob", value: 7, active: true },
      { _internal_id: 7, name: "Bob", value: 9, active: true },
      { _internal_id: 8, name: "Carol", value: 6, active: false },
      { _internal_id: 9, name: "Carol", value: 3, active: true },
    ],
    hovered: null,
    compare: { mode: "single-view", compared: [0, -1] },
  }}
/>

_Be sure to click the play button to see the database in action!_

This second approach of scanning the entire table was less efficient than the first in the sense that all records, including those which are not `active`, were scanned. **But** looking at this fact in isolation is misleading and may cause us to try to solve the problem in the wrong way.

We can explore this further by comparing the two approaches more directly. Check out the extra steps (work) that the database does when scanning the index:

<IxrEmbed
  data={{
    queryAst: {
      select: ["name", "value"],
      from: "foo",
      where: [
        {
          id: "94f384a3-69fc-498c-9b35-394f9ac0587b",
          key: "active",
          operator: "=",
          value: true,
        },
      ],
      orderBy: [],
    },
    columns: [
      {
        name: "name",
        type: "string",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
      {
        name: "value",
        type: "number",
        autofill: { dataType: "number", randomnessPool: "few" },
      },
      {
        name: "active",
        type: "boolean",
        autofill: { dataType: "boolean", randomnessPool: "few" },
      },
    ],
    indexes: [{ name: "foos", columns: [{ name: "active", order: "asc" }] }],
    data: [
      { _internal_id: 1, name: "Alice", value: 3, active: true },
      { _internal_id: 2, name: "Alice", value: 8, active: true },
      { _internal_id: 3, name: "Bob", value: 1, active: true },
      { _internal_id: 4, name: "Bob", value: 2, active: true },
      { _internal_id: 5, name: "Bob", value: 5, active: false },
      { _internal_id: 6, name: "Bob", value: 7, active: true },
      { _internal_id: 7, name: "Bob", value: 9, active: true },
      { _internal_id: 8, name: "Carol", value: 6, active: false },
      { _internal_id: 9, name: "Carol", value: 3, active: true },
    ],
    hovered: null,
    compare: { mode: "compare-view", compared: [0, -1] },
  }}
/>

Unintuitively and even though it is "more efficient", using the index is _slower_ than foregoing it and scanning the records in the table directly! This means that the optimizer's decision to avoid using the index is correct as forcing it to use the index by hinting it makes the query slower.

## Result Set Size Matters

This begs the question:

> _What is happening and are indexes useless?_

The reason for the behavior above comes down to what an index is and how it can (and cannot) be used. Keep in mind that it is not free or instantaneous to traverse through an index to find a piece of information. The cost to use an index can be relatively small when compared to searching through a full and unordered set of records<sup>[1](#h-footnotes)</sup> in a table, but there is additional overhead nonetheless. In general the smaller the result set is the faster and more desirable using an index will be.

We can demonstrate this point by flipping our query around to check for `false` values instead:

<IxrEmbed
  data={{
    queryAst: {
      select: ["name", "value"],
      from: "foo",
      where: [
        {
          id: "94f384a3-69fc-498c-9b35-394f9ac0587b",
          key: "active",
          operator: "=",
          value: false,
        },
      ],
      orderBy: [],
    },
    columns: [
      {
        name: "name",
        type: "string",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
      {
        name: "value",
        type: "number",
        autofill: { dataType: "number", randomnessPool: "few" },
      },
      {
        name: "active",
        type: "boolean",
        autofill: { dataType: "boolean", randomnessPool: "few" },
      },
    ],
    indexes: [{ name: "foos", columns: [{ name: "active", order: "asc" }] }],
    data: [
      { _internal_id: 1, name: "Alice", value: 3, active: true },
      { _internal_id: 2, name: "Alice", value: 8, active: true },
      { _internal_id: 3, name: "Bob", value: 1, active: true },
      { _internal_id: 4, name: "Bob", value: 2, active: true },
      { _internal_id: 5, name: "Bob", value: 5, active: false },
      { _internal_id: 6, name: "Bob", value: 7, active: true },
      { _internal_id: 7, name: "Bob", value: 9, active: true },
      { _internal_id: 8, name: "Carol", value: 6, active: false },
      { _internal_id: 9, name: "Carol", value: 3, active: true },
    ],
    hovered: null,
    compare: { mode: "compare-view", compared: [0, -1] },
  }}
/>

Now the query executes more efficiently (and faster) by using the index than scanning the table. This simple example helps demonstrate that the <LinkTodo>same query</LinkTodo> can have different optimal execution plans that are dependent on the values used in the query and the data in the table.

The change in performance here is associated with a ‘tipping point’. This particular tipping point is when the size of the result set crosses a threshold relative to the total size of the table. Our latest example above contains a result set for `false` records that represents a pretty large `22%` of the total records. Even so using the index is was still faster at that point. Somewhere between `22%` and `78%` the result set would cross the threshold where the table scan ends up being faster in this simulation. Use the link in the diagram above to head over to the playground and try to find what that thershold is!

---

### Summary

If the database is choosing to execute a query without using an index, it is doing so for some specific reason. It is generally a mistake to force the database into using some other index or plan without better understanding the reasoning for the optimizer’s plan selection in the first place.

Using the information available to it, the database will select a plan that it expects is the most efficient for any given operation. That does _not_ mean that _any_ of the plans available to it are efficient. Sometimes there simply is no ‘good’ (cheap) plan. If the optimizer is electing to perform a collection scan it is possible that there is no better plan available to it. What steps can or should be taken to improve performance depend on the specifics of the situation.

<ClosingSnippet />

---

## Footnotes

1. Unordered with respect to the query predicate(s) that we are searching on. Regardless of storage for the data, most databases have some sort of internal identifier for records that monotonically increases. That identifier is unrelated, and therefore unhelpful, when it comes to finding records that match filters on other arbitrary column values.


Indexes are incredible, but not magical. There are times when they should not be used. Forcing a database to use one when it doesn’t naturally want to could cause performance to get worse.

Care, for your database

EXPLAIN Quirks: PostgreSQL's Missing Index Usage Details

IndeX-Ray™: Imaging Technology for Database Indexes

Covered Queries

What is an Index?

Don’t (Always) Use The Index