search

quadstorejs / quadstore

A LevelDB-backed graph database for JS runtimes (Node.js, Deno, browsers, ...) supporting SPARQL queries and the RDF/JS interface.
https://github.com/quadstorejs/quadstore
MIT License
202 stars 14 forks source link

PERFORMANCE: window sorting #144

Closed jacoscaz closed 2 years ago

jacoscaz commented 2 years ago

Although the current sorting mechanism seems to be reasonably fast already, there's an optimization that could make it even faster.

As it stands today, any difference between the requested order and the order provided by the selected index leads to a complete re-ordering of results. However, there are cases in which partial re-ordering would be a better pick. For example, a requested ordering of ['subject', 'object'] against the index ['subject', 'predicate', 'object', 'graph'] would be better served by re-ordering quads _per each value ofsubject`_. This likely wouldn't make a dramatic difference in terms of total sorting time but it would lead to the sorting iterator beginning to emit quads much faster.

Comunica has already implemented sorting based on sliding windows, although its windows are defined by their length rather than by the value of a given term/variable.

jacoscaz commented 2 years ago

Closing this as ideas for performance improvements are now tracked as cards in https://github.com/beautifulinteractions/node-quadstore/projects/9 .