12

I would like to know if there is an implicit SELECT being run prior to performing an INSERT on a table that has any column defined as UNIQUE. I cannot find anything about this in the documentation for INSERT.

I have asked some other questions that nobody seems to be able to answer - perhaps because I'm not properly explaining myself - that are related to the above question.

If I understand correctly, then I assume the following would be true:

CASE 1: You have a table with 1 billion rows. Each row has a UUID column which is unique. If you perform an insert the server must do some kind of implicit SELECT COUNT(*) FROM table WHERE UUID = [new uuid] and determine if the count is 0 or 1. Correct?

CASE 2: You have a table with 1 billion rows. Each row has a composite unique key consisting of a DATE and a UUID. If you perform an insert the server must do some kind of implicit SELECT COUNT(*) FROM table WHERE DATE = [date] AND UUID = [new uuid] and check if the count is 0 or 1. Yes?

I use the word implicit because at some point, somewhere in the process, the server MUST be checking the value. If not it would require that the laws of physics dictate that two identical rows cannot exist - and as far as I'm informed physics don't play a big role when it comes to the uniqueness of numbers written down somewhere, in binary, on a magnetic disk in a computer.

Let's assume your 1 billion rows are equally and sequentially distributed across 2,000 different dates. Would this not mean that case 2 would perform the insert faster because it can look up the UUIDs segmented into dates? If not, then would it be better to use case 1 for insert speed - and in that case, why?

This question is theoretical, so don't bother with considering regular SELECT performance in this case. The primary key wouldn't be the UUID+DATE index.

As a response to comments: The UUID in my case is designed solely for the purpose of avoiding duplicate entries because of bad connections. Since you cannot make the same entry for a different date twice (without it logically being a new entry), the UUID does not need to be globally unique - it needs only be unique for each date. This is why I can permit it being part of a composite key.

8
  • 2
    The database does an index lookup. It doesn't scan through the whole table.
    – user330315
    Jan 22, 2015 at 9:17
  • As far as I know, supplying all values in the corresponding order of the index also means that WHERE is not used anyway. This is what EXPLAIN will tell me if I do the above query: USING INDEX. BUT - is this implicitly done for each INSERT?
    – nickdnk
    Jan 22, 2015 at 9:18
  • As DBMS needs to fulfill the ACID this is not solved by using a SELECT COUNT(*) FROM table WHERE UUID = [new uuid],. A index tree is created for the UNIQUE column(s). And on insert mysql will try to create an entry in the index for the column, if there is a duplicate then it will fail, if not it will insert.
    – t.niese
    Jan 22, 2015 at 9:19
  • Okay, @t.niese - then would the performance be better in case 1?
    – nickdnk
    Jan 22, 2015 at 9:20
  • If UUID is unique anyway then adding DATE to the unique key would not make much sense because mysql could not ensure the uniqueness of UUID anymore. Referring to the docs: MySQL: Multiple-Column Indexes : [...]As an alternative to a composite index, you can introduce a column that is “hashed” based on information from other columns. If this column is short, reasonably unique, and indexed, it might be faster than a “wide” index on many columns.[...]
    – t.niese
    Jan 22, 2015 at 9:24

3 Answers 3

13

There are a few flaws and misconceptions in the previous answers; rather than point them out, I will start from scratch.

Referring to InnoDB only...

An INDEX (including UNIQUE and PRIMARY KEY) is a BTree. BTrees are very efficient a locating one row based on the key the BTree is sorted on. (It is also efficient at scanning in key-order.) The "fan out" of a typical BTree in MySQL is on the order of 100. So, for a million rows, the BTree is about 3 levels deep (log100(million)); for a trillion rows, it is only twice as deep (approximately). So, even if nothing is cached, it takes only 3 disk hits to locate one particular row in a million-row index.

I am being loose here with "index" versus "table" because they are essentially the same (in InnoDB, at least). Both are BTrees. What differs is what is in the leaf nodes: The leaf nodes of a table BTree has all the columns. (I am ignoring the off-block storage for TEXT/BLOB in InnoDB.) An INDEX (other than the PRIMARY KEY) has a copy of the PRIMARY KEY in the leaf node. This is how a secondary key can get from the INDEX BTree to the rest of the row's columns, and how InnoDB does not have to store multiple copies of all the columns.

The PRIMARY KEY is "clustered" with the data. That is one BTree contains both all the columns of all the rows, and it is ordered according to the PRIMARY KEY specification.

Locating a record by PRIMARY KEY is one BTree search. Locating a record by a SECONDARY KEY is two BTree searches, one in the secondary INDEX's BTree which gives you the PRIMARY KEY; then a second one to drill down the data/PK BTree.

PRIMARY KEY(UUID)... Since the UUID is very random, the "next" row you INSERT will be located at a 'random' spot. If the table is much bigger than be cached in the buffer_pool, the block the new row needs to go into is very likely to not be cached. This leads to a disk hit to pull the block into cache (the buffer pool), and eventually another disk hit to write it back to disk.

