公开(公告)号：US11947539B2

公开(公告)日：2024-04-02

申请号：US17750339

申请日：2022-05-21

Applicant: ORACLE INTERNATIONAL CORPORATION

Inventor： Vasileios Trigonakis ,  Calin Iorgulescu ,  Tomas Faltin ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F16/00 ,  G06F9/48 ,  G06F16/2453 ,  G06F16/27 ,  G06F16/901

CPC classification number: G06F16/24542 ,  G06F9/4881 ,  G06F16/27 ,  G06F16/9024

Abstract: Techniques to efficiently assign available workers to executing multiple graph queries concurrently on a distributed graph database are disclosed. The techniques comprise a runtime engine assigning multiple workers to executing portions of multiple graph queries, each worker in each assignment asynchronously executing a portion of a graph query within a parallel-while construct that includes return statements at different locations, and the runtime engine reassigning a worker to executing another portion of the same or a different graph query to optimize the overall performance of all workers.

公开(公告)号：US11720630B2

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

申请号：US17141018

申请日：2021-01-04

Applicant: Oracle International Corporation

Inventor： Arnaud Delamare ,  Vasileios Trigonakis ,  Yahya Ez-Zainabi ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F16/901

CPC classification number: G06F16/9024 ,  G06F16/9027

Abstract: Techniques are provided for finding unused vertex and edge identifiers (IDs) in a distributed graph engine. A run-time data structure may be built during the loading of the graph. The data structure identifies unavailable IDs that are associated with graph entities of the graph. The data structure is traversed to determine one or more ranges of free IDs. Unused IDs are generated from the ranges.

公开(公告)号：US11461130B2

公开(公告)日：2022-10-04

申请号：US16883317

申请日：2020-05-26

Applicant: Oracle International Corporation

Inventor： Petr Koupy ,  Vasileios Trigonakis ,  Iraklis Psaroudakis ,  Jinsoo Lee ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F9/48 ,  G06F9/448 ,  G06F16/901 ,  G06F11/07 ,  G06F9/38

Abstract: In an embodiment, a computer of a cluster of computers receives graph logic that specifies a sequence of invocations, including a current invocation and a next invocation, of parallelism operations that can detect whether the graph logic should prematurely terminate. The computer initiates, on the computers of the cluster, execution of the graph logic to process a distributed graph. Before the current invocation, the graph logic registers reversion logic for a modification of the distributed graph that execution of the graph logic has caused. During the current invocation, it is detected that the graph logic should prematurely terminate. Execution of the graph logic on the cluster is terminated without performing the next invocation in the sequence of invocations. The reversion logic reverses the modification of the distributed graph to restore consistency. The distributed graph is retained in volatile memory of the cluster for reuse such as relaunch of the graph logic.

公开(公告)号：US20220284056A1

公开(公告)日：2022-09-08

申请号：US17194165

申请日：2021-03-05

Applicant: Oracle International Corporation

Inventor： Damien Hilloulin ,  Vasileios Trigonakis ,  Alexander Weld ,  Valentin Venzin ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F16/901 ,  G06F16/22

Abstract: Techniques are provided for updating in-memory property graphs in a fast manner, while minimizing memory consumption. A graph is represented as delta compressed sparse rows (CSR), in which its data structure stores forward edge offsets that map reverse edges to forward edges, enabling fast traversals of graph edges in forward and reverse directions. To support fast graph updates, delta logs are used to store changes to the graph. In an embodiment, a base version of the graph data structure is initially loaded or created, and subsequent versions of the graph are created from the reference to the initial graph and a delta log data structure that records the changes compared to the base version of the graph.

公开(公告)号：US11363093B2

公开(公告)日：2022-06-14

申请号：US15968637

申请日：2018-05-01

Applicant: Oracle International Corporation

Inventor： Jinsu Lee ,  Thomas Manhardt ,  Sungpack Hong ,  Petr Koupy ,  Hassan Chafi ,  Vasileios Trigonakis

IPC: H04L29/08 ,  G06F16/901 ,  H04L67/10

Abstract: Techniques are described herein for evaluating graph processing tasks using a multi-stage pipelining communication mechanism. In a multi-node system comprising a plurality of nodes, each node of said plurality of nodes executes a respective communication agent object. The respective communication agent object comprises: a sender lambda function is configured to perform sending operations and generate source messages based on the sender operations. An intermediate lambda function is configured to read source messages marked for a node, perform intermediate operations based on the source messages and generate intermediate messages based on the intermediate operations. A final receiver lambda function configured to: read intermediate messages marked for said each node, perform final operations based on the intermediate messages and generate a final result based on the final operations.

公开(公告)号：US20210392073A1

公开(公告)日：2021-12-16

