Ability to use custom sort order/collation in index?

[adueck]

I have been searching the documentation for this, but is there any way to apply a custom search order when making a binary index?

I need to be able to do this because I want to do $gte queries on a database of words written in a rare language with a special alphabet. Is this possible with loki.js?

Can different locales be used for sorting and comparing strings, ie (this ICU demo) ?

[obeliskos]

Well I have started refactoring our binary indexes for LokiDB and it currently allows passing a custom comparator on construction so a more full implementation will be implemented there.

For LokiJS, while we do currently have references (on default export) to our internal comparison functions, but don't think you can overwrite them as you would just be updating the references on export. You -can- currently pass a javascript filter function to a where() call but that is an array scan and does not leverage indexes. You could also pass in that same filter function to a chained sort() call to use for sorting.

I could look into wrapping those LokiJS comparison methods into an internal object and return that reference on our default export which should allow you to override that objects internal comparison functions, but that replaces comparisons -everywhere- (any normal comparisons would have to be in a separate loki db instance in which you did not override the comparisons). I would also need to benchmark this to ensure it does not adversely affect performance.

[Viatorus]

LokiDB has a full-text search (like a binary index for words) which supports any kind of characters.

…

[obeliskos]

Now that I re-read, yes I think this is referring more to searching -within- property values.

@adueck can you confirm whether your 'database of words' means multiple words within a single object property value or just (for example) a bunch of (separate) objects with property value to be considered in their entirety for comparison or sorting purposes.

Also, in case you weren't familiar with our references to LokiDB, it is next version of LokiJS that is in beta now.

[adueck]

@Viatorus Yes, I understand that I can search for any Unicode characters. Many other Javascript DBs have that feature. That's great but not exactly what I'm asking about.

@obeliskos In my use case it's the second thing you said:

a bunch of (separate) objects with property value to be considered in their entirety for comparison or sorting purposes.

If I have a dictionary app with English alphabet sorting, it's very easy for the client to search for a partial word and then get the next x number of results in alphabetical order using a $gte search.

For instance:

coll.find({'english': { '$gte': 'absol' }}); returns

