Methods and systems for hardware acceleration of database operations and queries

• US 20080183688A1
• Filed: 08/27/2007
• Published: 07/31/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: Cherabuddi, Raj, Chamdani, Joseph I., Yang, Liuxi, Krishnamurthy, Ravi, Corwin, Michael, Branscome, Jeremy
• Granted Patent: US 8,244,718 B2
• Time in Patent Office: Days
• US Class Current: 707/4
• CPC Class Codes: G06F 16/2453 Query optimisation

Abstract

Embodiments of the present invention provide a database system that is optimized by using hardware acceleration. The system may be implemented in several variations to accommodate a wide range of queries and database sizes. In some embodiments, the system may comprise a host system that is coupled to one or more hardware accelerator components. The host system may execute software or provide an interface for receiving queries. The host system analyzes and parses these queries into tasks. The host system may then select some of the tasks and translate them into machine code instructions, which are executed by one or more hardware accelerator components. The tasks executed by hardware accelerators are generally those tasks that may be repetitive or processing intensive. Such tasks may include, for example, indexing, searching, sorting, table scanning, record filtering, and the like.

Claims

1. A method of processing database queries, said method comprising:

receiving a query on information in a database from a database management system running on a first processor;

determining query fragments that accomplish the query;

selecting a set of the query fragments for offload to a second processor coupled to the first processor, based on their suitability for execution in hardware;

determining machine code database instructions for the selected query fragments;

determining results for the query fragments based on executing the machine code database instructions in the second processor; and

providing the results for the query fragments to the database management system.

2. The method of claim 1, wherein the second processor is coupled to a memory that is at least 256 Gigabytes and stores portions of the database.

3. The method of claim 1, wherein the second processor is configured to execute the machine code database instructions in a parallel and pipelined dataflow fashion.

4. The method of claim 1, wherein the database is stored in compressed, column-store format and the second processor is configured to execute the machine code database instructions directly on data in the database in compressed, column-store format.

5. The method of claim 1, wherein the machine code instructions comprise macro-operations that perform a fundamental database operation.

6. The method of claim 1, wherein the macro-operations comprise one or more micro-operations that perform data manipulation for the respective database operation of their macro-operations.

7. The method of claim 1, wherein the database is configured in column-store format having column groups of fixed width.

8. The method of claim 1, wherein the database is mapped to a global virtual address space that can be mapped to storage holding the database, a first memory coupled to the first processor, and a second memory coupled to the second processor.

9. An apparatus comprising means configured to perform the method of claim 1.

21. The method of claim 1, wherein records of the database are identified by a unique pointer.

22. The method of claim 1, wherein determining results for the query on information is based on a forward index in a first column that indicates corresponding rows of a primary key in a second column.

23. The method of claim 1, wherein determining results for the query on information is based on a reverse index that indicates corresponding rows of a foreign key in a second column.

24. The method of claim 1, wherein determining results for the query on information is based on a group index that indexes values in a column that are part of a group.

25. The method of claim 24, wherein determining results for the query on information is based on the group index accompanied with replicated columns that have been reordered according to the group index.

58. The method of claim 1, wherein the second processor is coupled to a memory that is about 32 Gigabytes and stores portions of the database.

59. The method of claim 1, wherein the second processor is coupled to a memory that is about 16 Gigabytes and stores portions of the database.

10. A system configured to process database queries, said system comprising:

a host system running a database management system (DBMS) configured to process queries on information in a database and running a storage engine configured to determine a query plan for the queries based on a set of query fragments, compile at least some of the query fragments query plan into machine code database instructions, and orchestrate execution of the query fragments to determine a result; and

a custom computing module, coupled to the host system, comprising a set of dataflow processing elements that are configured to execute the machine code database instructions to access information in the database and return a result to the host system and a memory capable of storing gigabyte portions of the database.

11. The system of claim 10, wherein the set of dataflow processing elements comprise at least one of a task processor, a scanning processor, a XCAM processor, and an indexing processor.

12. The system of claim 10, wherein the custom computing module is programmable by machine code database instructions.

13. The system of claim 10, wherein the custom computing module is programmable based on at least one Application Specific Integrated Circuit (ASIC).

14. The system of claim 10, wherein the custom computing module addresses the database using a global virtual address space that maps to physical addresses in memory in the host system, addresses in storage holding the database, and physical addresses in the memory of the custom computing module.

15. The system of claim 14, wherein the custom computing module uses a sub-global virtual address space that maps to physical addresses in memory in the host system and physical addresses in the memory of the custom computing module.

16. The system of claim 10, wherein the custom computing module is coupled to the host system via a Peripheral Component Interconnect Express connection.

