Associative file processing method and apparatus

• US 4,464,718 A
• Filed: 07/30/1982
• Issued: 08/07/1984
• Est. Priority Date: 07/30/1982
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Verdoorn, William G. Jr., Bandy, Peter B., Dixon, Jerry D., Farrell, Robert H., Merckel, Gerald U., Neely, Jack D., Schmitt, Stephen A.
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US06/404,200
• Time in Patent Office: 739 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/300
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method and apparatus for performing data base searches in which the host processor and main memory are free for other processing tasks between the time that the host processor requests the search until the search results are reported back to the host processor. To commence the search, an input/output controller communicates from the host processor to a record scan circuit values of a skip length, a key length and a data length. While data records are received serially from disk files, within each data record, a length of data equal to the specified skip length is initially skipped. Following this, a search argument is compared with a length of data specified by the key length value. This comparison operation is alternated with skipping of data specified by the data length value until the end of the record is reached or until a specified number of comparisons has taken place. The data record is stored as it is received from the files. If a successful comparison is found within a data record, either the entire data record or a specified portion thereof can be read back through the controller to the host processor.

Claims

1. A method for performing a search of data records comprising the steps of:

specifying values of a skip length, key length and data length and providing a search argument corresponding in length to said key length;

providing a serial stream of data from a file having data records to be searched commencing from a predetermined location in said file; and

for each data record received from said file, performing a comparison operation by skipping an initial length of said data of said record from the beginning of said record with said initial length being determined by said skip length, and subsequently repetitively and alternatingly comparing said search argument with a key field of said data having a length specified by said key length and skipping a next succeeding data field of said data having a length specified by said data length.

2. The method of claim 1, further comprising the steps of:

providing an indication if a favorable comparison has occurred between said search argument and a key field of said record during said comparing; and

scanning a next succeeding data record if no favorable comparison occurs.

3. The method of claim 2, further comprising the step of specifying a type of comparison to be made between said search argument and said key fields of said record.

4. The method of claim 3, where said type of comparison is selected from among =, ≠

, ≧

, ≦

, > and

<

.

5. The method of any one of claims 1-4, further comprising the steps of:

storing each data record as it is received from said file; and

transferring at least a predetermined portion of said data record to utilization means if a successful comparison has occurred.

6. The method of claim 1, wherein said step of comparing said search argument with said key fields of said record comprises serially comparing bit-by-bit data that is received from said file with correspondingly ordered bits of said search argument in said key fields.

7. The method of claim 1, further comprising the step of supplying a value of a key number representing a number of key fields to be scanned in each said record, and skipping data in each said record following scanning therein of a number of key fields equal to said key number.

8. The method of claim 1, further comprising the steps of:

storing said search argument in a memory; and

in each said key field, sequentially addressing said memory to read out and compare bytes of said search argument with corresponding bytes of said key field.

9. The method of claim 8, further comprising the steps of:

comparing addresses to said memory with said key length value; and

switching from an operation of comparing said search argument with said key field to an operation of skipping a next succeeding data field when an address to said memory bears a predetermined relationship to said key length value.

10. The method of claim 9, further comprising the steps of:

in each said data field, counting a number of bytes of data received from said file;

comparing the count of said number of bytes of data received from said file with said data length value; and

switching from an operation of counting said number of bytes of data received from said file in said data field to an operation of comparing said search argument with data in a next succeeding key field when said count of said number of bytes of data received from said file in said data field bears a predetermined relationship to said data length value.

11. The method of claim 10, wherein said step of sequentially addressing said memory in said key fields and said step of counting said bytes of data received from said file in said data fields are performed by a single counter.

12. The method of claim 11, further comprising the steps of:

storing said key length value and said data length value in respective first and second registers;

rotating data among said first and second registers and a third register upon either of said steps of switching such that said key length value is in said second register for key fields and said data length value is in said second register for data fields; and

wherein said steps of comparing addresses to said memory with said key length value and comparing the count of said number of bytes of data received from said file with said data length value comprise comparing a content of said second register with an output of said counter.

13. A method for performing a search of data records received from a file comprising the steps of:

(a) specifying values of a skip length, a key length, a data length and a key number, providing a search argument corresponding in length to said key length, and specifying a type of comparison operation to be performed;

(b) providing a serial stream of data from said file commencing from a predetermined location, wherein data is supplied serially from said file for a plurality of successive records to be scanned;

(c) counting bytes of data received from said file in each said data record until a number of bytes corresponding to said skip length has been reached;

(d) serially comparing said search argument with data in said record while counting a number of bytes of data received from said file until the number of bytes received is equal said key length;

(e) changing a count of a number of key fields scanned in said data record;

(f) counting a number of bytes received from said file until a number of bytes received is equal to said data length;

(g) repeating said steps (d), (e) and (f) until said count of said number of key fields reaches said key number or until an end of said record is reached; and

(h) if at any time during said step (d) a successful comparison is found, providing a signal indicating that said successful comparison has occurred.

14. The method of claim 13, further comprising the step of storing said data as it is received from said file.

15. The method of claim 13, wherein said step (d) of comparing said search argument with data received from said file comprises the steps of:

(i) receiving data from said file in a serial single bit stream;

(ii) supplying a first byte of said search argument of a predetermined length;

(iii) comparing a first bit of data received from said file after the start of said step (d) with a first order bit of said byte of said search argument;

(iv) simultaneously shifting said byte of said search argument and receiving a second bit of said data from said file;

(v) comparing said second bit of said data received from said file with a second order bit of said byte of said search argument;

(vi) continuing to receive serially bits of data from said file while simultaneously shifting said byte of said search argument and comparing bits of said data received from said file with like-ordered bits of said search argument until a last bit of said byte of said search argument is reached;

(vii) supplying a next succeeding byte of said search argument; and

(viii) repetitively performing steps (i) to (vii) until a number of bytes of data received from said file equal to said key length have been compared with bytes of said search argument.

16. The method of claim 15, further comprising the step of transferring at least a predetermined portion of said data record to utilization means if a successful comparison occurs in said step (d).

17. An apparatus for performing a search of data records comprising:

means for specifying values of a skip length, a key length, a data length and a search argument corresponding in length to said key length;

means for providing a serial stream of data from a file storing data records to be searched commencing from a predetermined location in said file;

means for skipping an initial length of said data of said record from the beginning of said record with said initial length being determined by said skip length;

means for comparing said search argument with a key field of said data having a length specified by said key length; and

means for skipping a next succeeding data field of said data having a length specified by said data length.

18. The apparatus of claim 17, further comprising:

means for providing an indication if a favorable comparison has occurred between said search argument and a key field of said record during comparison of said search argument with said key field.

19. The apparatus of claim 17, wherein said means for comparing said search argument with said key fields of said record comprises means for serially comparing bit-by-bit data that is received from said file with correspondingly ordered bits of said search argument in said key fields.

20. The apparatus of claim 17, further comprising:

means for supplying a value of a key number representing a number of key fields to be scanned in each said record; and

means for skipping data in each said record following scanning therein of a number of key fields equal to said key number.

21. The apparatus of claim 17, further comprising:

memory means for storing said search argument; and

means for sequentially addressing said memory means to read out bytes of said search argument to said means for comparing said search argument with said key field.

22. The apparatus of claim 21, further comprising:

means for comparing addresses to said memory with said key length value; and

means for switching from a first operation of comparing said search argument with said key field to a second operation of skipping a next succeeding data field when an address to said memory bears a predetermined relationship to said key length value.

23. The apparatus of claim 22, further comprising:

means for counting a number of bytes of data received from said file in each said data field;

means for comparing the count of said number of bytes of data received from said file with said data length value; and

means for switching from said second operation to said first operation when said count of said number of bytes of data received from said file in said data field bears a predetermined relationship to said data length value.

24. The apparatus of claim 23, wherein said means for sequentially addressing said memory in said key fields and said means for counting said bytes of data received from said file in said data fields comprise a single counter.

25. The apparatus of claim 24, further comprising:

first and second register means for storing said key length value and said data length value, respectively;

a third register; and

means for rotating data among said first and second registers and said third register upon switching from said first operation to said second operation and upon switching from said second operation to said first operation such that said key length value is in said second register for key fields and said data length value is in said second register for data fields.

26. The apparatus of claim 25, wherein said means for comparing addresses to said memory with said key length value and said means for comparing the count of said number of bytes of data received from said file with said data length value together comprise means for comparing a content of said second register with an output of said counter.

27. A computer system in which scanning of data records stored on disk files is performed outside of a host central processing unit, comprising:

a first central processing unit and a main memory coupled to said first central processing unit;

an input/output controller connected to an input/output bus of said first central processing unit;

at least one disk file and a control unit for operating said disk file coupled to an input/output bus of said input/output controller; and

a record scan circuit coupled to said input/output bus of said input/output controller and coupled to said at least one disk file for receiving data serially from said disk file starting at a predetermined location where scanning of data records is to be commenced, said record scan circuit comprising;

a key number register;

a data length register;

a key length register;

a skip length register;

a key storage memory, said key number register, said data length register, said key length register, said skip length register and said key storage memory being coupled to said input/output controller to be preset by said input/output controller through said input/output bus with values corresponding to a key number, data length, key length, skip length and a search argument, respectively;

a key number counter receiving a preset input from said key number register;

a key address counter receiving a preset input from said skip length register, an output of said key address counter addressing said key storage memory;

a data storage memory;

a data address counter having an output addressing said data storage memory;

first buffer means receiving bytes of data from said key storage memory;

shift register means receiving a preset input from said first buffer means on all bits thereof except for a lowest order bit, said shift register means receiving at said lowest order bit a serial stream of data from said data file;

second buffer means receiving data from said shift register means from all but a highest order bit thereof, an output of said second buffer means being coupled to a data input of said data storage means;

data comparing means for comparing said lowest order bit and said highest order bit of said shift register means; and

means for controlling said records scan circuit such that each data record received from said disk file is divided into an initial skip field and alternating key fields and data fields, the length of said skip field being determined by said skip length value stored in said skip length register, the length of said key fields being determined by said key length value stored in said key length register, the length of said data fields being determined by said data length value stored in said data length register, and the number of said key fields being determined by said key number value stored in said key number register, wherein, for each said data record received from said data file, said skip field is skipped, said search argument stored in said key storage memory is compared bit-by-bit with said key field by said data comparing means, and each said data field is skipped.

28. The computer system of claim 27, further comprising:

a temporary register, said temporary register, said data length register and said key register being coupled together in a re-circulating loop; and

address comparing means for comparing the output from said address counter with a content of said key length register; and

wherein said controlling means comprises means for circulating contents among said temporary register, said data length register and said key length register in response to an output from said address comparing means such that, for key fields, the content of said key length register is said key length, and for data fields, said content of said key length register is said data length.

29. The computer system of claim 28, wherein said key address counter and said data address counter are reset to a zero condition by said input/output controller through said input/output bus of said input/output controller at the beginning of a record scanning operation.