QUERYING INPUT DATA

• US 20160098450A1
• Filed: 09/23/2015
• Published: 04/07/2016
• Est. Priority Date: 10/03/2014
• Status: Active Grant

• Current Assignee: Board of Regents of the University of Michigan (University of Michigan)
• Original Assignee: Board of Regents of the University of Michigan (University of Michigan)
• Inventors: TANDON, Prateek, WENISCH, Thomas Friedrich, CAFARELLA, Michael John
• Granted Patent: US 10,496,642 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/2455 Query execution

Abstract

A hardware accelerator 2 for performing queries into, for example, an indexed text log files is formed of plurality of hardware execution units (text engines) 4, each executing a partial query program upon the same full set of input data. These partial query programs may switch between different query algorithms on up to a per-character basis. The sequence of data when loaded into a buffer memory 16 for querying may be searched for delimiters as the data is loaded. The hardware execution units may support a number match program instruction which serves to identify a numeric variable, and to determine a value of that numeric variable located at a variable position within a sequence of characters being queried.

Claims

1. A method of processing data comprising the steps of:

receiving a query specifying a query operation to be performed upon a set of input data;

generating a plurality of partial query programs each corresponding to a portion of said query operation; and

executing each of said plurality of partial query programs with all of said set of said input data as an input to each of said plurality of partial query programs.

2. A method as claimed in claim 1, wherein said step of executing executes each of said plurality of partial programs with one of a plurality of programmable hardware execution units.

3. A method as claimed in claim 1, wherein said input data is an unindexed sequence of character data.

4. A method as claimed in claim 1, comprising the step of aggregating a plurality of partial results resulting from respective ones of said partial query programs to form an aggregated result corresponding to a result of said query.

5. A method as claimed in claim 4, wherein said step of aggregating is performed as a single process upon said plurality of partial results.

6. A method of processing data comprising the steps of:

receiving a query specifying a query operation to be performed upon input data;

programming one or more hardware execution units to perform said query, wherein

said step of programming programs said one or more hardware execution units to use selected ones of a plurality of different query algorithms to perform different portions of said query operation upon different portions of said input data.

7. A method as claimed in claim 6, wherein said plurality of different algorithms comprise one or more of:

a per-character pattern matching algorithm using a character matching state machine representing a query operation to be performed with each sequence of one or more characters within a sequence of characters to be queried determining a transition between two states of said character matching state machine and each state within said character matching state machine corresponding a given sequence of received characters; and

a per-bit pattern matching algorithm using a plurality of bit matching state machines representing a query operation to be performed with each bit of each character within said sequence of characters to be queried determining a transition between two states of one said plurality of bit matching state machines and each state within said bit matching state machine corresponding a bit within one or more sequences of received characters; and

a content addressable memory based algorithm using a content addressable memory storing a plurality of target character sequences to be compared in parallel with one or more characters of a received sequence of characters.

8. A method as claimed in claim 6, wherein said one of more hardware execution units each comprise hardware circuits for performing any one of said plurality of different query algorithms.

9. A method as claimed in claim 6, wherein said step of programming selects which one of said plurality of different query algorithms to use on a per-character basis within a sequence of characters to be queried.

10. A method as claimed in claim 6, wherein said step of programming selects which of said plurality of different query algorithms to use so as to target one or more of:

a programming storage requirement limit of said one or more hardware execution units;

a processing time limit; and

a hardware resources limit of said one or more hardware execution units.

11. Apparatus for processing data comprising:

a memory to store a sequence of data to be queried;

delimiter identifying circuitry to identify data delimiters between portions of said sequence of data as said data is stored to said memory; and

a delimiter store to store storage locations of said data delimiters within said memory.

12. Apparatus as claimed in claim 11, comprising a plurality of hardware execution units to query said sequence of data stored within said memory, wherein said plurality of hardware execution units are free to query respective different portions of said sequence of data at a given time.

13. Apparatus as claimed in claim 12, wherein when a given one of said plurality of hardware execution units determines it has completed querying a portion of said sequence of data, a read of said delimiter store identifies a start of a next portion of said sequence of data to be queried by said given one of said plurality of hardware execution units.

14. Apparatus as claimed in claim 12, wherein said sequence of data stored within said memory is a part of a larger sequence of data and comprising management circuitry to manage which part of said larger sequence of data is stored within said memory at a given time, said management circuitry maintaining a pointer into said memory for each of said plurality of hardware execution units and including a head pointer to indicate a latest point within said larger sequence stored in said memory and a tail pointer to indicate an earliest point within said larger sequence already loaded to said memory for which processing by said plurality of hardware execution units is not yet completed, said management circuitry using said head pointer and said tail pointer to control loading data to said memory and removing data from said memory.

15. Apparatus as claimed in claim 11, wherein said data delimiters identify variable boundary locations between portions of said sequence of data to be separately queried.

16. Apparatus for processing data comprising:

programmable processing hardware responsive to a number match program instruction to identify a numeric variable and to determine a value of said numeric variable located at a variable position within a sequence of characters.

17. Apparatus as claimed in claim 16, wherein said numeric variable is one of:

an integer value;

a floating point value; and

a date value.

18. Apparatus as claimed in claim 16, wherein said programmable processing hardware is programmable to perform a query operation upon an unindexed sequence of character data.

19. Apparatus as claimed in claim 16, wherein an output of said number match program instruction comprises said number value stored within a register specified by said number match program instruction.

20. Apparatus as claimed in claim 16, comprising a plurality of instances of said programmable processing hardware to perform respective portions of a query upon said sequence of characters.