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

BOpUtility#preOrderTraversal() takes time exponential in the depth of the operator tree.

    XMLWordPrintable

    Details

    • Type: Bug
    • Status: Done
    • Resolution: Done
    • Affects Version/s: QUADS_QUERY_BRANCH
    • Fix Version/s: None
    • Component/s: B+Tree

      Description

      BOpUtility#preOrderTraversal() is used for several purposes during SPARQL query evaluation. This method can take time which appears to be exponential in the depth of the operator tree, as demonstrated by:

      com.bigdata.rdf.bop.TestBOpUtility
      

      Very nearly the same logic is used by the B+Tree iterators, but the B+Tree never has depths as high as those associated with a FILTER with a lot of components. Once the fix is identified, we should also look at the B+Tree to see if the fix can be applied there as well.

        Attachments

          Activity

            People

            Assignee:
            martyncutcher martyncutcher
            Reporter:
            bryanthompson bryanthompson
            Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

              Dates

              Created:
              Updated:
              Resolved: