Details

    • Type: Bug
    • Status: Done
    • Priority: Medium
    • Resolution: Done
    • Affects Version/s: None
    • Fix Version/s: BLAZEGRAPH_RELEASE_1_5_2
    • Component/s: None
    • Labels:
      None

      Description

      select * 
      with
      {
      select $a
      {
      }
        VALUES ($a) { (1) (2) }
             } AS %sub
      
      {
        include %sub
      }
      

      gives no results instead of two bindings for $a.
      All variants I can think of work correctly:

      select * 
      with
      {
      select $a
      {
        VALUES ($a) { (1) (2) }
      }
             } AS %sub
      
      {
        include %sub
      }
      
      select * {
        {
      select $a
      {
        hint:SubQuery hint:runOnce true .
      }
      VALUES ($a) { (1) (2) }
             }
        }
      
      select $a
      {
      }
      VALUES ($a) { (1) (2) }
      

      etc

        Activity

        jjc Jeremy Carroll created issue -
        michaelschmidt michaelschmidt made changes -
        Field Original Value New Value
        Assignee bryanthompson [ bryanthompson ] michaelschmidt [ michaelschmidt ]
        beebs Brad Bebee made changes -
        Workflow Trac Import v2 [ 13132 ] Trac Import v3 [ 13308 ]
        beebs Brad Bebee made changes -
        Workflow Trac Import v3 [ 13308 ] Trac Import v4 [ 14637 ]
        beebs Brad Bebee made changes -
        Workflow Trac Import v4 [ 14637 ] Trac Import v5 [ 15988 ]
        michaelschmidt michaelschmidt made changes -
        Status Open [ 1 ] Accepted [ 10101 ]
        Hide
        michaelschmidt michaelschmidt added a comment -

        Issue has been fixed in the master as part of join refactoring, test cases have been added. Please find below some generic comments on the join order refactoring which includes fixes for the current ticket.

        1. Key changes:
          1. Implemented new optimizer (ASTJoinGroupOptimizer), which puts the constructs into the right order
            1. Addressing mainly two correctness problems
              1. Reordering of non-reorderable constructs (OPTIONAL problematics)
              2. Proper handling of nodes that require variables to be bound (FILTER NOT EXISTS, BIND, certain SERVICEs)
          2. Approaches to the two problems
            1. Join order optimization now takes “partitions” (in form of OPTIONALs into account), reordering across partitions only where valid
            2. New Interface IVariableBindingRequirements with central method getRequiredVariables(), which determines the variables that must be bound prior to executing a mode
          3. Optimizations:
            1. Proper treatment of FILTER NOT EXISTS queries, now correct + more precise placement (as for other FILTERs)
            2. Also more precise placement of FILTER expressions that cannot be attached to a single join group node, namely
              1. … as early as possible
              2. … correctly placed in case triple patterns are reordered by the static optimizer
            3. Proper treatment of complex SERVICEs requiring incoming bound variables -> placed at first possible position
            4. Proper treatment of BIND and VALUES clauses -> placed at first
          4. Reusable components for FILTER placement, extraction of interesting variable sets from join groups, etc. -> clear the way for accelerated implementation of other rewriting heuristics
          5. Two “modes” for optimizer:
            1. Assert valid order & optimize
            2. Assert valid order only
          6. Test cases for optimizer itself at query and AST level
        1. Refactoring changes
          1. Interface IVariableBindingRequirements, with the central method getRequiredBound() and associated methods at ServiceFactory (with slightly different signature for extracting this information from service nodes)
            1. Implementation of the interface in various classes based on StaticAnalysis utility methods
            2. For services, the interface implementation is (at the time being) the same everywhere (requiredBound = \emptyset, imposing no constraint), see FulltextSearchServiceFactory.getRequiredBound() for how an implementation could look like (and we may want to adjust other services to offer incoming bound variables in the future)
            3. The implementation of this interface amounts for most of the changes. Many of them invoke setting up a new empty hash set.
          2. The optimizer itself: ASTJoinGroupOrderOptimizer
            1. Closely related are ASTJoinGroupPartition(s), offering data structure and the key utility methods for placement of nodes within partitions based on heuristics and variable binding constraints
            2. IASTJoinGroupPartitionReorderer: interface for an inter-partition optimizer; currently, there’s only a simple implementation (TypeBasedASTJoinGroupPartitionReorderer, in large parts reflecting the behaviour of the old optimizer), but this is how I would envision to hook in the StaticAnalysis (the interface might need to be changed/extended, it’s a first step).
          3. Reusable utility classes (used by the optimizer)
            1. GroupNodeVarBindingInfo & GroupNodeVarBindingInfoMap -> summary container for looking up different aspects related to variables in the group node (independent from its position in a given join group), and an associated class easing construction of GroupNodeVarBindingInfo objects for a set of nodes
            2. ASTFilterPlacer: utility class that supports the precise and correct placement of FILTER expressions within a list of IGroupMemberNodes
              ASTJoinGroupFilterExistsInfo: class implementing functionality to identify and access FILTER [NOT] EXISTS nodes within a join group (which are translated as a hybrid of an ASK subquery and a FilterNode, thus requiring special handling)
            3. ASTTypeBasedNodeClassifier (&ASTTypeBasedNodeClassifierConstraint): supports, given a set of types as input, the partitioning of a node list into lists of nodes with the give type + rest, including additional constraints for membership to a certain partition
          4. Minor things
        2. ASTBottomUpOptimizer -> minor bugfix (as documented inline)
        3. ASTSparql11SubqueryOptimizer -> minor bugfix (inheritance of bindings clauses to subqueries)
        4. ASTStaticBindingsOptimizer -> minor bugfix (see in code documentation for details)
        5. DefaultOptimizerList -> hooked in new optimizer
        Show
        michaelschmidt michaelschmidt added a comment - Issue has been fixed in the master as part of join refactoring, test cases have been added. Please find below some generic comments on the join order refactoring which includes fixes for the current ticket. — Key changes: Implemented new optimizer (ASTJoinGroupOptimizer), which puts the constructs into the right order Addressing mainly two correctness problems Reordering of non-reorderable constructs (OPTIONAL problematics) Proper handling of nodes that require variables to be bound (FILTER NOT EXISTS, BIND, certain SERVICEs) Approaches to the two problems Join order optimization now takes “partitions” (in form of OPTIONALs into account), reordering across partitions only where valid New Interface IVariableBindingRequirements with central method getRequiredVariables(), which determines the variables that must be bound prior to executing a mode Optimizations: Proper treatment of FILTER NOT EXISTS queries, now correct + more precise placement (as for other FILTERs) Also more precise placement of FILTER expressions that cannot be attached to a single join group node, namely … as early as possible … correctly placed in case triple patterns are reordered by the static optimizer Proper treatment of complex SERVICEs requiring incoming bound variables -> placed at first possible position Proper treatment of BIND and VALUES clauses -> placed at first Reusable components for FILTER placement, extraction of interesting variable sets from join groups, etc. -> clear the way for accelerated implementation of other rewriting heuristics Two “modes” for optimizer: Assert valid order & optimize Assert valid order only Test cases for optimizer itself at query and AST level Refactoring changes Interface IVariableBindingRequirements, with the central method getRequiredBound() and associated methods at ServiceFactory (with slightly different signature for extracting this information from service nodes) Implementation of the interface in various classes based on StaticAnalysis utility methods For services, the interface implementation is (at the time being) the same everywhere (requiredBound = \emptyset, imposing no constraint), see FulltextSearchServiceFactory.getRequiredBound() for how an implementation could look like (and we may want to adjust other services to offer incoming bound variables in the future) The implementation of this interface amounts for most of the changes. Many of them invoke setting up a new empty hash set. The optimizer itself: ASTJoinGroupOrderOptimizer Closely related are ASTJoinGroupPartition(s), offering data structure and the key utility methods for placement of nodes within partitions based on heuristics and variable binding constraints IASTJoinGroupPartitionReorderer: interface for an inter-partition optimizer; currently, there’s only a simple implementation (TypeBasedASTJoinGroupPartitionReorderer, in large parts reflecting the behaviour of the old optimizer), but this is how I would envision to hook in the StaticAnalysis (the interface might need to be changed/extended, it’s a first step). Reusable utility classes (used by the optimizer) GroupNodeVarBindingInfo & GroupNodeVarBindingInfoMap -> summary container for looking up different aspects related to variables in the group node (independent from its position in a given join group), and an associated class easing construction of GroupNodeVarBindingInfo objects for a set of nodes ASTFilterPlacer: utility class that supports the precise and correct placement of FILTER expressions within a list of IGroupMemberNodes ASTJoinGroupFilterExistsInfo: class implementing functionality to identify and access FILTER [NOT] EXISTS nodes within a join group (which are translated as a hybrid of an ASK subquery and a FilterNode, thus requiring special handling) ASTTypeBasedNodeClassifier (&ASTTypeBasedNodeClassifierConstraint): supports, given a set of types as input, the partitioning of a node list into lists of nodes with the give type + rest, including additional constraints for membership to a certain partition Minor things ASTBottomUpOptimizer -> minor bugfix (as documented inline) ASTSparql11SubqueryOptimizer -> minor bugfix (inheritance of bindings clauses to subqueries) ASTStaticBindingsOptimizer -> minor bugfix (see in code documentation for details) DefaultOptimizerList -> hooked in new optimizer
        michaelschmidt michaelschmidt made changes -
        Status Accepted [ 10101 ] In Progress [ 3 ]
        michaelschmidt michaelschmidt made changes -
        Status In Progress [ 3 ] Resolved [ 5 ]
        michaelschmidt michaelschmidt made changes -
        Status Resolved [ 5 ] In Review [ 10100 ]
        michaelschmidt michaelschmidt made changes -
        Resolution Done [ 10000 ]
        Status In Review [ 10100 ] Done [ 10000 ]
        beebs Brad Bebee made changes -
        Workflow Trac Import v5 [ 15988 ] Trac Import v6 [ 18379 ]
        michaelschmidt michaelschmidt made changes -
        Fix Version/s BLAZEGRAPH_RELEASE_1_5_2 [ 10164 ]
        beebs Brad Bebee made changes -
        Workflow Trac Import v6 [ 18379 ] Trac Import v7 [ 19781 ]
        beebs Brad Bebee made changes -
        Workflow Trac Import v7 [ 19781 ] Trac Import v8 [ 21408 ]

          People

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

            Dates

            • Created:
              Updated:
              Resolved: