Text search across multiple tables using MySQL

query.sql

select
  first_name,
  last_name
from
  users
left join
  companies on companies.id = users.company_id
where (
    companies.name like 'TERM%' or
    first_name like 'TERM%' or
    last_name like 'TERM%'
)

sample_data.md

Find the sample data here:

https://gist.github.com/reinink/30210fd48ef0435f475ed9d13270b09e

schema.txt

Companies

+------------+-----------------+------+-----+---------+----------------+
| Field      | Type            | Null | Key | Default | Extra          |
+------------+-----------------+------+-----+---------+----------------+
| id         | bigint unsigned | NO   | PRI | NULL    | auto_increment |
| name       | varchar(255)    | NO   | MUL | NULL    |                |
+------------+-----------------+------+-----+---------+----------------+

+-----------+------------+----------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table     | Non_unique | Key_name             | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+-----------+------------+----------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| companies |          0 | PRIMARY              |            1 | id          | A         |       10106 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| companies |          1 | companies_name_index |            1 | name        | A         |        8624 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
+-----------+------------+----------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+

Users

+------------+-----------------+------+-----+---------+----------------+
| Field      | Type            | Null | Key | Default | Extra          |
+------------+-----------------+------+-----+---------+----------------+
| id         | bigint unsigned | NO   | PRI | NULL    | auto_increment |
| company_id | bigint unsigned | NO   | MUL | NULL    |                |
| first_name | varchar(255)    | NO   | MUL | NULL    |                |
| last_name  | varchar(255)    | NO   | MUL | NULL    |                |
+------------+-----------------+------+-----+---------+----------------+

+-------+------------+--------------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table | Non_unique | Key_name                 | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+-------+------------+--------------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| users |          0 | PRIMARY                  |            1 | id          | A         |           0 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| users |          1 | users_company_id_foreign |            1 | company_id  | A         |           0 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| users |          1 | users_first_name_index   |            1 | first_name  | A         |           0 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| users |          1 | users_last_name_index    |            1 | last_name   | A         |           0 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
+-------+------------+--------------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+

Not a lot to offer. As soon as I see performance problems with a query like that, my gut tells me I'm really doing two queries and want a union, rather than smash all the data together and query in one.

One thing to note, in the query.sql snippet you use an INNER JOIN, then you use LEFT JOIN in your comment. That will make a difference to the query planner.

@davedevelopment Totally. I think I'm going to go with two queries, since that tends to work better in Laravel. Doing unions on Eloquent models is a total nightmare.

And yes, sorry, they should all be left joins. I'll correct that.

MySQL is usually having a hard time optimizing such OR conditions, and in many cases it will not be able to use the correct indexes.
Therefore, I recommend modifying the query to include one condition per UNION, which will let MySQL use the relevant indexes for each of the conditions in the WHERE clause.

I tested this query and its execution duration is 1-3ms, compared to 500ms on my local MySQL.
Hope this is helpful and that I didn't miss anything.

SELECT
  users_first_name,
  users_last_name
FROM
  (
    (
      SELECT
        users.first_name AS users_first_name,
        users.last_name AS users_last_name
      FROM
        users
        INNER JOIN companies ON companies.id = users.company_id
      WHERE
        (
          users.last_name LIKE 'TERM%'
        )
    )
    UNION
      DISTINCT (
        SELECT
          users.first_name AS users_first_name,
          users.last_name AS users_last_name
        FROM
          users
          INNER JOIN companies ON companies.id = users.company_id
        WHERE
          (users.first_name LIKE 'TERM%')
      )
    UNION
      DISTINCT (
        SELECT
          users.first_name AS users_first_name,
          users.last_name AS users_last_name
        FROM
          users
          INNER JOIN companies ON companies.id = users.company_id
        WHERE
          (companies.name LIKE 'TERM%')
      )
  ) AS union1;

@tomershay Awesome, thanks for sharing!

So, thanks to everyone for helping with this problem. It blows my mind how hard this has been.

As many of you suggested, the UNION approach is very fast. The problem, however, with the UNION approach is:

1. It's very difficult to convert to the Laravel Eloquent ORM (a priority for me).
2. It only handles one term well. What I haven't told you this whole time is that I actually want to run a query like this:

   WHERE
       (first_name LIKE 'TERM%' OR user_name LIKE 'TERM%' OR company_name LIKE 'TERM%')
       AND
       (first_name LIKE 'TERM%' OR user_name LIKE 'TERM%' OR company_name LIKE 'TERM%')

