inexorabletash/@ Indexed DB - N-Dimensional Select.md

## @ Indexed DB - N-Dimensional Select.md

      
    Raw
  

              @ Indexed DB - N-Dimensional Select.md
            
          
    Indexed DB - N-Dimensional Selection

The problem

We have an index with keys of the form:
[ dim1, dim2, dim3, ... ]

e.g. created with:
store.createIndex('coords', ['x', 'y', 'z'], {unique: false});
And we want to select a subset bounded along each dimension.
What does NOT work

Using an key range, e.g. created with
IDBKeyRange.bound([minX, minY, minZ], [maxX, maxY, maxZ]), will
not be sufficient. For example, the range IDBKeyRange.bound([2,2,2], [4,4,4])
includes [3,0,0] and [3,5,5] as [2,2,2] < [3,0,0] < [3,5,5] < [4,4,4]
per the definition of keys in Indexed DB
This is a subtle trap, since it appears to work in some basic cases.
The solution

We can start with a range - which handles the first dimension property,
but still need to filter the results. To be most efficient, when we see any key
outside the range we should skip immediately to the next possible value in
key order.
Here's the basic algorithm:

open a cursor on [minX, minY, minZ] ... [maxX, maxY, maxZ]
for each result, check the key [x, y, z]
if y < minY, continue with [x, minY, minZ] and go to step 2
if z < minZ, continue with [x, y, minZ] and go to step 2
if y > maxY, continue with [x+1, minY, minZ] and go to step 2
if z > maxZ, continue with [x, y+1, minZ] and go to step 2
the value is in range! use it
continue, and go to step 2

If you're not using integer for keys, then that + 1 actually needs
to be "the next smallest key greater than" which gets tricky for floating
point values, strings or dates. Sample code provided.

  
## demo.html
<!DOCTYPE html>
<title>Indexed DB: N-Dimensional Select Example</title>
<script src="select.js"></script>
<script>
// Copyright 2019 Google LLC.
// SPDX-License-Identifier: Apache-2.0

indexedDB.deleteDatabase('example');
var open = indexedDB.open('example');
open.onupgradeneeded = function() {
  var db = open.result;
  var store = db.createObjectStore('things', {autoIncrement: true});
  var index = store.createIndex('coords', ['x', 'y', 'z'], {unique: false});
  for (var x = 1; x <= 10; ++x) {
    for (var y = 1; y <= 10; ++y) {
      for (var z = 1; z <= 10; ++z) {
        store.put({name:''+x+','+y+','+z, x:x, y:y, z:z});
      }
    }
  }
};

function log(m) {
  document.documentElement
    .appendChild(document.createElement('div'))
    .appendChild(document.createTextNode(m));
}
open.onsuccess = function() {
  var db = open.result;
  var tx = db.transaction('things');
  var index = tx.objectStore('things').index('coords');

  select(index, [[4,6], [3,5], [7,10]],
    function(value) {
      log(JSON.stringify(value));
    },
    function() {
      log('done!');
    });
};
</script>

## select.js
// Copyright 2019 Google LLC.
// SPDX-License-Identifier: Apache-2.0

// First, we need to define a "successor" function. This works for numbers and
// strings, but not other key types - add as necessary.
function successor(key) {
  switch (typeof key) {
  case 'number':
    if (key === -Infinity) return -Number.MAX_VALUE;
    if (key === Infinity) return new Date(-8640000000000000);
    if (key === 0) return Number.MIN_VALUE;
    var epsilon = Math.abs(key);
    while (key + epsilon / 2 !== key)
      epsilon = epsilon / 2;
    return key + epsilon;
  case 'string':
    return key + '\x00';
  default:
    throw TypeError('Unsupported key type: ' + key);
  }
}

// And here's the N-dimensions selection function.
// * index is the IDBIndex with an array key path of length N
// * query is [[dim1_min, dim1_max], [dim2_min, dim3_max]]
// * valueCallback() will be called synchronously with each value
// * completeCallback() will be called when completed
function select(index, query, valueCallback, completeCallback) {
  var min = query.map(function(dim) { return dim[0]; });
  var max = query.map(function(dim) { return dim[1]; });
  index.openCursor(IDBKeyRange.bound(min, max)).onsuccess = function(e) {
    var cursor = e.target.result;
    if (!cursor) {
      completeCallback();
      return;
    }

    for (var i = 1; i < cursor.key.length; ++i) {
      var key_tail = cursor.key.slice(i);

      var min_tail = min.slice(i);
      if (indexedDB.cmp(key_tail, min_tail) < 0) {
        cursor.continue(cursor.key.slice(0, i).concat(min_tail));
        return;
      }

      var max_tail = max.slice(i);
      if (indexedDB.cmp(key_tail, max_tail) > 0) {
        cursor.continue(cursor.key.slice(0, i)
                        .concat([successor(cursor.key[i])])
                        .concat(min.slice(i + 1)));
        return;
      }
    }
    valueCallback(cursor.value);
    cursor.continue();
  };
}
	<!DOCTYPE html>
	<title>Indexed DB: N-Dimensional Select Example</title>
	<script src="select.js"></script>
	<script>
	// Copyright 2019 Google LLC.
	// SPDX-License-Identifier: Apache-2.0

	indexedDB.deleteDatabase('example');
	var open = indexedDB.open('example');
	open.onupgradeneeded = function() {
	var db = open.result;
	var store = db.createObjectStore('things', {autoIncrement: true});
	var index = store.createIndex('coords', ['x', 'y', 'z'], {unique: false});
	for (var x = 1; x <= 10; ++x) {
	for (var y = 1; y <= 10; ++y) {
	for (var z = 1; z <= 10; ++z) {
	store.put({name:''+x+','+y+','+z, x:x, y:y, z:z});
	}
	}
	}
	};

	function log(m) {
	document.documentElement
	.appendChild(document.createElement('div'))
	.appendChild(document.createTextNode(m));
	}
	open.onsuccess = function() {
	var db = open.result;
	var tx = db.transaction('things');
	var index = tx.objectStore('things').index('coords');

	select(index, [[4,6], [3,5], [7,10]],
	function(value) {
	log(JSON.stringify(value));
	},
	function() {
	log('done!');
	});
	};
	</script>
	// Copyright 2019 Google LLC.
	// SPDX-License-Identifier: Apache-2.0

	// First, we need to define a "successor" function. This works for numbers and
	// strings, but not other key types - add as necessary.
	function successor(key) {
	switch (typeof key) {
	case 'number':
	if (key === -Infinity) return -Number.MAX_VALUE;
	if (key === Infinity) return new Date(-8640000000000000);
	if (key === 0) return Number.MIN_VALUE;
	var epsilon = Math.abs(key);
	while (key + epsilon / 2 !== key)
	epsilon = epsilon / 2;
	return key + epsilon;
	case 'string':
	return key + '\x00';
	default:
	throw TypeError('Unsupported key type: ' + key);
	}
	}

	// And here's the N-dimensions selection function.
	// * index is the IDBIndex with an array key path of length N
	// * query is [[dim1_min, dim1_max], [dim2_min, dim3_max]]
	// * valueCallback() will be called synchronously with each value
	// * completeCallback() will be called when completed
	function select(index, query, valueCallback, completeCallback) {
	var min = query.map(function(dim) { return dim[0]; });
	var max = query.map(function(dim) { return dim[1]; });
	index.openCursor(IDBKeyRange.bound(min, max)).onsuccess = function(e) {
	var cursor = e.target.result;
	if (!cursor) {
	completeCallback();
	return;
	}

	for (var i = 1; i < cursor.key.length; ++i) {
	var key_tail = cursor.key.slice(i);

	var min_tail = min.slice(i);
	if (indexedDB.cmp(key_tail, min_tail) < 0) {
	cursor.continue(cursor.key.slice(0, i).concat(min_tail));
	return;
	}

	var max_tail = max.slice(i);
	if (indexedDB.cmp(key_tail, max_tail) > 0) {
	cursor.continue(cursor.key.slice(0, i)
	.concat([successor(cursor.key[i])])
	.concat(min.slice(i + 1)));
	return;
	}
	}
	valueCallback(cursor.value);
	cursor.continue();
	};
	}