Query Efficiency - Filter people when name and surname are different columns, and string may appear in any of them I am working with a table representing real people data, with a schema like this (MySQL Server):

CREATE TABLE Users (
   id INTEGER PRIMARY KEY,
   name NVARCHAR(32) NOT NULL,
   surname1 NVARCHAR(32) NOT NULL,
   surname2 NVARCHAR(32),
   (more columns irrelevant to this problem)
);


From this table I need to be able to search people by name. As you can see, I have the name divided on three columns (the second surname is for accounting for Spaniards and other countries where people can have two surnames).

In lots of searches I found around the web, they usually let you put a keyword, and people with that keyword as name OR as a surname would both be retrieved. That's what I did:

SELECT * FROM Users WHERE
   (name LIKE '%keyword1%' OR surname1 LIKE '%keyword1%' OR surname2 LIKE '%keyword1%')
   AND (...same with the rest of the keywords)


It works as intended. If I send, for example, 'Mark Paul' I will get any people named 'Mark Paul' or 'Paul Mark', or 'Paul Markusson'.

However, someone pointed out to me that this query may start to take its sweet time once we start to have a respectable number of rows on the User table.

Honestly, I don't know what kind of optimization I should use for this type of query. I think MySQL can't use indexes when using LIKE comparisons starting by wildcards.

Do any of you more experienced people have an idea of what I can do or should I give up and make the app user have to search by each column separately?
If it is an innodb table you could just use 'match':
(see https://dev.mysql.com/doc/refman/8.0/en/fulltext-natural-language.html)

SELECT * FROM users WHERE MATCH (name, surname1, surname2) AGAINST ('Mark Paul' IN NATURAL LANGUAGE MODE);


But honestly i have no idea how it performs with millions of entries...

Cheers
Olaf