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

Choosing the index for testing fully bound access paths based on index locality

    Details

      Description

      We might benefit by choosing a non-SPO index when testing a fully bound triple. Consider:

      query :- (a b ?c) AND (?c, d, e).

      Assuming that (a b ?c) is more selective, we would normally choose the SPO index for both access paths. However, the POS index will have better locality for (?c d e), so perhaps we would do better by sending the binding sets to that index?

      The guiding priciple would be, "when fully bound, choose the index with better locality based on the variable(s) in the triple pattern."

      If you think this makes sense, let's file and issue for this. I would have to review LUBM/BSBM to be certain, but I would not be suprised if both of those benchmarks included queries which had the same characteristic. As the number of variables in the second triple pattern increases, there will be less locality in the index so this might work better for one unbound triple patterns than for two unbound triple patterns.

      One other factor, especially in scale-out, is that we have a bloom filter in front of the primary index for the statement relation (SPO/SPOC). The bloom filter provides a significant performance boost. If we decide to choose indices other than SPO/SPOC, then we should make sure that we enable the bloom filter for the rest of the statement indices.

        Activity

        Hide
        bryanthompson bryanthompson added a comment -

        Mike has been reporting significant performance improvements associated with the use of the POS index for point tests on fully bound access paths for triple patterns such as "P??" and "PO?". The rationale for improved performance is that the index accesses are concentrated in the same region of the index because the P is a constant in this triple pattern.

        Historically, we have been using SPO (or SPOC for quads) whenever the predicate became fully bound during query evaluation (as a result of the propagation of variable bindings from solutions). After talking this through with Mike, we have decided to change the code in SPOKeyOrder#getKeyOrder()/2 to use the index associated with the original triple pattern rather than the SPO/SPOC index.

        The ASTStaticJoinOptimizer currently annotations the predicates with AST2BOpBase.Annotations.ORIGINAL_INDEX. This is the index associated with the original triple or quad pattern without regard to any propagation of variable bindings. Therefore, I have modified SPOKeyOrder#getKeyOrder()/2 to use this ORIGINAL_INDEX annotation (if present) when the predicate is fully bound during evaluation and to default to the SPO / SPOC index if the predicate is fully bound by the ORIGINAL_INDEX annotation is not present.

        The only drawback with this approach is that the ORIGINAL_INDEX annotation is not present if the static join order optimizer is disabled. However, the ORIGINAL_INDEX annotation COULD be lifted into another ASTOptimizer in order to guarantee that it is always predicate. I have added a TODO for this where ORIGINAL_INDEX is declared and where it is applied by the static optimizer to the predicate.

        Since point tests can now occur against any statement index, I also modified SPORelation#getStatementIndexMetadata() to enable the bloom filter for ALL statement indices, not just SPO. Also, through an oversight, we were not enabling the bloom filter for ANY of the statement indices in quads mode. It is now enabled it both triples and quads modes.

        Changes to SPOKeyOrder#getKeyOrder()/2 and SPORelation#getStatementIndexMetadata().

        Committed revision r6357.

        Show
        bryanthompson bryanthompson added a comment - Mike has been reporting significant performance improvements associated with the use of the POS index for point tests on fully bound access paths for triple patterns such as "P??" and "PO?". The rationale for improved performance is that the index accesses are concentrated in the same region of the index because the P is a constant in this triple pattern. Historically, we have been using SPO (or SPOC for quads) whenever the predicate became fully bound during query evaluation (as a result of the propagation of variable bindings from solutions). After talking this through with Mike, we have decided to change the code in SPOKeyOrder#getKeyOrder()/2 to use the index associated with the original triple pattern rather than the SPO/SPOC index. The ASTStaticJoinOptimizer currently annotations the predicates with AST2BOpBase.Annotations.ORIGINAL_INDEX. This is the index associated with the original triple or quad pattern without regard to any propagation of variable bindings. Therefore, I have modified SPOKeyOrder#getKeyOrder()/2 to use this ORIGINAL_INDEX annotation (if present) when the predicate is fully bound during evaluation and to default to the SPO / SPOC index if the predicate is fully bound by the ORIGINAL_INDEX annotation is not present. The only drawback with this approach is that the ORIGINAL_INDEX annotation is not present if the static join order optimizer is disabled. However, the ORIGINAL_INDEX annotation COULD be lifted into another ASTOptimizer in order to guarantee that it is always predicate. I have added a TODO for this where ORIGINAL_INDEX is declared and where it is applied by the static optimizer to the predicate. Since point tests can now occur against any statement index, I also modified SPORelation#getStatementIndexMetadata() to enable the bloom filter for ALL statement indices, not just SPO. Also, through an oversight, we were not enabling the bloom filter for ANY of the statement indices in quads mode. It is now enabled it both triples and quads modes. Changes to SPOKeyOrder#getKeyOrder()/2 and SPORelation#getStatementIndexMetadata(). Committed revision r6357.
        Hide
        bryanthompson bryanthompson added a comment -

        [comment \\- it was on the wrong ticket|removed]

        Show
        bryanthompson bryanthompson added a comment - [comment \\- it was on the wrong ticket|removed]
        Hide
        bryanthompson bryanthompson added a comment -

        I have not observed any performance gain on either LUBM or BSBM yet. I want to go back and verify this observation by taking the change out of the current SVN revision and verifying that performance looks the same (apples to apples with only the single delta involved in the comparison).

        Show
        bryanthompson bryanthompson added a comment - I have not observed any performance gain on either LUBM or BSBM yet. I want to go back and verify this observation by taking the change out of the current SVN revision and verifying that performance looks the same (apples to apples with only the single delta involved in the comparison).
        Hide
        bryanthompson bryanthompson added a comment -

        I just added a static boolean to enable/disable the locality optimization to SPOKeyOrder. It is at the top of the class. It is currently disabled.

        Committed revision r6360.
        Committed revision r6361. (marks the flag as transient as well as static and final)

        Show
        bryanthompson bryanthompson added a comment - I just added a static boolean to enable/disable the locality optimization to SPOKeyOrder. It is at the top of the class. It is currently disabled. Committed revision r6360. Committed revision r6361. (marks the flag as transient as well as static and final)
        Hide
        bryanthompson bryanthompson added a comment -

        I am assigning this issue over to Mike. It looks like we should lift the code to attach the ESTIMATED_CARDINALITY and the ORIGINAL_INDEX out of the static join order optimizer. This optimizer would run before the static join order optimizer and would run even when the static join order optimizer does not run.

        The test suite for the static optimizer needs to be reviewed with respect to its use of the ESTIMATED_CARDINALITY annotation (I think that there will not be a problem, but that annotation is used to mock up cardinality without data in the indices).

        However, the main problem is that the locality optimization is not showing improved performance on standard benchmarks even though Mike has been able to demonstrate performance on application queries using an explicit index override query hint.

        While I am not sure about the BSBM queries, it is quite common that queries become fully bound and wind up doing a series of point tests. LUBM Q9 in particular is known to have this characteristic.

        It is possible that we would do better with a bloom filter on the other indices as well, but Mike is already showing a significant performance advantage when choosing POS rather than SPO for some application specific queries -- without a bloom filter on POS.

        It looks like my report of "no improvement" on LUBM was premature. I had not recompiled the code on the workstation so it was not testing the right SVN revision. However, the BSBM results are valid and indicate a negative impact on query performance.

        The re-run LUBM results are an average of 1 second slower (10136ms versus 11059ms with the locality optimization). This is conclusive evidence that the optimization is have a negative effect on LUBM as well.

        Show
        bryanthompson bryanthompson added a comment - I am assigning this issue over to Mike. It looks like we should lift the code to attach the ESTIMATED_CARDINALITY and the ORIGINAL_INDEX out of the static join order optimizer. This optimizer would run before the static join order optimizer and would run even when the static join order optimizer does not run. The test suite for the static optimizer needs to be reviewed with respect to its use of the ESTIMATED_CARDINALITY annotation (I think that there will not be a problem, but that annotation is used to mock up cardinality without data in the indices). However, the main problem is that the locality optimization is not showing improved performance on standard benchmarks even though Mike has been able to demonstrate performance on application queries using an explicit index override query hint. While I am not sure about the BSBM queries, it is quite common that queries become fully bound and wind up doing a series of point tests. LUBM Q9 in particular is known to have this characteristic. It is possible that we would do better with a bloom filter on the other indices as well, but Mike is already showing a significant performance advantage when choosing POS rather than SPO for some application specific queries -- without a bloom filter on POS. It looks like my report of "no improvement" on LUBM was premature. I had not recompiled the code on the workstation so it was not testing the right SVN revision. However, the BSBM results are valid and indicate a negative impact on query performance. The re-run LUBM results are an average of 1 second slower (10136ms versus 11059ms with the locality optimization). This is conclusive evidence that the optimization is have a negative effect on LUBM as well.
        Hide
        bryanthompson bryanthompson added a comment -

        I am assigning this issue over to Mike. It looks like we should lift the code to attach the ESTIMATED_CARDINALITY and the ORIGINAL_INDEX out of the static join order optimizer. This optimizer would run before the static join order optimizer and would run even when the static join order optimizer does not run.

        The test suite for the static optimizer needs to be reviewed with respect to its use of the ESTIMATED_CARDINALITY annotation (I think that there will not be a problem, but that annotation is used to mock up cardinality without data in the indices).

        However, the main problem is that the locality optimization is not showing improved performance on standard benchmarks even though Mike has been able to demonstrate performance on application queries using an explicit index override query hint.

        While I am not sure about the BSBM queries, it is quite common that queries become fully bound and wind up doing a series of point tests. LUBM Q9 in particular is known to have this characteristic.

        It is possible that we would do better with a bloom filter on the other indices as well, but Mike is already showing a significant performance advantage when choosing POS rather than SPO for some application specific queries -- without a bloom filter on POS.

        It looks like my report of "no improvement" on LUBM was premature. I had not recompiled the code on the workstation so it was not testing the right SVN revision. However, I re-ran the results and the locality optimization resulted in a 10% penalty. Also, the BSBM results are valid and indicate a negative impact on query performance. This optimization is clearly not working at this point and it is disabled in SPOKeyOrder.

        Show
        bryanthompson bryanthompson added a comment - I am assigning this issue over to Mike. It looks like we should lift the code to attach the ESTIMATED_CARDINALITY and the ORIGINAL_INDEX out of the static join order optimizer. This optimizer would run before the static join order optimizer and would run even when the static join order optimizer does not run. The test suite for the static optimizer needs to be reviewed with respect to its use of the ESTIMATED_CARDINALITY annotation (I think that there will not be a problem, but that annotation is used to mock up cardinality without data in the indices). However, the main problem is that the locality optimization is not showing improved performance on standard benchmarks even though Mike has been able to demonstrate performance on application queries using an explicit index override query hint. While I am not sure about the BSBM queries, it is quite common that queries become fully bound and wind up doing a series of point tests. LUBM Q9 in particular is known to have this characteristic. It is possible that we would do better with a bloom filter on the other indices as well, but Mike is already showing a significant performance advantage when choosing POS rather than SPO for some application specific queries -- without a bloom filter on POS. It looks like my report of "no improvement" on LUBM was premature. I had not recompiled the code on the workstation so it was not testing the right SVN revision. However, I re-ran the results and the locality optimization resulted in a 10% penalty. Also, the BSBM results are valid and indicate a negative impact on query performance. This optimization is clearly not working at this point and it is disabled in SPOKeyOrder.

          People

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

            Dates

            • Created:
              Updated:
              Resolved: