公开(公告)号：US11593323B2

公开(公告)日：2023-02-28

申请号：US17370418

申请日：2021-07-08

Applicant: Oracle International Corporation

Inventor： Marco Arnaboldi ,  Jean-Pierre Lozi ,  Laurent Phillipe Daynes ,  Vlad Ioan Haprian ,  Shasank Kisan Chavan ,  Hugo Kapp ,  Sungpack Hong

IPC: G06F16/21 ,  G06F16/27 ,  G06F16/28 ,  G06F16/901 ,  G06F16/22

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.

公开(公告)号：US11250059B2

公开(公告)日：2022-02-15

申请号：US16738972

申请日：2020-01-09

Applicant: ORACLE INTERNATIONAL CORPORATION

Inventor： Arnaud Delamare ,  Vasileios Trigonakis ,  Jean-Pierre Lozi ,  Vlad Ioan Haprian ,  Petr Koupy ,  Hassan Chafi ,  Sungpack Hong

IPC: G06F16/00 ,  G06F16/901 ,  G06F16/2453 ,  G06F16/903 ,  G06F16/9032

Abstract: Techniques are described herein for early pruning of potential graph query results. Specifically, based on determining that property values of a path through graph data cannot affect results of a query, the path is pruned from a set of potential query solutions prior to fully exploring the path. Early solution pruning is performed on prunable queries that project prunable functions including MIN, MAX, SUM, and DISTINCT, the results of which are not tied to a number of paths explored for query execution. A database system implements early solution pruning for a prunable query based on intermediate results maintained for the query during query execution. Specifically, when a system determines that property values of a given potential solution path cannot affect the query results reflected in intermediate results maintained for the query, the path is discarded from the set of possible query solutions without further exploration of the path.

公开(公告)号：US10853137B2

公开(公告)日：2020-12-01

申请号：US16351377

申请日：2019-03-12

Applicant: Oracle International Corporation

Inventor： Vlad Ioan Haprian ,  Iraklis Psaroudakis ,  Alexander Weld ,  Oskar Van Rest ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F9/46 ,  G06F9/50 ,  G06F9/38 ,  G06F11/30 ,  G06K9/62 ,  G06F16/901

Abstract: Techniques are described herein for allocating and rebalancing computing resources for executing graph workloads in manner that increases system throughput. According to one embodiment, a method includes receiving a request to execute a graph processing workload on a dataset, identifying a plurality of graph operators that constitute the graph processing workload, and determining whether execution of each graph operator is processor intensive or memory intensive. The method also includes assigning a task weight for each graph operator of the plurality of graph operators, and performing, based on the assigned task weights, a first allocation of computing resources to execute the plurality of graph operators. Further, the method includes causing, according to the first allocation, execution of the plurality of graph operators by the computing resources, and monitoring computing resource usage of graph operators executed by the computing resources according to the first allocation. In addition, the method includes performing, responsive to monitoring computing resource usage, a second allocation of computing resources to execute the plurality of graph operators, and causing, according to the second allocation instead of according to the first allocation, execution of the plurality of graph operators by the computing resources.

公开(公告)号：US20200293372A1

公开(公告)日：2020-09-17

申请号：US16351377

申请日：2019-03-12

Applicant: Oracle International Corporation

Inventor： Vlad Ioan Haprian ,  Iraklis Psaroudakis ,  Alexander Weld ,  Oskar Van Rest ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F9/50 ,  G06F9/38 ,  G06F16/901 ,  G06K9/62 ,  G06F11/30

