0

One of the main reasons given for using auto-increment PK in MySQL is that it guarantees all inserts into the clustered PK index will be in order and hence fast. I understand that.

But what about secondary indexes? Say my table has a secondary index. Inserts will be in-order with respect to the PK clustered index, but out-of-order with respect to the secondary index B+ Tree.

So wouldn't the inserts still be slow because MySQL needs to be constantly re-arranging the secondary index B+ Tree as inserts are coming in?

I just wondered if using auto-increment here really is buying me anything in terms of insert performance. Would greatly appreciate some clarifications here.

Continuation
  • 12,722
  • 20
  • 82
  • 106
  • http://dev.mysql.com/doc/refman/5.0/en/innodb-insert-buffering.html and http://www.mysqlperformanceblog.com/2009/01/13/some-little-known-facts-about-innodb-insert-buffer/ – Jon Black Mar 28 '11 at 22:46

3 Answers3

1

The primary key will be clustered, which means that it directly points to the data on disk. Having to rearrange that data means that full records must be moved around. For a secondary index, it is really just a bunch of pointers to locations on disk. The secondary index has nothing to do with the ordering of the records, so having to shift pointers around in a secondary index is just that, moving pointers. This is a much faster operation than having to move full records.

Nik
  • 7,113
  • 13
  • 51
  • 80
0

Your basic assumption is only true if you have a write-only (or at least update-only) table. If you are deleting records the PKs for new records will be inserted non-sequentially (physically).

Efficiency of index inserts is almost always a secondary consideration and messing with it is a premature optimization antipattern. Have you considered the typically more significant issues of cardinality, key field lengths, cache sizes, etc.?

Using autoincrement surrogate PK's is usually suboptimal in the first place - there's usually a more useful unique key with real values that cluster in more meaningful ways. (And you can only cluster with innodb tables - you realize that, right?)

"Clustering" means the index essentially is the table. So it has a benefit when inserting a surrogate key because everything gets added to the end of the table because the next index value is always higher than any previous (as you already know.)

Unless you're filling holes created by deleted records. This may happen indirectly but can be an overhead issue because entire records must be relocated which is self-evidently more work than just moving index key values and pointers.

Clustered records don't provide much benefit for queries for single records so much as for ranges of records (e.g. items for an order, a customer, a user. If you can pick up several (or several hundred) records for the same user, for instance, that's worth clustering for. It's much less likely that records will be contiguously inserted for a single user (in most scenarios), so clustering chronologically doesn't help much. But your requirement may differ.

You didn't specify innodb so I answered primarily for myisam (the default) where only an autoincrement or chronological index would simulate clustering - there's no explicit option.

dkretz
  • 37,399
  • 13
  • 80
  • 138
  • Even with delete, all new inserts will still be in-order as far as the PK is concerned. And using autoincrement surrogate PK's is not "usually suboptimal." In fact InnoDB (the company) recommends the use of auto-increment PK's. – Continuation Apr 13 '11 at 01:34
0

From my findings:

Rows inside database tables are ordered by the clustered-index. There's only one clustered index on a table because you can only sort the rows in one way. When you define a primary key, a clustered index is automatically created on this key. So, your table is ordered by the primary key. Assuming that the index uses B+ tree implementation, the leaf node of the clustered-index are actually the pages that contain the actual rows of the database table(or pointer to the actual pages that contain the data on disk). So, when you traverse down this index, you reach the page that contain the record that you're searching for. NOTE: you must search by the primary key as the intermediate nodes in the B+ tree contain the values present inside the primary key.

When you create a secondary index(non-clustered index), the database creates a B+ tree where the values present in the intermediate B+ tree nodes are actually the value present inside the column on which secondary index has been created. As you traverse down the secondary index you get to the leaf node(which is a page) which contain the value of the primary key corresponding to the value that you're searching for. NOTE: if the secondary-index column contain duplicate values then search algorithm is such that you get to those pages which contain a set of primary keys corresponding to the value you're searching for. After you get the primary key values that correspond to the value being searched, you use the primary index(clustered index) to reach the actual page that contain those rows.

NOTE: the expensive operation in the above part is IO wherein you fetch the page from the disk and insert it into the memory(precisely the buffered_pool).

Pictorial representation - https://stackoverflow.com/a/67958216/7547722 More - https://dba.stackexchange.com/a/260337/198502

asn
  • 2,408
  • 5
  • 23
  • 37