W3C home > Mailing lists > Public > public-webapps@w3.org > April to June 2010

Re: [IndexedDB] Multi-value keys

From: Mikeal Rogers <mikeal.rogers@gmail.com>
Date: Fri, 18 Jun 2010 17:03:07 -0700
Message-ID: <AANLkTim3kFiGnoPphWfYcX6q6yIaRgZKHtV7OgEizJbG@mail.gmail.com>
To: Jonas Sicking <jonas@sicking.cc>
Cc: Webapps WG <public-webapps@w3.org>
The complex keys are how we do this in CouchDB as well. But, again,
the sorting algorithm needs to be well defined in order for it work.

http://wiki.apache.org/couchdb/View_collation#Collation_Specification

Most pertinent to your example is how arrays of varying length might
be ordered, for instance range queries over your example would break
for [firstName, lastName] if an entry omitted lastName and arrays were
sorted by length and then by comparison of each item. This is why the
CouchDB collation algorithm sorts:

["a"]
["b"]
["b","c"]
["b","c", "a"]
["b","d"]
["b","d", "e"]

-Mikeal

On Fri, Jun 18, 2010 at 4:08 PM, Jonas Sicking <jonas@sicking.cc> wrote:
> Hi All,
>
> One thing that (if I'm reading the spec correctly) is currently
> impossible is to create multi-valued keys. Consider for example an
> object store containing objects like:
>
> { firstName: "Sven", lastName: "Svensson", age: 57 }
> { firstName: "Benny", lastName: "Andersson", age: 63 }
> { firstName: "Benny", lastName: "Bedrup", age: 9 }
>
> It is easy to create an index which lets you quickly find everyone
> with a given firstName or a given lastName. However it doesn't seem
> possible to create an index that finds everyone with a given firstName
> *and* lastName, or sort the list of people based on firstName and then
> lastName.
>
> The best thing you could do is to concatenate the firstname and
> lastname and insert a ascii-null character in between and then use
> that as a key in the index. However this doesn't work if firstName or
> lastName can contain null characters. Also, if you want to be able to
> sort by firstName and then age there is no good way to put all the
> information into a single string while having sorting work.
>
> Generally the way this is done in SQL is that you can create an index
> on multiple columns. That way each row has multiple values as the key,
> and sorting is first done on the first value, then the second, then
> the third etc.
>
> However since we don't really have columns we can't use that exact
> solution. Instead, the way we could allow multiple values is to add an
> additional type as keys: Arrays.
>
> That way you can use ["Sven",  57], ["Benny", 63] and ["Benny", 9] as
> keys for the respective objects above. This would allow sorting and
> searching on firstName and age.
>
> The way that array keys would be compared is that we'd first compare
> the first item in both arrays. If they are different the arrays are
> ordered the same way as the two first-values are order. If they are
> the same you look at the second value and so on. If you reach the end
> of one array before finding a difference then that array is sorted
> before the other.
>
> We'd also have to define the order if an array is compared to a
> non-array value. It doesn't really matter what we say here, but I
> propose that we put all array after all non-arrays.
>
> Note that I don't think we need to allow arrays to contain arrays.
> That just seems to add complication without adding additional
> functionality.
>
> Let me know what you think.
>
> / Jonas
>
>
Received on Saturday, 19 June 2010 00:03:34 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 18:49:39 GMT