apache / apache/jena

Improvements to path evaluation

Open
#1,629 2 comments 2 reactions 0 assignees View on GitHub
enhancement
Dominant language
Java
Stars
1.4k
Forks
712
Avg merge
15h 41m
Merged PRs (30d)
53

Description

This issue proposes a roadmap for changes to path evaluation.

4.7.0 is December-ish and is already a significant release because of other, unrelated changes.

There are several strands in progress.

1. Iterators, not materialized lists, so LIMIT and timeout have an effect.
1. Better starting points for P_Alt in the case of `_ (:p1|:p2) _`.
1. Further P_Alt evaluation - transform or `PathLib`.
1. Triple pattern reordering across paths.

#### Iterators

Item 1 can be done now. We then have a starting point for the rest of the items.
It needs to ensure `PathLib` iterators are closed eventually (caveat:
cancellation is not on the iterator execution thread).

The iterators in `PathLib` don't need to be QueryIterators. They get wrapped in
a QueryIterator so cancellation will still happen. Cancellation needs to close
(Iter.close) the iterators carefully (caveat: different threads).
(functional decomposition) is better is not clear.

Proposal:
* Do this item now as a separate step

#### P_Alt starting points

`PathLib.determineUngroundedStartingSet` could handle the `(:p1|:p2)` case instead of relying on OpUnion expansion. There are more cases that just `(:p1|:p2)` that are the same general mechanism of "seeding by property" -- `:p+`, `(:p+|:q)` -- to find starting points but cardinality rules start to come into play.

Proposal:
* do point 2 in PathLib because it applies to other forms.

The test coverage needs to be verified.

Up to here is a target for 4.7.0 as 2 changes.

It gives a common base for further changes. Otherwise we have one big change that all has to be assessed so it will take longer before any change happens.

#### Further Path and Transform work

The objective is to have one set of active code in the codebase.

This needs an investigation is to run tests to perform both transforms and compare the output
to look for their optimization coverage.

The `PathTransform` (`PathVisitor` based) one may be a better base because it naturally handles `P_Alt`, but it may be harder to consider triple pattern reordering across paths and harder for some other cases like `?x (:p1+|...) ?z` which involve multiple path operators to be examined. The `PathCompiler` approach is easier for handling state across different path
operators and keeps what is the original path together but isn't yet flexible enough.

#### Process

Process-wise, discussing architecture on PRs does not work well. The PR UX is
focues on keeping code-related comments together but foir longer running PRs
when broader points are made, the time-ordering discussion of the overall
architecture is lost.

Proposal:
* Use this github issue for the general and architecture discussions
* Use the PR for discussion on specific code

See also #1616

Contributor guide

Open the contributing guide

Research direction

Start by reading PathLib.determineUngroundedStartingSet, PathTransform and PathCompiler, then run tests that compare both transform approaches as proposed. Review how PathLib iterators are wrapped in QueryIterator and how cancellation calls Iter.close. Done requires an agreed architecture and verified test coverage for iterator evaluation, starting points, and later path transformations.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
backend
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.