Uploaded image for project: 'Apache Jena'
  1. Apache Jena
  2. JENA-615

Possible optimisation for FILTER(?var != <constant>)

    XMLWordPrintableJSON

    Details

      Description

      I have an idea for a possible optimisation for queries of the following general form:

      SELECT *
      WHERE
      {
        # Some Patterns
        FILTER(?var != <http://constant>)
      } 
      

      This pattern crops up surprisingly often in real SPARQL workloads since it is often used to either limit a variable to exclude certain possibilities or to avoid self referential links in the data.

      In some cases it seems like this could be safely rewritten as follows:

      SELECT *
      WHERE
      {
        # Some Patterns
        MINUS { BIND(<http://constant> AS ?var) }
      }
      

      Or perhaps in a more generalised form like so:

      SELECT * WHERE
      {
        # Some patterns
        MINUS { VALUES ?var { <http://constant/1> <http://constant/2> } }
      }
      

      Which would nicely deal with the case of stating that a variable is not equal to multiple constant values.

      As I pointed out earlier this would not apply in every case, specifically I think at least the following must be true:

      • The variable must be guaranteed to be bound (similar to existing filter equality and implicit join optimisations)

      There is also the potential to spot cases where the variable will always be unbound and thus the expression is always an error and replace the entire sub-tree with table empty as we already do for equality and implicit join filters.

      I plan on taking a look at implementing this in the new year, if anyone has any thoughts on this (especially wrt to restrictions that should apply to when the optimisation is considered safe) then please comment.

        Attachments

        1. inequality_bsbm_1M.csv
          3 kB
          Rob Vesse
        2. inequality_bsbm_1M.txt
          29 kB
          Rob Vesse
        3. inequality_lubm0.csv
          3 kB
          Rob Vesse
        4. inequality_lubm0.txt
          29 kB
          Rob Vesse
        5. inequality_sp2b_10k.csv
          3 kB
          Rob Vesse
        6. inequality_sp2b_10k.txt
          29 kB
          Rob Vesse
        7. inequality_sp2b_50k.csv
          3 kB
          Rob Vesse
        8. inequality_sp2b_50k.txt
          29 kB
          Rob Vesse
        9. inequality_sp2b_250k.csv
          3 kB
          Rob Vesse
        10. inequality_sp2b_250k.txt
          29 kB
          Rob Vesse

          Activity

            People

            • Assignee:
              rvesse Rob Vesse
              Reporter:
              rvesse Rob Vesse
            • Votes:
              0 Vote for this issue
              Watchers:
              4 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: