System for iterated generation from an array of records of a posting file with row segments based on column entry value ranges

• US 5,367,677 A
• Filed: 07/21/1993
• Issued: 11/22/1994
• Est. Priority Date: 05/11/1990
• Status: Expired due to Fees

• Current Assignee: TM Patents LP
• Original Assignee: Thinking Machines Corporation (Oracle Corporation)
• Inventors: Stanfill, Craig W.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/096,192
• Time in Patent Office: 489 Days
• Field of Search: 395/600, 395/725, 395/800, 340/146.2
• US Class Current: 707/700
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A query processing system for processing queries in connection with a document text base which has entries each identifying a document and a word in the document. The query processing system includes a plurality of processing elements for processing data in response to commands, and a control arrangement for controlling the processing elements in parallel. The control arrangement first enables the processing elements to generate a segmented posting file having entries, at least some of which have a word identifier and a document identifier. The entries form an array all of whose entries with the same document identifier are contained within one column. The rows of the segmented posting file are aggregated into segments each having a selected number of rows with each segment containing entries having word identifiers within an identified word identifier range. Thereafter, the control arrangement enables the processing elements to use the segmented posting file to process, in parallel, a query in a series of iterations each with respect to a query word. In each iteration, the processing elements receive respective portions of columns comprising a segment of the segmented posting file associated with the word identifier range containing the query word, then identify entries in the segment whose word identifiers correspond to the query word, and finally modify a score maintained for the document identified in the identified entry. Those documents which have a selected score at the end of the series of iterations have the required relationship to the query.

Claims

1. A segmented posting file generating system for generating a segmented posting file in response to a record base comprising a plurality of the record base entries represented by an array comprising a plurality of columns and rows, the entries within each column having an order according to their respective word identifiers, the segmented posting file generating system generating said segmented posting file in a series of segment generation iteration, the segmented posting file generating system comprising:

A. a computer for performing processing operations in response to commands;

B. a segmented posting file generation control including;

i. a segment word value identifier determination portion for providing commands to enable said computer to

(a) select, for each segment generation iteration, an entry in each column of said record base as a segment word value determiner entry, and

(b) identify as a segment word value identifier range value a value having a selected value relation to the word identifier values in the segment word value determiner entries; and

ii. a segment establishment portion for, during each segment generation iteration, providing commands to enable said computer to generate a series of rows of the segmented posting file in each of a series of segment row generation iterations, the commands enabling the computer to, for each column of the record base

(a) determined whether, a record base entry of the column of the record base contains a word identifier having a value having a selected relation to the segment word identifier determination value and

(b) in response to a positive determination, copy the entry in the record base to the entry in a corresponding column of the segmented posting file and select the next entry of the record base for the next segment row generation iteration.

2. A segmented posting file generating system as defined in claim 1 in which the number of rows in a segment in the segmented posting file corresponds to a segment size factor,

A. the segmented posting file generation control further including a record base entry identifier establishment portion for providing commands to enable said computer to establish a record base entry identifier for each column of the record base, and a segment entry pointer establishment portion for providing commands to enable said computer to establish a segment entry pointer;

B. the segment word value identifier determination portion providing commands to enable said computer to use the record base entry identifiers for the columns of the record base to select from each column of the record base a record base entry as the segment determiner entry, the segment word identifier determination portion further providing commands to enable the computer to identify as a segment word identifier determiner value the minimum of the word identifier values in the segment determiner entries; and

C. the segment establishment portion providing commands to enable said computer during each iteration to use the segment entry pointer to establish each successive row in a segment of said segmented posting file.

3. A segmented posting file generating system as defined in claim 2 in which, for each segment generation iteration, the segment word value identifier determination portion generates commands to enable said computer to use, as the segment word value determiner entry for each column, a record base entry identified by the sum of the record base entry identifier for the column and the segment size factor.

4. A query processing system for processing queries in connection with a record base including a plurality of record base entries each of which includes a record identifier and a word identifier, each query containing at least one query word, the query processing system identifying records having a selected relationship between the query and the word identifiers contained in the record base, said query processing system comprising:

A. a plurality of processing elements, each for performing processing operations in response to commands;

B. a control arrangement including;

i. a segmented posting file generation control portion for providing commands to enable said processing elements to generate, in response to said record base, a segmented posting file, said segmented posting file having a plurality of segmented posting file entries, at least some of said segmented posting file entries having a word identifier and a record identifier, said segmented posting file entries being represented by an array comprising a plurality of columns and rows, said rows being aggregated into segments each having a selected number of rows with each segment containing entries having word identifiers within an identified word identifier range, the segmented posting file generation control portion generating commands so as to enable said processing elements to generate the columns of said segmented posting file in parallel; and

ii. a query processing control portion for providing, in a series of iterations each with respect to a query word in the query, commands to enable said processing elements to, in parallel;

(a) receive respective portions of columns comprising a segment of the segmented posting file associated with the word identifier range containing the query word, each processing element receiving said portion of one of said columns,

(b) identify entries in the segment whose word identifiers correspond to the query word, and

(c) modify a score maintained for the record identified in the identified entry,

the records having a selected score at the end of the series of iterations being determined to have the selected relationship to the query.

5. A query processing system as defined in claim 4 further comprising a mass storage system for storing data, said mass storage system being connected to said processing elements and said control arrangement,

A. said segmented posting file generation control portion enabling said processing elements to transfer said segmented posting file to said mass storage system for storage, and

B. said query processing control portion enabling said mass storage system to, during each iteration, transfer the segment of said segmented posting file associated with the query word to said processing elements.

6. A query processing system as defined in claim 4 in which, in said record base, the record base entries are represented by an array comprising a plurality of columns and rows, the entries within each column having an order according to their respective word identifiers, the segmented posting file generation control portion enabling said processing elements to establish the segmented posting file in response to the record base in a series of segment generation iterations, the segmented posting file generation control portion including:

A. segment word value identifier determination portion for providing commands to enable said processing elements to, in parallel,

i. select for the segment generation iteration a record base entry in respective associated columns of said record base as a segment word value determiner entry, and

ii. identify as a segment word value identifier range value a value having a selected value relation to the word identifier values in the segment word value determiner entries of all of said processing elements; and

B. a segment establishment portion for, during each of said segment generation iterations, providing commands to enable said processing elements to, in parallel, generate a series of rows of the segmented posting file in a series of segment row generation iterations, the commands during each segment row generation iteration enabling the processing elements to;

i. for each row of the segment, determine whether an a respective record base entry of the record base contains a word identifier having a value having a selected value relation to the segment word value identifier determination value and

ii. in response to a positive determination, copy the record base entry to the segmented posting file entry of the segmented posting file and selecting the next record base entry of the record base for the next segment row generation iteration.

7. A query processing system as defined in claim 6 in which the number of rows in a segment in the segmented posting file corresponds to a segment size factor,

A. the segmented posting file generation control portion further including a record base entry identifier establishment portion for providing commands to enable said processing elements to, in parallel, establish respective record base entry identifiers, and a segment entry pointer establishment portion for providing commands to enable said processing elements to, in parallel, establish respective segment entry pointers;

B. the segment word value identifier determination portion for providing commands to enable said processing elements to, in parallel, use the respective record base entry identifiers in the selection of the segment word value determiner entry, the segment word value identifier determination portion further providing commands to enable the processing elements to identify as a segment word value identifier determiner value the minimum of the word identifier values in the segment word value determiner entry of all of said processing elements; and

C. the segment establishment portion provides commands to enable said processing elements during each segment row generation iteration to, in parallel, use the respective segment entry pointers to establish segmented posting file entries in each successive row in a segment of said segmented posting file.

8. A query processing system as defined in claim 7 further comprising a mass storage system for storing data and a host, both said mass storage system and said host being connected to said processing elements, said host generating storage control commands for controlling:

