Patent · US Active

Fast algorithms for computing semijoin reduction sequences

US8271478B2 · kind B2 · utility

4Cited by

16References

17Claims

0Family size

Assignee

SAP AG · DE

Inventors

Gerhard Hill · St. Leon-Rot, DE
Thomas Peh · Bukit Mertajam, MY

Key dates

Filing date	Jul 27, 2006
Grant date	Sep 18, 2012
Priority date	—
Expiry date	Jan 25, 2029

Classification

Technology area (CPC G)Physics
CPC primaryG06F16/24534
WIPO fieldComputer technology
WIPO sectorElectrical engineering

Abstract

Systems and methods for using optimization techniques to construct a nearly optimal execution plan for an outer join query are disclosed. A query graph of the outer join query is constructed, by computing for each node the set of nodes influencing it, for each target node the set of its needed reducers, and predetermining the effects of all admissible moves in all possible sequences. The directed graph of all admissible move sequences is formed. An optimization process includes dynamically generating good estimations for the target distance of a search state. Some heuristics are disclosed for providing start solutions for the optimization process.

Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.