×

Fast algorithms for computing semijoin reduction sequences

  • US 8,271,478 B2
  • Filed: 07/27/2006
  • Issued: 09/18/2012
  • Est. Priority Date: 07/27/2006
  • Status: Active Grant
First Claim
Patent Images

1. A method for executing an outer join query on data arranged in a plurality of databases in which all joins are evaluated by semijoins, the method comprising:

  • generating, by one or more programmable processors executing one or more computer programs, a query graph of nodes maintaining the data arranged in the plurality of databases and target nodes for an outer join query, comprising;

    computing, by the one or more programmable processors executing one or more computer programs, for each node the set of nodes influencing it;

    computing, by the one or more programmable processors executing one or more computer programs, for each target node the set of its needed reducers;

    predetermining, by the one or more programmable processors executing one or more computer programs, the effects of admissible move sequences;

    forming, by the one or more programmable processors executing one or more computer programs, a directed graph for the admissible move sequences; and

    performing by the one or more programmable processors executing one or more computer programs, an optimization process using a search algorithm on the directed graph to determine a least-cost execution plan for the query, wherein the optimization process further comprises determining a start state, from a plurality of states in the formed directed graph, from which the determined execution plan is to start by performing one or more start heuristics procedures, the one or more start heuristics procedures comprising one or more first and second order heuristics, the least-cost execution plan for the query reducing total communication costs with regard to the query;

    wherein a snake heuristic (i) determines costs for a next move continuing in a same direction along the query graph as compared to costs for the next move turning and moving behind a last turning point; and

    (ii) selects the next move with lesser costs.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×