Suppose I have a MySQL table with a unique integer index id that is auto-incremented for each row.

id | PlanetName
 0 | Mercury
 1 | Venus
 2 | Neptune

Suppose that I am primarily interested in optimizing queries that look up rows by the unique index. For example:

SELECT PlanetName FROM Planets WHERE id = 2

If I were programming in another language and I had the data loaded up into an array, then it would be very quick to perform these lookups by pointer arithmetic. I would like to be able to get the same sort of performance when I carry out the queries in MySQL.

My thinking is:

  • a clustered index means the data is stored sequentially (i.e., very similarly to how a primitive array is stored in memory)
  • a unique integer index ensures that SQL does not have to worry about duplicate rows

So if I create a unique clustered index for id, does that mean that MySQL will carry out a pointer arithmetic-type lookup?

  • (1) Yes. Clustered index is an index where physical ordering of records matches their logical ordering by clustered index expression. (2) Yes. Any unique index (including primary) forbids index expression duplicated value insertion. – Akina Feb 13 at 11:28
  • @Akina So does that mean that lookups by the index happen in constant time (in the number of rows)? – John Gowers Feb 13 at 11:32
  • No. Sequental data in a file does not mean sequental clusters chain on disk. But when the index is cached in memory it doesn't matter does it is unique (the more clustered/primary). – Akina Feb 13 at 11:39
  • "array-like lookup performance" - do you mean O(1)? – akuzminsky Feb 17 at 17:42
  • @akuzminsky Yes, but more specifically that it performs a similar sort of procedure to get that O(1) performance - i.e., compute an offset and go to the data at that offset. – John Gowers Feb 17 at 20:37

Yes and no.

An "array" in a programming language does some trivial address arithmetic to quickly locate the Nth entry in the array.

In MySQL, most indexes are built as B+Trees. (See Wikipedia) This structure is more complex than an array, but still the best available. WHERE id=2 requires drilling down a "tree" of nodes to locate the item with "2" in the "id" column.

A BTree has several advantages over a simple array. And these advantages are necessary for the generality of database operations.

  • Database tables are designed to handle an arbitrarily large number of items. Arrays are limited to what can fit in RAM. This effectively prevents the address arithmetic of arrays, and forces some other implementation.
  • You can DELETE * FROM t WHERE id=2. (Arrays don't allow holes; BTrees do.) Note that it prevents the use of "address arithmetic" to locate a record.
  • A BTree index can use a string for lookup -- WHERE name = 'Venus'. And this works as easily and almost as fast as using numbers.
  • Since BTrees are "blocks"; they get scattered around and they could become empty. This leads to the overhead of maintenance of the tree. Don't worry about this; BTrees are still very fast, on average.
  • "Clustering" in this context implies that ids 1,2,3,... are "consecutive" and "adjacent" in some sense. (Or "1,3,...", if id=2 has been deleted.) In practice, there are about 100 consecutive values sitting in one B+Tree block. This allows for "range" to be very efficient. Example: WHERE name BETWEEN 'Mars' AND 'Venus' would be store alphabetically.
  • When a 'range' query runs off the end of a B+Tree block, the next block is linked from it. (This is the "+".)
  • Technically, array lookup is O(1) and a BTree lookup is O(logN). But the log is not that big a number -- A BTree for a million rows is about 3 levels deep; for a trillion rows, only about 6 levels deep. That is, looking up a row in a trillion-row table is only about twice as slow as in a million-row table.
  • MySQL (InnoDB specifically) requires a unique PRIMARY KEY and clusters it with the data.
  • Hence, a lookup by the PK (WHERE id=2, if id is the PK) is one drill-down of one BTree to get to the entire row.
  • A secondary index (not the PK) is implemented as a B+Tree with the key column(s) plus the column(s) of the PK.
  • Hence, lookup by a secondary key (SELECT * FROM t WHERE name='Venus' with INDEX(name)) is a little more complex. First drill down the name index to find the id, then drill down the PK+data BTree to find the entire row.
  • Prevention of duplicates -- This happens when INSERTing or UPDATEing a row. Effectively, it looks up the row via the PRIMARY KEY (if given -- cf AUTO_INCREMENT) and via every UNIQUE index. If any of those are a match, you get an error (unless doing INSERT IGNORE). Otherwise, the PK's BTree and the Unique BTrees are poised to take the new/modified row. Dealing with potential dups is not free, but cheap.
  • For a BETWEEN, the first row is accessed (O(logN)), then each subsequent row is O(1).

So, yes, an array lookup takes nanoseconds, which is faster than a database lookup, which takes microseconds (if cached in RAM), or milliseconds (if I/O is needed). That is the price you have to pay for unlimited size and many more features.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.