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! Only operator missing from that perspective is probably the "within" duration operator for 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.