Chuck Normal Form

The Guts of Indexing – Part 1

In my last post I used the analogy of a Library to describe indexes. However, I used very abstract ideas and did not speak to how an index in the database is structure, how it works, etc… In this post I will get into some of the guts of the most common indexes in a database: a B- Tree.

I will assume the reader has only the vaguest of ideas regarding indexes. If you are more experienced you may wish to skip ahead to later posts.

First lets talk about performance of an index on a database lookup. If you are like I was when I started, back when I needed to fend off velociraptors with my slide rule, I had the vague idea that indexes would quicken the time of a table lookup. However, how much it sped that query up was a complete mystery. Was it twice as fast? Three times? I had no idea

It turns out that searching for the appropriate record through an index is amazingly fast. For an idea of how fast imagine we have a list of 1,000,000 books and you want to locate a particular one. Further imagine the list of books is not ordered by title. You would need to look at every item in the list until you found the book. This would be on the order of 1,000,000/2 or 500,000 items on average you would need to look through.

Let’s try a different strategy. Imaging the list of 1,000,000 books is ordered by book title but there are no little index cards to tell you were each letter starts. A good stab at a strategy would be to find the middle of the list and examine the card. If you were looking for, say ‘Romeo and Juliet’ and the book at the middle was ‘Little Women’ you would know that you needed to look further in the list. If you took the same strategy again, finding the middle between the middle and the end and peeking and continued until you found your book you would be doing a binary search. For a list of 1,000,000 books you would need to do this ‘peek and search’ about 20 times. This is certainly better that 500,000 times!

Unfortunately this is still not fast enough for a database index. To see why imagine we have goofy list where the list of books has the correct number of cards (1,000,000) and each card represents a book. The cards are again sorted by book title but the cards are blank except for a card number! To determine what book the card represents you need to walk down the hall, hand the card to someone, who then finds and hands you the book. Say each time you did this it took you five minutes. Suddenly 20 peeks isn’t so pleasant. It still takes you the length of a feature movie to find ‘Romeo and Juliet’.

Let’s try again. We still need to find ‘Romeo and Juliet’ but we would like to do so before our next birthday. Imagine the following strategy instead of the binary search. We are given a card that has a card number, which appears completely random to you and 26 entries, one for every letter in the alphabet. We find the ‘R’ entry which has a related single item: another card number. Unfortunately some bureaucratic sadist has again decreed that the mapping from the random card number to a discrete card is held in that same office down the hall. Sigh. We trudge the two and half minutes down then hall, hand the card number associated with ‘R’ to the person. They look at it and tell you which other card is associated with the number. Unfortunately, again, the card you now need is back up the hall where you started. Another two and half minutes later you find the new card. This one has another set of entries that look something like

“Ra, The Egyptian Diety” – “Remy Lebeau: works in higher mathematics” : card 230942
“Ren and Stimpy – Philosophy of” – “Robert Burns – works of poetry” : card 338383
“Rockets R Fun” – “Rye Bread” : card 3982990

You find the section that would hold ‘Romeo and Juliet’ and look up the corresponding number, in this case card 3982990. You again follow the procedure until you finally locate the card with ‘Romeo and Juliet’ and it’s associated number. This time the number leads to the book itself rather than another index card. The number of times you need to make this back and forth trip is defined by the size of each ‘key’ (book title), the number of entries on each card (which is defined by the card size and the key size), and the number of total entries. In SQL Server with 1,000,000 million books and a maximum book size of 250 characters, you would expect to make about three or four trips. Much much better than 20 as now we are talking about fifteen to twenty minutes as opposed to an hour and forty minutes.

One final note before getting to Part 2. Why do I keep talking about warehouses and long hallways in these analogies? The answer has to do with the disk subsystem in a database. It takes about an order of magnitude longer to locate an object on a disk than it does to retrieve one from memory. Caching, SSD’s, and enormously fast SAN’s aside it takes about 8ms to 10ms to get a piece of data from a disk. Each lookup in an index, data page, etc… is another disk round trip (again, caching aside). I made the hallway, warehouse analogies to show this slowness in disk i/o. We will see more of that later when touching query optimization.

