0
309
ViewsForeign keys vs Composite keys in MySQL
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
2 answers
Answer question0
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:
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.
0
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.