Oracle International Corporation

Martijn Dwars

Hassan Chafi

Sungpack Hong

Martin Sevenich

Guido Wachsmuth

Alexander Weld

To execute function-step-based graph queries on a graph engine that has its own graph query language, rather than re-implementing an existing infrastructure to support function-step-based graph protocols, function-step-based graph queries are transformed to the graph query language that is understood by the graph engine. The existing infrastructure computes the results of the transformed queries. Result sets are then transformed to function-based-based result sets, which are returned to customers. In this manner, the graph engine supports function-step-based graph query workloads without implementation of the function-step-based graph protocol.

Transforming a function-step-based graph query to another graph query language

Techniques are described for compiling source code to generate graph-optimized intermediate representation instructions of the source code that implement techniques for optimizing algorithms for graph analysis. A compiler, executing on a computing device, receives source code instructions for a program to be compiled. The compiler identifies a target expression, within the source code instructions, that invokes a particular method call on a particular object type. The target expression contains a target block of code to be translated into an intermediate representation using graph-optimized compilation techniques. The compiler generates a block of graph-specific intermediate representation instructions to replace the target expression. The compiler compiles the source code instructions to generate intermediate representation instructions, where the intermediate representation instructions include the block of graph-specific intermediate representation instructions in place of the target expression.

Method for applying graph-specific compiler optimizations to graph analysis programs

Techniques are described herein for automatic generation of multi-source breadth-first search (MS-BFS) from high-level graph processing language that can be executed in a distributed computing environment. In an embodiment, a method involves a computer analyzing original software instructions. The original software instructions are configured to perform multiple breadth-first searches to determine a particular result. Each breadth-first search originates at each of a subset of vertices of a graph. Each breadth-first search is encoded for independent execution. Based on the analyzing, the computer generates transformed software instructions configured to perform a MS-BFS to determine the particular result. Each of the subset of vertices is a source of the MS-BFS. In an embodiment, the second plurality of software instructions comprises a node iteration loop and a neighbor iteration loop, and the plurality of vertices of the distributed graph comprise active vertices and neighbor vertices. The node iteration loop is configured to iterate once per each active vertex of the plurality of vertices of the distributed graph, and the node iteration loop is configured to determine the particular result. The neighbor iteration loop is configured to iterate once per each active vertex of the plurality of vertices of the distributed graph, and each iteration of the neighbor iteration loop is configured to activate one or more neighbor vertices of the plurality of vertices for the following iteration of the neighbor iteration loop.

Automatic generation of multi-source breadth-first search from high-level graph language for distributed graph processing systems

Techniques herein generate, such as during compilation, polymorphic dispatch logic (PDL) to switch between specialized implementations of a polymorphic graph algorithm. In an embodiment, a computer detects, within source logic of a graph algorithm, that the algorithm processes an instance of a generic graph type. The computer generates several alternative implementations of the algorithm. Each implementation is specialized to process the graph instance as an instance of a respective graph subtype. The computer generates PDL that performs dynamic dispatch as follows. At runtime, the PDL receives a graph instance of the generic graph type. The PDL detects which particular graph subtype is the graph instance. The PDL then invokes whichever alternative implementation that is specialized to process the graph instance as an instance of the detected particular graph subtype. In embodiments, the source logic is expressed in a domain specific language (DSL), e.g. for analysis, traversal, or querying of graphs.

Growing community of inventors

San Francisco, CA, United States of America

Martijn Dwars