I almost thought that @Cacobot had the solution, but after some testing, it has some really weird side affects where every SELECT column and ORDER BY added REALLY slowed it down.

As of right now, the best possible solution I can come up with is running a separate query to get the companies for each term, before running the main query. Here is what this looks like in Laravel:

<?php

class User
{
    public function scopeSearch($query, $terms)
    {
        Str::of($terms)->explode(' ')->filter()->each(function ($term) use ($query) {
            $query->where(function ($query) use ($term) {
                $query->where('email', $term)
                    ->orWhere('last_name', 'like', $term.'%')
                    ->orWhere('first_name', 'like', $term.'%')
                    ->orWhereIn('company_id', Company::query()
                        ->where('name', 'like', $term.'%')
                        ->pluck('id')
                    );
            });
        });
    }
}

$users = User::query()
    ->search(Request::input('search'))
    ->orderBy('last_name')
    ->orderBy('first_name')
    ->paginate();

It seems insane to introduce an N+1 intentionally, but I don't really have a better solution, and the results are actually really quite good. Here are the queries that are generated:

-- 2.09ms
select `id` from `companies` where `name` like 'Abbie%'

-- 480μs
select `id` from `companies` where `name` like 'Armstrong%'

-- 1.2ms (total for pagination)
select count(*) as aggregate from `users` where (`email` = 'Abbie' or `last_name` like 'Abbie%' or `first_name` like 'Abbie%' or 0 = 1) and (`email` = 'Armstrong' or `last_name` like 'Armstrong%' or `first_name` like 'Armstrong%' or `company_id` in (4211, 8674, 11838, 20590, 23361, 28869, 30739, 34837, 38305, 47335, 47424, 14761, 17342, 26008, 40535, 48473, 3691, 5159, 6059, 43551, 48434, 4629, 10168, 34613, 40971, 3342, 5030, 8895, 9359, 12397, 34029, 34248, 25601, 1561, 26392, 41562, 41496, 31682, 41638, 37991, 17725, 18232, 921, 32410, 11391, 46729, 40239, 11270, 21442, 46383, 24760, 40129, 22665, 39175, 33414, 18880, 11332, 11338, 6350, 42984, 2207, 46783, 26166, 687, 15758, 22790, 48446, 26709, 5266, 38082, 47310, 42517, 23894, 1552, 379, 29012, 11862, 43489, 9044, 25308, 1657, 14817, 29930, 14133, 27916, 29459, 10514, 6312, 9031, 20409, 5752, 33189, 4995, 28969, 7619, 38919, 49738, 8304, 39868, 46731, 10628, 34058, 48516, 32631, 10784))

-- 1.29ms
select * from `users` where (`email` = 'Abbie' or `last_name` like 'Abbie%' or `first_name` like 'Abbie%' or 0 = 1) and (`email` = 'Armstrong' or `last_name` like 'Armstrong%' or `first_name` like 'Armstrong%' or `company_id` in (4211, 8674, 11838, 20590, 23361, 28869, 30739, 34837, 38305, 47335, 47424, 14761, 17342, 26008, 40535, 48473, 3691, 5159, 6059, 43551, 48434, 4629, 10168, 34613, 40971, 3342, 5030, 8895, 9359, 12397, 34029, 34248, 25601, 1561, 26392, 41562, 41496, 31682, 41638, 37991, 17725, 18232, 921, 32410, 11391, 46729, 40239, 11270, 21442, 46383, 24760, 40129, 22665, 39175, 33414, 18880, 11332, 11338, 6350, 42984, 2207, 46783, 26166, 687, 15758, 22790, 48446, 26709, 5266, 38082, 47310, 42517, 23894, 1552, 379, 29012, 11862, 43489, 9044, 25308, 1657, 14817, 29930, 14133, 27916, 29459, 10514, 6312, 9031, 20409, 5752, 33189, 4995, 28969, 7619, 38919, 49738, 8304, 39868, 46731, 10628, 34058, 48516, 32631, 10784)) order by `last_name` asc, `first_name` asc limit 15 offset 0

In and around 5ms total, between all the queries. That's really fast. Much faster than any single query solution I could come up with.

