I've ended up using SimpleDB, which has no concept of joins but permits multiple values for attributes. So instead of 4 million rows, I've got 100,000 rows with around 40 values on each. Doing the same search takes a tenth of a second, plus, I get more information back and my algorithm is much more accurate.

Just registered a cool domain name, going to have a prototype within a week and beta by Xmas.

Edit: makes that a million records with 200 values on each. Doesn't seem to make any difference to response time.

Script kiddie? Shit, I /wish/.

I did write a blog once in PHP/MySQL, but I wouldn't go so far as to say it was crazy. ATM I'm working on a (probably (very) low traffic) commerce site. From what you're saying it's highly unlikely that performance is going to be an issue.

This project is being driven by my brother, though, and he's more of a completer/finisher than me.

I've just discovered a limitation of SimpleDB that changes the approach somewhat, but it's still the most scalable solution by a mile. I will be sharing more details soon.