I'm doing a query that is like this:

Table A has ~25K rows
Table B has ~50K rows.

This query ran for an hour before I killed it. I know the query is inherently slow and won't use indexes, but I need to get better performance. A few minutes is acceptable; over an hour isn't.

Doing an EXPLAIN shows two "all" joins. I know that's bad but I don't see a way around it.

Any ideas?

you really don't want me to say "we told you to redesign your table" do you?

okay, i won't

My table design isn't set in stone. I'd love to hear your suggestion.

FYI, this is mostly a one time operation that an administrator will paste into Query Browser (or whatever) and manually run; this isn't something that an end user could trigger via application use.

assuming you want to do something like finding the word "Foo" in a longer string like "The Inimitable Foo Company", write a script to parse the table A values into multiple rows, and then you can use an index

You mean split a row like "The Inimitable Foo Company" into every possible substring? That seems like overkill and very inefficient.

If I wrote an custom app in Java to do this with the same data set, it would run in no more than a few seconds. I know MySQL is very general purpose and can't meet every special use, but still, there must be a way to get reasonable performance out of these scenarios.

i understand, but it's not my data, and i don't want to guess at what the best way would be to improve the joins

all i can say is, you may have to do it without indexes, eh