Two indexes for every query required by google app engine

For every query, even simple ones like SELECT * FROM Entity, app engine maintains two indexes, one in ascending order and another in descending order. It then finds the first matching row, works down until it finds a non-matching row and returns the results.

But why? I don't understand why which ever mech开发者_运维百科anism google uses can't just be reversed for the descending case, especially given the space penalty caused by doubling the number of indexes. There must be a very good reason for this.

I can't say for sure, but my guess would be because the GAE datastore is running on top of Bigtable (think "Sharded Sorted Array").

When scans (think queries that return lots of rows) are done, it is probably faster to do contiguous reads from disk, and that's probably what Bigtable is optimized to do. Going in the reverse direction would require many disk seeks, which would slow things down.

There is a good talk by Ryan Barrett about Bigtable and the Datastore; he talks about scanning at around 7m 50s.