Hardware accelerated reconfigurable processor for accelerating database operations and queries

• US 20080189252A1
• Filed: 08/27/2007
• Published: 08/07/2008
• Est. Priority Date: 08/25/2006
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradata US, Inc. (Teradata Corporation)
• Inventors: Chamdani, Joseph I., Yang, Liuxi, Corwin, Michael, Branscome, Jeremy
• Granted Patent: US 7,908,259 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/2453 Query optimisation

Abstract

Embodiments of the present invention provide a hardware accelerator that assists a host database system in processing its queries. The hardware accelerator comprises special purpose processing elements that are capable of receiving database query/operation tasks in the form of machine code database instructions, execute them in hardware without software, and return the query/operation result back to the host system. For example, table and column descriptors are embedded in the machine code database instructions. For ease of installation, the hardware accelerators employ a standard interconnect, such as a PCIe or HT interconnect. The processing elements implement a novel dataflow design and Inter Macro-Op Communication (IMC) data structures to execute the machine code database instructions. The hardware accelerator may also comprise a relatively large memory to enhance the hardware execution of the query/operation tasks requested. The hardware accelerator utilizes hardware-friendly memory addressing, which allows for arithmetic derivation of a physical address from a global database virtual address simply based on a row identifier. The hardware accelerator minimizes memory reads/writes by keeping most intermediate results flowing through IMCs in pipelined and parallel fashion. Furthermore, the hardware accelerator may employ task pipelining and pre-fetch pipelining to enhance its performance.

Claims

1. A hardware accelerator for assisting in processing queries from a host system to a database, wherein the hardware accelerator executes machine code for database query tasks in hardware processing elements from a database management system, said hardware accelerator comprising:

a scanning processing element to perform at least one of parallel field extraction and comparison of database columns;

an indexing processing element to perform at least one of a database projection operation; and

an associative processing element to perform at least one of grouping/aggregating, sieving, sorting, and an associative join.

2. The hardware accelerator according to claim 1, further comprising a dedicated memory that is capable of storing gigabyte portions of the database.

3. The hardware accelerator according to claim 1, wherein the hardware accelerator is coupled to the host system over a Peripheral Component Interconnect Express connection.

4. The hardware accelerator according to claim 1, wherein the hardware accelerator is coupled to the host system over a HyperTransport connection.

5. The hardware accelerator according to claim 1, wherein the hardware accelerator comprises field programmable gate array (FPGA) logic that reconfigures operations of at least one of the scanning processing element, the indexing processing element, and the associative processing element.

6. The hardware accelerator according to claim 1, wherein comprises Application Specific Integrated Circuit (ASIC) logic that reconfigures operations of at least one of the scanning processing element, the indexing processing element, and the associative processing element.

25. The hardware accelerator of claim 1, further comprising a task processor configured to assign the database query tasks from the host database system to at least one of the scanning processing element, the indexing processing element, and the associative processing element.

26. The hardware accelerator of claim 2, wherein the dedicated memory is about 32 Gigabytes.

27. The hardware accelerator of claim 2, wherein the dedicated memory is at least 256 Gigabytes.

28. The hardware accelerator of claim 2, wherein the hardware accelerator is configured as a memory module package.

29. The hardware accelerator of claim 2, wherein the hardware accelerator is configured as a rack-mountable unit.

7. A database hardware accelerator module configured to be coupled with a host system running a database management system via an interconnect bus, said module comprising:

a set of processing elements configured to receive database machine code instructions and execute them in their respective hardware without software and return results back to the host system upon completion, wherein the processing elements are configured with a dataflow architecture;

a self-routing fabric coupling the processing elements, wherein the processing elements communicate with each other based on Inter Macro-Op Communication (IMC) data structures in a pipelined parallel fashion; and

a memory capable of storing gigabyte portions of the database in compressed, column-store format.

8. The module of claim 7, wherein the IMC is a physical data structure in the processing elements.

9. The module of claim 7, wherein the set of processing elements are configured to support task pipelining.

10. The module of claim 7, wherein the set of processing elements are configured to process data fetched from storage while data is being fetched from storage.

11. The module of claim 7, wherein the processing elements access data in the memory based on a physical address that is arithmetically derived from a global database virtual address space.

12. The module of claim 7, wherein the processing elements access data in the memory based on a physical address that is arithmetically derived from a global database virtual address space and an implicit row identifier of the data in the database.

30. The database hardware accelerator module of claim 7, wherein the hardware accelerator module is configured as a memory module package.

31. The database hardware accelerator module of claim 7, wherein the hardware accelerator module is configured as a rack-mountable unit.

33. The hardware accelerator of claim 31, further comprising a memory configured to store portions of the database in column-store format.

13. A database hardware accelerator node coupled to a host system, wherein the hardware accelerator executes machine code for database query tasks in hardware processing elements from a database management system running on the host system, said hardware accelerator comprising:

a set of processing cores comprising combined logic for a scanning processing element to perform at least one of parallel field extraction and comparison of database columns and an indexing processing element to perform at least one of a database projection operation and a hardware-accelerated index content addressable memory processing element to perform at least one of grouping/aggregating, sieving, sorting, and an associative join;

a self routing switching fabric that couples the processing cores together; and

a memory capable of storing gigabyte portions of the database.

14. The hardware accelerator according to claim 13, further comprising a Peripheral Component Interconnect Express interface.

15. The hardware accelerator according to claim 13, further comprising a HyperTransport interface.

16. The hardware accelerator according to claim 13, wherein the set of processing cores are implemented based on field programmable gate arrays.

