Under the Covers of the Google App Engine Datastore ‎(2008 Google I/O Session Videos and Slides)‎
http://sites.google.com/site/io/under-the-covers-of-the-google-app-engine-datastore

Presentation on how googleapps datastore implements filtering and sorting on top of bigtable. Basically, all queries are translated to bigtable prefix scans or range scans, without needing any in-memory postprocessing, all rows returned from the scan are relevant to, and in order, for the query. There's a built-in 'single property index' (or two actually: one asc and one desc) which can obviously be used for single-property searches, but also for queries consisting of only equals clauses, by doing multiple range scans and taking the intersection (not sure at which level this happens). More complex queries need specific pre-defined indexes. Index tables only have keys, no columns with values. Indexes are updated synchronously, so everything stays consistent (at the cost of contention problems?). Some mention of string-byte considerations when doing range queries. No fulltext queries. Ends with some talk on transactions.

posted by thraxil: http://quimby.ccnmtl.columbia.edu/ircbot/web/?y=2010&m=04&d=26#20100426105402

Awesome tutorial.

These slides and notes were originally written to accompany a three hour Redis tutorial I gave at the NoSQL Europe conference on the 22nd of April 2010.