Suppose I have user table my_users
in which there is a primary key id
. Also, I wish to design (in MySQL) a simple blacklist table, whose declaration looks like this:
CREATE TABLE IF NOT EXISTS black_list (
user_id INT NOT NULL,
bad_string VARCHAR(100) NOT NULL,
FOREIGN KEY (user_id) REFERENCES my_users(id),
PRIMARY KEY (user_id, bad_string));
The interpretation of any row in the black_list
is that a user with the ID user_id
wants to blacklist the string bad_string
. Obviously, user_id
cannot be unique since a single user may have more than one blacklisted string. Other way around, bad_string
cannot be unique since more than one users may have blacklisted the same string. However, the pair (user_id
, bad_string
) should be unique since it makes no sense for the user to black list the same string more than once.
When we select a black list via a user ID (SELECT * FROM black_list WHERE user_id = X
) in the worst case, MySQL will have to scan the entire black_list
table.
My question here is: is there a way for running the above SELECT
statement in sublinear time with regard to the number of rows in the black_list
table? If yes, how can I accomplish that?