
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


## The Problem

Here are two indexes, the first on `(score, gamerName)` and the second on `(game, gamerName)`:

<IxrEmbed
  orientation="horizontal"
  data={{
    queryAst: {
      select: ["gamerName","score"],
      from: "foo",
      where: [
        {
          id: "f3853ad9-3519-4c06-adfd-ad15d56f16de",
          key: "game",
          operator: "=",
          value: "Tetris",
        },
      ],
      orderBy: [],
    },
    columns: [
      {
        name: "gamerName",
        type: "string",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
      {
        name: "game",
        type: "string",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
      {
        name: "score",
        type: "number",
        autofill: { dataType: "number", randomnessPool: "few" },
      },
      {
        name: "certified",
        type: "boolean",
        autofill: { dataType: "boolean", randomnessPool: "few" },
      },
    ],
    indexes: [
      {
        name: "foos",
        columns: [
          { name: "score", order: "asc" },
          { name: "gamerName", order: "asc" },
        ],
      },
      {
        name: "foos",
        columns: [
          { name: "game", order: "asc" },
          { name: "gamerName", order: "asc" },
        ],
      },
    ],
    data: [
      {
        _internal_id: 8,
        gamerName: "Sky",
        game: "Tetris",
        score: 8,
        certified: false,
      },
    ],
    hovered: null,
    compare: { mode: "compare-view", compared: [0, 1] },
    showLegend: true,

}}
/>

And here is a simple query:

```sql
SELECT gamerName, score
FROM foo
WHERE game = 'Tetris';
```

How do we compare and describe the performance of these two indexes for this query?

---

## First Attempt (Metrics)

At a glance, these two indexes look like they would perform exactly the same on this data in our development environment. Descriptively, they both:

- Scanned the single entry in the index.
- Fetched and returned the single matching record from the table.
- Contain 2 of the 3 columns used in the query. The first index is only missing `game` while the second index is only missing `score`.

From this perspective the two indexes seem identical. Can they be used interchangeably for this query?

### Inspection

We can find the answer to that question by adding some more data and comparing the two once again:

<IxrEmbed
  orientation="horizontal"
  data={{
    queryAst: {
      select: ["gamerName","score"],
      from: "foo",
      where: [
        {
          id: "f3853ad9-3519-4c06-adfd-ad15d56f16de",
          key: "game",
          operator: "=",
          value: "Tetris",
        },
      ],
      orderBy: [],
    },
    columns: [
      {
        name: "gamerName",
        type: "string",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
      {
        name: "game",
        type: "string",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
      {
        name: "score",
        type: "number",
        autofill: { dataType: "number", randomnessPool: "few" },
      },
      {
        name: "certified",
        type: "boolean",
        autofill: { dataType: "boolean", randomnessPool: "few" },
      },
    ],
    indexes: [
      {
        name: "foos",
        columns: [
          { name: "score", order: "asc" },
          { name: "gamerName", order: "asc" },
        ],
      },
      {
        name: "foos",
        columns: [
          { name: "game", order: "asc" },
          { name: "gamerName", order: "asc" },
        ],
      },
    ],
    data: [
      {
        _internal_id: 8,
        gamerName: "Sky",
        game: "Tetris",
        score: 8,
        certified: false,
      },
      {
        _internal_id: 9,
        gamerName: "Ice",
        game: "Snake",
        score: 9,
        certified: false,
      },
       {
        _internal_id: 1,
        gamerName: "Sky",
        game: "Frogger",
        score: 1,
        certified: false,
      }, {
        _internal_id: 5,
        gamerName: "Sky",
        game: "Frogger",
        score: 5,
        certified: false,
      }, {
        _internal_id: 15,
        gamerName: "Sky",
        game: "Snake",
        score: 15,
        certified: false,
      },
    ],
    hovered: null,
    compare: { mode: "compare-view", compared: [0, 1] },
    showLegend: true,

}}
/>

<IXRIntroSnippet />

Even with just 4 additional records, we can already see that these two indexes _cannot_ be used interchangeably for the query. Indeed the first index neither limits the search at all nor does it [cover the query](covered-queries) to prevent records from being fetched. That means that the database had to do a full scan of the index _plus_ a full scan of the table. This index is therefore [_worse_ than a full table scan](dont-use-the-index) for the query and is useless for it.

What happened before is that we fell into the <LinkTodo>'It Works in Dev' trap</LinkTodo>. This was compounded by an inability to succinctly and consistently describe the _characteristics_ of the indexes for a given query. In particular, the <LinkTodo>ordering of columns in indexes is important</LinkTodo>. We need a quick and easy way to indicate how effective an index is for a query even when the execution metrics can be misleading.

---

## Index Rating System Overview

Enter our index rating system. Rather than reinvent the wheel, we are utilizing the tried and true method of ranking them using stars.

The guiding question behind the rating system is:

> _What makes an index good?_

We know that there are a number of things that <LinkTodo>indexes help with</LinkTodo>. These include:

- Reducing the amount of data searched when executing a query, driven primarily by column ordering in the index.
- Retrieving results in the order requested by the user.
- Returning results directly (avoiding accessing records altogether).

It makes sense to use this as the basis for the rating system, which is exactly what we have done. In short, the more effectively an index do these things (when applicable) for a query, the higher it will be rated for it.

So how well does this approach shape up when applied to the sample indexes above?

### Example Application

As the playground link will show, the ratings are:

- `(score, gamerName)` earns 0 out of a possible 5 stars
- `(game, gamerName)` earns near full marks

Why?

As noted above, the first index is not helpful for _this_ query at all. It adds a full index scan on top of (randomly) accessing the full table. The index could, however, be very helpful for a different query (such as one that finds the `gamerName`s of users with the top `score`s). The rating of this index _for that query_ would be quite different.

The second index is very helpful for the current query. The only filtering criteria on the `game` field, so this index allows for only relevant data to be processed. The only thing that could make this index more useful for this query would be to have it cover the operation (by including `score` in its definition), but doing so could improve the performance of this query by paying some cost elsewhere in the system.

---

## Limitations

Is the system perfect? Of course not.

Consider the following query:

```sql
SELECT *
FROM FOO
WHERE
  selectiveCol = 123
  AND booleanCol = TRUE;
```

The current system rates the two indexes `( selectiveCol )` and `( booleanCol )` the same. But if a filter on `selectiveCol` matches very few records whereas a filter on `booleanCol` matches many, then the performance of each would look as follows:

<IxrEmbed
  data={{
    queryAst: {
      select: [],
      from: "foo",
      where: [
        {
          id: "f3853ad9-3519-4c06-adfd-ad15d56f16de",
          key: "selectiveCol",
          operator: "=",
          value: 123,
        },{
          id: "f3853ad9-3519-4c06-adfd-ad15d56f16df",
          key: "booleanCol",
          operator: "=",
          value: true,
        },
      ],
      orderBy: [],
    },
    columns: [
      {
        name: "selectiveCol",
        type: "string",
        autofill: { dataType: "first_name", randomnessPool: "few" },
      },
      {
        name: "booleanCol",
        type: "boolean",
        autofill: { dataType: "boolean", randomnessPool: "few" },
      },
    ],
    indexes: [
      {
        name: "foos",
        columns: [
          { name: "selectiveCol", order: "asc" },
        ],
      },
      {
        name: "foos",
        columns: [
          { name: "booleanCol", order: "asc" },
        ],
      },
    ],
    data: [
      {
        _internal_id: 8,
        selectiveCol: 100,
        booleanCol: true,
      },
      {
        _internal_id: 0,
        selectiveCol: 250,
        booleanCol: true,
      },
      {
        _internal_id: 3,
        selectiveCol: 500,
        booleanCol: true,
      },
      {
        _internal_id: 2,
        selectiveCol: 123,
        booleanCol: true,
      },
      {
        _internal_id: 10,
        selectiveCol: 150,
        booleanCol: true,
      },
    ],
    hovered: null,
    compare: { mode: "compare-view", compared: [0, 1] },
    showLegend: true,

}}
/>

In this case, the two indexes would perform very differently and `( selectiveCol )` should be preferred. This is really just the data sampling problem from the beginning of this article in disguise. Apart from the suggestive column names we used here, there is no way for the system to determine how accurately that sample data reflects the actual data in the database either now or in the future.

In other words, the system currently does _not_ take the values of the sample data into consideration for the rating. That sample data _is_ important though. It is reflected in, and indeed the driver of, the efficiency metrics that accompany an index. Those metrics will always be there and provide that additional perspective that ratings alone may miss.

There are certainly some other factors that may be worth including in the future. Such factors could include constraints defined on the schema (such as a `unique` column) or the data type that the column is defined as (a `timestamp` is probably more selective than a `date` which may be more selective than a `boolean`, e.g.). We will post more about those as we roll out those changes in the future.

---

## Summary

Virtually the sole reason that indexes are used by databases is to speed up queries. Necessarily that means that nearly all discussions about indexes are focused on describing how 'good' or effective they are. While there is a lot of definitional nuance there, having a concise and consistent way to describe them is important.

We have introduced a simple and intuitive rating system to make reasoning and talking about indexes as easy as possible. Complimented by efficiency metrics and the innovative visuals powered by IndeX-Ray™, there has never been a more straightforward way to compare indexes for queries.

<ClosingSnippet />


We are introducing a system to make reviewing and comparing indexes easier.

Introducing an Index Rating System


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.

Blog

Care, for your database

IndeX-Ray™: Imaging Technology for Database Indexes

Introducing an Index Rating System

Covered Queries

What is an Index?

Don’t (Always) Use The Index