Filter perf vs Union. Any better solution?

Astn · April 27, 2017, 9:48pm

I have a query that I would like to simplify and still have it perform well.

The simple form of the query is as follows and I add additional filters depending on which subjects are requested,
But this performs quite poorly.

SELECT *
WHERE {
    ?s ?p ?o
    OPTIONAL {
    ?o ?pp ?oo
    }
    FILTER (
        ?s = <ex:id/12763>
        || ?s = <ex:id/15475>
        || ?s = <ex:id/26077>
        || ?s = <ex:id/10005>
        || ?s = <ex:id/12756>
        || ?s = <ex:id/29401>
        || ?s = <ex:id/14658>
        || ?s = <ex:id/29199>
        || ?s = <ex:id/53481>
        || ?s = <ex:id/41602>
        )
}

Query returned 60 results in 00:00:16.530

The Query Plan:

Projection(?s, ?p, ?o, ?pp, ?oo) [#38.4M]
`─ MergeJoinOuter(?o) [#38.4M]
   +─ Filter((?s = <ex:id/12763> || (?s = <ex:id/15475> || (?s = <ex:id/26077> || (?s = <ex:id/10005> || (?s = <ex:id/12756> || (?s = <ex:id/29401> || (?s = <ex:id/14658> || (?s = <ex:id/29199> || (?s = <ex:id/53481> || ?s = <ex:id/41602>)))))))))) [#0]
   │  `─ Scan[OSPC](?s, ?p, ?o) [#38.4M]
   `─ Scan[SPOC](?o, ?pp, ?oo) [#38.4M]

I rewrote it as follows, and it performs well, however its a huge ugly query.:

Select *
WHERE {
  
    {
	  select (<ex:id/12763> as ?s) ?p ?o 
      WHERE{ <ex:id/12763> ?p ?o.
           	OPTIONAL { ?o ?pp ?oo }
           } 
	}
  	UNION
  	{
	  select (<ex:id/15475> as ?s) ?p ?o 
      WHERE{ <ex:id/15475> ?p ?o.
           OPTIONAL { ?o ?pp ?oo }
           } 
	}
  UNION
  	{
	  select (<ex:id/26077> as ?s) ?p ?o 
      WHERE{ <ex:id/26077> ?p ?o.
           OPTIONAL { ?o ?pp ?oo }
           } 
	}
  UNION
  	{
	  select (<ex:id/10005> as ?s) ?p ?o 
      WHERE{ <ex:id/10005> ?p ?o.
           OPTIONAL { ?o ?pp ?oo }
           } 
	}
  UNION
  	{
	  select (<ex:id/12756> as ?s) ?p ?o 
      WHERE{ <ex:id/12756> ?p ?o.
           OPTIONAL { ?o ?pp ?oo }
           } 
	}
  UNION
  	{
	  select (<ex:id/29401> as ?s) ?p ?o 
      WHERE{ <ex:id/29401> ?p ?o.
           OPTIONAL { ?o ?pp ?oo }
           } 
	}
  UNION
  	{
	  select (<ex:id/14658> as ?s) ?p ?o 
      WHERE{ <ex:id/14658> ?p ?o.
           OPTIONAL { ?o ?pp ?oo }
           } 
	}
  UNION
  	{
	  select (<ex:id/29199> as ?s) ?p ?o 
      WHERE{ <ex:id/29199> ?p ?o.
           OPTIONAL { ?o ?pp ?oo }
           } 
	}
  UNION
  	{
	  select (<ex:id/53481> as ?s) ?p ?o 
      WHERE{ <ex:id/53481> ?p ?o.
           OPTIONAL { ?o ?pp ?oo }
           } 
	}
  UNION
  	{
	  select (<ex:id/41602> as ?s) ?p ?o 
      WHERE{ <ex:id/41602> ?p ?o.
           OPTIONAL { ?o ?pp ?oo }
           } 
	}
}

This produces the same results and runs quickly.

Query returned 60 results in 00:00:00.167

The Query Plan:

Projection(?s, ?p, ?o) [#60]
`─ Union [#60]
   +─ Projection(<ex:id/12763> AS ?s, ?p, ?o) [#6]
   │  `─ MergeJoinOuter(?o) [#6]
   │     +─ Sort(?o) [#6]
   │     │  `─ Scan[SPOC](<ex:id/12763>, ?p, ?o) [#6]
   │     `─ Scan[SC](?o, _, _) [#8.9M]
   `─ Union [#54]
      +─ Projection(<ex:id/15475> AS ?s, ?p, ?o) [#6]
      │  `─ MergeJoinOuter(?o) [#6]
      │     +─ Sort(?o) [#6]
      │     │  `─ Scan[SPOC](<ex:id/15475>, ?p, ?o) [#6]
      │     `─ Scan[SC](?o, _, _) [#8.9M]
      `─ Union [#48]
         +─ Projection(<ex:id/26077> AS ?s, ?p, ?o) [#6]
         │  `─ MergeJoinOuter(?o) [#6]
         │     +─ Sort(?o) [#6]
         │     │  `─ Scan[SPOC](<ex:id/26077>, ?p, ?o) [#6]
         │     `─ Scan[SC](?o, _, _) [#8.9M]
         `─ Union [#42]
            +─ Projection(<ex:id/10005> AS ?s, ?p, ?o) [#6]
            │  `─ MergeJoinOuter(?o) [#6]
            │     +─ Sort(?o) [#6]
            │     │  `─ Scan[SPOC](<ex:id/10005>, ?p, ?o) [#6]
            │     `─ Scan[SC](?o, _, _) [#8.9M]
            `─ Union [#36]
               +─ Projection(<ex:id/12756> AS ?s, ?p, ?o) [#6]
               │  `─ MergeJoinOuter(?o) [#6]
               │     +─ Sort(?o) [#6]
               │     │  `─ Scan[SPOC](<ex:id/12756>, ?p, ?o) [#6]
               │     `─ Scan[SC](?o, _, _) [#8.9M]
               `─ Union [#30]
                  +─ Projection(<ex:id/29401> AS ?s, ?p, ?o) [#6]
                  │  `─ MergeJoinOuter(?o) [#6]
                  │     +─ Sort(?o) [#6]
                  │     │  `─ Scan[SPOC](<ex:id/29401>, ?p, ?o) [#6]
                  │     `─ Scan[SC](?o, _, _) [#8.9M]
                  `─ Union [#24]
                     +─ Projection(<ex:id/14658> AS ?s, ?p, ?o) [#6]
                     │  `─ MergeJoinOuter(?o) [#6]
                     │     +─ Sort(?o) [#6]
                     │     │  `─ Scan[SPOC](<ex:id/14658>, ?p, ?o) [#6]
                     │     `─ Scan[SC](?o, _, _) [#8.9M]
                     `─ Union [#18]
                        +─ Projection(<ex:id/29199> AS ?s, ?p, ?o) [#6]
                        │  `─ MergeJoinOuter(?o) [#6]
                        │     +─ Sort(?o) [#6]
                        │     │  `─ Scan[SPOC](<ex:id/29199>, ?p, ?o) [#6]
                        │     `─ Scan[SC](?o, _, _) [#8.9M]
                        `─ Union [#12]
                           +─ Projection(<ex:id/53481> AS ?s, ?p, ?o) [#6]
                           │  `─ MergeJoinOuter(?o) [#6]
                           │     +─ Sort(?o) [#6]
                           │     │  `─ Scan[SPOC](<ex:id/53481>, ?p, ?o) [#6]
                           │     `─ Scan[SC](?o, _, _) [#8.9M]
                           `─ Projection(<ex:id/41602> AS ?s, ?p, ?o) [#6]
                              `─ MergeJoinOuter(?o) [#6]
                                 +─ Sort(?o) [#6]
                                 │  `─ Scan[SPOC](<ex:id/41602>, ?p, ?o) [#6]
                                 `─ Scan[SC](?o, _, _) [#8.9M]

Is there a better way to do this?

Astn · April 27, 2017, 10:01pm

I may have found a solution to this issue.

Here is my new query.

Query returned 60 results in 00:00:00.154


SELECT *
WHERE {
  
    VALUES ?s { 
    	<ex:id/12763>
        <ex:id/15475>
        <ex:id/26077>
        <ex:id/10005>
        <ex:id/12756>
        <ex:id/29401>
        <ex:id/14658>
        <ex:id/29199>
        <ex:id/53481>
        <ex:id/41602>
    }
    
    ?s ?p ?o
    OPTIONAL {
      ?o ?pp ?oo
    }
}

The Query Plan:

Projection(?s, ?p, ?o, ?pp, ?oo) [#0]
`─ MergeJoinOuter(?o) [#0]
   +─ Sort(?o) [#0]
   │  `─ DirectHashJoin(?s) [#0]
   │     +─ VALUES (?s) {
   │     │  +─ ( ex:id/12763 )
   │     │  +─ ( ex:id/15475 )
   │     │  +─ ( ex:id/26077 )
   │     │  +─ ( ex:id/10005 )
   │     │  +─ ( ex:id/12756 )
   │     │  +─ ( ex:id/29401 )
   │     │  +─ ( ex:id/14658 )
   │     │  +─ ( ex:id/29199 )
   │     │  +─ ( ex:id/53481 )
   │     │  `─ ( ex:id/41602 )
   │     │  }
   │     `─ Scan[SPOC](?s, ?p, ?o) [#38.7M]
   `─ Scan[SPOC](?o, ?pp, ?oo) [#38.7M]

evren · April 28, 2017, 1:25am

Yes, VALUES is the right thing to use here. Or you can use FILTER (s IN (...)) which will be transformed into VALUES by the query optimizer. In the future, query optimizer will do this transformation for || filters too.

Best,
Evren

Astn · April 28, 2017, 3:21pm

Thanks for the info, and I’m looking forward to the improved query optimizer.

system · May 12, 2017, 3:22pm

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.

Topic		Replies	Views
Binds in parallel Support	8	664	September 21, 2017
Query time blows out > 1000x moving from 5.0.3 => 5.0.4 Bug	7	608	November 8, 2017
Very different query plans for very similar queries, involving blank nodes Support	2	227	May 9, 2022
Error on query against multiple virtual graphs Bug	4	349	May 19, 2021
"optional" slow query Support	4	328	January 18, 2021

Filter perf vs Union. Any better solution?

Related Topics