Oracle International Corporation

Martin Sevenich

Hassan Chafi

Sungpack Hong

Alexander Weld

Korbinian Schmid

Martijn Dwars

Pit Fender

Benjamin Schlegel

Matthias Brantner

Zhe Wu

Jayanta Banerjee

Guido Wachsmuth

Michael Haubenschild

Daniel Lehmann

Iraklis Psaroudakis

Felix Kaser

Manuel Then

Mhd Yamen Haddad

A system for loading graph data from an external store in response to a graph query is disclosed. In some embodiment, given a graph database where all vertices are stored in memory and some but not all edges are stored in the external store, the system performs one of two methods. In the first method, the system iteratively expands a set of vertices that is initially specified in the graph query and collects all edges connected to the set of vertices, including edges stored in the external store, that satisfy a vertex constraint also specified in the query. In the second method, the system finds a set of vertices that satisfy the vertex constraint and collects all edges connected to the set of vertices, including edges stored in an external store.

Managing hybrid graph data storage and retrieval for efficient graph query execution

Techniques are described for a vectorized queue, which implements a vectorized 'contains' function that determines whether a value is in the queue. A three-phase vectorized shortest-path graph search splits each expanding and probing iteration into three phases that utilize vectorized instructions: (1) The neighbors of nodes that are in a next queue are fetched and written into a current queue. (2) It is determined whether the destination node is among the fetched neighbor nodes in the current queue. (3) The fetched neighbor nodes that have not yet been visited are put into the next queue. According to an embodiment, a vectorized copy operation performs vector-based data copying using vectorized load and store instructions. Specifically, vectors of data are copied from a source to a destination. Any invalid data copied to the destination is overwritten, either with a vector of additional valid data or with a vector of nonce data.

Vectorized queues for shortest-path graph searches

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 a vectorized hash table that uses very efficient grow and insert techniques. A single-probe hash table is grown via vectorized instructions that split each bucket, of the hash table, into a respective upper and lower bucket of the expanded hash table. Further, vacant slots are indicated using a vacant-slot-indicator value, e.g., '0', and all vacant slots follow to the right of all occupied slots in a bucket. A vectorized compare instruction determines whether a value is already in the bucket. If not, the vectorized compare instruction is also used to determine whether the bucket has a vacant slot based on whether the bucket contains the vacant-slot-indicator value. To insert the value into the bucket, vectorized instructions are used to shift the values in the bucket to the right by one slot and to insert the new value into the left-most slot.

Vectorized hash tables

Techniques herein are for navigation data structures for graph traversal. In an embodiment, navigation data structures that a computer stores include: a source vertex array of vertices; a neighbor array of dense identifiers of target vertices terminating edges; a bidirectional map associating, for each vertex, a sparse identifier of the vertex with a dense identifier of the vertex; and a vertex array containing, when a dense identifier of a source vertex is used as an offset, a pair of offsets defining an offset range, for use with the neighbor array. The source vertex array, using the dense identifier of a particular vertex as an offset, contains an offset, into a neighbor array, of a target vertex terminating an edge originating at the particular vertex. The neighbor array contiguously stores dense identifiers of target vertices terminating edges originating from a same source vertex.

In-memory graph analytics system that allows memory and performance trade-off between graph mutation and graph traversal

Techniques herein minimize memory needed to store distances between vertices of a graph for use during a multi-source breadth-first search (MS-BFS). In an embodiment, during each iteration of a first sequence of iterations of a MS-BFS, a computer updates a first matrix that contains elements that use a first primitive integer type having a first width to record a distance from a source vertex of a graph to another vertex. The computer detects that a count of iterations of the first sequence of iterations exceeds a threshold. Responsively, the computer creates a second matrix that contains elements that use a second primitive integer type having a second width that is larger than the first width to record a distance from a source vertex of the graph to another vertex. During each iteration of a second sequence of iterations of the MS-BFS, the computer updates the second matrix.

Multi-source breadth-first search (Ms-Bfs) technique and graph processing system that applies it

Embodiments perform real-time vertex connectivity checks in graph data representations via a multi-phase search process. This process includes an efficient first search phase using landmark connectivity data that is generated during a preprocessing phase. Landmark connectivity data maps the connectivity of a set of identified landmarks in a graph to other vertices in the graph. Upon determining that the subject vertices are not closely related via landmarks, embodiments implement a second search phase that performs a brute-force search for connectivity, between the subject vertices, among the graph's non-landmark vertices. This brute-force search prevents exploration of cyclical paths by recording the vertices on a currently-explored path in a stack data structure. The second search phase is automatically aborted upon detecting that the non-landmark vertices in the graph are over a threshold density. In this case, embodiments perform a third search phase involving either a modified breadth-first search or modified bidirectional search.

Fast detection of vertex-connectivity with distance constraint

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.

Methods of graph-type specialization and optimization in graph algorithm DSL compilation

Multi-source breadth-first search (MS-BFS) technique and graph processing system that applies it

An implementation of an abstract data type is automatically selected by a compiler of high-level language source code. The compiler chooses an implementation for each instance of an abstract data type in a program based on operations performed in the instance within the program. The compiler rewrites and compiles the high-level language source code in response to selecting the implementation.

Automatic selection of an abstract data type

Techniques for identifying common neighbors of two nodes in a graph are provided. One technique involves performing a binary split search and/or a linear search. Another technique involves creating a segmenting index for a first neighbor list. A second neighbor list is scanned and, for each node indicated in the second neighbor list, the segmenting index is used to determine whether the node is also indicated in the first neighbor list. Techniques are also provided for counting the number of triangles. One technique involves pruning nodes from neighbor lists based on the node values of the nodes whose neighbor lists are being pruned. Another technique involves sorting the nodes in a node array (and, thus, their respective neighbor lists) based on the nodes' respective degrees prior to identifying common neighbors. In this way, when pruning the neighbor lists, the neighbor lists of the highly connected nodes are significantly reduced.

Finding common neighbors between two nodes in a graph

Techniques are described herein for automatic generation of multi-source breadth-first search (MS-BFS) from high-level graph processing language. 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, parallel execution of the MS-BFS is regulated with batches of vertices. In an embodiment, the original software instructions are expressed in Green-Marl graph analysis language. In an embodiment, the transformed software instructions are expressed in a general purpose programming language such as C, C++, Python, or Java.

Growing community of inventors

Palo Alto, CA, United States of America

Martin Sevenich