I've got a table full of bricks here. I'm looking for all these red, star-shaped
ones. No matter how hard I try I can't seem to find them all! What I could do is
go through and look at every single brick to see if it's what I'm looking
for. But that's gonna take a while. It'd be much better if I had a list stating
the color and shape of every single brick and its exact location on the
table. With this I can then look up where the red stars are and then easily find
them all. Without having to look at every single other brick. A database index is
the same idea. It stores the values from the index columns and pointers to where
those rows are in the table. So with this you can find a few rows quickly. So
how do you create indexes and how do they make your SQL faster? Let's find out!
To create an index simply give it a name. State which table it's on. And list
the columns you want to index. The index then stores the values in these columns
along with a pointer to the row which has this value. With the index in place
every time you insert, update or delete a row, the database changes the
corresponding index entries. So once it's in place you can benefit from faster
queries without any further action on your part. Note Oracle Database only
indexes rows where at least one column has a non null value. If all the columns
are null then that row doesn't appear in the index. OK, but how is using the
index any more effective than reading the table itself? Well for a start the
index is - usually - a smaller data structure than the table it's on. You're
only storing values from the indexed columns and their row pointers instead
of every single column in the table. So it's just less work to read every entry
in the index than it is to read every row in the table. But the real power of
indexes is they enable you to find a few rows quickly. So how do they do this? We'll
find out by looking at the most common index structure in relational databases,
the B tree. As you can probably guess by the name these store values in a tree
structure. Each node in the tree is a database block. And like all trees the
index starts and it's root. If you create an index on the bricks' weight, the root
splits these weights into ranges along with a pointer to a child block for each
range. Each of these children then further split the range into the smaller
sub-ranges and so on down the tree until you get to the leaves. These leaves store
each non-null weight value and a pointer to the row with that value. If you want
to use this index to find the value 2, you start at the root and see this value
falls in the first range. So you go to the leftmost child. From here again you
see that two falls in the first range and go to the leftmost child where you
can find a pointer to the row. So that's three IOs to read the index. It's also
three IOs if you want to find the value 991. But this time you work along the
right-hand edge of the index. In fact, it's three IOs to find any single index
entry. This is because all the leaf blocks are at the same depth and the row
pointers are only in the leaves. This is a key feature of B trees: they are
balanced. So it's the same amount of work to find any single entry; which in
computer science terms is order log N. So even for a table storing millions of
rows you can find any one row in just a few IOs. This makes them incredibly
efficient for single row lookups. But what if many rows have the value
you're searching for? A B-tree is an ordered
data structure. It sorts all the leaf entries by the column values, then the
row pointers. So consecutive values are next to each other. And the leaf blocks
form a doubly linked list, with pointers to the next and previous leaf block in
the series. So if you want to find all the rows with weights between 90 and 110,
the database starts by searching for the smallest value that's greater than or
equal to 90. Once it's found this, it then walks along the leaves until it hits the
upper limit. So again this is nice and efficient. You just walk down the index
once, then across however many leaves match your search. So you created your
nice, shiny new, index. How do you know if the database used it? Just look for the
index name in the execution plan! There's an index on color. So this query can
count all the red rows using an index range scan of that index. But we're only
searching for one value. So why is it scanning a range? Remember the index has
an entry for every single non-null row. So to find all the red rows, the database
must walk through - scan - all the red entries in the index. So it's working
through a range of entries in the index. This is the most common form of index
access. But, there is a special case where the database is guaranteed to find at
most one row: an index unique scan. This happens when you've got equality
conditions on all the columns of a unique index. These guarantee that at
most one row can have a given set of values for the index columns. This
prevents duplicates and improves data quality. You create one by adding the
unique keyword to your create index statement. You can also get one by
defining a primary key or unique constraint. If there's not already an
index on these columns the database will create
unique one for you automatically. Finally the database may read every entry in the
index with an index full scan. Like a full table scan this reads the whole
index. The simplest case where this can happen is when your query only selects
the columns in an index without a where clause. Because the index is usually
smaller than the table it's quicker to read the index than the table. This highlights
another benefit of indexes: they can make your SQL faster by avoiding
the table altogether! Let's say I want to find my red brick here. So I'll get my
red brick, get rid of all these other ones
Bit noisy! Just get it so we've got just the red bricks and once I've done that
I want to group them by shape.
So we'll get the cubes there, those cuboids there, and these other various
shapes here. And then once I've done that I want to count how many have got of
each shape. If the table only has an index on color it can use this to get
the red rows. But it has to go to the table to find all the shapes. Which you
can see by the table access by index rowid operation. If instead you create an
index on color and shape then once again the database can read just the index,
potentially saving itself a lot of work. So if you have a multi column index, how
does a database store and search these values? The index sorts the rows using
the columns as they appear in the index, left-to-right. So an index on color, then
shape first splits the rows into color ranges. Then subdivides these into shape
ranges. So if I'm looking for red cuboids, we find the red entries then search
within these for the cuboids. We can also use this index when
searching for all the red bricks. Just find the first red entry, ignore the
shape, and return all the rows from this section of the index. So you've created
some indexes, looked at execution plan, and found: the database
isn't using any of them! Why?! Well there are two fundamental reasons for this.
Firstly the database may be unable to use the index. Secondly it may have
decided it's just more work to use the index then read the table itself. We'll
explore the second reason in the next episode. For now we'll focus on what
makes the database unable to use an index. In the previous example we created
an index on color and shape. Which gave a nice performance boost for our query
finding all the red bricks and grouping them by shape. But what if we want to
find all the cubes of any color? This column is second in the index. So the
index first sorts the rows by color and the cubes are spread throughout the
whole index. Meaning we're no longer restricted to a small section of it and
we'll have to read the whole thing. So the database is unlikely to use it. To
avoid this problem, ensure that the leftmost columns in the index all appear
in your where clause - ideally with equality conditions. But even when you do
this there can be another problem: applying functions to the columns in
your index. For example, let's say customers have entered colors in all
sorts of case. Some are lowercase, some are upper, and some are crazy mix
of the two! There's an index on color, so when searching for rows in a specific
case the database will use it. But what if you want to find all the red bricks
regardless of case? You could uppercase the color column and compare this to the
text RED in capitals. But do this and you'll find that the database no longer
uses the color index. So why is this? And what can we do about it? The values
stored in the index are the regular column values. To ensure that we only
find entries matching your search you need to go through every single index
entry and apply the function to it. Which kind of
defeats the point of having an index, right? Now at this point you might say,
"Isn't upper casing the text lowercase red the same as RED in capitals
obvious?" Well perhaps to us humans. But computers are pretty dumb. The only way
it knows this for sure is to run the function! Luckily there is
a way around this. You can store the result of the function in the index by
creating a function-based index. To do this use the function in your create
index statement and the database stores its result in the index. To ensure the
database uses this index, use the function in your where clause in exactly
the same way it appears in your index. Even small differences can stop the
database using it! But it's better if you can avoid applying a function to the
column altogether. For example. instead of adding one to a column, subtract one from
your search variable. So to give the database the best chance of using your
index ensure that the leftmost columns of that index all appear in your where
clause and that you apply no functions to the columns in the index. But even
when you do this the database may still decide not to use it at all! We'll
explore further why this can happen in the next episode. Thanks for watching!
Have you got any more questions about how to create indexes or the index types
available in Oracle Database? Let us know in the comments and subscribe for more
SQL tips