How? My understanding was that the four strings formed a natural key, and so wouldn't the index just be the size of the table? What do you gain from that? I'm a database noob so please enlighten me.

I thought the benefit here was that each of the four tables was much smaller (the original table was potentially the Cartesian join of all four mini tables) so fewer string comparisons were done.

I would have considered hashing the values in those four columns. Not sure how it would compare but if the string comparisons are the issue it might eliminate the problem without creating extra tables with indexes that need to be scanned. I wonder how that would compare.