Abstract: Techniques are described herein for allocating and rebalancing computing resources for executing graph workloads in manner that increases system throughput. According to one embodiment, a method includes receiving a request to execute a graph processing workload on a dataset, identifying a plurality of graph operators that constitute the graph processing workload, and determining whether execution of each graph operator is processor intensive or memory intensive. The method also includes assigning a task weight for each graph operator of the plurality of graph operators, and performing, based on the assigned task weights, a first allocation of computing resources to execute the plurality of graph operators. Further, the method includes causing, according to the first allocation, execution of the plurality of graph operators by the computing resources, and monitoring computing resource usage of graph operators executed by the computing resources according to the first allocation. In addition, the method includes performing, responsive to monitoring computing resource usage, a second allocation of computing resources to execute the plurality of graph operators, and causing, according to the second allocation instead of according to the first allocation, execution of the plurality of graph operators by the computing resources.

公开(公告)号：US20250139164A1

公开(公告)日：2025-05-01

申请号：US18385602

申请日：2023-10-31

Applicant: Oracle International Corporation

Inventor： Laurent Daynes ,  Martin Brugnara ,  Jean-Pierre Lozi ,  Calin Iorgulescu ,  Marco Arnaboldi ,  Hugo Kapp ,  Vlad Ioan Haprian ,  Zhen Hua Liu ,  Sungpack Hong

IPC: G06F16/901

Abstract: Techniques are described for applying topological graph changes and traversing the modified graph. In an implementation, a set of compile processes schedules the graph changes caused by a DML (Data Manipulation Language) statement. Based on the requested graph operation in a received query for graph, a set of graph operation processes generate extensions to the graph that capture the changes to the graph by the DML. The received graph operation(s) are then performed by traversing both the existing graph and the generated extensions.

公开(公告)号：US20230267120A1

公开(公告)日：2023-08-24

申请号：US17585146

申请日：2022-01-26

Applicant: Oracle International Corporation

Inventor： Hugo Kapp ,  Laurent Daynes ,  Vlad Ioan Haprian ,  Jean-Pierre Lozi ,  Zhen Hua Liu ,  Marco Arnaboldi ,  Sabina Petride ,  Andrew Witkowski ,  Hassan Chafi ,  Sungpack Hong

IPC: G06F16/2453

CPC classification number: G06F16/24539

Abstract: Techniques described herein allow a user of an RDBMS to specify 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. Thus, the input graph of a GAF may be a “heterogeneous” graph.

公开(公告)号：US20230095703A1

公开(公告)日：2023-03-30

申请号：US17479006

申请日：2021-09-20

Applicant: Oracle International Corporation

Inventor： Bence Czipo ,  Vlad Ioan Haprian ,  Oskar Van Rest ,  Damien Hilloulin ,  Vasileios Trigonakis ,  Yahya Ez-zainabi ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F16/23 ,  G06F11/07

Abstract: 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.

公开(公告)号：US11537579B2

公开(公告)日：2022-12-27

申请号：US16816686

申请日：2020-03-12

Applicant: Oracle International Corporation

Inventor： Jean-Pierre Lozi ,  Marco Arnaboldi ,  Laurent Phillipe Daynes ,  Vlad Ioan Haprian ,  Hugo Kapp

IPC: G06F16/22 ,  G06F16/21

Abstract: 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.

公开(公告)号：US20210334249A1

公开(公告)日：2021-10-28

申请号：US17370418

申请日：2021-07-08

Applicant: Oracle International Corporation

Inventor： Marco Arnaboldi ,  Jean-Pierre Lozi ,  Laurent Phillipe Daynes ,  Vlad Ioan Haprian ,  Shasank Kisan Chavan ,  Hugo Kapp ,  Sungpack Hong

IPC: G06F16/21 ,  G06F16/27 ,  G06F16/28 ,  G06F16/901

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.

公开(公告)号：US20210240705A1

公开(公告)日：2021-08-05

申请号：US16778668

申请日：2020-01-31

Applicant: ORACLE INTERNATIONAL CORPORATION

Inventor： Vasileios Trigonakis ,  Tomas Faltin ,  Jean-Pierre Lozi ,  Vlad Ioan Haprian ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F16/2452 ,  G06F16/2458

Abstract: 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.