I'm surprised no one brought up column-oriented databases.

When attributes can be added dynamically and/or are have a small value set, column-oriented databases with bitmap indices outperform traditional relational databases.

See MonetDB for an open source, usable column-oriented db with bitmap index support: http://monetdb.nl/

For more kvetching on the topic: http://dynamictyping.org/post/29661699#disqus_thread

I tried to find a public research document with performance comparisons, but to no avail.