OPTIMIZED RECORD PLACEMENT IN GRAPH DATABASE

• US 20190005071A1
• Filed: 06/29/2017
• Published: 01/03/2019
• Est. Priority Date: 06/29/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: KVALNES, Age, KARLBERG, Jan-Ove, KREUTZER, Tor, JOHANSEN, Amund Kronen, VALVAG, Steffen Viken
• Granted Patent: US 11,354,348 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0653 with centralised address assignment
• CPC Class Codes: G06F 16/1724 Details of de-fragmentation performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 16/1727 Details of free space management performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 16/7854 using shape G06F16/7837 takes precedence
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 2206/1004 Defragmentation
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 40/205 Parsing

Abstract

Methods and systems are disclosed for optimizing record placement in a graph by minimizing fragmentation when writing data. Issues with fragmented data within a graph database are addressed on the record level by placing data that is frequently accessed together contiguously within memory. For example, a dynamic rule set may be developed based on dynamically analyzing access patterns of the graph database, policies, system characteristics and/or other heuristics. Based on statistics regarding normal query patterns, the systems and methods may identify an optimal position for certain types of edges that are often traversed with respect to particular types of nodes.

Claims

1. A computer-implemented method for storing data in a graph database, the method comprising:

receiving a request to write the data to the graph database, wherein the graph database comprises a plurality of nodes, edges and properties;

parsing the request to identify at least one entity, wherein the at least one entity is related to at least one of a node and an edge within the graph database;

retrieving a dynamic ruleset for record placement;

based at least in part on the at least one entity and at least a first rule of the dynamic ruleset, determining a number of records for storing the at least one entity in the graph database;

allocating the number of records in a contiguous block of records; and

storing the at least one entity in the allocated contiguous block of records.

2. The computer-implemented method of claim 1, wherein the dynamic ruleset is derived based on one or more of:

statistical access patterns associated with the graph database, one or more policies, system configurations, system characteristics and heuristics.

3. The computer-implemented method of claim 2, wherein the access patterns are evaluated during query execution.

4. The computer-implemented method of claim 2, wherein the access patterns statistically characterize the traversal of edges from one node to another within the graph database for a plurality of queries.

5. The computer-implemented method of claim 4, wherein statistically characterizing the traversal of edges comprises one or more of:

identifying one or more edge types corresponding to the edges traversed;

identifying one or more node types traversed from; and

identifying one or more node types traversed to.

6. The computer-implemented method of claim 5, further comprising:

logging a number of each of the one or more node types traversed from; and

logging a number of each of the one or more node types traversed to.

8. The computer-implemented method of claim 1, further comprising:

based at least in part on the at least one entity and at least a second rule of the dynamic ruleset for record placement, determining a location in memory for storing the at least one entity.

9. The computer-implemented method of claim 8, wherein the location is adjacent to a record storing at least one of the related node and the related edge.

10. The computer-implemented method of claim 8, wherein the second rule and the first rule are different.

11. The computer-implemented method of claim 8, wherein the second rule and the first rule are the same.

12. The computer-implemented method of claim 8, further comprising:

allocating the contiguous block of records at the location in memory.

13. The computer-implemented method of claim 8, further comprising:

determining that the number of records is greater than a number of unused records at the location in memory; and

marking the at least one entity as dirty.

14. A computing device, comprising:

at least one processing unit; and

at least one memory storing computer executable instructions for storing data to a graph database, the instructions when executed by the at least one processing unit causing the computing device to;

receive a request to write the data to the graph database, wherein the graph database comprises a plurality of nodes and edges;

parse the request to identify at least one entity, wherein the at least one entity is related to at least one of a node and an edge within the graph database;

retrieve a dynamic ruleset for record placement;

based at least in part on the at least one entity and at least a first rule of the dynamic ruleset, determine a number of records for storing the at least one entity in the graph database;

based at least in part on the at least one entity and at least a second rule of the dynamic ruleset, determine a location in memory for storing the at least one entity;

allocate the number of records in a contiguous block of records at the location in memory; and

store the at least one entity in the allocated contiguous block of records.

15. The computing system of claim 14, wherein the second rule is one of:

different from the first rule; and

the same as the first rule.

16. The computing system of claim 14, wherein the location is in proximity to a record storing at least one of the node and the edge.

17. The computing system of claim 14, wherein the dynamic ruleset is derived based on one or more of:

statistical access patterns associated with the graph database, one or more policies, system configurations, system characteristics and heuristics.

18. The computing system of claim 17, wherein the access patterns statistically characterize the traversal of edges from one node to another within the graph database for a plurality of queries.

19. The computing system of claim 14, the computer executable instructions further causing the computing device to:

determine that the number of records is greater than a number of unused records at the location in memory;

allocate the contiguous block of records at a different location in memory; and

mark the at least one entity as dirty.

20. A computer storage medium storing computer executable instructions for storing data in a graph database, the instructions when executed by at least one processing unit, cause the at least one processing unit to:

receive a request to write the data to the graph database, wherein the graph database comprises a plurality of nodes and edges;

parse the request to identify at least one entity, wherein the at least one entity is related to at least one of a node and an edge within the graph database;

retrieve a dynamic ruleset for record placement;

based at least in part on a first rule of the dynamic ruleset, determine a number of records for storing the at least one entity in the graph database;

based at least in part on the at least one entity and at least a second rule of the dynamic ruleset, determine a location in memory for storing the at least one entity, wherein the location is proximate to at least one of the related node and the related edge;

allocate the number of records in a contiguous block of records at the location in memory; and

store the at least one entity in the allocated contiguous block of records.