Qlever query planner w.r.t. number of filters

[LorenzBuehmann]

Hi again Qlever devs and experts,

currently using Qlever on a 2 billion triples dataset.

While playing around with some queries, I recognized that for one query the addition of some FILTER clauses to omit specific IRIs from the solution bindings, the query takes way longer time than without 3s vs 200s basically (modulo caching of execution probably):

without the additional filters

SELECT 
?exportCountry ?exportIndustry ?originCountry 
(SUM(?value) AS ?sum)
WHERE
{
  BIND(<https://data.coypu.org/trade/tiva/GBR> AS ?exportCountry )

  VALUES ?exportIndustry {
ind:D10T12 ind:D13T15 ind:D16 ind:D17T18 ind:D19 ind:D20 ind:D21 ind:D22 ind:D23 ind:D24 ind:D25 ind:D26 ind:D27 ind:D28 ind:D29 ind:D30 ind:D31T33
  }
  ?s a tiva:ExgrBsci .
  ?s coy:hasValue ?value .
  ?s tiva:hasExport ?export .
  ?export coy:hasCountryLocation ?exportCountry .
  ?export tiva:hasIndustryCode ?exportIndustry .
  ?s tiva:hasValueAddedOrigin ?origin .
  ?origin coy:hasCountryLocation ?originCountry .
  ?origin tiva:hasIndustryCode ?originIndustry .

  FILTER(?exportIndustry != <https://data.coypu.org/classification/tiva-21/DTOTAL>)
  FILTER(?originIndustry != <https://data.coypu.org/classification/tiva-21/DTOTAL>)
}
GROUP BY ?exportCountry ?exportIndustry ?originCountry
ORDER BY DESC(?sum)
LIMIT 12

with the additional filters

SELECT 
?exportCountry ?exportIndustry ?originCountry 
(SUM(?value) AS ?sum)
WHERE
{
  BIND(<https://data.coypu.org/trade/tiva/GBR> AS ?exportCountry )

  VALUES ?exportIndustry {
ind:D10T12 ind:D13T15 ind:D16 ind:D17T18 ind:D19 ind:D20 ind:D21 ind:D22 ind:D23 ind:D24 ind:D25 ind:D26 ind:D27 ind:D28 ind:D29 ind:D30 ind:D31T33
  }
  ?s a tiva:ExgrBsci .
  ?s coy:hasValue ?value .
  ?s tiva:hasExport ?export .
  ?export coy:hasCountryLocation ?exportCountry .
  ?export tiva:hasIndustryCode ?exportIndustry .
  ?s tiva:hasValueAddedOrigin ?origin .
  ?origin coy:hasCountryLocation ?originCountry .
  ?origin tiva:hasIndustryCode ?originIndustry .
 
  FILTER(?exportIndustry != <https://data.coypu.org/classification/tiva-21/DTOTAL>)
  FILTER(?originIndustry != <https://data.coypu.org/classification/tiva-21/DTOTAL>)

  # those are the additional filters
  FILTER(?originCountry != economy:EU28)
  FILTER(?originCountry != economy:EU15)
  FILTER(?originCountry != economy:ZEUR) 
}
GROUP BY ?exportCountry ?exportIndustry ?originCountry
ORDER BY DESC(?sum)
LIMIT 12

I attached the query analysis plans and trees as zipped HTML + CSS stuff - I couldn't find any export format nor is it possible to print that modal dialog as PDF or the like. Or is there some e.g. JSON data somewhere that I could forward to you

So any idea what's going on the in the query planner? Does the number of possible plans explode due to the filters? I check w.r.t. number of filters:

• 1 -> 9s
• 2 -> 41s
• 3 -> 205s

By the way

• I don't know how good VALUES works with Qlever so far
• and I cant use FILTER ( (NOT) IN ( ... )) with Qlever yet, which would reduce the number of FILTER expressions in my example if that is the reason for the performance degradation here

Query trees

qlever_tree_no_additional_filters.zip
qlever_tree_with_filters.zip

[joka921]

Hi Lorenz,
You have identified the source of the problem yourself:
QLever currently only uses the "optimimal" (wrt estimates) plan, which uses a dynamic approach the complexity of which is somewhere between polynomial and exponential in the number of triples + filters given. We are planning to additionally implement some better query planning algorithm for "large" (wrt number of triples/filters) queries, but for now the default hack is to help the query planner by putting braces {} around some parts of the query, those are then respected and evaluated first.

Another way you could currently reformulate the unsupported not in filter is by a single Filter expression:

FILTER (?x != <a> && ?x != <b> && ?y != <c>)

[hannahbast]

@LorenzBuehmann What exactly did you mean when you wrote: "I don't know how good VALUES works with Qlever so far"? Was it just a suspicion because the query above was so slow? Or is there a more specific reason why you think that VALUES don't work well?

[LorenzBuehmann]

@joka921 Yep, that's what I expected - thank's for the answer. And sure, we could merge all filters on same variables. It's more that people tend to be lazy or query builders are rather limited, so I observed that behaviour yesterday.

@hannahbast
No specific reason, just curious how you're doing it. It is just a solution sequence used, right?
It's more that I experience from other triple stores different ways of executing or optimizing, especially in more complex queries. An optimizer could try to push the value in the query, but that is not always possible because of possible "blocking patterns" - which could change the semantics of a query.

By the way, it's possible to put the VALUES outside of the query pattern part

SELECT * WHERE { BIND(1 AS ?x) }
VALUES ?y {2}

Do you handle that query as well? It doesn't look like? I don't need that feature, I also think this is rarely used if it's event used at all.