Foreign keys vs Composite keys in MySQL

user_13668802 0
Viewed 203

I have a table just like this:

USER_RELATIONSHIP
----------------------
user_id     follows_id
1           2
1           3
2           1
3           1

Both user_id and follows_id are Foreign keys that point to a User table. The USER_RELATIONSHIP table is quite large and I am frequently checking to see if a user relationship exists or not (eg. user A follows user B).

Given that these Foreign keys are indexed, is SQL able to find a relationship (given a user_id and a follows_id) in O(1)?

If not, is it more performant to condense the two fields above into an indexed Composite key that hashes a user_id and a follows_id and having the USER_RELATIONSHIP table like this?

USER_RELATIONSHIP
----------------------
composite_key
298437920           
219873423           
918204329          
902348293
mysql sql
2 Answers

Storing into an index a string that is the result of a hash function does not make it a hash index.

It's still a B-tree index, and lookups take O(log n) time.

In MySQL, the common storage engines InnoDB (the default) and MyISAM do not support hash indexes. Only Memory and NDB storage engines support hash type indexes.

See https://dev.mysql.com/doc/refman/8.0/en/create-index.html:

enter image description here

There is no way to do an O(1) lookup in InnoDB.

There's no difference in complexity between using a multi-column index vs. an index on the string result of a hash function.

Bill_Karwin_208600

It is not more performant to condense the data into a single column. I'm rather curious why you are even asking.

If you have a compound index on (user_id, follows_id), then the lookup is in O(log n) time -- the log of the number of rows in the table. That is pretty tiny for most tables. And, if the table is so large that the index lookup time is measurable, then you need the index all-the-more.

user_11440350
Related