• Type: New Feature
    • Status: Open
    • Priority: Low
    • Resolution: Unresolved
    • Affects Version/s: BIGDATA_RELEASE_1_2_0
    • Fix Version/s: None
    • Component/s: Query Plan Generator
    • Labels:


      I just saw a fascinating presentation on a multi-way join technique (it turns out that this is very closely related to symmetric hash joins and that U-SIP is very closely related to eddies as well). This was developed in the context of federated query where each AP could be answered by a different end point. However, the work also applies to our common cases (local and clustered). What they are doing is grouping joins which have one variable into "stars" and pushing them down together with any joins which chain through an intermediated variable not projected from the query. We have looked at this before. It is the probable problem for BSBM Q5.

      Then they run an N-way hash join on a set of access paths which have only one unbound variable for each predicate (not necessarily for the same variable). Within that n-way hash join they run each access path unbound and they run the APs in parallel. They are basically joining everything against everything. So, there is a hash index which is build for all solutions for the join variable. Solutions (really triples) out of the APs are indexed (so they are available to be joined against by the other of the N-1 APs). Those solutions are also joined against each hash index based on the variable for a given join.

      The speed up appears to come from two sources. First, the APs are highly selective and fully materialized in parallel. This cuts latency. Also, there is no need to do range counts on these APs with only a single variable since they are not being "ordered". That could really speed up our query planning. On a cluster, it would mean reading on the remote APs from within this N-way join.

      Second, solutions flow out of the N-way join as soon as they are produced. This again is cutting latency. So that is less latency in the query planner and less latency to get the solutions out of the n-way join.

      The big speedups from our perspective (local indices case) is going to NOT taking range counts for 1-bound APs and managing those join groups correctly.

      I think that there is also an opportunity to exploit the U-SIP (ubiquituous sideways information passing() methods of RDF-3X. U-SIP
      runs AP scans in parallel as well. That does not make a lot of sense for our query engine if they are independent join operators, but it is a LOT easier to see how to do that if this is an N-way join. The key think that U-SIP does is pass information about necessary gaps in APs based on observed ascending values for the bindings of a variable on another AP. RDF-3X uses this to skip over regions of the AP scan which are dynamically proven to not contain solutions which can complete the join group. However, it seems to me that the U-SIP mechanism is only useful when the APs are scanning multiple pages of tuples. If you have APs with only one variable, then this is much less likely
      - except perhaps on POS. You could have very high cardinality there. In that case, a parallel scan on another AP might identify that you can skip ahead to a key, potentially skipping many pages. The other advantage of implementing this U-SIP style join is that (if you have this quality of merge joins on AP scans) then the joins themselves are less expensive because you can exploit a known order.

      We could also combine this with the rewrite of required and optional joins seeking to pull attributes off of the SPO index by leaving only S bound and lifting the filter on the AP. For such a case, we would also want to keep it in the same join group in which it would have been processed as a 2-bound AP
      - since that is what it is in effect. The lift of the filter onto the iterator just let's us simplify the join group and do only a single scan of that AP key range. We've tried something like this before without great success, but I think it would be interesting to revisit this in the context of N-way hash joins against 2-bound APs (the first case that I describe above) and N-way merge joins against APs (the U-SIP case). On a cluster, this could also turn M-AP reads into one (where M is the number of required or optional attribute joins). Overall, this reduction in the #of APs that we evaluate might be the source of a big performance gain.

        Issue Links


          There are no comments yet on this issue.


            • Assignee:
              bryanthompson bryanthompson
              bryanthompson bryanthompson
            • Votes:
              0 Vote for this issue
              2 Start watching this issue


              • Created: