公开(公告)号：US20220129461A1

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

申请号：US17080700

申请日：2020-10-26

Applicant: Oracle International Corporation

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

IPC: G06F16/2453 ,  G06F16/901 ,  G06F16/2455

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

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

公开(公告)号：US20210279282A1

公开(公告)日：2021-09-09

申请号：US17330046

申请日：2021-05-25

Applicant: Oracle International Corporation

Inventor： DAMIEN HILLOULIN ,  DAVIDE BARTOLINI ,  OSKAR VAN REST ,  Alexander Weld ,  Sungpack Hong ,  Hassan Chafi

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

Abstract: Techniques are provided herein for efficient representation of heterogeneous graphs in memory. In an embodiment, vertices and edges of the graph are segregated by type. Each property of a type of vertex or edge has values stored in a respective vector. Directed or undirected edges of a same type are stored in compressed sparse row (CSR) format. The CSR format is more or less repeated for edge traversal in either forward or reverse direction. An edge map translates edge offsets obtained from traversal in the reverse direction for use with data structures that expect edge offsets in the forward direction. Subsequent filtration and/or traversal by type or property of vertex or edge entails minimal data access and maximal data locality, thereby increasing efficient use of the graph.

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

公开(公告)号：US20210042102A1

公开(公告)日：2021-02-11

申请号：US17069104

申请日：2020-10-13

Applicant: Oracle International Corporation

Inventor： Petr Koupy ,  Thomas Manhardt ,  Siegfried Depner ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F8/41 ,  G06F9/50 ,  G06F17/16 ,  G06F16/27 ,  G06F17/10 ,  G06F11/34

Abstract: Techniques herein minimally communicate between computers to repartition a graph. In embodiments, each computer receives a partition of edges and vertices of the graph. For each of its edges or vertices, each computer stores an intermediate representation into an edge table (ET) or vertex table. Different edges of a vertex may be loaded by different computers, which may cause a conflict. Each computer announces that a vertex resides on the computer to a respective tracking computer. Each tracking computer makes assignments of vertices to computers and publicizes those assignments. Each computer that loaded conflicted vertices transfers those vertices to computers of the respective assignments. Each computer stores a materialized representation of a partition based on: the ET and vertex table of the computer, and the vertices and edges that were transferred to the computer. Edges stored in the materialized representation are stored differently than edges stored in the ET.

公开(公告)号：US10896223B2

公开(公告)日：2021-01-19

申请号：US16223805

申请日：2018-12-18

Applicant: Oracle International Corporation

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

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

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.

公开(公告)号：US20200133663A1

公开(公告)日：2020-04-30

申请号：US16176853

申请日：2018-10-31

Applicant: Oracle International Corporation

Inventor： Martijn Dwars ,  Martin Sevenich ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F8/75 ,  G06F8/51 ,  G06F17/30 ,  G06F8/30 ,  G06F8/41

Abstract: Techniques are described herein for automatic generation of multi-source breadth-first search (MS-BFS) from high-level graph processing language that can be executed in a distributed computing environment. In an embodiment, a method involves a computer analyzing original software instructions. The original software instructions are configured to perform multiple breadth-first searches to determine a particular result. Each breadth-first search originates at each of a subset of vertices of a graph. Each breadth-first search is encoded for independent execution. Based on the analyzing, the computer generates transformed software instructions configured to perform a MS-BFS to determine the particular result. Each of the subset of vertices is a source of the MS-BFS. In an embodiment, the second plurality of software instructions comprises a node iteration loop and a neighbor iteration loop, and the plurality of vertices of the distributed graph comprise active vertices and neighbor vertices. The node iteration loop is configured to iterate once per each active vertex of the plurality of vertices of the distributed graph, and the node iteration loop is configured to determine the particular result. The neighbor iteration loop is configured to iterate once per each active vertex of the plurality of vertices of the distributed graph, and each iteration of the neighbor iteration loop is configured to activate one or more neighbor vertices of the plurality of vertices for the following iteration of the neighbor iteration loop.

公开(公告)号：US20190325075A1

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

申请号：US15956115

申请日：2018-04-18

Applicant: Oracle International Corporation

Inventor： DAMIEN HILLOULIN ,  DAVIDE BARTOLINI ,  OSKAR VAN REST ,  Alexander Weld ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F17/30

Abstract: Techniques are provided herein for efficient representation of heterogeneous graphs in memory. In an embodiment, vertices and edges of the graph are segregated by type. Each property of a type of vertex or edge has values stored in a respective vector. Directed or undirected edges of a same type are stored in compressed sparse row (CSR) format. The CSR format is more or less repeated for edge traversal in either forward or reverse direction. An edge map translates edge offsets obtained from traversal in the reverse direction for use with data structures that expect edge offsets in the forward direction. Subsequent filtration and/or traversal by type or property of vertex or edge entails minimal data access and maximal data locality, thereby increasing efficient use of the graph.

公开(公告)号：US20190235913A1

公开(公告)日：2019-08-01

申请号：US15886745

申请日：2018-02-01

Applicant: Oracle International Corporation

Inventor： Alexander Weld ,  Korbinian Schmid ,  Sungpack Hong ,  Hassan Chafi ,  Vlad Ioan Haprian

IPC: G06F9/48

CPC classification number: G06F9/48

Abstract: Techniques are described herein for concurrently evaluating graph processing tasks in a fair and efficient manner. In an embodiment, a request to execute a graph processing task is received. A first mapping associates each graph processing task of a plurality of graph processing tasks to a set of workload characteristics of a plurality of sets of workload characteristics. A second mapping associates each set of workload characteristics of the plurality of sets of workload characteristics to a set of execution parameters of a plurality of sets of execution parameters. Using the first mapping, a set of workload characteristics is determined based on the graph processing task. Using the second mapping, a set of execution parameters is determined based on the determined set of workload characteristics. The graph processing task is executed based on the determined set of execution parameters.

公开(公告)号：US20180307777A1

公开(公告)日：2018-10-25

申请号：US15495193

申请日：2017-04-24

Applicant: Oracle International Corporation

Inventor： Martin Sevenich ,  Sungpack Hong ,  Alexander Weld ,  Hassan Chafi ,  Daniel Lehmann

IPC: G06F17/30

CPC classification number: G06F16/9024 ,  G06F16/23 ,  G06F16/90335

Abstract: Techniques herein minimize memory needed to store distances between vertices of a graph for use during a multi-source breadth-first search (MS-BFS). In an embodiment, during each iteration of a first sequence of iterations of a MS-BFS, a computer updates a first matrix that contains elements that use a first primitive integer type having a first width to record a distance from a source vertex of a graph to another vertex. The computer detects that a count of iterations of the first sequence of iterations exceeds a threshold. Responsively, the computer creates a second matrix that contains elements that use a second primitive integer type having a second width that is larger than the first width to record a distance from a source vertex of the graph to another vertex. During each iteration of a second sequence of iterations of the MS-BFS, the computer updates the second matrix.