Since a PRIMARY KEY is a UNIQUE KEY, something else is going on at the same time (No SELECT COUNT(*) etc). The UNIQUEness is checked after the block is fetched and before deciding whether to give a "duplicate key" error, or to store the row. Also, if the block is "full" then the block will need to be 'split' to make room for the new row.

INDEX(UUID) or UNIQUE(UUID)... There is a BTree for that index. On INSERT, some randomly located block will need to be fetched, modified, possibly split, and written back to disk, very much like the PK discussion above. If you had UNIQUE(UUID), there would also be a check for UNIQUEness and possibly an error message. In either case, there is, now and/or later, disk I/O.

AUTO_INCREMENT PK... If the PRIMARY KEY is an auto_increment, then new records are added to the 'last' block in the data BTree. When it gets full (every 100 or so records) there is (logically) a block split and flush of the old block to disk. (Actually, the I/O is probably delayed and done in the background.)

PRIMARY KEY(id) + UNIQUE(UUID)... Two BTrees. On an INSERT, there is activity in both. This is likely to be worse than simply PRIMARY KEY(UUID). Add up the disk hits above to see what I mean.

"Disk hits" are the killer in huge tables, and especially with UUIDs. "Count the disk hits" to get a feel for performance, especially when comparing two possible techniques.

Now for your secret sauce... PRIMARY KEY(date, UUID)... You are allowing the same UUID to show up on two different days. This can help! Back to how a PK works and checking for UNIQUEness... The "compound" index (date, UUID) is checked for UNIQUEness as the record is inserted. The records are sorted by date+UUID, so all of today's records are clumped together. IF (and this might be a big IF) one day's data fits in the buffer pool (but the entire table does not), then this is what is happening every morning... INSERTs are suddenly adding new records to the "end" of the table because of the new "date". These inserts are occurring randomly within the new date. Blocks in the buffer_pool are being pushed out to disk to make room for the new blocks. But, nicely, what you see is smooth, fast, INSERTs. This is unlike what you saw with PRIMARY KEY(UUID), when many rows had to wait for a disk read before UNIQUEness could be checked. All of today's blocks stay cached, and you don't have to wait for I/O.

But, if you ever get so big that you cannot fit one day's data in the buffer pool, things will start slowing down, first at the end of the day, then it will creep earlier and earlier as the frequency of INSERTs increases.

By the way, PARTITION BY RANGE(date), together with PRIMARY KEY(uuid, date) has somewhat similar characteristics. (Yes I deliberately flipped the PK columns.)

6
  • So, basically, what you're saying is that I should use PRIMARY KEY(date,UUID) instead of PRIMARY KEY(int, AI) + UNIQUE (date,UUID). Each day will most likely not generate more than 10.000 rows in my case - per database, that is. The number of databases is not really something I can predict. Would this not be bad for joining? Currently all my joins are on the integer primary key. I need that and can't really change it either.
    – nickdnk
    Feb 17, 2015 at 10:09
  • If you have more data than can be cached in RAM, UUIDs slow you down terribly. PK(date, UUID) is a partial workaround that. So, yes, I am recommending such. And having one UNIQUE/PRIMARY key helps in INSERTs. As for JOINs -- Sure 4 bytes would be better than 19 (or so) for the key, but I see that is less of a problem.
    – Rick James
    Feb 18, 2015 at 1:39
  • That's too bad. I can't change the primary key now. It will break the entire setup. When you say "terribly" - how much are we talking? I was under the impression that when having a different primary key than the date/UUID the sorting and insertion of rows was not affected as the primary key is incremental
    – nickdnk
    Feb 18, 2015 at 9:07
  • Sure the data inserts are civilized when the table is being "appended" to because of an AUTO_INCREMENT PRIMARY KEY. But a secondary INDEX(uuid) (or UNIQUE(uuid)), which is a BTree, is very unruly. Each INSERT must find the seemingly random spot to do the insert into. If this BTree is 20 times as big as what can be cached, only 1 in 20 INSERTs will find the desired block already cached. On an ordinary disk, this slows down to about 100 INSERTs per second, just because of any index on UUID. (RAID striping and/or SSDs can help.)
    – Rick James
    Feb 18, 2015 at 20:38
  • Your (date, UUID) amends my previous comment by limiting the size that needs to be cached to one day's worth. Therefore, there is a chance that you can go all day before blowing out cache.
    – Rick James
    Feb 18, 2015 at 20:40
7
+50

When inserting large amounts of data in a table, keep in mind that the data ends up being physically stored on a disk somewhere. To actually read and write the data from the disk, MySQL (and most other RDBMS) uses something called a clustered index. If you specify a Primary Key or a Unique Index on a table, the column or columns participating in the key/index becomes the clustered index key. This means that on the disk, data is physically stored in the same order as the values in the key column(s).

