27 Dec 2011

Explaining Indexes with a Library Metaphor - Reloaded

I wanted to build on the metaphor I used to explain indexes and continue a bit further into disk and memory usage.


Sorting without index cards

Let us say that we would like to get a list of all books written by J.R. Hartley and we would like this list ordered by the most recently published books.
What we would do is:

  • Enter the library
  • Speak to our trusty librarian about the list that we need
  • The librarian would consult his or her index cards and would then give us a list of where all those books are on the shelves in the library. 
  • We then head over to find those books in the different positions in the library.
  • Once located, we can do one of two things in order to sort the books:
    1. We can get the information we need from the books and simply remember the list and sort it in our heads (in memory)
    2. We can take all the books over to an available desk (temporary table on disk) then take a pad and pencil and write down that information on it. After that is done, we can sort that list on the pad and produce the list we want.

As you can imagine, doing calculations in memory would be much faster than sitting down next to a table and writing it down. The reasons why we would prefer to write it down would be:

  1. The list of items would be too long to keep in our memory.
  2. We may need to keep a text that is or may be too long  to hold in our memory (such as text or blob datatype).




Sorting with index cards 

Let us suppose that the piece of information we need is kept within the librarian's index cards.
What we would then do is:

  • Enter the library
  • Ask for the index cards from the librarian
  • Place it on his or her counter and change their positions until they are in the order that we want. 
  • Leave the library with the ordered list that we wanted
http://blogs.fashion.arts.ac.uk/snapshot/2007/10/24/student-focus-group/ 

As you can imagine, using indexes to sort the data can be much faster than the alternative.


How can we use indexes to speed up our sorting?

One example of where you can use indexes to speed up your sorting is by using a multi-column index in your table structure. The index you set should first cover the search condition and then cover the sorting requirement.
For example:
SELECT * FROM table1 WHERE a = 100 ORDER BY b

Your index should be idx_sort(a,b)


Try it out on your own system and see if you notice any improvements!