Details

      Description

      It would be nice to have more sophisticated optimization strategies for FILTER expressions. This optimizer may apply strategies such as


      - the elimination of duplicate filter expressions,
      - decomposition of complex conjunctive filter expressions (to make the components pushable independently),
      - reordering of filters (where it makes sense)
      - etc.

      The optimizer should run before running the ASTAttachJoinFilterRewriter, and improve the outcome of the latter.

        Activity

        beebs Brad Bebee created issue -
        Hide
        michaelschmidt michaelschmidt added a comment -

        See also https://phabricator.wikimedia.org/T96094 for an example that bears optimization potential (comment from Bryan, Fri, Apr 17, 8:05 PM)

        Show
        michaelschmidt michaelschmidt added a comment - See also https://phabricator.wikimedia.org/T96094 for an example that bears optimization potential (comment from Bryan, Fri, Apr 17, 8:05 PM)
        Hide
        michaelschmidt michaelschmidt added a comment - - edited

        Other possibilities are:

        • Pushing FILTERs into the join operation (rather than applying them on top), in order to avoid materialization of unneeded results
        • Inlining of non-equality FILTER expressions that do not require materialization
        • Inlining of non-equality FILTER expressions that require materialization with prior materialization step
        • Eliminate redundant application of already inlined FILTERS (cf. SP2B q6)
        • Eliminate redundant filters (e.g. bound(?x) where ?x is known to be bound)

        Note that there are already mechanisms to inline FILTERs at access path iterator level (see IndexLocalFilter, AccessPathFilter as entry points).

        This will not be addressed as part of this ticket, opened the new ticket BLZG-1338.

        Show
        michaelschmidt michaelschmidt added a comment - - edited Other possibilities are: Pushing FILTERs into the join operation (rather than applying them on top), in order to avoid materialization of unneeded results Inlining of non-equality FILTER expressions that do not require materialization Inlining of non-equality FILTER expressions that require materialization with prior materialization step Eliminate redundant application of already inlined FILTERS (cf. SP2B q6) Eliminate redundant filters (e.g. bound(?x) where ?x is known to be bound) Note that there are already mechanisms to inline FILTERs at access path iterator level (see IndexLocalFilter, AccessPathFilter as entry points). This will not be addressed as part of this ticket, opened the new ticket BLZG-1338 .
        beebs Brad Bebee made changes -
        Field Original Value New Value
        Workflow Trac Import v2 [ 12967 ] Trac Import v3 [ 13406 ]
        beebs Brad Bebee made changes -
        Workflow Trac Import v3 [ 13406 ] Trac Import v4 [ 14735 ]
        Hide
        michaelschmidt michaelschmidt added a comment -

        Implemented filter decomposition and elimination of duplicate filter expressions. Covers the following functionality from the features mentioned above:

        • the elimination of duplicate filter expressions,
        • decomposition of complex conjunctive filter expressions (to make the components pushable independently),
        • eliminate redundant filters (e.g. bound(?x) where ?x is known to be bound)

        The implementation comprises the following:

        1. Functionality in StaticAnalysis to
          1. Check CNF (methods isCNF(FilterNode), isCNF(IValueExpressionNode), isCNFDisjunct, isCNFNegationOrTerminal)
          2. Convert to CNF (methods toCNF, pushNegations, pushDisjuncts)
          3. Some smaller convenience methods
        2. ASTFilterNormalizationOptimizer -> the optimizer, which brings FILTERs into CNF, decomposes them, and eliminates duplicate (as well as some “always satisfied” disjuncts)
        3. Test case TestASTFilterNormalizationOptimizer, covering both the utility functions in StaticAnalysis as well as the optimizer itself
        4. Minor extensions to FunctionNode (added some convenience methods)

        Issued pull request in branch filter-decomposition. Once merged, I'll close down this ticket and open up a follow-up ticket for filter improved inlining/attachment (which is a separate issue).

        Show
        michaelschmidt michaelschmidt added a comment - Implemented filter decomposition and elimination of duplicate filter expressions. Covers the following functionality from the features mentioned above: the elimination of duplicate filter expressions, decomposition of complex conjunctive filter expressions (to make the components pushable independently), eliminate redundant filters (e.g. bound(?x) where ?x is known to be bound) The implementation comprises the following: Functionality in StaticAnalysis to Check CNF (methods isCNF(FilterNode), isCNF(IValueExpressionNode), isCNFDisjunct, isCNFNegationOrTerminal) Convert to CNF (methods toCNF, pushNegations, pushDisjuncts) Some smaller convenience methods ASTFilterNormalizationOptimizer -> the optimizer, which brings FILTERs into CNF, decomposes them, and eliminates duplicate (as well as some “always satisfied” disjuncts) Test case TestASTFilterNormalizationOptimizer, covering both the utility functions in StaticAnalysis as well as the optimizer itself Minor extensions to FunctionNode (added some convenience methods) Issued pull request in branch filter-decomposition. Once merged, I'll close down this ticket and open up a follow-up ticket for filter improved inlining/attachment (which is a separate issue).
        michaelschmidt michaelschmidt made changes -
        Status Accepted [ 10101 ] In Progress [ 3 ]
        Priority Highest [ 1 ]
        michaelschmidt michaelschmidt made changes -
        Status In Progress [ 3 ] Resolved [ 5 ]
        michaelschmidt michaelschmidt made changes -
        Status Resolved [ 5 ] In Review [ 10100 ]
        michaelschmidt michaelschmidt made changes -
        Status In Review [ 10100 ] Done [ 10000 ]
        beebs Brad Bebee made changes -
        Workflow Trac Import v4 [ 14735 ] Trac Import v5 [ 16043 ]
        beebs Brad Bebee made changes -
        Workflow Trac Import v5 [ 16043 ] Trac Import v6 [ 18312 ]
        beebs Brad Bebee made changes -
        Fix Version/s BLAZEGRAPH_RELEASE_1_5_2 [ 10164 ]
        beebs Brad Bebee made changes -
        Workflow Trac Import v6 [ 18312 ] Trac Import v7 [ 19710 ]
        beebs Brad Bebee made changes -
        Workflow Trac Import v7 [ 19710 ] Trac Import v8 [ 21333 ]

          People

          • Assignee:
            michaelschmidt michaelschmidt
            Reporter:
            michaelschmidt michaelschmidt
          • Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved: