Foreign 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           

Answer

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.