LiUSemWeb / LiUSemWeb/HeFQUIN

Avoid duplicate requests in index nested loops joins

Open
#147 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

performance improvement
Dominant language
Java
Stars
35
Forks
3
Avg merge
2d 4h
Merged PRs (30d)
26

Description

Both alternatives of the index nested loops join (ExecOpGenericIndexNestedLoopsJoinWithRequestOps and ExecOpGenericIndexNestedLoopsJoinWithRequests) are considering all input solution mappings separate from one another. As a consequence, the same request may be created and processed multiple times.

For instance, assume two solution mappings with the same value for variable ?x and different values for variable ?y, and ?x is the join variable (i.e., the triple pattern considered by the iNLJ contains ?x). Then, for each of the two solution mappings, the same triple pattern request is created (by replacing the variable ?x in the triple pattern with the same value).

While the second of these requests (and note that there may be many more than just two!) may ultimately be served from the request cache, creating and processing it should be avoided. The purpose of this issue is to develop and implement an approach to do so.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reading ExecOpGenericIndexNestedLoopsJoinWithRequestOps and ExecOpGenericIndexNestedLoopsJoinWithRequests, then trace how each creates requests and how the request cache is used. Reproduce the two-solution-mapping scenario described in the issue and determine where equivalent instantiated triple-pattern requests can be identified. Done means each unique request is created and processed only once.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
databases, distributed-systems
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.