In Indexeddb, How to Make a Sorted Compound Query

In IndexedDB, is there a way to make a sorted compound query?

The term compound query as used in this answer refers to an SQL SELECT statement involving more than one condition in its WHERE clause. Although such queries are not mentioned in the indexedDB specification, you can approximate the behavior of a compound query by creating an index with a keypath that consists of an array of property names.

This is completely unrelated to using the multi-entry flag when creating an index. The multi-entry flag adjusts how indexedDB creates an index over a single array property. We are indexing an array of object properties, not the values of a single array property of an object.

Creating the index

In this example, 'name', 'gender', and 'age' correspond to property names of student objects stored within the students object store.

// An example student object in the students store
var foo = {
  'name': 'bar',
  'age': 15,
  'gender': 'M'
};

function myOnUpgradeNeeded(event) {
  var db = event.target.result;
  var students = db.createObjectStore('students');
  var name = 'males25';
  var keyPath = ['name', 'gender', 'age'];
  students.createIndex(name, keyPath);
}

Opening a cursor on the index

You can then open a cursor on the index:

var students = transaction.objectStore('students');
var index = students.index('males25');
var lowerBound = ['AAAAA','male',26];
var upperBound = ['ZZZZZ','male',200];
var range = IDBKeyRange.bound(lowerBound, upperBound);
var request = index.openCursor(range);

However, for reasons I am about to explain, this won't always work.

Aside: using a range parameter to openCursor or get is optional. If you do not specify a range, then IDBKeyRange.only is implicitly used for you. In other words, you only need to use IDBKeyRange for bounded cursors.

Fundamental index concepts

Indices are like object stores but are not directly mutable. Instead, you use CRUD (create read update delete) operations on the referenced object store, and then indexedDB automatically cascades updates to the index.

Understanding sorting is fundamental to understanding indices. An index is basically just a specially sorted collection of objects. Technically, it is also filtered, but I'll touch on that in a moment. Generally, when you open a cursor on an index, you are iterating according to the index's order. This order could be, and probably is, different than the order of the objects in the referenced object store. The order is important because this allows iteration to be more efficient, and allows a custom lower and upper bound that only makes sense in the context of an index-specific order.

The objects in the index are sorted at the time changes to the store occur. When you add an object to the store, it is added to the proper position in the index. Sorting boils down to a comparison function, similar to Array.prototype.sort, that compares two items and returns whether one object is less than the other one, greater than the other one, or equal. So we can understand sorting behavior better by diving into more details on comparison functions.

Strings are compared lexicographically

This means, for example, that 'Z' is less than 'a' and that the string '10' is greater than the string '020'.

Values of different types are compared using a specification-defined order

For example, the specification specifies how a string-type value comes before or after a date-type value. It does not matter what the values contain, just the types.

IndexedDB does not coerce types for you. You can shoot yourself in the foot here. You generally never want to be comparing different types.

Objects with undefined properties do not appear in indices whose keypath is comprised of one or more of those properties

As I mentioned, indices may not always include all objects from the referenced object store. When you put an object into an object store, the object will not appear in the index if it has missing values for the properties upon which the index is based. For example, if we have a student where we don't know the age, and we insert this into the students store, the particular student will not appear in the males25 index.

Remember this when you wonder why an object doesn't appear when iterating a cursor on the index.

Also note the subtle difference between null and an empty string. An empty string is not a missing value. An object with an empty string for a property could still appear in an index based on that property, but will not appear in the index if the property is present but undefined or not present. And if it is not in the index, you won't see it when iterating a cursor over the index.

You must specify each property of an array keypath when creating an IDBKeyRange

You must specify a valid value for each property in the array keypath when creating a lower or upper bound to use in a range for when opening a cursor over that range. Otherwise, you will get some type of Javascript error (varies by browser). For example, you cannot create a range such as IDBKeyRange.only([undefined, 'male', 25]) because the name property is undefined.

Confusingly, if you specify the wrong type of value, such as IDBKeyRange.only(['male', 25]), where name is undefined, you won't get an error in the above sense, but you will get nonsensical results.

There is an exception to this general rule: you can compare arrays of different lengths. Therefore, you technically can omit properties from the range, provided that you do so from the end of the array, and that you appropriately truncate the array. For example, you could use IDBKeyRange.only(['josh','male']).

Short-circuited array sorting

The indexedDB specification provides an explicit method for sorting arrays:

Values of type Array are compared to other values of type Array as follows:

1. Let A be the first Array value and B be the second Array value.
2. Let length be the lesser of A's length and B's length.
3. Let i be 0.
4. If the ith value of A is less than the ith value of B, then A is less
   than B. Skip the remaining steps.
5. If the ith value of A is greater than the ith value of B, then A is greater than B. Skip the remaining steps.
6. Increase i by 1.
7. If i is not equal to length, go back to step 4. Otherwise continue to next step.
8. If A's length is less than B's length, then A is less than B. If A's length is greater than B's length, then A is greater than B. Otherwise A and B are equal.

The catch is in steps 4 and 5: Skip the remaining steps. What this basically means is that if we are comparing two arrays for order, such as [1,'Z'] and [0,'A'], the method only considers the first element because at that point 1 is > 0. It never gets around to checking Z vs A because of short-circuited evaluation (steps 4 and 5 in the spec).

So, the earlier example is not going to work. It actually works more like the following:

WHERE (students.name >= 'AAAAA' && students.name <= 'ZZZZZ') || 
(students.name >= 'AAAAA' && students.name <= 'ZZZZZ' && 
students.gender >= 'male' && students.gender <= 'male') || 
(students.name >= 'AAAAA' && students.name <= 'ZZZZZ' && 
students.gender >= 'male' && students.gender <= 'male' && 
students.age >= 26 && students.age <= 200)

If you have any experience with such Boolean clauses in SQL or in general programming, then you already should recognize how the full set of conditions are not necessarily involved. That means you will not get the list of objects you want, and this is why you cannot truly get the same behavior as SQL compound queries.

Dealing with short-circuiting

You cannot easily avoid this short-circuiting behavior in the current implementation. In the worst case you have to load all objects from the store/index into memory and then sort the collection using your own custom sorting function.

There are ways to minimize or avoid some of the short-circuiting issues:

For example, if you are using index.get(array) or index.openCursor(array), then there is no short-circuiting concern. There is either an entire match or not an entire match. In this case, the comparison function is only evaluating whether two values are the same, not whether one is greater than or less than the other.

Other techniques to consider:

• Rearrange the elements of the keypath from narrowest to widest. Basically provide early clamps on ranges that cut off some of the unwanted results of short-circuiting.
• Store a wrapped object in a store that uses specially customized properties so that it can be sorted using a non-array keypath (a non-compound index), or, can make use of a compound index that is not affected by the short-circuiting behavior.
• Use multiple indices. This leads to the exploding index problem. Note this link is about another no-sql database, but the same concepts and explanation applies to indexedDB, and the link is a reasonable (and lengthy and complicated) explanation so I am not repeating it here.
• One of the creators of indexedDB (the spec, and the Chrome implementation) recently suggested using cursor.continue: https://gist.github.com/inexorabletash/704e9688f99ac12dd336

Testing with indexedDB.cmp

The cmp function provides a quick and simple way to examine how sorting works. For example:

var a = ['Hello',1];
var b = ['World',2];
alert(indexedDB.cmp(a,b));

One nice property of the indexedDB.cmp function is that its signature is the same as the function parameter to Array.prototype.sort. You can easily test values from the console without dealing with connections/schemas/indices and all that. Furthermore, indexedDB.cmp is synchronous, so your test code does not need to involve async callbacks/promises.

Querying an IndexedDB compound index with a shorter array

You should use key range IDBKeyRange.bound([0], [0, '']), so that all keys started with [0] included.