The only thing that's a bummer is Postgres. This solution doesn't work quite as well there, although it's still better than most options. I'mg getting around 90ms total between all the queries with this approach in Postgres.

One last note, these numbers are not based on the original 30,000 users, 10,000 companies. I bumped that up to 200,000 users, and 50,000 companies.

@reinink when you say convert to Eloquent, do you mean to end up with Eloquent models as a result, or to use the query builder type thing? If the former, I quite often use raw queries to fetch the IDs, then the orm to fetch the models. If the latter, that's a weird priority 🙂

@davedevelopment The first thing, exactly. I generally can convert most queries to the query builder, but it's sometimes hard to do with Eloquent if you're using a "computed" base table. Good idea on getting the IDs, and then doing a subsequent query. 👌

Which version of MySQL are you using? Are you using MySQL MySQL, or Maria, or some other fork?

What about these options:

• In Laravel you can try caching your local query scope

return Cache::remeber('key-to-associate', 15, function() {
   //here your localscope
});

• Using like operator with a beginning match maybe could not be a good idea if when you run it this one makes a full table scan
• What about using a regular expressions? in this way:

SELECT * FROM masters WHERE REGEXP_LIKE(degree, '^al');

I think this query gives you results that you expect with better performance, though it has a semantic difference. It doesn't do a table scan. I tested it with MySQL 5.7.29-0ubuntu0.18.04.1 on Ubuntu .

select
  first_name,
  last_name
From users
WHERE first_name like 'NAD%'
    or last_name like 'NAD%'
OR company_id IN (select id from companies where name LIKE 'NAD%');

I think it's important to explain why this rewritten query works better.

The original query first does a join between the users and companies tables. Of the matching tuples, it finds the rows that match the LIKE conditions in the WHERE clause. The QP must do the join first to generate candidate rows for the WHERE clause. The execution plan of the original query enumerates all the rows in the companies table. For each row enumerated, it probes the Users table to find a match on company_id. If found, it further filters to see if the LIKE clauses match.

It seems like the goal (the complaint?) is that the filters aren't applied to tables on both sides of the join first, we'd only have companies that match the WHERE clause, and couldn't JOIN users that matched their clauses in the WHERE. All of the LIKE clauses are disjunctive -- they're OR statements. If we filtered a row from the Users table, we'd still maybe want to match it because OR Companies.Name LIKE was a match.

