I'm looking for a way to do a fast-as-possible incomplete-word `LIKE "%foo%"` lookup across two tables in a MySQL database.

Let's say I have two tables, Boxes and Objects, where each Box contains multiple Objects. What we want to do is find the ID of the box (Box.id) by matching a search string against `Box.name` OR `Object.name`.

To give you a picture of the scale we're dealing with, Boxes contains ~500,000 entries, while Objects contains ~200,000 entries. 

Every Object is in a Box, not every Box contains Objects. I have indices on `Box.id`, `Object.id`, and `Object.box_id`.

**Why?**

I need this data fast (200ms) so I can offer suggestions as a user types a search. The data set is essentially static, updated en masse yearly. `Box.id` will never, ever change. I'm using an initial wildcard because the matching word may not start at the start of the string- for example, `"flo"` needs to suggest `"cake flour"` as well as `"flour"`.

**What I've tried:**

**Doing a LEFT JOIN between the two tables:**

`SELECT b.id, b.name, o.name FROM boxes b LEFT JOIN objects o ON (b.id = o.box_id) WHERE ((b.name LIKE "%test str%") OR (o.name LIKE "%test str%")) LIMIT 10;`

Time to search: `3900ms.`

**Denormalizing everything to one lookup table:**

`SELECT n.id, n.box_name, n.object_name from lookup_table n WHERE ((n.box_name LIKE "%test str%") OR (n.object_name LIKE "%test str%")) LIMIT 10;`

Time to search: `1100ms`. 

Getting rid of that JOIN clearly does wonders; however, this is still too slow. Ideally, this should take 200ms or less. Does anyone have any insight into how to optimize partial-word match queries?