The hitch with relational databases is that you need to know what you are doing. This is mostly true for programming in general and a big reason why a lot of software isn't much faster today than it was in 1995, even though processors are many orders of magnitude faster. It's much more visible with relational databases, as they tend to accumulate so much data that bad solutions immediately break.

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.