Basically, some combination of puts to one of our models would cause queries to return inconsistent results. For example, the query:
SELECT * FROM MyModel WHERE property=True
would return N results, but
SELECT * FROM MyModel WHERE property=True ORDER BY foo
would return far fewer than N results.
It appears that _something_ we were doing exercised an AppEngine bug that caused the indexes to get corrupted. (Note that this would happen even from AppEngine's data viewer -- which is to say, we got N by paging through ALL results, not just one fetched batch.)
We worked with Google but designing a simple repro case proved difficult -- the corruption happened only under high load, and only on one of our models.
Trial and error showed us that if we manually fetched and re-put() the "broken" rows in our table (aka the ones that didn't show up when we used ORDER BY,) the indexes would right themselves. So I wrote a bit of code to do this, and started running a cron job on a local box to invoke that code regularly. Lame, but only temporary.
Last time we exchanged mail with the AppEngine team, they told us they were aware that this was a bug on their end and were working on a fix. However, to my knowledge, they're still working on it...
I believe the app engine datastore has been stated as being built upon bigtable. I suppose the index creation is "newer" code than the core of bigtable, but I'd like to hope that the Google bigtable code is bugfree at this point...
http://code.google.com/p/googleappengine/issues/detail?id=90...
Seems like a serious bug, but I haven't seen any updates as yet.