In this case, I don't think the 3NF-solution they came up with was necessary, it typically ends up requiring really complicated transactions and in some cases it may even be slower because of cache thrashing. What they really needed was to index their table. You can index strings, that's fine. It's reasonably fast, like even with a hundred million rows it's doable.
"But why doesn't the database build indices automatically?", I hear someone about to type, it's because indices make inserts slower and require more memory. In many cases auto-indexing would probably help, but it would break a lot of use-cases too.
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.
> I would have considered hashing the values in those four columns.
That's a good idea that definitely works, but at least to me it's not clear that it's more efficient than a compound index or a computed index (where a compound index is basically the special case of a computed index on a concatenation that is supported natively even in RDBMS packages that don't support generalized computed indices). It might very well end up a wash.
They don't work poorly, and there is no alternative. The database should not monitor the contents and opportunistically normalise the schema itself.
It's not "business rules", it's just normalisation.