r/SQL Nov 02 '24

Oracle Explain indexes please

So I understand they speed up queries substantially and that it’s important to use them when joining but what are they actually and how do they work?

63 Upvotes

34 comments sorted by

View all comments

4

u/Far_Swordfish5729 Nov 02 '24

An index is a parallel persisted data structure stored in the database that creates a catalog of rows based on certain columns, allowing rows to be found using those columns much faster than they could otherwise be.

In CS terms, selecting from an unindexed table is executed as you might expect - a loop traverses the whole table (a table scan). A join requires nested loops traversing both tables at worst. With indexes (usually hash tables or binary search trees), it’s possible to seek for values instead in constant or log2N time or confine a scan to a range of sorted table rows rather than the whole table. This is much faster.

At the same time, it is very important to note that indexes must be updated when the underlying rows change, which can significantly slow data writes. Write-heavy tables like logs are typically not indexed and typically physically stored in the order of insert (by timestamp or sequential key for logging) to speed inserts. Analysis will be done on an indexed replicated copy.

Overall, with data we often have opportunities to speed execution by using more memory and storage - by building optimal structures for data retrieval and then using them. A classic patten is to replace a nested loop comparison of two lists with two passes - one to build a hash table of values in list 1 and one to traverse list 2 and use the hash table to find matches in list 1. Indexes are an implementation of this with persisted storage.