A. the transfer of said segmented posting file from said processing elements, after generation in response to commands provided by said segmented posting file generation control portion, to said mass storage system for storage; and

B. the transfer of segments of said segmented posting file from said mass storage system to said processing elements for processing in response to commands provided by said query processing control portion.

9. A query processing system as defined in claim 8 in which said host further operates in response to commands, said segmented posting file generation control portion further providing commands for enabling said host to establish a host segmented posting file portion having a plurality of entries each associated with a segment of said segmented posting file and identifying for the associated segment the range of word identifier values of the entries in the segment.

10. A query processing system as defined in claim 9 in which the query processing control portion further provides commands to said host to enable it to, for each word of the query, use the host segmented posting file portion to identify a segment which contains word identifier values corresponding to the word of the query, the host enabling the identified segment to be transferred from the mass storage system to the processing elements.

11. A query processing system as defined in claim 7 in which, for each segment generation iteration, the segment word value identifier determination portion generates commands to enable said processing elements to use, as their respective segment word value determiner entries, a record base entry identified by the sum of their respective record base entry identifiers and the segment size factor.

12. A query processing system as defined in claim 4 in which said query processing control portion includes:

A. a score table establishment portion for providing commands to enable said processing elements to, in parallel, establish a score table having a plurality of entries each for receiving a score, each score table entry being associated with a record identified in segmented posting file entries comprising a column of the segmented posting file associated with a respective processing element, and

B. a score processing portion for, in a series of score generation iterations each with respect to a query word of the query, generating commands to enable the processing elements to, in parallel;

i. receive respective segmented posting file entries of the associated columns comprising a segment of the segmented posting file associated with the word identifier range containing the query word, and

ii. iteratively identify segmented posting file entries in the segment whose word identifiers correspond to the query word and modify the score in the score table entry maintained for the record identified in the identified segmented posting file entry,

the records associated with score table entries containing a selected score at the end of the series of score generation iterations being determined to have the selected relationship to the query.

13. A query processing system as defined in claim 12 further comprising a mass storage system for storing data and a host, both said mass storage system and said host being connected to said processing elements, said host generating storage control commands for controlling the transfer of segments of said segmented posting file from said mass storage system to said processing elements for processing in response to commands provided by said query processing control portion.

14. A segmented posting file generating system for generating a segmented posting file in response to a record base comprising a plurality of record base entries represented by an array comprising a plurality of columns and rows, the entries within each column having an order according to their respective word identifiers, the segmented posting file generating system enabling said processing elements to establish the segmented posting file in response to the record base in a series of segment generation iterations, the segmented posting file generating system comprising:

A. a plurality of processing elements, each for performing processing operations in response to commands;

B. a segmented posting file generation control including;

i. a segment word value identifier determination portion for providing commands to enable said processing elements to, in parallel,

(a) select for an entry in said record base as a segment word value determiner entry, and

(b) identify as a segment word value identifier range value a value having a selected value relation to the word identifier values in the segment word value determiner entries of all of said processing elements; and

ii. a segment establishment portion for, during each of said segment generation iterations, providing commands to enable said processing elements to, in parallel, generate a series of rows of the segmented posting file in each of a series of segment row generation iterations, the commands enabling the processing elements to

(a) determine whether a record base entry of the record base contains a word identifier having a value having a selected value relation to the segment word value identifier determination value, and

(b) in response to a positive determination, copy the record base entry to the segmented posting file entry in the respective column of the segmented posting file and select the next entry of the record base for the next segment row generation iteration.

15. A segmented posting file generating system as defined in claim 14 in which the number of rows in a segment in the segmented posting file corresponds to a segment size factor,

A. the segmented posting file generation control further including a record base entry identifier establishment portion for providing commands to enable said processing elements to, in parallel, establish respective record base entry identifiers, and a segment entry pointer establishment portion for providing commands to enable said processing elements to, in parallel, establish respective entries in said segmented posting file;

B. the segment word value identifier determination portion providing commands to enable said processing elements to, in parallel, use their respective record base entry identifiers in the selection of the segment value determiner entry, the segment word value identifier determination portion further providing commands to enable the processing elements to identify as a segment word identifier determiner value the minimum of the word identifier values in the segment word value determiner entries of all of said processing elements; and

C. the segment establishment portion provides commands to enable said processing elements during each iteration to, in parallel, use their respective segment entry pointers to establish a segmented posting file entry in each successive row in a segment of said segmented posting file.

16. A segmented posting file generating system as defined in claim 15 in which, for each segment generation iteration, the segment word value identifier determination portion generates commands to enable said processing elements to use, as their respective segment word value determiner entries, a record base entry identified by the sum of their respective record base entry identifiers and the segment size factor.

17. A control arrangement for generating commands for controlling a plurality of processing elements to facilitate the processing of queries in connection with a record base including a plurality of record base entries each of which includes a record identifier and a word identifier, each query containing at least one query word, the query processing system identifying records having a selected relationship between the query and the word identifiers contained in the record base, said control arrangement including:

A. a segmented posting file generation control portion for providing commands to enable said processing elements to generate, in response to said record base, a segmented posting file, said segmented posting file having a plurality of segmented posting file entries, at least some of said segmented posting file entries having a word identifier and a record identifier, said segmented posting file entries being represented by an array comprising a plurality of columns and rows, said rows being aggregated into segments each having a selected number of rows with each segment containing segmented posting file entries having word identifiers within an identified word identifier range, the segmented posting file generation control portion generating commands so as to enable said processing elements to generate the columns of said segmented posting file in parallel; and

B. a query processing control portion for providing, in a series of iterations each with respect to a query word in the query, commands to enable said processing elements to, in parallel;

(i) receive respective portions of columns comprising a segment of the segmented posting file associated with the word identifier range containing the query word, each processing element receiving said portion of one of said columns,

(ii) identify entries in the segment whose word identifiers correspond to the query word, and

(iii) modify a score maintained for the record identified in the identified entry, records having a selected score at the end of the series of iterations being determined to have the selected relationship to the query.

18. A control arrangement as defined in claim 17 in which, in said record base, the record base entries are represented by an array comprising a plurality of columns and rows, the entries within each column having an order according to their respective word identifiers, the segmented posting file generation control portion enabling said processing elements to establish the segmented posting file in response to the record base in a series of segment generation iterations, the segmented posting file generation control portion including:

A. a segment word value identifier determination portion for providing commands to enable said processing elements to, in parallel,

i. select for the segment generation iteration a record base entry in respective associated columns of said record base as a segment word value determiner entry, and

ii. identify as a segment word value identifier range value a value having a selected value relation to the word identifier values in the segment word value determiner entries of all of said processing elements; and

B. a segment establishment portion for, during each of said segment generation iterations, providing commands to enable said processing elements to, in parallel, generate a series of rows of the segmented posting file in a series of segment row generation iterations, the commands enabling the processing elements to

i. for each row of the segment determine whether a respective record base entry of the record base contains a word identifier having a value having a selected value relation to the segment word value identifier determination value, and

ii. in response to a positive determination, copy the record base entry to the segmented posting file entry of the segmented posting file and select the next record base entry of the record base for the next segment row generation iteration.

19. A control arrangement as defined in claim 18 in which the number of rows in a segment in the segmented posting file corresponds to a segment size factor,

A. the segmented posting file generation control portion further including a record base entry identifier establishment portion for providing commands to enable said processing elements to, in parallel, establish respective record base entry identifiers, and a segment entry pointer establishment portion for providing commands to enable said processing elements to, in parallel, establish respective segment entry pointers;