申请号：US16899185

申请日：2020-06-11

Applicant: Oracle International Corporation

Inventor： Petar Tonkovic ,  Vasileios Trigonakis ,  Tomas Faltin ,  Sungpack Hong ,  Hassan Chafi

IPC: H04L12/733 ,  H04L12/721 ,  H04L12/803 ,  G06F16/901 ,  G06F9/54

Abstract: A pattern matching engine interprets a query into a data structure resembling a finite state machine. Vertices in the query pattern are treated as states or stages, while edges connecting them are treated as state transitions or hops. To match the full pattern, the first stage is first matched by applying vertex filters, if any. If the vertex is eligible, its edges that satisfy the edge filters, if any, are followed to move to the neighbors that can potentially produce results, thus progressing to the next stage. This process is repeated; if all stages are matched, then the whole pattern has been matched successfully.

公开(公告)号：US20210182315A1

公开(公告)日：2021-06-17

申请号：US16710719

申请日：2019-12-11

Applicant: Oracle International Corporation

Inventor： Vlad Haprian ,  Laurent Daynes ,  Shasank K. Chavan ,  Jean-Pierre Lozi ,  Vasileios Trigonakis ,  Sungpack Hong ,  Marco Arnaboldi ,  Ciprian Baetu

IPC: G06F16/28 ,  G06F16/22 ,  G06F16/901 ,  G06F16/242

Abstract: An in-memory graph query runtime is integrated inside a database management system and is capable of performing simple patter-matching queries against homogeneous graphs. The runtime efficiently combines breadth-first (BFS) and depth-first (DFS) neighbor traversal algorithms to achieve a hybrid runtime that takes the best from both sides. As a result, the hybrid runtime is able to process arbitrarily large queries with a fixed amount of memory, optimizing for memory locality.

公开(公告)号：US12197436B2

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

申请号：US18091242

申请日：2022-12-29

Applicant: Oracle International Corporation

Inventor： Vasileios Trigonakis ,  Anton Ragot ,  Yahya Ez-zainabi ,  Tomas Faltin ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F16/2453 ,  G06F16/901

Abstract: A graph processing engine is provided for executing a graph query comprising a parent query and a subquery nested within the parent query. The subquery uses a reference to one or more correlated variables from the parent query. Executing the graph query comprises initiating execution of the parent query, pausing the execution of the parent query responsive to the parent query matching the one or more correlated variables in an intermediate result set, generating a subquery identifier for each match of the one or more correlated variables, modifying the subquery to include a subquery aggregate function and a clause to group results by subquery identifier, executing the modified subquery using the intermediate result set and collecting subquery results into a subquery results table responsive to pausing execution of the parent query, and resuming execution of the parent query using the subquery results table.

公开(公告)号：US20240273093A1

公开(公告)日：2024-08-15

申请号：US18648272

申请日：2024-04-26

Applicant: Oracle International Corporation

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

IPC: G06F16/2452 ,  G06F16/2455 ,  G06F16/248

CPC classification number: G06F16/24526 ,  G06F16/24556 ,  G06F16/248

Abstract: A node of a multi-node computing system determines, in a particular instance of evaluating the graph query, that a vertex that is to be evaluated next is stored on a second node separate from the first node and generates a first message based on one or more first results of the particular instance of evaluating the graph query. The node determines, in a subsequent instance of evaluating the graph query, that a vertex to be evaluated next is stored on the second node. The node generates a merged message based on the first message and one or more subsequent results of the second instance of evaluating the graph query. The node sends the merged message to the second node.

公开(公告)号：US11907255B2

公开(公告)日：2024-02-20

申请号：US17686938

申请日：2022-03-04

Applicant: Oracle International Corporation

Inventor： Jinsu Lee ,  Petr Koupy ,  Vasileios Trigonakis ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F17/00 ,  G06F16/27 ,  G06F16/22 ,  G06F16/28

CPC classification number: G06F16/27 ,  G06F16/2282 ,  G06F16/284

Abstract: In an embodiment, multiple computers cooperate to retrieve content from tables in a relational database. Each table contains respective rows. Each row contains a vertex of a graph. Many high-degree vertices are identified. Each high-degree vertex is connected to respective edges in the graph. A count of the edges of each high-degree vertex exceeds a degree threshold. A central computer detects that all vertices in a high-degree subset of tables are high-degree vertices. Based on detecting the high-degree subset of tables, multiple vertices of the graph that are not in the high-degree subset of tables are replicated. Within local storage capacity limits of the computers, this degree-based replication may be supplemented with other vertex replication strategies that are schema based, content based, or workload based. This intelligent selective replication maximizes system throughput by minimizing graph data access latency based on data locality.