Processing elements of a hardware accelerated reconfigurable processor for accelerating database operations and queries

• US 20080189251A1
• Filed: 08/27/2007
• Published: 08/07/2008
• Est. Priority Date: 08/25/2006
• Status: Abandoned Application

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradata US, Inc. (Teradata Corporation)
• Inventors: Chamdani, Joseph I., Yang, Liuxi, Shau, James, Krishnamurthy, Ravi, Corwin, Michael, Branscome, Jeremy
• Application Number:
  US11/895,997
• Publication Number:
  US 20080189251A1
• 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 processing elements that are capable of performing high level database operations in hardware based on machine code instructions. These processing elements employ a dataflow architecture that operates on data in hardware without interruption or software. A scanning/indexing processing element may comprise logic that analyze database column groups stored in local memory, perform parallel field extraction and comparison, and generates a list of row pointers (row ids or RIDs) referencing those rows whose value(s) satisfy an applied predicate. The scanning/indexing processing may also be used to project database column groups, search and join index structures, and manipulate in-flight metadata flows, composing, merging, reducing, and modifying multi-dimensional lists of intermediate and final results. Furthermore, a scanning/indexing processing element may be used for joins with indexes, like a Group Index, which involves the association of each input tuple with potentially many related data components, in a one-to-many mapping. An XCAM processing element may comprise logic to perform associative database operations, like accumulation and aggregation, sieving, sorting and associative joins.

Claims

1. A scanning processing element configured to scan a dataflow of data from a column of a database, based on a set of machine code database instructions, said processing element comprising:

an interface to a memory holding at least a portion of the database;

an interface configured to receive machine code database instructions;

logic, configured to process a dataflow based on the machine code database instructions, for scanning and extracting data, determining whether data satisfies a given predicate, and emitting a result; and

logic for emitting the result to a communication data structure.

2. (canceled)

3. A processing element configured to index a dataflow of data from a column of a database, based on a set of machine code database instructions, said processing element comprising:

an interface to a memory holding at least a portion of the database;

an interface configured to receive machine code database instructions; and

logic, configured by the machine code database instructions, for composing tuples from a set of columns in the database, projection data into columns, selection of one or more tuples for row reduction, list selection of variables over a column pair, and for emitting a result to a communication data structure.

4. An associative processing element comprising:

an interface to a memory holding at least a portion of the database;

an interface configured to receive machine code database instructions; and

logic, configured by the machine code database instructions, for concatenating key fragments into a group key and associating keys with a result, aggregating information in the database based on accessing the memory, aggregating and sorting results, gathering sieved results, for providing results to a communication data structure.

5. A scanning processing element comprising:

an interface to a memory holding at least a portion of a database;

an input for receiving a dataflow of values retrieved from the memory; and

an output, coupled to the input, for emitting a dataflow of results for a scan comparing the values to a predicate based on a program having at least one machine code database instruction.

6. The scanning processing element of claim 5, further comprising reconfigurable logic coupled to the input and the output and configured to scan a set of pointers and data from the portion of the database in memory against a predicate specified in the program.

7. The scanning processing element of claim 6, wherein the reconfigurable logic comprises a cache for holding a series of machine code database instructions that are executed in multi-threaded fashion.

8. The scanning processing element of claim 6, wherein the reconfigurable logic comprises a plurality of distinct stages for a database operation.

9. The scanning processing element of claim 8, wherein the reconfigurable logic comprises a stage for a fetch database operation.

10. The scanning processing element of claim 8, wherein the reconfigurable logic comprises a stage for a format database operation.

11. The scanning processing element of claim 8, wherein the reconfigurable logic comprises a stage for a join database operation.

12. The scanning processing element of claim 8, wherein the reconfigurable logic comprises a stage for executing machine code instructions that process tuples in the dataflow.

13. The scanning processing element of claim 8, wherein the reconfigurable logic comprises a stage for providing a result.

14. The scanning processing element of claim 5, wherein the output is configured to emit a dataflow of a scan of contiguous rows in the portion of the database in the memory based on the program.

15. The scanning processing element of claim 5, wherein the output is configured to emit a dataflow of a nested-loop cross-product join of two columns in the portion of the database based on the program.

16. The scanning processing element of claim 5, wherein the output is configured to emit a dataflow of an index-based nested join of columns in the portion of the database based on the program.

17. The scanning processing element of claim 5, wherein the output is configured to emit a dataflow of scans of a dispersed subset of rows in a column of the portion of the database based on the program.

18. The scanning processing element of claim 5, wherein the memory is configured to hold a column of the database in column-store format.

19. The scanning processing element of claim 5, wherein the memory is configured to hold a group of columns of the database in column-store format.

20. The scanning processing element of claim 5, 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.

21. The scanning processing element of claim 5, wherein the input is configured to receive the dataflow in a numbered communications channel.

