[google-appengine] Why are both ascending and descending indexes required ?

[leo]

Hi,
Are both the ascending and descending indexes (for example for a
property) physically stored in Bigtable ? I mean, can´t the ascending
order index also be used as descending (starting from the bottom up) ?

I´m just a bit curious. I guess there are some good reasons to have
both indexes.

Thanks.

--
You received this message because you are subscribed to the Google Groups "Google App Engine" group.
To post to this group, send email to google-a...@googlegroups.com.
To unsubscribe from this group, send email to google-appengi...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/google-appengine?hl=en.

[Ikai L (Google)]

It's a consequence of how Bigtable works and how we can preserve ordering in a meaningful way for developers (I don't think this topic is covered in this paper: http://static.googleusercontent.com/external_content/untrusted_dlcp/labs.google.com/en/us/papers/bigtable-osdi06.pdf).

Let's say you have keys that look like this:

[..lots of stuff ,a,b,c,d,e,f, ...lots of stuff]

If you did the range query "Give me all keys greater than c", you'd get, predictably:

[d,e,f, ... lots of stuff]

If you did the range query, "Give me all keys less than c", you'd get:

[...lots of stuff, a,b]

On an extremely large dataset, this doesn't happen in the order that you care about. Most of the time, you want the list to look like this:

[b, a, ...lots of stuff]

By keeping both ASC and DESC indexes, it allows us to do this.

You can read more about indexing here:

http://code.google.com/appengine/articles/datastore/overview.html

http://code.google.com/appengine/articles/storage_breakdown.html

We can probably expand on how and why indexes work. If you have any suggestions please let us know.

--
Ikai Lan 
Developer Relations, Google App Engine

Twitter: http://twitter.com/ikai

Delicious: http://delicious.com/ikailan

----------------

Google App Engine links:
Blog: http://googleappengine.blogspot.com 

Twitter: http://twitter.com/app_engine

Reddit: http://www.reddit.com/r/appengine

[leo]

Thanks Ikai.

I´ve read the links you mentioned but I haven´t found any specific
"direction" issue which prevents using indexes bottom up. According to
the documentation Bigtable root tablet contains indexes to the tablets
(a tablet is a range of consecutive entries), so all ranges are known
and apparently you could start from the bottom up if you want to.

The only thing should be that the datastore result [...lots of stuff,
a,b] should be reversed to get [b, a, ...lots of stuff] before
sending back to the client (i.e. GAE app). For instance this could be
done when building the protocol buffer sent back to the client.

If only one index was needeed for ascending and descending order,
about half index storage space could be saved !

Regards,
Leo

On Apr 29, 7:07 pm, "Ikai L (Google)" <ika...@google.com> wrote:
> It's a consequence of how Bigtable works and how we can preserve ordering in
> a meaningful way for developers (I don't think this topic is covered in this

> paper:http://static.googleusercontent.com/external_content/untrusted_dlcp/l...
> ).

>
> Let's say you have keys that look like this:
>
> [..lots of stuff ,a,b,c,d,e,f, ...lots of stuff]
>
> If you did the range query "Give me all keys greater than c", you'd get,
> predictably:
>
> [d,e,f, ... lots of stuff]
>
> If you did the range query, "Give me all keys less than c", you'd get:
>
> [...lots of stuff, a,b]
>
> On an extremely large dataset, this doesn't happen in the order that you
> care about. Most of the time, you want the list to look like this:
>
> [b, a, ...lots of stuff]
>
> By keeping both ASC and DESC indexes, it allows us to do this.
>
> You can read more about indexing here:
>

> http://code.google.com/appengine/articles/datastore/overview.htmlhttp://code.google.com/appengine/articles/storage_breakdown.html

>
> We can probably expand on how and why indexes work. If you have any
> suggestions please let us know.
>
>
>
>
>
> On Thu, Apr 29, 2010 at 9:11 AM, leo <leo.ant...@gmail.com> wrote:
> > Hi,
> > Are both the ascending and descending indexes (for example for a
> > property) physically stored in Bigtable ? I mean, can´t the ascending
> > order index also be used as descending (starting from the bottom up) ?
>
> > I´m just a bit curious. I guess there are some good reasons to have
> > both indexes.
>
> > Thanks.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Google App Engine" group.
> > To post to this group, send email to google-a...@googlegroups.com.
> > To unsubscribe from this group, send email to

> > google-appengi...@googlegroups.com<google-appengine%2Bunsubscrib e...@googlegroups.com>
> > .

[Ikai L (Google)]

The documentation doesn't explicitly state it (and I can't seem to find it in these Bigtable docs either: http://labs.google.com/papers/bigtable-osdi06.pdf), but the underlying storage engine only lets you retrieve keys in ascending key order, though you can specify a "less than key" filter to stop retrieving keys. On an extremely large dataset, you'd have to retrieve all the indexes you wanted, then start backwards. This is why the reverse index exists.