Indexes By Analogy

Recently I ran across a blog which tried to use the analogy of a library to describe the difference between clustered and non-clustered indexes in SQL Server. I found the post useful as a very general idea of indexes though I thought it suffered from too much abstraction. I thought I might give the same analogy a try. Full Disclosure: I don’t find the library analogy a particularly good one. There are too many things which work well in a computer system that a person would find difficult or cumbersome. With that said, lets give it a whirl.

Setup

Our library, unlike a real one, stores it’s books in a warehouse connected to the main library where the books are stored in boxes, a few hundred books per box. A library patron gets a book by asking the librarian for it. The librarian in turn asks a warehouse worker to bring the box or boxes back to her so she can get the requested book and give it to the patron.

First Pass – No indexes

This pass will be simplest version where there a no indexes at all. The books are stored randomly in the warehouse. A patron asks the librarian for all books by Agatha Christie. As the books are in random order there is no easy way for the librarian to find the books the patron wants. Rather, the librarian must ask for each box in the warehouse, open the box, and look through it for books by Agatha Christie. When she finds one, she pulls in out of the box and continues looking for more. She must do this for every box until she has looked in them all. This is a table scan and takes a LONG time.

Second Pass – No indexes, Read Ahead Threads

Obviously this is not an optimal way to get the books the patron wants. One issue is that the warehouse worker is just sitting there doing nothing as the librarian looks through the box of books the worker just delivered. Further, the librarian is just sitting there waiting for the next box to be delivered. As the librarian is going to look through all the boxes in any case, the warehouse worker could busy himself by bringing boxes of books to the librarian as she is looking through the first box. In this way the ‘waiting’ time is decreased and the librarian can scan through all the boxes without having to wait for each new box to be returned from the warehouse. This is a scan with read ahead.

Third Pass – Non Clustered Index

This is where the Library analogy begins to break down. In the original blog post there was no attempt to describe an index other than to say it was ordered by some column or columns. We will do something similar here. Understand that what is being described does not mimic a true database index. Those are B-Tree structures which are easy for a computer to traverse; a librarian, not so much.

In order to speed up the search we are going to use a card catalog. Our card catalog will be a set of drawers, one for every letter of the alphabet. In each drawer will be a set of cards, one per book, ordered by the authors last name and then the first name. In addition to the authors name and the title of the book each card will also have the box number which contains the book and the position of the book within the box. Now to find all books written by Agatha Christie the librarian would go to the ‘C’ drawer, find the beginning of the ‘Christy, Agatha’ section, and write down box number and what position the book has in the box. She then gives the list of box numbers to the warehouse worker who retrieves only those boxes from the warehouse. The librarian now only needs to look in each box and use the position number to find the correct book. Unfortunately, the books will be scattered in many boxes so it still may take some time to find them all.

Fourth Pass – Clustered index

A clustered index is similar to a non clustered index. We still have card catalogs, cards, etc.. The big difference with a clustered index is that when we build one the books are sorted by the columns the index is built on. In our example the books will be sorted by author’s last name, author’s first name, and book title. Now each box has a set of sorted books and the boxes themselves are laid out in that same order.

The same query to find all Agatha Christie books will return a much smaller set of boxes and those boxes will almost exclusively contain Agatha Christie books (there will likely be some non Agatha Christie books at the beginning of the first box and then again at the end of the last box). The librarian now needs to look in the first box for the beginning of the ‘Agatha Christy’ section and remove book after book until she hits the end of the section.

It should be obvious why can only have one clustered index: the books can only be in one order.

What’s Next?

In the next post I’ll try to show where this analogy breaks down and what the index structures, including the clustered indexes, really look like.

Chuck Normal Form

The Guts of Indexing – Part 1

Indexes By Analogy

Archives

Meta

Follow Blog via Email

Meta