Graph storage in a database

Patent metadata

Field	Value
Publication number	US-11704365-B2
Application number	US-202117356192-A
Country	US
Kind code	B2
Filing date	Jun 23, 2021
Priority date	Jul 1, 2020
Publication date	Jul 18, 2023
Grant date	Jul 18, 2023

Abstract

Techniques are disclosed for storing an arranging data in a database. A method includes a computer system storing, in a database, data indicative of a graph data structure having a plurality of nodes connected by a plurality of edges. The method further includes the computer system determining that a number of edges connected to a first node satisfies a threshold number. In response to the determining, the computer system may store an index in an index row associated with the first node. The index identifies a first row having first and second ranges of values stored in first and second rows, respectively. The values in the first and second rows correspond to edges connected to the first node. The values in the first and second ranges are usable to indicate properties of corresponding ones of the plurality of edges.

First claim

What is claimed is:

1. A method, comprising:
storing, by a computer system, data in a database, wherein the data is indicative of a graph data structure that includes a plurality of nodes connected by a plurality of edges;
determining, by the computer system, that a number of edges connected to a first node of the plurality of nodes satisfies a threshold number;
in response to the determining:
storing, by the computer system in an index row associated with the first node, a first index identifying a first row as having a first range of values corresponding to edges connected to the first node and a second row as having a second range of values corresponding to edges connected to the first node, wherein values within the first and second ranges are of a first data type supported by the first index;
storing, by the computer system in the index row, a second index associated with the first node, the second index identifying a third row as having a third range of values corresponding to edges connected to the first node, wherein values within the third range are of a second data type;
storing, by the computer system in the first row, the values within the first range;
storing, by the computer system in the second row, the values within the second range;
storing, by the computer system in the third row, values within the third range of values; and
wherein the values in the first and second ranges are usable to indicate properties of corresponding ones of the plurality of edges.

2. The method of claim 1 , further comprising:
receiving, by the computer system, a request to store information associated with an edge being connected to the first node, wherein the information includes a value indexable by the first index;
in response to the request:
accessing, by the computer system, the first index in the index row to identify one of the first row or the second row for storing the information based on the indexable value residing in one of the first range or the second range; and
storing, by the computer system, the information in the identified row.

3. The method of claim 1 , further comprising:
receiving, by the computer system, a query for information about an edge connected to the first node, wherein the query specifies a value corresponding to the edge and indexable by the first index;
in response to the query:
accessing, by the computer system, the first index in the index row to identify one of the first row or the second row as storing the information based on the indexable value residing in one of the first range or the second range; and
retrieving, by the computer system, the information in the identified row.

4. The method of claim 3 , wherein information within the identified row is sorted based on the stored values indexable by the first index, and wherein the retrieving includes performance of a binary search on the stored values within the identified row.

5. The method of claim 1 , further comprising:
in response to determining that a size of the first row satisfies a size threshold:
adding, by the computer system to the database, a third fourth row to store values corresponding to edges connected to the first node; and
modifying, by the computer system, the first index to identify the fourth row as having a fourth range of values.

6. The method of claim 1 , further comprising:
storing, by the computer system in a fourth row, values of the second data type and corresponding to edges coupled to the first node
wherein the second index further identifies a fourth range of values for the values stored in the fourth row.

7. The method of claim 1 , further comprising:
storing, by the computer system, a global index that associates values of a particular data type to rows of the database that correspond to two or more of the plurality of nodes.

8. The method of claim 7 , further comprising:
receiving, by the computer system, a query for information corresponding to edges connected to the two or more nodes, wherein the query specifies values of the particular data type; and
in response to the query and based on the specified values, using, by the computer system, the global index to retrieve the information.

9. A non-transitory computer-readable storage medium storing program instructions executable by a computer system to perform operations comprising:
storing data in a database, the data being indicative of a graph structure having a plurality of nodes connected by a plurality of edges, wherein the database includes a plurality of value rows;
determining that a number of edges connected to a first node of the plurality of nodes is at least a threshold value;
in response to the determining:
storing in a first value row, values within a first range of values, the first range of values being identified in a first index stored in an index row associated with the first node;
storing in a second value row, values within a second range of values, the second range of values being identified in the first index, wherein the values in the first and second ranges are usable to indicate a first type of properties corresponding to ones of the plurality of edges; and
storing a second index in the index row, the second index having a third range of values, wherein values within the third range are usable to indicate a second type of properties corresponding to ones of the plurality of edges, the second type being different from the first type.

10. The computer readable medium of claim 9 , wherein the instructions are further executable to store, in a third value row, a value of the second type falling within the third range of values.

11. The computer readable medium of claim 10 , wherein the instructions are further executable to:
receive a query for information regarding an edge connected to the first node, wherein the query specifies a value corresponding to an edge having a value type of one of the first and second types; and
access one of the first and second indexes based on which of the first and second value types to which the value corresponds; and
access the information from one of the plurality of rows based on the one of the first and second indexes accessed and a range in which the value falls.

12. The computer readable medium of claim 9 , further comprising instructions executable to sort, in a particular one of the plurality of value rows, values indexable by an index and a range of values corresponding to the particular one of the plurality of rows.

13. The computer readable medium of claim 9 , further comprising instructions executable to:
determine that a size of a one of the plurality of rows satisfies a size threshold;
add, to the plurality of rows, an additional row; and
modify an index corresponding to the additional row to identify the additional row as storing an additional range of values.

14. The computer readable medium of claim 9 , further comprising instructions executable to perform a binary search among a plurality of values in a given row of the plurality of rows in response to determining that a queried value is stored in the given row.

15. The computer readable medium of claim 9 , further comprising instructions executable to store a global index that associates values of a particular data type to ones of the plurality of rows that correspond to two or more of the plurality of nodes.

16. The computer readable medium of claim 15 , further comprising instructions executable to:
receive a query for information corresponding to edges connected to two or more nodes, wherein the query specifies values of the particular data typ

Assignees

• Paypal Inc

Inventors

• Li Xin
• Wang Lei
• Chen Xin
• Zhang Pengshan
• Zhang Jun
• Zhang Haoran
• Zuo Quin
• Tan Junsheng
• Yue Ying
• Zhang Chao
• Yun Xiaohan
• Yang Zhenyin

Classifications

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/90335

  Query processing · CPC title