公开(公告)号：US11928097B2

公开(公告)日：2024-03-12

申请号：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

CPC classification number: G06F16/2315 ,  G06F11/0772 ,  G06F16/2365

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.

公开(公告)号：US11256750B2

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

申请号：US16540605

申请日：2019-08-14

Applicant: ORACLE INTERNATIONAL CORPORATION

Inventor： Oskar Van Rest ,  Jinha Kim ,  Xuming Meng ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F16/00 ,  G06F16/901

Abstract: Techniques herein accelerate graph querying by caching neighbor vertices (NVs) of super-node vertices. In an embodiment, a computer receives a graph query (GQ) to extract result paths from a graph in a database. The GQ has a sequence of query vertices (QVs) and a sequence of query edges (QEs). The computer successively traverses each QE and QV to detect paths of the graph that match the GQ. Traversing each QE and QV entails retrieving NVs of a current graph vertex (CGV) of a current traversal path. If the CGV is a key in a cache whose keys are graph vertices having an excessive degree, then the computer retrieves NVs from the cache. Otherwise, the computer retrieves NVs from the database. If the degree is excessive, and the CGV is not a key in the cache, then the computer stores, into the cache, the CGV as a key for the NVs.

公开(公告)号：US20210209108A1

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

申请号：US16734035

申请日：2020-01-03

Applicant: Oracle International Corporation

Inventor： Vlad Haprian ,  Oskar Van Rest ,  Sungpack Hong ,  Hassan Chafi ,  Bence Czipo

IPC: G06F16/2453 ,  G06F16/22

Abstract: Herein are techniques to accelerate finding a top few shortest paths between two vertices of a graph. In an embodiment, a computer calculates, for a graph that contains vertices that include landmark vertices, distances between each vertex and each landmark vertex. Based on the distances from each vertex to each landmark vertex, a top few shortest paths from a source vertex to a target vertex are calculated. In an embodiment, triangulation establishes a lower bound on a distance from a neighbor vertex of a current vertex to a target vertex of a query. In an embodiment, distance predictions based on the distance lower bounds are used to accelerate a K-A star search for the top few shortest paths.

公开(公告)号：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.

公开(公告)号：US10810257B2

公开(公告)日：2020-10-20

申请号：US14837696

申请日：2015-08-27

Applicant: Oracle International Corporation

Inventor： Oskar Van Rest ,  Jinha Kim ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F16/901

Abstract: Techniques herein are for fast processing of path-finding queries in large graph databases. A computer system receives a graph search request to find a set of result paths between one or more source vertices of a graph and one or more target vertices of the graph. The graph comprises vertices connected by edges. During a first pass, the computer system performs one or more breadth-first searches to identify a subset of edges of the graph. The one or more breadth-first searches originate at the one or more source vertices. After the first pass and during a second pass, the computer system performs one or more depth-first searches to identify the set of result paths. The one or more depth-first searches originate at the one or more target vertices. The one or more depth-first searches traverse at most the subset of edges of the graph.

公开(公告)号：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.

公开(公告)号：US20200265090A1

公开(公告)日：2020-08-20

申请号：US16280591

申请日：2019-02-20

Applicant: Oracle International Corporation

Inventor： Damien Hilloulin ,  Davide Bartolini ,  Oskar Van Rest ,  Vlad Haprian, ,  Sungpack Hong ,  Hassan Chafi,

IPC: G06F16/901 ,  G06F16/903

Abstract: Herein are computerized techniques for processing a heterogeneous graph according to scan-avoidant query planning. In an embodiment, a computer respectively stores a first and second kind of vertices of a property graph into a first and second vertex tables. The computer generates, without scanning the second vertex table: a) an initial partial result of a query of the property graph based on the first vertex table, and b) a subsequent partial result of the query based on the initial partial result and the second kind of vertices. Herein are graph encodings that are dense, without requiring extra computation, and that exploit graph heterogeneity to achieve an aggregation granularity that reduces data working set scope, optimizes for caching, and encourages compression. Herein are query execution mechanisms and techniques that intelligently avoid accessing circumstantially extraneous data and/or structures and that can horizontally scale.

公开(公告)号：US10423663B2

公开(公告)日：2019-09-24

申请号：US15409091

申请日：2017-01-18

Applicant: ORACLE INTERNATIONAL CORPORATION

Inventor： Oskar Van Rest ,  Jinha Kim ,  Xuming Meng ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F16/00 ,  G06F16/901

Abstract: Techniques herein accelerate graph querying by caching neighbor vertices (NVs) of super-node vertices. In an embodiment, a computer receives a graph query (GQ) to extract result paths from a graph in a database. The GQ has a sequence of query vertices (QVs) and a sequence of query edges (QEs). The computer successively traverses each QE and QV to detect paths of the graph that match the GQ. Traversing each QE and QV entails retrieving NVs of a current graph vertex (CGV) of a current traversal path. If the CGV is a key in a cache whose keys are graph vertices having an excessive degree, then the computer retrieves NVs from the cache. Otherwise, the computer retrieves NVs from the database. If the degree is excessive, and the CGV is not a key in the cache, then the computer stores, into the cache, the CGV as a key for the NVs.

公开(公告)号：US20190121825A1

公开(公告)日：2019-04-25

申请号：US16223805

申请日：2018-12-18

Applicant: Oracle International Corporation

Inventor： Jinha Kim ,  Oskar Van Rest ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F16/901 ,  G06F16/22

Abstract: Techniques herein optimize subgraph pattern matching. A computer receives a graph vertex array and a graph edge array. Each vertex and each edge has labels. The computer stores an array of index entries and an array of edge label sets. Each index entry corresponds to a respective vertex originating an edge and associates an offset of the edge with an offset of the respective vertex. Each edge label set contains labels of a respective edge. The computer selects a candidate subset of edges originating at a current vertex. The edge labels of each candidate edge of the candidate subset include a same particular query edge labels. The computer selects the candidate subset based on the index array and afterwards selects a result subset of vertices from among the terminating vertices of the candidate edges. The labels of each vertex of the result subset include a same particular query vertex labels.

公开(公告)号：US10204174B2

公开(公告)日：2019-02-12

申请号：US14969789

申请日：2015-12-15

Applicant: Oracle International Corporation

Inventor： Jinha Kim ,  Oskar Van Rest ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F17/30

Abstract: Techniques herein optimize subgraph pattern matching. A computer receives a graph vertex array and a graph edge array. Each vertex and each edge has labels. The computer stores an array of index entries and an array of edge label sets. Each index entry corresponds to a respective vertex originating an edge and associates an offset of the edge with an offset of the respective vertex. Each edge label set contains labels of a respective edge. The computer selects a candidate subset of edges originating at a current vertex. The edge labels of each candidate edge of the candidate subset include a same particular query edge labels. The computer selects the candidate subset based on the index array and afterwards selects a result subset of vertices from among the terminating vertices of the candidate edges. The labels of each vertex of the result subset include a same particular query vertex labels.