Dr. StrangeTree or: How I learned to love the index!
Tags: mysql
Published: 2020-04-25 15:48:37

Designing an efficient index for a huge table is a challenge, and trying to understand why your index is not performant or "slow" can get very annoying. This is mainly because designing an index is hugely tied to how you're going to query that table! I found plenty of resources and "best practises" on choices to make when creating an index. But what helped me understand and debug some of the issues I faced was understanding the "whys" behind these choices!

Since I started working in my current position at Dalia Research and facing real-world magnitudes when it comes to data size. I started realising that I need to refresh my knowledge on how indexes work in relational databases to start optimising our queries!

My aim here is to explain how BTree indexes look like, and use this understanding to make better decisions when indexing and querying. So not only enumerate some "best practises", but also try to highlight how they originated.


#### TLDR; Here you go the short version..

1. Ordering of index columns should be based on which fields are queryable and how they are queried!
2. If one of the columns used for equality is going to be queried alone, then it should be the first column.
3. Fields used for equality should always come first. Fields that are only used in Range queries ( >, <, between) should come last!
4. Following on 3, having two columns that are queried by range queries in the index have no added value. Only include the first one.
5. Does cardinality of a column matters? Yes! But not on its own, the overall cardinality of the index is what matters.
6. Indexes can take too much space (due to info stored on leaf nodes, pointers to the row ID, info stored on branch nodes as well). Big indexes will make the insertion and deletion slow


## Anatomy of an Index

_If you're still here, let's look how BTree indexes look like_

In MySQL and Postgres, the default type of indexes is a BTree. A BTree stands for “balanced” tree (not binary). Which means a tree where all the leaves have the same distance from the root as each other. Most BTrees are B+Trees, which means that the desired information (ex. the row ID referencing the main table) is stored in leaf nodes. This means that search needs to go through the whole length of the tree.