B. the segment word value identifier determination portion for providing commands to enable said processing elements to, in parallel, use their respective record base entry identifiers in the selection of the segment word value determiner entry, the segment word value identifier determination portion further providing commands to enable the processing elements to identify as a segment word value identifier determiner value the minimum of the word identifier values in the segment word value determiner entries of all of said processing elements; and

C. the segment establishment portion provides commands to enable said processing elements during each iteration to, in parallel, use the respective segment entry pointers to establish segmented posting file entries in each successive row in a segment of said segmented posting file.

20. A control arrangement as defined in claim 19, in which the commands further control a mass storage system for storing data and a host, both said mass storage system and said host being connected to said processing elements, said control arrangement further including a storage control command generating portion for providing commands for controlling:

A. the transfer of said segmented posting file from said processing elements, after generation in response to commands provided by said segmented posting file generation control portion, to said mass storage system for storage; and

B. The transfer of segments of said segmented posting file from said mass storage system to said processing elements for processing in response to commands provided by said query processing control portion.

21. A control arrangement as defined in claim 20 in which said segmented posting file generation control portion further provides commands for enabling said host to establish a host segmented posting file portion having a plurality of entries each associated with a segment of said segmented posting file and identifying for the associated segment the range of word identifier values of the entries in the segment.

22. A control arrangement as defined in claim 21 in which the query processing control portion further provides commands to said host to enable it to, for each word of the query, use the host segmented posting file portion to identify a segment which contains word identifier values corresponding to the word of the query, the host enabling the identified segment to be transferred from the mass storage system to the processing elements.

23. A control arrangement as defined in claim 19 in which, for each segment generation iteration, the segment word value identifier determination portion generates commands to enable said processing elements to use, as their respective segment word value determiner entries, a record base entry identified by the sum of their respective record base entry identifiers and the segment size factor.

24. A control arrangement as defined in claim 17 in which said query processing control portion includes:

A. a score table establishment portion for providing commands to enable said processing elements to, in parallel, establish a score table having a plurality of entries each for receiving a score, each score table entry being associated with a record identified in segmented posting file entries comprising a column of the segmented posting file associated with a respective processing element; and

B. a score processing portion for, in a series of iterations each with respect to a query word of the query, generating commands to enable the processing elements to, in parallel;

i. receive respective segmented posting file entries of the associated columns comprising a segment of the segmented posting file associated with the word identifier range containing the query word, and

ii. iteratively identify segmented posting file entries in the segment whose word identifiers correspond to the query word and modify the score in the score table entry maintained for the record identified in the identified segmented posting file entry,

the records associated with score table entries containing a selected score at the end of the series of iterations being determined to have the selected relationship to the query.

25. A control arrangement as defined in claim 24 further including a storage control portion for providing storage control commands for controlling a mass storage system for storing data and a host, both said mass storage system and said host being connected to said processing elements, said storage control commands controlling the transfer of segments of said segmented posting file from said mass storage system to said processing elements for processing in response to commands provided by said query processing control portion.

26. A method of controlling a computer to process queries in connection with a record base including a plurality of record base entries each of which includes a record identifier and a word identifier, each query containing at least one query word, the query processing system identifying records having a selected relationship between the query and the word identifiers contained in the record base, said method comprising:

A. a segmented posting file generation step in which commands are provided to enable said computer to generate, in response to said record base, a segmented posting file, said segmented posting file having a plurality of segmented posting file entries, at least some of said segmented posting file entries having a word identifier and a record identifier, said segmented posting file entries being represented by an array comprising a plurality of columns and rows, said rows being aggregated into segments each having a selected number of rows with each segment containing entries having word identifiers within an identified word identifier range; and

B. a query processing step in which, in a series of iterations each with respect to a query word in the query, commands are provided to enable said computer to;

(i) receive respective portions of columns comprising a segment of the segmented posting file associated with the word identifier range containing the query word,

(ii) identify entries in the segment whose word identifiers correspond to the query word, and

(iii) modify a score maintained for the record identified in the identified entry,

records having a selected score at the end of the series of iterations being determined to have the selected relationship to the query.

