The inverted index for prefix indexes turned out to work great for some of our queries. This means that we got roughly 10-20x improvements on common queries (key, vote links etc). All of these are now < 1ms on a full database (1.5 million messages).