Leaf nodes are all linked together (they're actually a linked list). The reason for this is to have the ability to traverse through them once the search went through its path. More on that later!

Now, given that the BTrees are always balanced. This means that reaching the depth of the tree is in order of O(log(n)) (This is good).


<mark> In summary, there's two ways of traversing the BTree.</mark>

1. Traversing From Root to Leaf. Which is very fast, and needs to happen in all cases.
2. Traversing the leaf nodes (RANGE SCAN). Which is slow and should be minimised as much as possible.

A simple BTree index of ids can look like this:


![simple_single_column_index](https://docs.google.com/drawings/d/e/2PACX-1vT8lwos41mJoQK2ncWz73GD5IbM6NF3L9OAdH3c0KSrF-u9hVbe7qlpVT30YbHqSAEL_MAB5h8aRyB7/pub?w=960&h=720)

Where: 
- Each value `x` in a non-leaf node has a pointer to another node with values `<= x`
- And each value in a leaf node has a reference to the the corresponding row in the original table.
- And all leaf nodes are connected together as a linked list (via pointers) so that traversing them is possible.

Now let’s trace a sample search in the above segment.If we are looking for _id = 16_ 

1. Start at the root
2. Follow the pointer where 16 is not larger than the value of the pointer
4. Repeat until reaching the leaf node
4. Find all entries where id = 16 and return

_Straightforward right?_



### What does a multi-column index look like?

The first thing to note is that the length of the tree gets longer as we move from one column index to multi column index!

![simple_multi_column_index](https://docs.google.com/drawings/d/e/2PACX-1vRAnmcjnr9s1F0vHXK1wdWjR-QQ1ie97GfBoJUlPjBybGNOANyvBDQPCj1iuD6J7kUEvh25TvK7HCMs/pub?w=960&h=720)

The main order of the tree is based __only__ on the first column. The ordering of the second column is only relevant in regards to the value(s) of the first column. (i.e. above tree ordered by the id)

Meaning that we might find entries for a given value of the second column, in two completely parts of the tree. <mark>And therefore the index is not useful for looking for only the second column in the tree.</mark> (ex. You can see _Dublin_ values scattered in different places)!

Think of it as a telephone directory sorted by last names. Looking only for the first name isn't going to get you anywhere unless you know the last name.

_Now, you might think; so what difference it makes if we use equality or range operators? And why should have columns used in equality comes first?_

#### Equality operator (=)

As a simple example with the tree above as a reference. If we are looking for rows with id = 16 and city = “Sao Paolo”, this is the rough path the search is going to take.

`SELECT * FROM table WHERE id = 16 AND city = “Sao Paolo”`

1. Starts from the root
2. Follow the pointer of the nodes till reaching the leaf node where _id = 16_
4. Traverse that leaf node till finding row(s) with city “Sao Paolo”
5. Return


Now, as pointed out, if we are looking for rows with only city “Sao Paolo”, the index is actually useless. As rows with city “Sao Paolo” can exist anywhere in the leaf nodes.

#### Adding Range operators (>, <, BETWEEN)

Range operators are where things can get slow. <mark>Because whenever we are dealing with ranges we start doing wider INDEX RANGE SCAN which is traversing the leaf nodes of a tree, and this is the most expensive operation that can be done on a tree</mark>. And it’s very important to have the structure of an index in one’s mind in order to optimise those.  

We will consider two examples to demonstrate how choice of order of columns and knowing that one of them will be queried using a range operator, **is very important.**

**A)** Taking the same tree above as a reference, if we are looking for rows with id = 16 and "Berlin" <= city <= "Sao Paolo" _(i.e equality come before range)_

`SELECT * FROM table WHERE id = 16 AND city BETWEEN "Berlin" AND "Sao Paolo"`

1. Starts from the root
2. Look for entry where `id = 16`
3. Reach a leaf node and finds the first entry with `id = 16`
4. Traverse the leaf node till finding rows with city greater than or equal “Dublin”
5. Start storing the corresponding row_ids to return
6. Stop when reaching a row where city > "Sao Paolo" and return


Note that this is where the fact that leaf nodes are connected come in handy. Search will keep going from one leaf node to the next until finding all the required range.

**B)** Now taking the same tree above (with same column ordering) as a reference, but instead we are looking for rows with 12 <= id <= 16 and city = “Cairo” _(i.e range comes before equality)_

`SELECT * FROM table WHERE id BETWEEN 12 AND 16 AND city = “Cairo”`

1. Starts from the root
2. Search till reaching a leaf node that have the first `id = 12`
4. Start traverse _all_ the leaf nodes and find the rows with `city = “Cairo”` where `id = 12`
5. Repeat (4) for all the values in the range (12 to 16).
5. Stop when reaching the next id after the higher bound (16)

It's clear that in **B)** there is more scanning of the leaf nodes. Because for every id in the range we need to scan the tree to find the values where `city = Cairo`.

From here came the rule of <mark>“Always put columns used in equality checks first”. Because equality checks help _zooming_ in as much as possible on a smaller segment, that is then either returned or further scanned for a range check.</mark>

### ZOOM ZOOM ZOOM (Cardinality)

_Does cardinality of a single column matters on its own?_ 

There’s a misconception that columns with high cardinality should come first. <mark>This is not true, because what really matters is the cardinality of the index as a whole; each column helps in zooming in and it’s important that the combination of columns used, in index and equality operators, divide up the tree in a way that the range scan at the end is as small as possible</mark>. We can have 3 columns each with low cardinality, but together they can nail down the search space to a very small region.

Cardinality is still important to think about of course. If, for example, there’s a column that is string and only has 5 values (ex. branch_name). Then it might be the case that it’s not helping. <mark>Actually it might be harming, because it can take up a lot of space (stored in all leaf nodes + non-leaf nodes) and make the index bloated. It can also affect the performance of insertion and deletion, since it’s one more column to take into consideration when re-ordering the tree.</mark>

_**Cardinality** of a column is how variant the values of this column are. A `branch_id` column in a restaurant `customer_orders` table  has low cardinality because a restaurant might have only 3 branches. Where `invoice_id` has very high cardinality because there are millions of them._

### Coming back to those points

#### 1. Ordering should be based on what fields are queryable (obvious)


#### 2. A field that is queried on its own but also queried with other fields should be indexed first.


#### 3. Fields used for equality should come first. Fields that are only used in Range queries ( >, <, between) should come last
The idea here is to limit and postpone the INDEX RANGE SCAN (traversing the leaf nodes) till the very end. 

#### 4. Similar to 3, having two columns that are queried by range queries will be slow and its not worth having both of them in the index.
Keeping in mind that the index is sorted based on the first column. And per each value for this column, the values for the second column are sorted. Therefore having two ranges would mean that after identifying the range for the first column, the search need to iterate over all these rows to pick what suits the required range of the second column. Which, in most cases, is as performant as doing the same on the main table. 

#### 5. Cardinality of a column matters? Yes! But not on its own, the overall cardinality of the index is what matters.
A column may have a very low cardinality on its own, but in combination with another column, they can have a very effective division of the DB. 

#### 6. Indexes can take too much space (due to info stored on leaf nodes, pointers to the row ID, info stored on branch nodes as well). Big indexes will make the insertion and deletion slow
Ex. Be careful with indexing a text field that has low cardinality (repeated a lot) and does not divide the search space in a useful way. 



### Summary

The index structure explained here is very very simplified and it aims at explaining the "why" to the rules of thumbs of indexing. Every DB engine has its own further much more sophisticated optimisations over how indexing work, but the minimum understanding of the structure of indexes is important to make reasonable decisions of what to index and how to query it.










https://docs.oracle.com/cd/E18283_01/server.112/e16508/indexiot.htm
https://use-the-index-luke.com/sql/where-clause/the-equals-operator/concatenated-keys