Fast Range Queries and how to Code them

[GavinMendelGleason]

The storage of all XSD data types is stored in sorted order. This means that it is possible in principle to perform fast range queries. There are however a number of technical steps that have to be undertaken for this to work.

The prolog code functions by means of iterators, writen in rust, driven by mode. Different iterators are used for different modes. In the case of a sorting order it would need to be driven by an additional low level iterator which knew which direction to sort of objects on.

In addition terminus store is composed (in the general case) of parts. You will have negative and positive layers which tell whether something has been deleted or added. A general sort requires that the iterator walk up and down layers according to the next object across every layer which is exposed, adding the next result from each layer and filtering out those that are deleted.

If this iterator is implemented then the query compiler needs to be informed that a particular ordering will improve performance. This is a symbolic sort that can be performed in pure and not so complicated prolog. However after this is done some primitive needs to be exposed for the compilation step which will utilise the rust iterator.

So it will require work in both rust and prolog. The good news is that it should be possible to get very fast range queries this way as the storage primitives support it.