Algorithmic order of table indexes for table operations

Question

I have not been able to find a clear indication of the impact table indexes have on the algorithmic order of table operations.

I am not interested in the nuts & bolts of specific implementations; I assume RDMS designers know what they are doing and they have made these as efficient as possible.

I am going to limit my discussion to a single index, I think that additional indexes simply add an additional dimension (i.e. the fundamental process has to be performed more than once).

The following assumes a single record in each case - the benefits of indexes are greatly enhanced for multiple record operations because (generally) the seek operations need to be done less times than the number of records being sought as they can be retrieved in a range.

For an unindexed table I believe the operations are:

Step                INSERT     SELECT     DELETE     UPDATE
Find the record      N/A        O(n)       O(n)       O(n)
Modify the record    O(1)       N/A        O(1)       O(1)
OVERALL              O(1)       O(n)       O(n)       O(n)

This assumes that finding the record requires a table scan but a new record is simply slammed onto the end.

To set up an index is an O(nlog(n)) operation based on an efficient sorting algorithm.

For an indexed table I believe the operations are:

Step                INSERT     SELECT     DELETE     UPDATE
Find the record      N/A      O(log(n))  O(log(n))  O(log(n))
Modify the record    O(1)       N/A        O(1)       O(1)
Update the index   O(log(n))    N/A        O(1)       O(1)
OVERALL            O(log(n))  O(log(n))  O(log(n))  O(log(n))

This assumes that finding the record is now an ordered lookup operation on the index and updating the index is a single step for DELETE and UPDATE (because you have already found the record) and an ordered lookup for INSERT

That is, inserts get worse but everything else gets better.

Is this correct?

Answer 1

Things are more complicated than that. Here are a few points of consideration.

First, this entire discussion assumes B-Trees or B+ Trees (Hence the o(log(n))). There are other types of indexes, like hash indexes, where access is in O(1). Your question insinuates you're looking up values using "equals" search (e.g. looking for X=17). But in this particular scenario, a Hash index is preferable, when possible.

I do agree though that most indexes you'll find today are B/B+ Trees, so let's continue with this assumption.

You've also implicitly indicated that there's always only one resulting row in a SELECT, which is hardly a representative case; plenty times do we look for 1,000 rows at a time. But let's continue with the assumption of a single matching row.

Your next assumption is that searches are always done by the indexed column. This is fine, but I'm just noting that DELETEing a record by some unindexed column Y turns out to be more expensive: you're both wasting O(n) time in finding the record, and then paying an additional O(log(n)) for updating the index.

But let us continue with the assumption that we're only discussing queries which are looking up at indexed columns.

Some tables use unclustered index format (which fits into your calculations) - the table is one entity and the index is another. Others use clustered index format: table rows (or rather blocks of rows, or rather yet pages of rows) are actually stored as leaves inside the clustering index. In such scenario, you will pay O(log(n)) for finding a record in an INSERT command. An optimization for that is in the case you're inserting to the end of the table, and a decent implementation would hold a pointer to the last record/page in the index. (Oh, yes, you should not the possibility that your record gets INSERTed to the middle of the table).

Actually, records could get inserted to the middle of the table even in unclustered tables; it would make sense to spend more search time so as to avoid fragmentation, and at least one implementation that I know of does that. I'm assuming other may, too.

Deleting/Inserting an index from a BTree is O(1) on average, but may cost up to log(n) operations in case of propagated page merging/splitting.

Also, the fact that always comes as a surprise to many, is that sometimes a table scan is faster than index lookup. This is particularly true for queries resulting in multiple rows. It turns out looking up the index adds overhead; when compared to full table scan the overhead could actually make total cost higher. For single row lookup the vast majority of index lookups should be faster than a full table scan.

But do consider the following general convention: you pay with dollars any action that accesses disk. You pay with nickels actions that act on in memory data. This is actually at the heart of database disk I/O optimization. If index pages are on disk, and table pages happen to be in memory, you will possibly pay less for table scan.

And that's where havoc comes in: it really all depends on your workloads, on your memory size, on your dataset size.

Did you ever take a math class where you had to solve some complex integral? It took you hours to solve it, and got point off for missing some tiny minus sign somewhere?

Did you even take a physics class where you had to solve some complex integral? The professor would just throw away chunks of the equation, saying "this is neglect-able", and you would rip your hair off? WHY is it neglect-able? Why not other things?

Computer science is based on math. Computers are based on physics. They are physical objects. They need to spin disks, access a memory bus, manage billions of transistors... You just can't actually anticipate what will happen and put it all under some equation.

It may just turn out that for some particular dataset your entire equation does not hold water. In other times, it may be just fine.

Answer 2

Indexes will normally speed up updates and deletes as it be quicker to find the particular rows. Keep in mind that there is overhead for updating indexes and each additional index will add to this. I believe updates only update indexes when an indexed column is being updated.

Also take into account the effects on queries that cannot be optimized through the use of an index. This will slow down deletes and possibly updates.