27. A method as defined in claim 26 in which, in said record base, the record base entries are represented by an array comprising a plurality of columns and rows, each column of said record base having an associated column in said segmented posting file, the entries within each column of said record base having an order according to their respective word identifiers, during the segmented posting file generation step said computer establishing the segmented posting file in response to the record base in a series of segment generation iterations, the segmented posting file generation step including:

A. a segment word identifier determination step in which commands are provided to enable said computer to

i. select for the segment generation iteration a record base entry in said record base as a segment word value determiner entry, and

ii. identify as a segment word value identifier range value a value having a selected value relation to the word identifier values in the segment word value determiner entries; and

B. a segment establishment step in which commands are provided to enable said computer to generate a series of rows of the segmented posting file in a series of segment row generation iterations, the commands enabling the computer to

i. determine whether a record base entry of the record base contains a word identifier having a value having a selected value relation to the segment word value identifier determination value; and

ii. in response to a positive determination, copy the record base entry to an entry of the associated column of the segmented posting file and select the next record base entry of the record base for the next segment row generation iteration.

28. A method as defined in claim 27 in which the number of rows in a segment in the segmented posting file corresponds to a segment size factor,

A. the segmented posting file generation step further including a record base entry identifier establishment step during which commands are provided to enable said computer to establish for each column of said record base a record base entry identifier, and a segment entry pointer establishment step during which commands are provided to enable said computer to establish a segment entry pointer;

B. during the segment word value identifier determination step, providing commands to enable said computer to use the record base entry identifier in the selection of the segment word value determiner entry, and in addition providing commands to enable the computer to identify as a segment word value identifier determiner value the minimum of the word identifier values in the segment word value determiner entries; and

C. during the segment establishment step, providing commands to enable said computer during a series of segment row generation iteration to use the segment entry pointer to establish segmented posting file entries in successive rows in a segment of said segmented posting file.

29. A method as defined in claim 28 further for controlling a mass storage system for storing data, said mass storage system being connected to said computer, the method including a storage control step for providing:

A. commands to enable said computer to transfer of said segmented posting file after generation to said mass storage system for storage; and

B. the transfer of segments of said segmented posting file from said mass storage system to said computer for processing in response to commands provided during said query processing step.

30. A method as defined in claim 29 in which during, said segmented posting file generation step, commands are further provided for enabling said computer to establish a segmented posting file index portion having a plurality of entries each associated with a segment of said segmented posting file and identifying for the associated segment the range of word identifier values of the entries in the segment.

31. A method as defined in claim 30 in which, during the query processing step, commands are provided to enable said computer to, for each word of the query, use the segmented posting file index portion to identify a segment which contains word identifier values corresponding to the word of the query, the commands enabling the computer and mass storage system to transfer the identified segment from the mass storage system to the computer.

32. A method as defined in claim 28 in which, for each segment generation iteration, during the segment word value identifier determination portion commands are provided to enable said computer to use, as the segment word value determiner entry for each column, a record base entry identified by the sum of the record base entry identifier for the column and the segment size factor.

33. A method as defined in claim 26 in which said query processing step includes:

A. a score table establishment step during which commands are provided to enable said computer to establish a score table having a plurality of score table entries each for receiving a score, each score table entry being associated with a record identified in the segmented posting file, and

B. a score processing portion step during which, in a series of score generation iterations each with respect to a query word of the query, commands are provided to enable the computer to

i. receive a segment of the segmented posting file associated with the word identifier range containing the query word, and

ii. iteratively identify segmented posting file entries in the segment whose word identifiers correspond to the query word and modify the score in the score table entry of the score table maintained for the record identified in the identified segmented posting file entry,

the records associated with score table entries containing a selected score at the end of the series of iterations being determined to have the selected relationship to the query.