17. The hardware accelerator according to claim 13, wherein the set of processing cores are implemented based on Application Specific Integrated Circuits.

18. The hardware accelerator according claim 13, wherein the hardware accelerator comprises a set of four identical processing cores.

19. The hardware accelerator according claim 13, wherein the hardware accelerator comprises pairs of identical processing cores.

20. The hardware accelerator according to claim 13, wherein the memory is at least 256 Gigabytes.

21. The hardware accelerator according to claim 13, wherein the memory is about 32 Gigabytes.

22. The hardware accelerator according to claim 13, wherein the memory is about 16 Gigabytes.

23. The hardware accelerator according to claim 13, wherein the set of processing cores are programmable by machine code database instructions.

24. The hardware accelerator according to claim 13, wherein the set of processing cores are reconfigurable in the manner in which they execute machine code database instructions.

32. A hardware accelerator for assisting in processing queries from a host system to a database, wherein the hardware accelerator is configured to execute database machine code instructions for at least a portion of the queries, said hardware accelerator comprising:

an input for receiving database machine code instructions for tasks of a query offloaded to the hardware accelerator;

a set of processing elements configured to execute the database machine code instructions on data from the database for the tasks; and

an output for providing a result for the tasks based on the execution of the database machine code instructions.

34. The hardware accelerator of claim 32, wherein the processing elements are configured to process data from the memory in a dataflow based on the database machine code instructions.

35. The hardware accelerator of claim 32, wherein processing elements comprise logic configured to scan a set of pointers and data from the portion of the database in memory against a predicate specified in the database machine code instructions.

36. The hardware accelerator of claim 32, wherein the processing elements can be configured to perform a fetch database operation based on the database machine code instructions.

37. The hardware accelerator of claim 32, wherein the processing elements can be configured to perform a format database operation based on the database machine code instructions.

38. The hardware accelerator of claim 32, wherein the processing elements can be configured to perform a join database operation based on the database machine code instructions.

39. The hardware accelerator of claim 32, wherein the processing elements can be configured to emit a dataflow of a scan of contiguous rows in a portion of the database in the memory based on the database machine code instructions.

40. The hardware accelerator of claim 32, wherein the processing elements can be configured to emit a dataflow of a nested-loop cross-product join of two columns in the portion of the database in the memory based on the database machine code instructions.

41. The hardware accelerator of claim 32, wherein the processing elements can be configured to emit a dataflow of an index-based nested join of columns in the portion of the database in the memory based on the database machine code instructions.

42. The hardware accelerator of claim 32, wherein the processing elements can be configured to emit a dataflow of scans of a dispersed subset of rows in a column of the portion of the database in the memory based on the database machine code instructions.

43. The hardware accelerator of claim 38, wherein the processing elements are configured to communicate via numbered communications channels specified in the database machine code instructions.

44. The hardware accelerator of claim 32, wherein the processing elements are configured to traverse an index of data from the portion of the database in the memory against a set of predicates specified in the database machine code instructions.

45. The hardware accelerator of claim 32, wherein the processing elements are configured to scan a group index source column and emit a dataflow of pointers to a target table that have been joined through the index based on the database machine code instructions.

46. The hardware accelerator of claim 32, wherein the processing elements are configured to emit a dataflow of results for database list operations based on a database machine code instructions.

47. The hardware accelerator of claim 32, wherein the processing elements are configured to collect items from a dataflow of data from the portion of the database in memory against at least one predicate specified in the database machine code instructions.

48. The hardware accelerator of claim 32, wherein the processing elements can be configured to emit a dataflow for a two dimensional list composed of a set of input lists that are horizontally correlated based on the database machine code instructions

49. The hardware accelerator of claim 32, wherein the processing elements are configured to emit a dataflow for an inner-loop cross-product nested join of lists against a predicate specifying one or more columns based on the database machine code instructions.

50. The hardware accelerator of claim 32, wherein the processing elements are configured to emit a vertical merger of two lists from the portion of the database in the memory based on the database machine code instructions.

51. The hardware accelerator of claim 32, wherein the processing elements are configured to emit a dataflow of tuples from the portion of the database selected from the memory against at least one column predicate based on the database machine code instructions.

52. The hardware accelerator of claim 32, wherein the processing elements are configured to emit a dataflow of arithmetic results performed on at least one list based on the database machine code instructions.

53. The hardware accelerator of claim 32, wherein the processing elements are configured to emit a dataflow of results for operations that are based on an associative key based on the database machine code instructions.

54. The hardware accelerator of claim 32, wherein the processing elements are configured to emit results mapped to locations in memory for operations that are based on an associative key based on the database machine code instructions.

55. The hardware accelerator of claim 32, wherein the processing elements are configured to perform value-based database operations on the dataflow of data from the portion of the database in the memory based on the database machine code instructions.

56. The hardware accelerator of claim 32, wherein the processing elements are configured to emit a dataflow of results for a histogram of like keys found in an input list of a dataflow from the memory using a specified mapping based on the database machine code instructions.

57. The hardware accelerator of claim 32, wherein the processing elements are configured to emit a dataflow of reordered tuples in a 2-dimensional input list of two columns from a dataflow from the memory such that extreme N keys occur in the final N tuple rows, contiguously based on the database machine code instructions.

58. The hardware accelerator of claim 32, wherein the processing elements are configured to emit a dataflow of an aggregation function performed on the dataflow based on the database machine code instructions.

59. The hardware accelerator of claim 32, wherein the processing elements are configured to emit results to locations in memory for an aggregation function performed on the dataflow based on the database machine code instructions.