Oracle International Corporation

Vlad Ioan Haprian

Sungpack Hong

Hassan Chafi

Laurent Daynes

Jean-Pierre Lozi

Marco Arnaboldi

Hugo Kapp

Vasileios Trigonakis

Zhen Hua Liu

Andrew Witkowski

Shasank Kisan Chavan

Oskar Van Rest

Lei Sheng

Arnaud Delamare

Ioannis Alagiannis

Ciprian Baetu

Sabina Petride

Alexander Weld

Korbinian Schmid

Tomas Faltin

Damien Hilloulin

Jinsu Lee

Huagang Li

Iraklis Psaroudakis

Petr Koupy

Angela Amor

Yahya Ez-Zainabi

Danica Porobic

Jonas Schweizer

Benita Kathleen Britto

Chun-Hung Tseng

Lukas Kapp-Schwoerer

Luigi Fusco

Ayoub Berdai

Martin Brugnara

Rohan Aggarwal

Agnivo Saha

Bence Czipo

Steven Serra

Florian Gratzer

Andrea Segalini

Techniques for generating and leveraging a multi-snapshot HNSW index are provided. In one technique, multiple snapshots of an HNSW index that was generated based on a vector table comprising an initial set of vectors are stored. Each of snapshots has a different build time and is associated with a shared journal that stores a plurality of changes to a plurality of vectors in the vector table. A latest snapshot of the plurality of snapshots is identified. The shared journal is identified. It is determined, based on one or more criteria, whether to generate a new snapshot based on the latest snapshot and the shared journal. In another technique, in response to receiving a vector query that is associated with a timestamp, a particular snapshot is selected from the snapshots based on the timestamp. The vector query is executed against the particular snapshot and the shared journal.

Multi-snapshot HNSW index

The present disclosure relates to various approaches for fast and scalable TOP K SHORTEST and CHEAPEST graph queries supporting horizontal aggregations on the group variables of a path in a distributed graph query engine. A distributed graph query processing engine may execute a graph query in a plurality of computing devices. A plurality of subjobs may be generated based at least in part on the graph query. Execution of an asynchronous pattern matching subjob of the plurality of subjobs may be initiated, and, in response to the asynchronous pattern matching subjob identifying one or more source vertices of a plurality of vertices, the execution of the asynchronous pattern matching subjob may be paused. An output context set comprising the one or more source vertices may be generated. Execution of a synchronous path matching subjob of the plurality of subjobs may be initiated, and a reachability map may be generated based at least in part on one or more matched paths between the one or more source vertices and one or more destination vertices of the plurality of vertices. The execution of the asynchronous pattern matching subjob may be resumed based at least in part on the output context set and the reachability map.

Shortest and cheapest paths in distributed asynchronous graph traversals

A sampling procedure is performed for paths on a multi-hop distributed graph that includes vertices partitioned on a plurality of machines; a sampled path includes first and second vertices hosted on first and second machines respectively. The sampling procedure includes communicating, by the first machine to the second machine, first path information comprising an identifier for the second vertex and an identifier for a target vertex of the sampled path; the target vertex is hosted on a target host machine. The procedure further includes communicating edge information by the first machine to the target host machine, and communicating feature information by the second machine to the target host machine. Communication of the edge information and communication of the feature information are deferred relative to communication of the first path information.

Distributed multi-hop neighborhood extraction for graph machine-learning via push-lazy-push-traversal

A computer-implemented method includes receiving a graph pattern matching query, determining that the query is an unbounded recursive path query (RPQ), and initializing an unbounded root vertex match operator (UBRM) using a starting vertex as input to the UBRM; the UBRM is configured to compute multiple hops between vertices on the graph. The method also includes performing a first reachability search using the UBRM; the UBRM traverses the graph to identify all vertices reachable from the starting vertex. The method further includes generating first level vertices of a path pattern that computes the RPQ; and adding the first level vertices to a first level context for processing by a successor match operator; the successor match operator comprises an unbounded intermediate neighbor match operator (UBNM), the UBNM is configured to compute multiple hops between vertices on the graph and to identify neighbors for each of the first level vertices.

In-memory processing of unbounded recursive graph queries in relational databases

A breadth first search (BFS) algorithm is provided that uses out-of-core external storage in a memory constrained system. Memory resources are used as long as they are available and external storage is used when necessary due to memory pressure. The BFS algorithm uses a disk-spilling hash-table (DSH) as the visited set and disk-spilling queues (DSQs) as the BFS frontier queue. To get the most out of the DSH, subsequent inserts and lookups must happen in the same DSH partition. To ensure that consecutive lookups happen in the same DSH partition, the BFS frontier queue is partitioned in a manner similar to the DSH partitions.

Out-of-core BFS for shortest path graph queries

A method, apparatus, and product to provide a parser for property graph queries with precise error reporting and auto-completion based on information from property graph schemas. The approach generally comprises analysis of graph queries prior to their execution to identify issues prior to execution. In some embodiments, the approach includes any of: use of a property graph schema to determine whether names in a received property graph query exist within a corresponding property graph; determining whether the property graph query includes a comparison of mismatched data types; providing an autocomplete suggestion feature for assistance in resolving errors or corresponding to a cursor position within a query string; or evaluation of a property graph query to determine whether it would return an empty result. In some embodiments, property graph query analysis is performed using a context aware approach.