By utilising the clustered index, the database engine can quickly determine whether a value already exists, without having to scan the whole table. In theory, if a table contains N = 1.000.000 records, the engine on average needs log2(N) = 20 operations to check if a value exists, regardless of how many columns participate in the index. For secondary indexes, a B-tree or a hash table is typically used (search the web for these terms, for a detailed explanation of how they work).

The conclusion of this article is wrong:

"... MySQL is unable to buffer enough data to guarantee a value is unique and is therefore caused to perform a tremendous amount of reading for each insert to guarantee uniqueness"

This is incorrect. Checking uniqueness does not really require any additional work, as the engine had to locate the place to insert the new record anyway. What causes the performance slowdown, is the use of UUID's. Remember that UUID's are randomly generated, whenever a new record is inserted. This means that the new record needs to be inserted at a random physical position on the disk, and this causes existing data to be shifted around, to accomodate the new record. If, on the other hand, the index column is a value that increases monotonically (such as an auto-increment INT), new records will always be inserted after the last record, meaning no existing data will ever need to be moved.

In your case, there won't be any performance difference between case 1 and case 2. But you will still run into trouble because of the randomness of the UUID's. It would be much better if you used an auto-incrementing value instead of the UUID. Also, since UUID's are always unique by nature, it really doesn't make much sense to index them with a UNIQUE constraint. Alternatively, if you really must use UUID's, make sure that you have a primary key on your table, that is based on auto-incrementing INT's, to ensure that new records are never randomly inserted on the disk.

18
  • Thanks for your response. This was very helpful. I will wait a day or two before I grant the bounty, though. So you would say that case 1 would be just as effective as case 2?
    – nickdnk
    Jan 27, 2015 at 11:23
  • Yes. For all practical purposes, you should not feel any performance difference whether you're including the DATE column in your UNIQUE index or not.
    – Dan
    Jan 27, 2015 at 11:25
  • Okay. As I commented on the other answer, how do you explain the findings of this article kccoder.com/mysql/uuid-vs-int-insert-performance ? - it seems odd to me that there is such as big difference if indexes actually work as "instantly" as you suggest.
    – nickdnk
    Jan 27, 2015 at 11:27
  • I have edited my answer to comment on the article. In my opinion, the conclusion of that article is wrong, as explained in my answer. Let me know if you need me to elaborate further.
    – Dan
    Jan 27, 2015 at 11:43
  • I've completely rewritten my answer to clarify my point. Hope it helps.
    – Dan
    Jan 27, 2015 at 12:04
1

This is the very purpose of a UNIQUE constraint:

A UNIQUE index creates a constraint such that all values in the index must be distinct. An error occurs if you try to add a new row [or update an existing row] with a key value that matches [another] existing row.

Earlier in the same manual page, it is stated that

A column list of the form (col1,col2,...) creates a multiple-column index. Index key values are formed by concatenating the values of the given columns.

How this constraint is implemented is not documented, but it must somehow equate to a preliminary SELECT with the values to be inserted/updated. The cost of such a check is often negligible, because, by definition, the fields are indexed (this overhead becomes relevant when dealing with bulk inserts).

The number of columns covered by the index is not meaningful in terms of performance (for example, compared to the number of rows in the table). It does impact the disk space occupied by the index, but this should really not matter in your design decisions.

5
  • Thank you. I beg to differ that the amount of rows is not meaningful. Take a look at this here: kccoder.com/mysql/uuid-vs-int-insert-performance - somehow the UUID is out-performed by the integer auto-increment, even significantly. This is why I was wondering how the index is selected and evaluated, as they start out equally fast.
    – nickdnk
    Jan 27, 2015 at 11:26
  • This is because the UUID ends up belonging to the clustered index, which is a big no-no, because inserts will be placed at random location on disk, causing existing data to be shifted around. Check my answer for a detailed explanation.
    – Dan
    Jan 27, 2015 at 12:24
  • While the accepted answer addresses the OP's actual concerns (which were not explicitely expressed in the question), the downvote may be unfair, as I seem to answer the question as it stands: "How does MySQL determine if an INSERT is unique?", and also I cover the comparison between the two indexing options that OP proposes.
    – RandomSeed
    Jan 27, 2015 at 13:18
  • @nickdnk: Indexing a UUID is costly once you have exceed what can be cached in RAM. Think of it this way: The 'next' uuid you insert will be random, hence possibly not cached. As the index grows, the likelihood of being not cached grows, hence the curve in the graphs there.
    – Rick James
    Feb 18, 2015 at 1:46
  • If I do it with date first, won't I only have to cache the part of the table that is on the same date? since dates are sequential won't it be less of a task to make this work right ?
    – nickdnk
    Feb 18, 2015 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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