22. The scanning processing element of claim 5, wherein the output is configured to emit the dataflow to a numbered communications channel.

23. An indexing processing element comprising:

an interface to a memory holding at least a portion of a database;

an input for receiving a dataflow of values retrieved from the memory; and

an output, coupled to the input, for emitting a dataflow of results for database index operations based on a program having at least one machine code database instruction.

24. The indexing processing element of claim 23, further comprising reconfigurable logic coupled to the input and the output and configured to traverse an index of data from the portion of the database in memory against a set of predicates specified in the program.

25. The indexing processing element of claim 24, wherein the reconfigurable logic comprises a cache for holding a series of machine code database instructions that are executed in multi-threaded fashion.

26. The indexing processing element of claim 24, wherein the processing element is 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.

27. The indexing processing element of claim 23, wherein the memory is configured to hold a column of the database in column-store format.

28. The indexing processing element of claim 23, wherein the memory is configured to hold a group of columns of the database in column-store format.

29. The indexing processing element of claim 23, 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.

30. The indexing processing element of claim 23, wherein the input is configured to receive the dataflow in at least one numbered communications channel.

31. The indexing processing element of claim 23, wherein the output is configured to emit the dataflow to a numbered communications channel.

32. An indexing processing element comprising:

an interface to a memory;

an input for receiving a dataflow of values retrieved from the memory; and

an output, coupled to the input, for emitting a dataflow of results for database list operations based on a program of at least one machine code database instruction.

33. The indexing processing element of claim 32, further comprising reconfigurable logic coupled to the input and the output and configured to collect items from the dataflow of data from the portion of the database in memory against at least one predicate specified in the program.

34. The indexing processing element of claim 33, wherein the reconfigurable logic comprises a cache for holding a series of machine code database instructions that are executed in multi-threaded fashion.

35. The indexing processing element of claim 32, wherein the output is configured to emit a two dimensional list composed of a set of input lists that are horizontally correlated based on the program.

36. The indexing processing element of claim 32, wherein the output is configured to emit an inner-loop cross-product nested join of lists against a predicate specifying one or more columns based on the program.

37. The indexing processing element of claim 32, wherein the output is configured to emit a vertical merger of two lists from the portion of the database based on the program.

38. The indexing processing element of claim 32, wherein the output is configured to emit a dataflow of tuples from the portion of the database selected against at least one column predicate based on the program.

39. The indexing processing element of claim 32, wherein the output is configured to emit a dataflow of arithmetic results performed on at least one list based on the program.

40. The indexing processing element of claim 32, wherein the memory is configured to hold a column of the database in column-store format.

41. The indexing processing element of claim 32, wherein the memory is configured to hold a group of columns of the database in column-store format.

42. The indexing processing element of claim 32, 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.

43. The indexing processing element of claim 32, wherein the input is configured to receive the dataflow in at least one numbered communications channel.

44. The indexing processing element of claim 32, wherein the output is configured to emit the dataflow to a numbered communications channel.

45. An associative processing element comprising:

an read/write interface to a memory holding at least a portion of a database;

an input for receiving a dataflow of values retrieved from the memory; and

an output, coupled to the input, for emitting a dataflow of results for operations that are based on an associative key based on a program of at least one machine code database instruction.

46. The associative processing element of claim 45, further comprising reconfigurable logic coupled to the input and the output and configured to perform value-based database operations on the dataflow of data from the portion of the database in memory specified in the program.

47. The associative processing element of claim 45, wherein the reconfigurable logic comprises a cache for holding a series of machine code database instructions that are executed in multi-threaded fashion.

48. The associative processing element of claim 45, wherein the input is configured to receive the dataflow in at least one numbered communications channel.

49. The associative processing element of claim 45, wherein the output is configured to emit the dataflow to a numbered communications channel.

50. The associative processing element of claim 45, wherein the output is configured to emit the dataflow to locations in the memory based on the associative key.

51. The associative processing element of claim 45, wherein the output is configured to emit a dataflow a histogram of like keys found in an input list of the dataflow using a specified mapping from the program.

52. The associative processing element of claim 45, wherein the output is configured to emit a dataflow of reordered tuples in a 2-dimensional input list of two columns from the dataflow such that extreme N keys occur in the final N tuple rows, contiguously based on the program.

53. The associative processing element of claim 45, wherein the output is configured to emit a dataflow of an aggregation function performed on the dataflow based on the program.

54. The associative processing element of claim 45, wherein the output is configured to emit results to locations of a memory based on the associative key for an aggregation function performed on the dataflow based on the program.

55. The associative processing element of claim 45, wherein the memory is configured to hold a column of the database in column-store format.

56. The associative processing element of claim 45, wherein the memory is configured to hold a group of columns of the database in column-store format.

57. The associative processing element of claim 45, 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.

58. The associative processing element of claim 45, wherein the output is configured to distribute results to locations of a memory based on the associate key for a write function performed on the dataflow based on the program.