US 2021/0334249 A1 · PARALLEL AND EFFICIENT TECHNIQUE FOR BUILDING AND MAINTAINING A MAIN MEMORY CSR BASED GRAPH INDEX IN A RDBMS

Abstract

Herein are techniques that concurrently populate entries in a compressed sparse row (CSR) encoding, of a type of edge of a heterogenous graph. In an embodiment, a computer obtains a mapping of a relational schema to a graph data model. The relational schema defines vertex tables that correspond to vertex types in the graph data model, and edge tables that correspond to edge types in the graph data model. Each edge type is associated with a source vertex type and a target vertex type. For each vertex type, a sequence of persistent identifiers of vertices is obtained. Based on the mapping and for a CSR representation of each edge type, a source array is populated that, for a same vertex ordering as the sequence of persistent identifiers for the source vertex type, is based on counts of edges of the edge type that originate from vertices of the source vertex type. For the CSR, the computer populates, in parallel and based on said mapping, a destination array that contains canonical offsets as sequence positions within the sequence of persistent identifiers of the vertices.

Claims20

Dependent claims

A method comprising:

obtaining, for each vertex type in a plurality of vertex types, a sequence of persistent identifiers of vertices for the vertex type, wherein each edge type in a plurality of edge types is associated with a respective source vertex type of the plurality of vertex types and a respective target vertex type of the plurality of vertex types;
populating, for each edge type in a plurality of edge types, a source array of a respective compressed sparse row (CSR) representation of said each edge type that, for a same vertex ordering as the sequence of persistent identifiers for the source vertex type of the edge type, is based on counts of edges of the edge type that originate from vertices of the source vertex type;
concurrently populating, based on an atomic fetch-and-add instruction, multiple offsets in a destination array of the CSR representation for a particular edge type of the plurality of edge types, wherein the destination array contains offsets that correspond to respective sequence positions within the sequence of persistent identifiers of vertices of the target vertex type of the edge type.

One or more non-transitory computer-readable storage media storing instructions that, when executed by one or more processors, cause:

obtaining, for each vertex type in a plurality of vertex types, a sequence of persistent identifiers of vertices for the vertex type, wherein each edge type in a plurality of edge types is associated with a respective source vertex type of the plurality of vertex types and a respective target vertex type of the plurality of vertex types;
populating, for each edge type in a plurality of edge types, a source array of a respective compressed sparse row (CSR) representation of said each edge type that, for a same vertex ordering as the sequence of persistent identifiers for the source vertex type of the edge type, is based on counts of edges of the edge type that originate from vertices of the source vertex type;
concurrently populating, based on an atomic fetch-and-add instruction, multiple offsets in a destination array of the CSR representation for a particular edge type of the plurality of edge types, wherein the destination array contains offsets that correspond to respective sequence positions within the sequence of persistent identifiers of vertices of the target vertex type of the edge type.

Dependencies are inferred from the claim text.

Parallel and efficient technique for building and maintaining a main memory csr based graph index in a rdbms

Life of this patent

Parallel and efficient technique for building and maintaining a main memory csr based graph index in a rdbms

Life of this patent

Abstract

Claims20