Systems and Methods for Providing Distributed Tree Traversal Using Hardware-Based Processing

• US 20160147779A1
• Filed: 11/26/2014
• Published: 05/26/2016
• Est. Priority Date: 11/26/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Eguro, Kenneth H., Istvan, Zsolt, Arasu, Arvind, Ramamurthy, Ravishankar, Shriraghav, Kaushik
• Granted Patent: US 10,572,442 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/122 using management policies backup systems G06F11/1446; file migration policies for HSM systems G06F16/185
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/9027 Trees

Abstract

A database management system (DBMS) run a host CPU and a hardware coprocessor accelerate traversal of a tree-type data structure by allocating reusable memory in cache to store portions of the tree-type data structure as the tree-type data structure is being requested by the host CPU. The hardware coprocessor manages the cached tree-type data structure in a manner that is transparent to the host CPU. A driver located at the host CPU or at a separate computing device can provide an interface between the host CPU and the hardware coprocessor, thus reducing communications between the host CPU and the hardware coprocessor.

Claims

1. A method comprising:

at a database management system (DBMS) at least partially embodied in computer-readable media executable by one or more processors,

in response to receiving the query, sending a query to a driver; and

at the driver at least partially embodied in computer-readable media executable by one or more processors,

in response to receiving the query from the DBMS, sending a modified query to a hardware logic device.

2. The method of claim 1, further comprising:

at the hardware logic device,

in response to receiving the modified query,

traversing nodes of a tree-type relational database data-structure previously cached in memory associated with the hardware logic device based at least on the modified query;

retrieving at least portions of data located at each traversed node; and

sending the retrieved portions of data to the driver.

3. The method of claim 1, further comprising:

at the driver,

in response to receiving portions of data from the hardware logic device, validating the portions of the data based at least on associated data stored at one of the one or more tree-type relational database data-structures associated with the DBMS; and

in response to validating the portions of the data, sending the validated portions of the data to the DBMS.

4. The method of claim 1, wherein the query is a node-level query comprising at least a query value and data located at an associated node, wherein the modified query is a tree-level request comprising the query value and a node identifier.

5. The method of claim 1, further comprising:

at the driver,

in response to receiving portions of data from the hardware logic device, determining whether the received portions of the data are inconsistent; and

in response to determining that the received portions are inconsistent, sending the query, node data and path information to the hardware logic device; and

at the hardware logic device, in response to receiving the query, the node data and the path information, performing at least one of;

allocating a page for a node associated with the node data;

or

updating at least one of data values or pointer information included in a previously cached page associated with the node data.

6. The method of claim 1, further comprising:

at the hardware logic device,

in response to receiving the query, node data and path information,

sequentially allocating a page within a cache memory associated with the hardware logic device for a node associated with the received query, the node data and the path information being based at least on allocation rules when the cache memory does not currently include a page associated with the node that is associated with the received query.

7. The method of claim 1, further comprising:

at the driver,

attempting to validate portions of data sent from the hardware logic device; and

in response to not being able to validate the portions of data, sending the query, node data, and path information to the hardware logic device; and

at the hardware logic device, in response to receiving the query, the node data, and the path information and after the hardware logic device previously sent the portions of data, updating at least one of the data values or pointer information included in the previously cached page associated with at least one of the received node data or the received path information.

8. The method of claim 1, further comprising:

at the driver,

storing portions of data received from the hardware logic device within a lookup table (LUT);

in response to receiving the query from the DBMS,

determining whether information stored within the LUT is associated with the received query; and

sending information stored within the LUT to the DBMS based on a determination that the information stored within the LUT is associated with the received query.

9. The method of claim 1, further comprising:

at the hardware logic device,

in response to receiving the modified query,

traversing nodes of a tree-type relational database data-structure previously cached in memory associated with the hardware logic device based at least on the modified query;

retrieving at least portions of data located at each traversed node; and

sending the retrieved portions of data to the driver,

wherein the retrieved portions of data located at a traversed node comprise at least one of a first data value associated with a node identifier and the first data value'"'"'s ordinal position of the first data value within an associated cached page and at least one second data value located at a predefined location relative to the first data value and the second data value'"'"'s ordinal position within the cached page.

10. The method of claim 1,

further comprising:

at the hardware logic device,

in response to receiving the modified query,

traversing nodes of a tree-type relational database data-structure previously cached in memory associated with the hardware logic device based at least on the modified query;

retrieving at least portions of data located at each traversed node; and

sending the retrieved portions of data to the driver,

wherein the retrieved portions of data located at a traversed node comprise at least one first data value associated with a node identifier and an ordinal position of the at least one first data value within an associated cached page and at least one second data value located at a predefined location relative to the at least one first data value and the at least one second data value'"'"'s ordinal position within the cached page,

wherein the at least one first data value comprises at least one of a lower bounded value or an upper bounded value associated with the node identifier, wherein the at least one second value comprises at least one of a value located at an ordinal position that is at least one less than the lower bounded value or a value located at an ordinal position that is at least one greater than the upper bounded value.

11. A system comprising:

a database management system (DBMS) at least partially embodied in a computer-readable media executable by one or more processors, wherein the DBMS,

in response to receiving a query, sends a query; and

a driver at least partially embodied in a computer-readable media executable by one or more processors, wherein the driver, in response to receiving the query from the DBMS, sends a modified query.

12. The system of claim 11, further comprising:

a logic device, at least partially embodied in hardware, comprises cache memory for storing a tree-type relational database data-structure associated with at least a portion of one of the one or more tree-type relational database data-structures associated with the DBMS, the logic device,

in response to receiving the modified query,

traverses nodes of the tree-type relational database data-structure stored in the cache memory based at least on the modified query;

retrieves portions of data located at each traversed node; and

sends the retrieved portions of data to the driver.

13. The system of claim 11, wherein the driver, in response to receiving the portions of data,

validates the portions of the data, based at least on data stored at one of the tree-type relational database data-structures associated with the DBMS;

and

sends the validated portions of the data to the DBMS.

14. The system of claim 11, wherein the query is a node-level query comprising at least a query value and data located at an associated node, wherein the modified query is a tree-level request comprising the query value and a node identifier.

15. The system of claim 11, wherein the driver, in response to receiving portions of data,

determines whether the received portions of the data are inconsistent;

and

in response to determining that the received portions of the data are inconsistent, sends the query, node data and path information, and

further comprising a logic device, in response to receiving the query, the node data, and the path information, performs at least one of;

allocating a page for a node associated with the node data;

or

updating at least one of data values or pointer information included in a previously cached page associated with the node data.

16. The system of claim 11, further comprising a logic device, in response to receiving the query, node data and path information,

sequentially allocates a page within a cache memory associated with the logic device for a node associated with the received query, the node data and the path information being based at least on allocation rules when the cache memory does not currently include a page associated with the node that is associated with the received query.

17. The system of claim 11, wherein the driver,

attempts to validate portions of data sent from the logic device;

and

in response to not being able to validate the portions of data, sends the query, node data and path information, and

further comprising a logic device, in response to receiving the query, the node data, and the path information after the logic device previously sent the portions of data, updates at least one of the data values or pointer information included in the previously cached page associated with at least one of the received node data or the received path information.

18. The system of claim 11, wherein the driver,

stores portions of received data received from the logic device as nodes within a lookup table (LUT);

in response to receiving the query from the DBMS,

determines whether information stored within the LUT is associated with the received query; and

sends information stored within the LUT to the DBMS based at least on a determination that the information stored within the LUT is associated with the received query.

19. The system of claim 11, further comprising a logic device, in response to receiving the modified query,

traverses nodes of a tree-type relational database data-structure previously cached in memory associated with the logic device based at least on the modified query;

retrieves at least portions of data located at each traversed node; and

sends the retrieved portions of data to the driver,

wherein the retrieved portions of data located at a traversed node comprise at least one first data value associated with a node identifier and an ordinal position of the first data value within an associated cached page and at least one second data value located at a predefined location relative to the first data value and an ordinal position of the second data value within the cached node.

20. The system of claim 11, further comprising a logic device, in response to receiving the modified query,

traverses nodes of a tree-type relational database data-structure previously cached in memory associated with the logic device based at least on the modified query;

retrieves at least portions of data located at each traversed node; and

sends the retrieved portions of data to the driver,

wherein the at least one first data value comprises at least one of a lower bounded value or upper bounded value associated with the node identifier and wherein the at least one second value comprises at least one of a value located at an ordinal position that is at least one less than the lower bounded value or a value located at an ordinal position that is at least one greater than the upper bounded value.