It isn't just package search which is the problem, it is everything which has to parse the packages file, which is basically every apt command. So if you can trim "main" down to 10,000 packages, suddenly every part of apt is faster, and no one has to install any custom apt replacements.

But wouldn't just storing that file as a database solve most of the issues?

Yes, and that would be awesome, but it means rewriting apt.