As is always the case, disk I/O rather sucks for performance. On the other hand, Postgres's I/O scheduling -- while far from state of the art compared to prop

As is always the case, disk I/O rather sucks for performance. On the other hand, Postgres's I/O scheduling -- while far from state of the art compared to proprietary databases -- is probably better than leaving it to the operating system entirely, particularly for writing. 500,000 small hstores should perform just fine. We have tables with millions or quite possibly billions of not-entirely trivially sized hstores sitting around on a pretty unremarkable machine with a few indexes. Hstore's storage format is probably not tuned as carefully (it's basically text) as bson, and yet its indexing can be richer (GIN/GiST). Binary formats can be overrated, though, especially when the amount of meta-information is quite or people use them with strings. However, it's an interesting area of optimization that I think will happen because document storage in Postgres has become something people are actually using now.