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

Patent metadata

Field	Value
Publication number	US-2016147779-A1
Application number	US-201414555275-A
Country	US
Kind code	A1
Filing date	Nov 26, 2014
Priority date	Nov 26, 2014
Publication date	May 26, 2016
Grant date	—

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.

First claim

What is claimed is:

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 th

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Eguro Kenneth H
• Istvan Zsolt
• Arasu Arvind
• Ramamurthy Ravishankar
• Shriraghav Kaushik

Classifications

• G06F16/172

  Caching, prefetching or hoarding of files · CPC title

• G06F16/122 Primary

  using management policies (point-in-time backing up or restoration of persistent data G06F11/1446; file migration policies for HSM systems G06F16/185) · CPC title

• G06F16/24539 Primary

  using cached or materialised query results · CPC title

• G06F16/9027

  Trees · CPC title

• G06F16/24552

  Database cache management · CPC title