17. The system of claim 10, wherein the database is configured as a column-store database, wherein data in the columns are compressed.

18. The system of claim 10 further comprising at least one additional custom computing module coupled to the host system.

19. The system of claim 10 further comprising at least one additional host system and custom computing module that are coupled to the host system and custom computing module in a federated structure.

26. The system of claim 10, wherein the custom computing module is coupled to the host system via a HyperTransport connection.

27. The system of claim 10, wherein the custom computing module comprises a memory of at least 256 Gigabytes.

28. The system of claim 10, wherein the custom computing module comprises a memory of about 16 Gigabytes.

29. The system of claim 10, wherein the custom computing module comprises a memory of about 32 Gigabytes.

30. The system of claim 10, wherein the memory is configured to hold a set of rows of the database in column-store format and wherein each row is identified by a unique pointer.

31. The system of claim 10, wherein the custom computing module comprises a set of reconfigurable processing elements that are programmed based on the machine code database instructions.

32. The system of claim 10, wherein the custom computing module is integrated into a single package with the host system.

33. The system of claim 10, wherein the custom computing module is configured as a memory module that is coupled to the host system.

20. A method of processing queries using hardware acceleration for at least some portion of the queries, said method comprising:

receiving a query on information in a database;

parsing the query into a set of query fragments;

compiling at least some of the query fragments into machine code instructions;

transferring the machine code instructions from a host processor to at least one query co-processor;

executing the machine code instructions in the at least one query co-processor; and

determining a result for the query based on the query fragment results.

34. The method of claim 20, wherein the query co-processor is configured to execute the machine code database instructions in a parallel and pipelined dataflow fashion.

35. The method of claim 20, wherein the database is stored in compressed, column-store format and the query co-processor is configured to execute the machine code database instructions directly on data in the database in compressed, column-store format.

36. The method of claim 20, wherein the machine code instructions comprise macro-operations that perform a fundamental database operation.

37. The method of claim 20, wherein the macro-operations comprise one or more micro-operations that perform data manipulation for the respective database operation of their macro-operations.

38. The method of claim 20, wherein the database is configured in column-store format having column groups of fixed width.

39. The method of claim 20, wherein the database is mapped to a global virtual address space that can be mapped to storage holding the database, a first memory coupled to the first processor, and a second memory coupled to the query co-processor.

40. The method of claim 20, wherein records of the database are identified by a unique pointer.

41. The method of claim 20, wherein determining results for the query on information is based on a forward index in a first column that indicates corresponding rows of a primary key in a second column.

42. The method of claim 20, wherein determining results for the query on information is based on a reverse index that indicates corresponding rows of a foreign key in a second column.

43. The method of claim 20, wherein determining results for the query on information is based on a group index that indexes values in a column that are part of a group.

44. The method of claim 43, wherein determining results for the query on information is based on the group index accompanied with replicated columns that have been reordered according to the group index.

45. A system configured to process database queries, said system comprising:

a custom computing hardware module comprising a set of reconfigurable dataflow processing elements that are configured to execute machine code database instructions to access information from a portion of a database stored in a memory and return a result; and

a host system comprising;

a database management system (DBMS) configured to process queries on information in the database; and

a middleware application, coupled to the DBMS, configured to determine a query plan for the queries, compile at least some parts of the queries into machine code database instructions, schedule execution of parts of the queries in the custom computing hardware module, and provide the results to the DBMS.

46. The system of claim 45, wherein the custom computing hardware module comprises a memory of at least 256 Gigabytes.

47. The system of claim 45, wherein the custom computing hardware module comprises a memory of about 32 Gigabytes.

48. The system of claim 45, wherein the custom computing hardware module comprises a memory of about 16 Gigabytes.

49. The system of claim 45, wherein the custom computing hardware module comprises a set of processing elements having field programmable gate array logic.

50. The system of claim 45, wherein the custom computing hardware module comprises a set of processing elements having Application Specific Integrated Circuitry.

51. The system of claim 45, wherein the custom computing hardware module is configured as a memory module of the host system.

52. The system of claim 45, wherein the custom computing hardware module is coupled to the host system via a Peripheral Component Interconnection Express connection.

53. The system of claim 45, wherein the custom computing hardware module is coupled to the host system via a HyperTransport connection.

54. The system of claim 45, wherein the host system comprises a set of device drivers corresponding to the custom computing hardware module.

55. The system of claim 45, wherein the host system is configured to be coupled to a plurality of custom computing hardware modules.

56. The system of claim 45, wherein the host system is configured to comprise a MySQL DBMS.

57. The system of claim 54, wherein the middleware is configured to connect to the MySQL DBMS via a storage engine application programming interface.