{ "english": "absolent", ...
{ "english": "absolute", ...
{ "english": "absolutely", ...
{ "english": "absoluteness", ...
{ "english": "absoluter", ...
{ "english": "absolutes", ...
{ "english": "absolutest", ...
... etc.

Each of these results would be a separate object/document, in this case sorted by the english property value.

This is extremely useful for dictionary applications, and imitates the experience of browsing through a paper dictionary.

But this only works when you can sort a property value in alphabetical order. If you try this in a foreign language with different characters and a different alphabet order, the results get totally garbled and unusable.

There needs to be a way to customize the sorting order to do something different than the regular ASCII ordering. (ie. see this question explaining how CouchDB has this feature disabled: CouchDB Finnish/Swedish collation view)

If you guys could implement the capability for locale/language-based or custom sorting, that would be amazing. Currently PouchDB and AlaSQL do not have this feature either, and it would fill a real need. (PouchDB is open to working on making this feature pluggable and AlaSQL says it can't be done).

[obeliskos]

Ok still sounds similar to how @Viatorus's fts works but you could make do with the workaround I described.

I already have this done but feel the need to point out / clear up a few things :

• This setting would seem affect all loaded loki instances, all collections within loaded loki db instances, and all binary indices contained within all collections within all loaded loki db instances. If this is a web page that probably means per page load... for node it will probably cache the 'required' object so maybe for lifetime of node.js process (until the executable closes and restarts).
• If you intend to support multiple languages/sort ordering, you will have to 'hot-swap' the comparators when switching between different languages/sorting and any inserts/updates/removes/finds on a collection should always be done with the same set of comparators.
• You should only override the Comparators (aeq/lt/gt) if you are using binary indices, otherwise you can just override LokiOps operators.
• If you only have one set of comparators (one language) you can just override it directly after require() or script loaded and leave in effect without changing again.
• for each custom sort you will probably have to write a custom sort function that accepts two values and returns 1 if a > b, 0 if a == b, and -1 if a < b. If some languages share a sort ordering you can share compare function.

So, easy to shoot yourself in the foot...

LokiDB will have more fine grained comparators. Internally we will probably have 'loki' sorting and plain 'js' sorting (when strongly typed/typescript). We will probably also let you pass in named set of comparator functions on construction and optionally specify one of them when creating a binary index.

[obeliskos]

Ok, I added a 'Compators' property on default export... you can override its 'aeq', 'lt', and 'gt' function properties to point to your versions.

I made a Loki Sandbox gist example which just creates a sort function and then retrofits those three onto it. You can replace the 'cmp' function anytime you want to hot-swap a new comparator... such as swapping the 1 and -1 (gt/lt) values to sort descending.

[adueck]

Wow, thanks for the quick help on this.

I also found out that there is already a JavaScript localCompare() method that allows you to pass in any locale/language and it seems to work great! See: String.prototype.localeCompare() or Intl.Collator in the MDN docs.

So this works perfectly when I replace the sort function with,

var cmp = function(a, b) {
  return a.localeCompare(b, 'locale-HERE');
}

Thankfully the two languages I need to sort don't share any of the same characters and so the localeCompare() method works for comparing/sorting strings in both languages. No need for swapping back and forth for me.

Thank you so much for your great work and help!!

(edit: I see that specifying a different locale with localeCompare() is not supported across the board though, so I guess I would have to use a custom sort function for full device and browser compatibility).

[obeliskos]

Great all comparisons of all properties will go through that method now so if you query on data types other than string make sure to do type checking and provide alternate compare paths.

[adueck]

Thank you so much.

LokiDB will have more fine grained comparators. Internally we will probably have 'loki' sorting and plain 'js' sorting (when strongly typed/typescript). We will probably also let you pass in named set of comparator functions on construction and optionally specify one of them when creating a binary index.`

This will be fantastic when if fully implemented. I don't think there's any other JavaScript database out there that currently does this?

Also, one last little question... you mentioned:

You should only override the Comparators (aeq/lt/gt) if you are using binary indices, otherwise you can just override LokiOps operators.

Can you explain what you mean by the LokiOps operators ?

[obeliskos]

LokiOps contains an unindexed implementation of all the operators you can use within find() queries.

LokiJS/src/lokijs.js

Lines 384 to 567 in 00cc735

	var LokiOps = {
	// comparison operators
	// a is the value in the collection
	// b is the query value
	$eq: function (a, b) {
	return a === b;
	},
	// abstract/loose equality
	$aeq: function (a, b) {
	return a == b;
	},
	$ne: function (a, b) {
	// ecma 5 safe test for NaN
	if (b !== b) {
	// ecma 5 test value is not NaN
	return (a === a);
	}
	return a !== b;
	},
	// date equality / loki abstract equality test
	$dteq: function (a, b) {
	return Comparators.aeq(a, b);
	},
	// loki comparisons: return identical unindexed results as indexed comparisons
	$gt: function (a, b) {
	return Comparators.gt(a, b, false);
	},
	$gte: function (a, b) {
	return Comparators.gt(a, b, true);
	},
	$lt: function (a, b) {
	return Comparators.lt(a, b, false);
	},
	$lte: function (a, b) {
	return Comparators.lt(a, b, true);
	},
	// lightweight javascript comparisons
	$jgt: function (a, b) {
	return a > b;
	},
	$jgte: function (a, b) {
	return a >= b;
	},
	$jlt: function (a, b) {
	return a < b;
	},
	$jlte: function (a, b) {
	return a <= b;
	},
	// ex : coll.find({'orderCount': {$between: [10, 50]}});
	$between: function (a, vals) {
	if (a === undefined || a === null) return false;
	return (Comparators.gt(a, vals[0], true) && Comparators.lt(a, vals[1], true));
	},
	$jbetween: function (a, vals) {
	if (a === undefined || a === null) return false;
	return (a >= vals[0] && a <= vals[1]);
	},
	$in: function (a, b) {
	return b.indexOf(a) !== -1;
	},
	$nin: function (a, b) {
	return b.indexOf(a) === -1;
	},
	$keyin: function (a, b) {
	return a in b;
	},
	$nkeyin: function (a, b) {
	return !(a in b);
	},
	$definedin: function (a, b) {
	return b[a] !== undefined;
	},
	$undefinedin: function (a, b) {
	return b[a] === undefined;
	},
	$regex: function (a, b) {
	return b.test(a);
	},
	$containsString: function (a, b) {
	return (typeof a === 'string') && (a.indexOf(b) !== -1);
	},
	$containsNone: function (a, b) {
	return !LokiOps.$containsAny(a, b);
	},
	$containsAny: function (a, b) {
	var checkFn = containsCheckFn(a);
	if (checkFn !== null) {
	return (Array.isArray(b)) ? (b.some(checkFn)) : (checkFn(b));
	}
	return false;
	},
	$contains: function (a, b) {
	var checkFn = containsCheckFn(a);
	if (checkFn !== null) {
	return (Array.isArray(b)) ? (b.every(checkFn)) : (checkFn(b));
	}
	return false;
	},
	$type: function (a, b) {
	var type = typeof a;
	if (type === 'object') {
	if (Array.isArray(a)) {
	type = 'array';
	} else if (a instanceof Date) {
	type = 'date';
	}
	}
	return (typeof b !== 'object') ? (type === b) : doQueryOp(type, b);
	},
	$finite: function(a, b) {
	return (b === isFinite(a));
	},
	$size: function (a, b) {
	if (Array.isArray(a)) {
	return (typeof b !== 'object') ? (a.length === b) : doQueryOp(a.length, b);
	}
	return false;
	},
	$len: function (a, b) {
	if (typeof a === 'string') {
	return (typeof b !== 'object') ? (a.length === b) : doQueryOp(a.length, b);
	}
	return false;
	},
	$where: function (a, b) {
	return b(a) === true;
	},
	// field-level logical operators
	// a is the value in the collection
	// b is the nested query operation (for '$not')
	// or an array of nested query operations (for '$and' and '$or')
	$not: function (a, b) {
	return !doQueryOp(a, b);
	},
	$and: function (a, b) {
	for (var idx = 0, len = b.length; idx < len; idx += 1) {
	if (!doQueryOp(a, b[idx])) {
	return false;
	}
	}
	return true;
	},
	$or: function (a, b) {
	for (var idx = 0, len = b.length; idx < len; idx += 1) {
	if (doQueryOp(a, b[idx])) {
	return true;
	}
	}
	return false;
	}
	};

We expose LokiOps similarly to how we just added Comparators now... on the default export

LokiJS/src/lokijs.js

Lines 7327 to 7342 in 00cc735

	Loki.LokiOps = LokiOps;
	Loki.Collection = Collection;
	Loki.KeyValueStore = KeyValueStore;
	Loki.LokiMemoryAdapter = LokiMemoryAdapter;
	Loki.LokiPartitioningAdapter = LokiPartitioningAdapter;
	Loki.LokiLocalStorageAdapter = LokiLocalStorageAdapter;
	Loki.LokiFsAdapter = LokiFsAdapter;
	Loki.persistenceAdapters = {
	fs: LokiFsAdapter,
	localStorage: LokiLocalStorageAdapter
	};
	Loki.aeq = aeqHelper;
	Loki.lt = ltHelper;
	Loki.gt = gtHelper;
	Loki.Comparators = Comparators;
	return Loki;

If you have a binary index defined, some of those ops can use that instead of LokiOps for much faster filtering, those items are determined by this (internal only) map :

LokiJS/src/lokijs.js

Lines 569 to 582 in 00cc735

	// if an op is registered in this object, our 'calculateRange' can use it with our binary indices.
	// if the op is registered to a function, we will run that function/op as a 2nd pass filter on results.
	// those 2nd pass filter functions should be similar to LokiOps functions, accepting 2 vals to compare.
	var indexedOps = {
	$eq: LokiOps.$eq,
	$aeq: true,
	$dteq: true,
	$gt: true,
	$gte: true,
	$lt: true,
	$lte: true,
	$in: true,
	$between: true
	};

If you only want to override the unindexed LokiOps implementations you could (for example) just override LokiOps.$gte and all unindexed finds will use your new function.

So to be clear, how many collections do you have, (roughly) how many objects within those collections, and have you or will you be using loki binary indices within collection(s) to do ranged filtering or sorting?

[adueck]

Thank you very much for the attention and info. I wish I could give your repo 5 stars, not just one.

I only have one collection to be queried. There are currently about 5000 objects, but it will grow to around 15,000. I was planning on using the binary indexes because I'm aiming for maximum speed.

Along with the $gte I also have another feature to do fuzzy searching using $regex queries to correct common spelling mistakes. (Currently I am doing this with PouchDB using IndexedDB but it's too slow for this, taking 4-5 seconds per $regex query on older phones). Does the loki binary index help the speed of $regex full-text queries much? Or is it more important with a $gte type query?

(I noticed that with PouchDB the indexed $gte queries are instant/fast, but it's the $regex queries that are really too slow for my application. I'm looking forward to seeing the difference in speed that comes with an in-memory database.)

[Viatorus]

Well, me again: LokiDBs full-text search has a fuzzy search using levenstain distance adopted from here: http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is-100-times-faster.html?m=1. I would say it's the fastest JavaScript token based fuzzy out there. ;) The full-text search can also be used as standalone without LokiDB.