The query I wrote has a semantic difference; it will return rows from users that don't have a matching company. I think the OUTER JOIN was meant to take care of that, but I'm not positive it will. (Because NULL is NOT LIKE anything, so ... but I'm not positive of that, and I have too much lockdown time to think particularly clearly.)

My revised query will poke at the first_name index, then the last_name index, both on the users table. Then, with a subselect, it develops a list of company_ids that match using the names index on the companies table; it will probe each resulting entry in the company_ids index on the users table. All the results are then projected back to the user.

We all want SQL statements to run as fast as possible, but getting good performance has to start with careful thought about what the statement we're executing really does, and how it really works.

@mikeblas Thanks for sharing your thoughts. You'll notice that I did try this query, but it's still giving me 10ms+ (or worse) performance, where running two queries got me <1ms per query.

So, just an update here, for anyone who is interested. 😂

I managed to get this query working in Laravel, as a SINGLE query, using the union approach, where it supports searching multiple queries. 🎊

The following is my final User model scope.

Brace yourselves. 😬

public function scopeSearch($query, string $term = null)
{
    collect(str_getcsv($term, ' ', '"'))->filter()->each(function ($term) use ($query) {
        $term = $term.'%';
        $query->whereIn('id', function ($query) use ($term) {
            $query->select('id')
                ->from(function ($query) use ($term) {
                    $query->select('users.id')
                        ->from('users')
                        ->where('users.first_name', 'like', $term)
                        ->orWhere('users.last_name', 'like', $term)
                        ->union(
                            $query->newQuery()
                                ->select('users.id')
                                ->from('users')
                                ->join('companies', 'users.company_id', '=', 'companies.id')
                                ->where('companies.name', 'like', $term)
                        );
                }, 'matches');
        });
    });
}

And the generated query (for the search "bill gates microsoft"):

SELECT
    *
FROM
    `users`
WHERE
    `id` in(
        SELECT
            `id` FROM ((
                SELECT
                    `users`.`id` FROM `users`
                WHERE
                    `users`.`first_name` LIKE 'bill%'
                    OR `users`.`last_name` LIKE 'bill%')
            UNION (
                SELECT
                    `users`.`id` FROM `users`
                    INNER JOIN `companies` ON `users`.`company_id` = `companies`.`id`
                WHERE
                    `companies`.`name` LIKE 'bill%')) AS `matches`)
    AND `id` in(
        SELECT
            `id` FROM ((
                SELECT
                    `users`.`id` FROM `users`
                WHERE
                    `users`.`first_name` LIKE 'gates%'
                    OR `users`.`last_name` LIKE 'gates%')
            UNION (
                SELECT
                    `users`.`id` FROM `users`
                    INNER JOIN `companies` ON `users`.`company_id` = `companies`.`id`
                WHERE
                    `companies`.`name` LIKE 'gates%')) AS `matches`)
    AND `id` in(
        SELECT
            `id` FROM ((
                SELECT
                    `users`.`id` FROM `users`
                WHERE
                    `users`.`first_name` LIKE 'microsoft%'
                    OR `users`.`last_name` LIKE 'microsoft%')
            UNION (
                SELECT
                    `users`.`id` FROM `users`
                    INNER JOIN `companies` ON `users`.`company_id` = `companies`.`id`
                WHERE
                    `companies`.`name` LIKE 'microsoft%')) AS `matches`)
ORDER BY
    `last_name` ASC, `first_name` ASC
LIMIT 15 OFFSET 0

Overall, the final results are amazing.

Running it for three terms (ie. "bill gates microsoft"), against 1 million users, and 100,000 companies results in query times between 3-6ms.

The trick? Err..tricks?

First, using a union (as folks have suggested) allows the query builder to run each query (the users match and companies match) independently of each other, and therefore use all the available indexes. This final query now successfully uses the users_first_name_index, users_last_name_index and companies_name_index.

Second, and this was the piece I was missing before, you must run this union as a derived table, not a normal (correlated/dependent) subquery.

Without the derived table, all of subqueries are "dependent":

Adding the derived table makes all the problems go away:

I would have thought that the sub queries would only be dependent if you actually had some type of dependency between the two. For example, inner.id = outer.id, or something like that. But I guess the MySQL query planner doesn't look at the conditions to see if these two queries are actually dependent.

The only outstanding issue I have still is running a 1-2 character search. For example, searching for "b", or even "bi" is rather slow, taking upwards of 800ms on a million rows. The previous approaches that don't use the indexes are faster in those cases. I suspect that this is because the derived tables end up becoming massive, and that just takes computation time. One simple solution is to just not perform the search until you have at least 3 characters, which seems to be the sweet spot.

And, now for a quick sales pitch. 😂

I plan to cover all this in detail in my upcoming Eloquent Performance Patterns course. If that sounds interesting to you, be sure to join my mailing list on that website. 🤟

@reinink - interested in the course - the above is very close to an issue I want to solve - so wondering if the course will cover it - querying unrelated data at the same time and returning not just the ID of the model, but the table reference it is derived from, in the return?

The purpose is to allow users to just have one search box to find any one model in the search. So say you have 4 tables - COMPANY, SERVICE, PRODUCT, and DEVICE. I want to design a query that queries for a typeahead "meta" search of the description or name (or some other column) in each table, and returns the ID and the model type (i.e. table reference) so that if someone selected that, it would take them to that particular record. Right now these are 4 different searches on my application - in other words, the person needs to know they are looking for a DEVICE, and then search the DEVICE table.

I think this can be done with Unions - just including an AS column (from an SO post):

(SELECT content, title, 'msg' as type FROM messages WHERE content LIKE '%" . 
$keyword . "%' OR title LIKE '%" . $keyword ."%') 
UNION
(SELECT content, title, 'topic' as type FROM topics WHERE content LIKE '%" . 
$keyword . "%' OR title LIKE '%" . $keyword ."%') 
UNION
(SELECT content, title, 'comment' as type FROM comments WHERE content LIKE '%" . 
$keyword . "%' OR title LIKE '%" . $keyword ."%')";

In my case the tables have different columns in each table, so instead of say content, title above, say the table has description, name in one of the tables. As per your post above, however, I suspect this is not performant at all . . . and thus have not implemented it.

In any event, I am on your email list and very interested in this course and really appreciate the above gist and all the comments on it.