Back to articles list December 25, 2020 - 10 minutes read What Is a Database Index? Ignacio L. Bisso Ignacio is a database consultant from Buenos Aires, Argentina. He’s worked for 15 years as a database consultant for IT companies like Informix and IBM. These days, he teaches databases at Sarmiento University and works as a PostgreSQL independent SQL consultant. A proud father of four kids with 54 years in his backpack, Ignacio plays soccer every Saturday afternoon, enjoying every match as if it’s his last one. Tags: sql learn sql sql index Database indexes are critical to query speed and efficiency. Learn when, why, and how to use them – and when not to – in this post. Indexes are very important database objects; they optimize data access and improve database performance by helping the database execute SQL queries faster. Why not take this opportunity to learn how indexes work and how to create them? What Is a Database Index? Indexes are data structures that can increase a database’s efficiency in accessing tables. Indexes are not required; the database can function properly without them, but query response time can be slower. Every index is associated with a table and has a key, which is formed by one or more table columns. When a query needs to access a table that has an index, the database can decide to use the index to retrieve records faster. How Does an Index Work? If you’ve ever used a book index, you’ll understand immediately how a database index works. In a book index, we first search the index for the topic we want. We get the page number where that topic is found in the book, and we go to this page. It’s very simple. When the database searches in an index, the first step is to find the key value in the index. Every key value is stored with a pointer to the record in the table associated with this key value. Then, when the key value is found, the database follows that pointer and directly reads the record(s) from the table. Suppose we table with 40 million records and a schema like the following: ssnfirst_namelast_namezip_code 5436782JohnSmithZZ123459 5123456IgorChernoskyZZ123459 4325834MaryConneryAF432112 4748122SueLeclercAW543112 We run this query: SELECT ssn FROM persons WHERE last_name = ‘Chernosky’ To get the results, the database must do a full sequential scan of the table persons, which means that the database must read every record on the table and verify if the WHERE condition last_name = ‘Chernosky’ for this record is true or false. As this table has 40 million rows, the database is carrying out more than a few operations. On my local machine, this query takes 46 seconds! How to Add an Index to a Table At this point, we have a really slow query – it takes 46 seconds to return just one record. We can try to add an index to the table persons using the column last_name as the index key. The idea is to improve query performance by avoiding a full sequential scan of the entire table. Here’s how to create such an index: CREATE INDEX ix1_test ON persons ( last_name ) The syntax for index creation is simple. We need a CREATE INDEX statement specifying: The index name (here, ix1_test). The associated table (persons). The column to use as the index key (last_name). After creating the index and executing the previous query a second time, the database will do an index search for the last_name = ‘Chernosky’ condition instead of a full sequential scan. Let’s see how much time it takes. With the new index, the same query takes 15 milliseconds – 30,000 times faster! The reason behind this huge performance increase is using the index to look for last_name = ‘Chernosky’ instead of doing a full sequential scan. Remember, an index’s process is similar to the process of using a book index. Imagine how much time you’d need to find a specific topic if you decided to search for it by reading the entire book, page by page! Before closing this section, I would like to suggest the course Understanding Indexes, which has hands-on exercises that show how indexes work. Also, the article What is a Primary Key in SQL? explains the role of primary keys in SQL databases; it’s a good read if you’re not already familiar with the concept. How An Index Works Internally In SQL databases, indexes are internally organized in the form of trees. Like actual trees, database indexes have many branch bifurcations, and individual records are represented (or pointed) by the leaves. A database index tree is composed of several nodes connected by pointers. The index tree is created when the CREATE INDEX statement is executed. The database software has an algorithm that builds the index tree. The first step of the index creation algorithm is to sort the records based on the index key. Next, it builds the structure by creating and populating every node of the tree index. The creation of an index tree can take some time, especially when the table has many records. If we use an index to search for a specific record in the table, we need to start searching from the root of the index tree. On every branch bifurcation, a decision must be made about which branch to choose. This means logically evaluating the search condition and the range of values in each branch. As a very simple example, imagine you want to find the number 12 in a tree that has two branches. Branch X has numbers from 0-10 and Branch Y has numbers from 11-20. As 12 is greater than 11, you’d search for the number in Branch Y. One special kind of index tree is the B-tree. B-trees are Balanced trees, meaning that the quantity of nodes from the root to any leaf node in the B-tree is the same. We will show a graphical representation of a B-tree index. First, let’s look at the table we’ll associate with the index. It’s called part, and the index will be placed on the part_id column: part_idnamepricemanufacturer 1Touch screen m81$90Cbios Inc 2Processor quad core I4$92Xcreators Inc 5Keyboard 101K$13Xcreators Inc 7Ram Memory 265Mb$145Cbios Inc 8Ram Memory 512Mb$211Cbios Inc 11Processor octo core I8$178Xcreators Inc Next, let’s see the SQL that will create the index ix_part_id: CREATE INDEX ix_part_id ON part ( part_id ) At the time of CREATE INDEX execution, the complete index data structure is created and populated. In the following image, we can see the graphical representation of the B-tree index ix_part_id and the table part: The B-tree index is represented as an inverted tree, where the root is on top and the leaves are on the bottom. Notice that the red boxes representing leaf nodes have a pointer that indicates one record in the table. Every leaf node is a pair consisting of a key value and a pointer to the record. The intermediate and root-level nodes can store four key values (although some of them are not in use). When new records are inserted into the table, these empty places will be used to store new key values. This index can be used for searching records. Suppose the database has to execute a query to search for a specific part_id or a range of part_ids, e.g. WHERE part_id = 2. To find the record with part_id = 2, we start searching in the root of the index, and comparing 2 with the root index value 7. If the result of the comparison is “<”, we take the pointer on the left side. If the result of the comparison is “>=” we take the pointer on the right side. As 2 is less than 7, we take the left pointer to the next node and repeat the same process. When the node has more than one value, we’ll compare until we find a range where the searched value belongs and take the pointer for that range. In our example, the range for 2 is (2,5]; we take the pointer to the leaf node and see that the leaf node value is 2, so we take the pointer to that record in the table. In the image below, the green lines show how we traverse the B-tree to search part_id = 2: An index is an ordered data structure where the index keys are ordered by some criteria; thus, we can take advantage of that and use indexes to avoid sorting records. Then if we have a query with an ORDER BY or a GROUP BY using the same key as an existing index, the database can use the index to avoid sorting the records – a performance improvement! Who Chooses Which Index to Use? We can have more than one index per table as long as each index uses a different column as its key. Depending on the query, perhaps more than one index can be used to improve its performance. So, who decides the best index to use for a given SQL query ? This is selected by an internal database module called the “query planner”. The following example has a query on a table with two indexes. We will see how the database chooses the index that will execute the query faster. First, let’s add a new index to the table persons: CREATE INDEX ix3_test ON persons ( zip_code ) Here’s the query we will execute: SELECT ssn FROM persons WHERE last_name = ‘Smith’ AND zip_code = ‘12345’ In this query, the database has two indexes to choose from: ix1_test based on the key last_name ix3_test based on the key zip_code The execution of the query takes 22 milliseconds, as we can see below: We know the query has used an index, but we don’t know which index was chosen. SQL databases have an EXPLAIN statement that returns the query planner’s execution plan. The output includes several technical details which are outside the scope of this article, but it is simple to identify which index has been chosen. Let’s execute the same query, this time adding the EXPLAIN before the SELECT. We can see the index chosen was idx1_test. Multi-Column Key Indexes Index keys can be formed for one column or several columns, much like primary keys. The syntax for a multi-column key index is pretty simple: CREATE INDEX ix4_test ON person ( first_name, last_name ) We can put any combination of columns in the key of a multi-column index; however, best practices suggest putting columns that are frequently used in queries’ WHERE clauses. For example, the previous index would be very helpful on the following query: SELECT social_security_number FROM person WHERE first_name = ‘Kevin’ AND last_name = ‘Smith’ There are other WHERE conditions that can take advantage of the previous multi-column index, e.g. a query with WHERE first_name = ‘Kevin’ can also use the index, even when last_name is not in the WHERE. Another interesting facet of this topic is redundant indexes; however, due to its length and complexity, we can’t cover it in this article. For a complete review of SQL tables and the many different options available, see How to Create a Table in SQL. The Cost of Having Indexes Indexes – like most things in life – are not free. Every time a table with an index is modified by an INSERT, UPDATE, or DELETE, all the indexes associated with the table have to be refreshed. These changes take time, and the performance of a process that massively modifies tables can be affected when several indexes exist in the table. Before creating an index, we need to evaluate the cost-benefit of having it. Do we expect noticeable performance improvements? Is this table statistical or heavily modified? Can we accept a degradation in performance when we modify the table? After doing this analysis, we can decide if the index needs to be created. Another option is to create and drop indexes based on different needs; in fact, some databases do that automatically. What’s Next with Indexes? We’ve covered the basics of database indexes: The syntax for creating an index. When an index is used by a query. How to know if an index is being used (the EXPLAIN statement). When to put an index on a table. If you want to really get familiar with indexes, I suggest the course Creating Database Structure. It will teach you the secrets of creating and managing the structure of a relational database. Finally, I would also like to suggest the e-book SQL Performance Explained by Markus Winand, where you can find a lot of technical details about SQL performance. Tags: sql learn sql sql index You may also like Learning SQL for Free – Is It Worth Betting on Free Online Learning? Want to learn SQL for free? See where you can find free online courses and how to choose the perfect one for you. Read more Don't Be a SQL Noob! Start Learning with Our SQL Basics Course Find the right SQL course, learn the basics, and start on a path to success. Your job can be easier and you can earn more. Win at your career by learning SQL! Read more Our Picks for 2020’s 7 Best Online SQL Schools Looking for the best online SQL courses but aren’t sure where to start? I evaluated the top 7 ranked online SQL schools to help you find your match. Read more New LearnSQL.com Online Practice – Solve Basic SQL Questions with the SQL Practice Set We created our SQL practice set to help you master your SQL skills. Get access to our SQL online practice exercises for free! Read more Top 3 Platforms to Learn SQL Online: A Complete Comparison What is the best place to learn SQL online? It is hard to choose without enough information. I tested and compared 3 major platforms to help you decide. Read more Video Tutorial or Interactive SQL Course – Which Is Better? Decide what SQL learning method will be best for you - tutorial or course. Don't waste your time or money! Read more Subscribe to our newsletter Join our weekly newsletter to be notified about the latest posts.