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.

[hoijnet]

I have been thinking a bit on the syntax for the range queries, please share your input if this is a relevant way!

• Range queries, what supports placing constraints in the rust engine instead:
  *triple(“v:subj”, “v:pred”, “v:obj”).where(“v:obj”, “eq”, “queen”)
  • triple(“v:subj”, “v:pred”, “v:obj”).where(“v:obj”, “gt”, 37.4)
  • triple(“v:subj”, “v:pred”, “v:obj”).
    • where(“v:obj”, “gt”, 37.4).
    • where(“v:pred”, “eq”, “temp”)
  • triple(“v:subj”, “v:pred”, “v:obj”).
    • where_doc(“temp”, “gt”, 37.4)
    • Note: the first parameter indicates a json-ld path, where arrays [], elements of array [1] or object memberships (a.b.c) at depth can be indicated. When a first match is found, make triples with “v:subj” fulfilling all the where_doc become returned
  • It may be prudent to support “and” + “or” + “not” constructs in the where clauses, or reuse existing terms for the operations
  • It should be possible to extend later with at least following operations: eq, neq, ge, le, gt, lt, within*
  • *within is a specific term to indicate time durations according to iso8601 so that one can specify day of week, day of month, month of year and specific periods of time.
  • Note: we need to ensure prefixes are correctly parsed and handled

Should a separate term, where be introduced, does it make sense to use the way of expressing as() as a template form for where, or should we use the base mechanisms (perhaps better) to express this, but expect that they get bolted on to the triple to make them pass into the rust engine.

There are some considerations to make for the WOQL language to continue with the correct traditions.

[GavinMendelGleason]

I think the current constraints are sufficient without having to add another operator. We just need to find the constraints on a given meta-variable and then send it in during the original triple query as an additional parameter to the iterator.

[hoijnet]

Makes sense!

As for the range queries, I think there could be two steps of the implementation as more than ranges could be offloaded:

1. Use WOQL triples constraints detection to offload triples selection to the filter mechanisms used by GraphQL in rust; they are about an order of magnitude faster than WOQL currently and would most likely filter triples much faster
2. Once the triples constraints detection is performed, let the range queries be optimised further for another magnitude or two faster range queries.
3. Consider the special case where inclusive ranges (greaterThan/lessThan) query optimisation as that can be further optimised in one go in the range queries

Removed the ISO8601 durations for now (were previously the below), that will have to be a separate thing:

Only operator missing from that perspective is probably the "within" duration operator to support iso8601 durations for time based checking that I would like to propose, I'll put it as an enhancement on Github. The engine can pass it on to the range query module when relevant for pre-filtering. But the within operator should be added to WOQL instead and then passed on.

[hoijnet]

I noticed an additional possible improvement for the triple() WOQL after comparing the performance between WOQL and GraphQL. GraphQL is (as expected) significantly faster in traversing the triple store. By potentially combining the filtering available in the GraphQL interface, a significant improvement could be achieved even before the range queries are implemented.

What would be needed in any case, as mentioned, is to identify the triple constraints on the variable in WOQL and feed them into rust so that rust could pre-filter the query. That would already be a significant improvement in itself, and the range queries take the next step in improvement.

[alexander-mart]

https://www.w3.org/TR/owl-time/