34. A method of controlling a computer to enable the generation of a segmented posting file in response to a record base comprising a plurality of record base entries represented by an array comprising a plurality of columns and rows, the entries within each column having an order according to their respective word identifiers, the method enabling said computer to establish the segmented posting file in response to the record base in a series of segment generation iterations, during each segment generation iteration the method including:

A. a segment word value identifier determination step during which commands are provided to enable said computer to

i. select for the segment generation iteration a record base entry in said record base as a segment word value determiner entry, and

ii. identify as a segment word value identifier range value a value having a selected value relation to the word identifier values in the segment word value determiner entries; and

B. a segment establishment step during which commands are provided to enable said computer to, in a series of segment row generation iterations, establish a series of rows thereby to form a segment of said segmented posting file, for each row of the segment the commands enabling said computer to

i. determine, for each column of the record base, whether a record base entry of the record base contains a word identifier having a value having a selected value relation to the segment word value identifier determination value and

ii. in response to a positive determination, copy the record base entry to a segmented posting file entry in the associated column of the segmented posting file and select the next record base entry of the record base for the next segment row generation iteration.

35. A method as defined in claim 34 in which the number of rows in a segment in the segmented posting file corresponds to a segment size factor,

A. the segmented posting file generation step further including a record base entry identifier establishment step during which commands are provided to enable said computer to establish a record base entry identifier for each column of the record base, and a segment entry pointer establishment step during which commands are provided to enable said computer to establish a segment entry pointer;

B. during the segment word value identifier determination step, providing commands to enable said computer to use the record base entry identifier in the selection of the segment word value determiner entry, and in addition providing commands to enable the computer to identify as a segment word value identifier determiner value the minimum of the word identifier values in the segment word value determiner entries; and

C. during the segment establishment step, providing commands to enable said computer, during a series of segment row generation iterations, to use the segment entry pointer to establish segmented posting file entries in successive rows in a segment of said segmented posting file.

36. A method as defined in claim 35 in which, for each segment generation iteration, during the segment word value identifier determination portion commands are provided to enable said computer to use, as the segment word value determiner entry for each column, a record base entry identified by the sum of the record base entry identifier for the column and the segment size factor.

37. A query processing system for processing queries in connection with a record base including a plurality of record base entries each of which includes a record identifier and a word identifier, each query containing at least one query word, the query processing system identifying records having a selected relationship between the query and the word identifiers contained in the record base, said query processing system comprising:

A. a computer for performing processing operations in response to commands;

B. a control arrangement including;

i. a segmented posting file generation control portion for providing commands to enable said computer to generate, in response to said record base, a segmented posting file, said segmented posting file having a plurality of segmented posting file entries, at least some of said segmented posting file entries having a word identifier and a record identifier, said segmented posting file entries being represented by an array comprising a plurality of columns and rows, said rows being aggregated into segments each having a selected number of rows with each segment containing entries having word identifiers within an identified word identifier range; and

ii. a query processing control portion for providing, in a series of iterations each with respect to a query word in the query, commands to;

(a) enable said computer to receive respective portions of columns comprising a segment of the segmented posting file associated with the word identifier range containing the query word,

(b) identify entries in the segment whose word identifiers correspond to the query word, and

(c) modify a score maintained for the record identified in the identified entry,

records having a selected score at the end of the series of iterations being determined to have the selected relationship to the query.

38. A query processing system as defined in claim 37 further comprising a mass storage system for storing data, said mass storage system being connected to said computer and said control arrangement,

A. said segmented posting file generation control portion enabling said computer to transfer said segmented posting file to said mass storage system for storage, and

B. said query processing control portion enabling said mass storage system to, during each iteration, transfer the segment of said segmented posting file associated with the query word to said computer.

39. A query processing system as defined in claim 37 in which, in said record base, the record base entries are represented by an array comprising a plurality of columns and rows, each column of said record base having an associated column in said segmented posting file, the entries within each column of said record base having an order according to their respective word identifiers, the segmented posting file generation control portion enabling said computer to establish the segmented posting file in response to the record base in a series of segment generation iterations, the segmented posting file generation control portion including:

A. a segment word value identifier determination portion for providing commands to enable said computer to

i. select for the segment generation iteration a record base entry from each column of said record base as a segment word value determiner entry, and

ii. identify as a segment word value identifier range value a value having a selected value relation to the word identifier values in the segment word value determiner entries from all of said columns; and

B. a segment establishment portion for, during each of said segment generation iterations, providing commands to enable said computer to generate a series of rows of the segmented posting file in a series of segment row generation iterations, the commands enabling the computer to, for each column of said record base,

i. determine whether a record base entry from the column of the record base contains a word identifier having a value having a selected value relation to the segment word value identifier determination value and,

ii. in response to a positive determination, copy the record base entry to a segmented posting file entry of an associated column of the segmented posting file and select the next record base entry from the respective column of the record base for the next segment row generation iteration.

40. A query processing system as defined in claim 39 in which the number of rows in a segment in the segmented posting file corresponds to a segment size factor,

A. the segmented posting file generation control portion further including a record base entry identifier establishment portion for providing commands to enable said computer to establish, for each column of said record base, a record base entry identifier, and a segment entry pointer establishment portion for providing commands to enable said computer to establish a segment entry pointer;

B. the segment word value identifier determination portion for providing commands to enable said computer to use the record base entry identifiers in the selection of segment word value determiner entries from the respective columns of said record base, the segment word value identifier determination portion further providing commands to enable the computer to identify as a segment word value identifier determiner value the minimum of the word identifier values in the entries in the segment word value determiner entries; and

C. the segment establishment portion provides commands to enable said computer during each segment row generation iteration to use the segment entry pointer to establish segmented posting file entries in a row in a segment of said segmented posting file.

41. A query processing system as defined in claim 40 further comprising a mass storage system connected to said computer for storing data, said query processing system further including:

A. the segmented posting file generation control portion further providing commands to enable transfer of said segmented posting file from said computer to said mass storage system for storage; and

B. the query processing control portion further providing commands to the computer to enable the transfer of segments of said segmented posting file from said mass storage system to said computer for processing in response to further commands provided by said query processing control portion.

42. A query processing system as defined in claim 41 in which said segmented posting file generation control portion further provides commands for enabling said computer to establish a segmented posting file index portion having a plurality of entries each associated with a segment of said segmented posting file and identifying for the associated segment the range of word identifier values of the entries in the segment.

43. A query processing system as defined in claim 42 in which the query processing control portion further provides commands to said computer to enable it to, for each word of the query, use the segmented posting file index portion to identify a segment which contains word identifier values corresponding to the word of the query, the commands further enabling the identified segment to be transferred from the mass storage system to the computer.

44. A segmented posting file generating system as defined in claim 40 in which, for each segment generation iteration, the segment word value identifier determination portion generates commands to enable said computer to use, as the segment word value determiner entry for each column, a record base entry identified by the sum of the record base entry identifier for the column and the segment size factor.

45. A query processing system as defined in claim 37 in which said query processing control portion includes:

A. score table establishment portion for providing commands to enable said computer to establish a score table having a plurality of score table entries each for receiving a score, each score table entry being associated with a record identified in a column of the segmented posting file, and

B. a score processing portion for, in a series of score generation iterations each with respect to a query word of the query, generating commands to enable the computer to;

i. receive a segment of the segmented posting file associated with the word identifier range containing the query word, and

ii. iteratively identify segmented posting file entries in the segment whose word identifiers correspond to the query word and modify the score in the score table entry maintained for the record identified in the identified segmented posting file entry,

the records associated with score table entries containing a selected score at the end of the series of iterations being determined to have the selected relationship to the query.

46. A query processing system as defined in claim 45 further comprising a mass storage system for storing data, said computer generating storage control commands for controlling the transfer of segments of said segmented posting file from said mass storage system to said computer for processing in response to commands provided by said query processing control portion.