Uploaded image for project: 'Blazegraph (by SYSTAP)'
  1. Blazegraph (by SYSTAP)
  2. BLZG-741

Extend ASTStaticJoinOptimizer to reorder arbitrary length path nodes.

    Details

    • Type: New Feature
    • Status: In Progress
    • Resolution: Unresolved
    • Affects Version/s: BIGDATA_RELEASE_1_2_0
    • Fix Version/s: None
    • Labels:
      None

      Description

      The static join optimizer currently only considers statement patterns for re-ordering. It needs to be extended to take into account other types of join nodes, including the ArbitraryLengthPathNode (property paths with a '*' or '+' operator).

      This query, submitted by an open-source user, demonstrates the problem well (when run on his data):

      SELECT distinct ?a WHERE {

      ?a np:precision/rdfs:subClassOf+ CV:3.4.19.-

      }

      This query can be re-written as follows:

      SELECT distinct ?a WHERE {

      ?a np:precision ?b .

      ?b rdfs:subClassOf+ CV:3.4.19.- .

      }

      The real cardinalities of this query are as follows:

      SELECT distinct ?a WHERE {

      ?a np:precision ?b . #cardinality=4266240

      ?b rdfs:subClassOf+ CV:3.4.19.- . #cardinality=15

      }

      When I manually force the property path to run first, the query completes almost instantly. The static join optimizer needs to get this right automatically.

        Activity

        Hide
        mikepersonick mikepersonick added a comment -

        THis is a fairly significant refactor that I was not able to complete in one day. Will continue tomorrow. Basically refactoring the ASTStaticJoinOptimizer to work on instances of a new interface IReorderableNode instead of operating only on StatementPatternNodes.

        It may be possible to extend this to other types of nodes as well
        - for example UNIONs and possibly subqueries.

        Show
        mikepersonick mikepersonick added a comment - THis is a fairly significant refactor that I was not able to complete in one day. Will continue tomorrow. Basically refactoring the ASTStaticJoinOptimizer to work on instances of a new interface IReorderableNode instead of operating only on StatementPatternNodes. It may be possible to extend this to other types of nodes as well - for example UNIONs and possibly subqueries.
        Hide
        mikepersonick mikepersonick added a comment -

        Committed a fix to the simple case where there is only one statement pattern in the arbitrary length path expression. This fixes the query in the description.

        Needs to be extended to more complex arbitrary length path expressions, but no time for this right now. Checked in a placeholder called the ASTCardinalityOptimizer that would calculate the estimated cardinality of a join group. Leaving this ticket open for now.

        Show
        mikepersonick mikepersonick added a comment - Committed a fix to the simple case where there is only one statement pattern in the arbitrary length path expression. This fixes the query in the description. Needs to be extended to more complex arbitrary length path expressions, but no time for this right now. Checked in a placeholder called the ASTCardinalityOptimizer that would calculate the estimated cardinality of a join group. Leaving this ticket open for now.
        Hide
        mikepersonick mikepersonick added a comment -

        This works for simple ALP nodes now
        - one where there is just a single statement pattern. This is probably good enough for now, but I would like to hold this ticket open and extend the implementation to handle complex ALP nodes (ones with nested conjunctive joins).

        Show
        mikepersonick mikepersonick added a comment - This works for simple ALP nodes now - one where there is just a single statement pattern. This is probably good enough for now, but I would like to hold this ticket open and extend the implementation to handle complex ALP nodes (ones with nested conjunctive joins).

          People

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

            Dates

            • Created:
              Updated: