I see a few good lessons here:

1. You can learn a lot about your own code and your tools by digging in and debugging and experimenting.

2. As macspoofing argues, having a correct mental model of your application, and your tools, is what separates professional programmers from amateurs and beginners. You don't need to do much math or understand Fermi estimates to figure out that removing 30 bytes of excess key name from, say, 100,000 rows is only going to get back a few megs. However doing the experiment validated your hypothesis and taught you something about how Redis (probably) stores keys internally. For many real problems with real data, estimating is orders of magnitude faster and simpler (and probably safer) than experimenting, so it's a skill to cultivate.

3. This is exactly the kind of data management problem that relational databases are really good at. Relational theory is based on sets and RDBMSs are good at working with sets. But you would need to normalize your schema and know how to write efficient SQL -- perhaps an exercise for another day. RDBMSs and SQL are not easy to learn and take real study and practice, but the rewards are significant. I agree with AznHisoka that dropping PostgreSQL (or MySQL) in favor of Redis was a premature optimization, but you would need to spend a lot of time mastering relational database design and SQL to get the benefits of an RDBMS, whereas Redis doesn't make the same demand. If you posted more details of your data and how you need to query it on stackoverflow you'd get some free lessons in schema design and normalization.

4. A database of a few tens or even hundreds of thousands of rows and taking up only 50 megs of RAM is trivial for any RDBMS. Not trivial as in not important, but in the same sense that delivering a carton of milk with a semi truck is a trivial use of the truck. Your data set would not begin to run into any performance limits of a stock RDBMS. I'm not criticizing or making fun, just stating a fact.

5. Don't assume you know what the problem is when debugging or optimizing -- it's too easy to go into the weeds and get frustrated. Over time you'll probably get better at narrowing the range of possibilities but even the most experienced programmers are frequently wrong about the source of a bug or performance problem. Your methodology is correct, do the same thing next time.

You say that you are relatively new to programming and databases, and there's nothing wrong with that. We've all made the same kinds of decisions you have, and some of us are still making them without the kind of introspection you've documented.

If your code seems too complex (something you develop a feel for over time) you need to choose better data structures. With the right data structures the code writes itself. When you speculate about using an array column type in Postgres I know with 99.99% certainty that you are not normalizing -- nothing you've described can't be accomplished with normalized relations. And you'd be able to do all of your queries with simple SQL statements.

I recommend Chris Date's book "Database in Depth: Relational Theory for Practitioners," which is aimed at programmers rather than DBAs.

I've written more on this (and linked to some more good books) on my site at http://typicalprogrammer.com/?p=14