Sorting the results of an indexedDB query

Thanks to zomg, hughfdjackson of javascript irc, I sorted the final array. Modified code as below:

var trans = db.transaction(['msgs'], IDBTransaction.READ);
var store = trans.objectStore('msgs');

// Get everything in the store;
var keyRange = IDBKeyRange.lowerBound("");
var cursorRequest = store.openCursor(keyRange);

var res = new Array();

cursorRequest.onsuccess = function(e) {
    var result = e.target.result;
    if(!!result == false){
        **res.sort(function(a,b){return Number(a.date) - Number(b.date);});**
        //print res etc....
        return;
    }
    res.push(result.value);
    result.continue();
};

Cursors order in query using composite index

See In IndexedDB, is there a way to make a sorted compound query?. Basically, the index is sorted first by user id and then by date created, because that is the order of the properties in the array you passed to the createIndex method.

The sorting function is indexedDB.cmp. This is a customized sorting function specific to indexedDB. You need to read a large part of the indexedDB specification to understand it. It is partially summarized in the linked question.

How to create an indexeddb composite key

A:

As it turns out, the answer is very simple, but not documented well anywhere I have looked, and not obvious at first glance. Use an array of strings...

var store = db.createObjectStore('myStore', 
    {keyPath: ['id1', 'id2']}
);

Composite indexes can also be created in the same fashion.

For work with composite key data, see the answer below by Malvineous

Indexed DB - compound index query where one or the other matches

Opening and index on two fields at once it's not possible however there is a indexed solution for your case.

You need to create a new index for an array field which will contain both teams with multiEntry property set to true.

objectStore.createIndex("teams", ["teams"], {unique: false, multiEntry: true});

And then store both teams as array of strings into that field

var obj = {
    hometeam: "Russia",
    awayteam: "Usa",
    teams: ["Russia", "Usa"]
}

Now when you query the database on that field you should get all games in which Russia is playing:

var index = objectStore.index("teams");
var keyRange = IDBKeyRange.only("Russia");
var cursorRequest = index.openCursor(keyRange);

Querying an index with multiple fields, by direction, where one field is specified

And the answer is really similar, you need to create a compound index and then retrieve the data from that index in reverse order. In this example I'm using time stamps for storing the Date.

First you need to create the compound index during onupgradeneeded event:

store.createIndex('nametimestamp', ['text', 'timeStamp']);
//text and timestamp are my field names

And then use it for your search function:

searchIndexedDB = function (value, callback) {
  var request = indexedDB.open(dbName);
  request.onsuccess = function(e) {
    var db = e.target.result;
    var trans = db.transaction(objectStoreName, 'readonly');
    var store = trans.objectStore(objectStoreName);
    var index = store.index('nametimestamp');
    var keyRange = IDBKeyRange.bound([value,0], [value, new Date().getTime()]);
    //open the index for all dates and for only one value
    var openCursorRequest = index.openCursor(keyRange, 'prev');
    //open the database sorted by time stamp - descending 

    openCursorRequest.onsuccess = function(e) {
        if(e.target.result)
            callback(e.target.result.value);
    };

    trans.oncomplete = function(e) {
        db.close();
    };

    openCursorRequest.onerror = function(e) {
        console.log("Error Getting: ", e);
    };
  };
  request.onerror = myStorage.indexedDB.onerror;
}

Querying on multiple keys (range on one of them) with indexedb or ydn

Prefix key query, as you described above, is very fast and recommended for key-value store filtered query.

You can query as follow:

key_range = IDBKeyRange.bound([a, b, c], [a, b, d], true, true);

or in ydn-db

key_range = ydb.db.KeyRange.bound([a, b, c], [a, b, d], true, true);

How do I get part of a compound index following a where clause?

As you are querying the compound index, the argument must be an array of first and second value.

Just change it to:

await db.LOGS.where('[timestamp+activity]')
    .below([Date.now() - 604800000, -Infinity])
    .delete();

---

Related Topics