Method, product, and system to provide a parser for property graph queries with precise error reporting and auto-completion based on information from property graph schemas

Techniques support graph pattern matching queries inside a relational database management system (RDBMS) that supports SQL execution. The techniques compile a graph pattern matching query that includes a bounded recursive pattern query into a SQL query that can then be executed by the relational engine. As a result, techniques enable execution of graph pattern matching queries that include bounded recursive patterns on top of the relational engine by avoiding any change in the existing SQL engine.

Efficient compilation of bounded recursive graph queries on top of SQL based relational engine

An RDBMS specifies a graph algorithm function (GAF) that takes a graph object as input and returns a logical graph object as output. GAFs are used within graph queries to compute temporary and output properties ('GAF-computed properties'), which are live for the duration of the query cursor execution. GAF-computed output properties are accessible in the enclosing graph pattern matching query as though they were part of the input graph object of the GAF. Temporary cursor-duration tables are generated for the query cursor during compilation of a graph query that includes a GAF, and are used to store the GAF-computed properties. Each temporary table corresponds to one of the primary tables of the input graph, and includes, as a foreign key, primary key information from the corresponding primary table.

Using temporary tables to store graph algorithm results for a relational database management system

Techniques support graph pattern matching queries inside a relational database management system (RDBMS) that supports SQL execution. The techniques compile a graph pattern matching query into a SQL query that can then be executed by the relational engine. As a result, techniques enable execution of graph pattern matching queries on top of the relational engine by avoiding any change in the existing SQL engine.

Efficient compilation of graph queries including complex expressions on top of sql based relational engine

Efficiently implemented herein is a deterministic semantic for property updates by graph queries. Mechanisms of determinism herein ensure data consistency for graph mutation. These mechanisms facilitate optimistic execution of graph access despite a potential data access conflict. This approach may include various combinations of special activities such as detecting potential conflicts during query compile time, applying query transformations to eliminate those conflicts during code generation where possible, and executing updates in an optimistic way that safely fails if determinism cannot be guaranteed. In an embodiment, a computer receives a request to modify a graph. The request to modify the graph is optimistically executed after preparation and according to safety precautions as presented herein. Based on optimistically executing the request, a data access conflict actually occurs and is automatically detected. Based on the data access conflict, optimistically executing the request is prematurely and automatically halted without finishing executing the request.

Deterministic semantic for graph property update queries and its efficient implementation

Techniques described herein allow a user of an RDBMS to specify a graph algorithm function (GAF) declaration, which defines a graph algorithm that takes a graph object as input and returns a logical graph object as output. A database dictionary stores the GAF declaration, which allows addition of GAFs without changing the RDBMS kernel. GAFs are used within graph queries to compute output properties of property graph objects. Output properties are accessible in the enclosing graph pattern matching query, and are live for the duration of the query cursor execution. According to various embodiments, the declaration of a GAF includes a DESCRIBE function, used for semantic analysis of the GAF, and an EXECUTE function, which defines the operations performed by the GAF. Furthermore, composition of GAFs in a graph query is done by supplying, as the input graph argument of an outer GAF, the result of an inner GAF.

Inline graph algorithm execution with a relational SQL engine

Techniques are described for enabling in-memory execution of any-sized graph data query by utilizing both depth first search (DFS) principles and breadth first search (BFS) principles to control the amount of memory used during query execution. Specifically, threads implementing a graph DBMS switch between a BFS mode of data traversal and a DFS mode of data traversal. For example, when a thread detects that there are less than a configurable threshold number of intermediate results in memory, the thread enters BFS-based traversal techniques to increase the number of intermediate results in memory. When the thread detects that there are at least the configurable threshold number of intermediate results in memory, the thread enters DFS mode to produce final results, which generally works to move the intermediate results that are currently available in memory to final query results, thereby reducing the number of intermediate results in memory.

Dynamic asynchronous traversals for distributed graph queries

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.

Parallel and efficient technique for building and maintaining a main memory CSR based graph index in a RDBMS

Efficient compilation of graph queries on top of SQL based relational engine

In an embodiment, a computer obtains a mapping of a relational schema of a database to a graph data model. The relational schema identifies vertex table(s) that correspond to vertex type(s) in the graph data model and edge table(s) that correspond to edge type(s) in the graph data model. Each edge type is associated with a source vertex type and a target vertex type. Based on that mapping, a forward compressed sparse row (CSR) representation is populated for forward traversal of edges of a same edge type. Each edge originates at a source vertex and terminates at a target vertex. Based on the forward CSR representation, a reverse CSR representation of the edge type is populated for reverse traversal of the edges of the edge type. Acceleration occurs in two ways. Values calculated for the forward CSR are reused for the reverse CSR. Elastic and inelastic scaling may occur.

Fast in-memory technique to build a reverse CSR graph index in an RDBMS

Growing community of inventors

Zurich, Switzerland

Vlad Ioan Haprian