Questions about SPARQL query processing

[elem güzel <el...@gmail.com>]

Hello;

I have been studying about join ordering problems at SPARQL queries and i
have been using ARQ for that. I aim to change order of triple patterns at
algebra level.
But i have some problems and i need to ask you.

1 -   Which kind of algorithms are used for join operation? (Nested-loop,
merge-join ...etc.) (Especially at "Algebra.exec(op, model)" function)
2-    Is ARQ using bushy trees or left-deep trees at execution of query?

Could you answer these questions or send related articles?

Thank you very much,
Best regards.

-- 
Elem GÜZEL

Re: Questions about SPARQL query processing

[Andy Seaborne <an...@apache.org>]

On 22/02/12 11:18, elem güzel wrote:
> Hello;
>
> I have been studying about join ordering problems at SPARQL queries and i
> have been using ARQ for that. I aim to change order of triple patterns at
> algebra level.
> But i have some problems and i need to ask you.
>
> 1 -   Which kind of algorithms are used for join operation? (Nested-loop,
> merge-join ...etc.) (Especially at "Algebra.exec(op, model)" function)

It depends on the storage layer's execution.

The ARQ high level optimizer has functions to reorg the join patterns - 
it introduces (sequence) and (conditional) which flag that the execution 
can be done with an unscoped index join.  If the query is not amenable 
to that reordering it uses a fairly dumb inner loop join; but such 
queries are not that common, excpt in test cases!

If you see improvements to make, I hope you will submit the improvements 
to the project?

The TDB storage layer uses that transformation set and also does stats 
based reordering of BGPs.

The memory execution executes the algebra after high-level optimization 
fairly directly.

What SDB does depends on the database.

> 2-    Is ARQ using bushy trees or left-deep trees at execution of query?

(sequence) is basically trying to make things left-deep.

> Could you answer these questions or send related articles?

The code for OpExecutorTDB and (in ARQ) OpExecutor.

	Andy

>
> Thank you very much,
> Best regards.
>