Indexing databases for efficient relational querying

• US 6,507,846 B1
• Filed: 11/09/1999
• Issued: 01/14/2003
• Est. Priority Date: 11/09/1999
• Status: Expired due to Term

• Current Assignee: Progress Software Corporation
• Original Assignee: Joint Technology Corporation
• Inventors: Consens, Mariano Paulo
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): Ali, Mohammad
• Application Number:
  US09/437,766
• Time in Patent Office: 1,162 Days
• Field of Search: 707/1-10, 707/100-104, 345/356, 345/854, 709/231, 709/102, 709/226, 709/215
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99939 Privileged access
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Provided is an indexing system for structured or semi-structured source data comprising a tokenizer for accepting source data and generating tokens representing the source data, the tokens from the tokenization representing the source data in a relational view, where for tokens representing a subset of the source data, the system generates tokens identifying the table and column of the subset of the data in the relational view of the source data, and an index builder for building index structures based on the tokens generated by the tokenizer, the index builder creating indexes which comprise a set of positional indexes for indicating the position of token data in the source data, a set of lexicographical indexes comprising a sort vector index and a join bit index, associated with the sort vector index, a set of data structures mapping between the lexicographical indexes and the positional indexes.

Claims

1. An indexing system for structured or semi-structured source data, the source data being capable of being represented by a relational data view, the source data comprising data subsets which in the relational view correspond to attributes in one or more tables, each table comprising columns and rows, the indexing system comprising

a tokenizer for accepting the source data and generating data tokens in a token stream representing the source data,

the tokenizer comprising means for generating identifier tokens identifying the table and column of the relational view for the data subsets of the source data, the identifier tokens being inserted in the token stream to precede the data tokens for the data subsets to which the identifier tokens correspond, and

an index builder for building indexes based on the token stream, the index builder creating token stream indexes which comprise

a set of positional indexes for indicating the position of data tokens in the source data,

a set of lexicographical indexes for indicating the lexicographical ordering of all tokens, the set of lexicographical indexes comprising a sort vector index and an associated join bit index, and

a set of data structures mapping between the lexicographical indexes and the positional indexes, comprising a lexicographic permutation data structure.

2. The indexing system of claim 1 further comprising join operation means for performing relational join operations on the source data, the join operation means comprising,

means for selecting a first join column and a second join column in the relational view of the source data,

means for accessing the sort vector index entries for identifier tokens corresponding to the first join column and for accessing the sort vector index entries for identifier tokens corresponding to the second join column,

means for determining a relational join data set for the first join column and the second join column, by accessing the sort vector index and the associated join bit index and identifying the token values for each of the attributes in the first join table column which are matched by token values for attributes in the second join column,

means for accessing the source data by the positional indexes to retrieve the set of rows in the tables of the first join column and the second join column which correspond to the relational join data set.

3. The indexing system of claim 1 further comprising query operation means for performing a relational constrained query operation for a column constant on the source data, the column constant having a column identifier and an attribute value, the query operation means comprising,

means for representing the column constant as a constant token stream comprising an identifier token corresponding to the column constant column identifier and data tokens corresponding to the column constant attribute value,

means for accessing the sort vector index entries for identifier tokens corresponding to the column identifier,

means for determining a query return data set by accessing the sort vector index and the associated join bit index to identify token values in the sort vector index which are matched by data token values in the constant column token stream,

means for accessing the source data by the positional indexes to retrieve the set of rows in the tables of the relational view of the source data which correspond to the query return data set.

4. The indexing system of claim 1 in which the index builder further comprises:

means for making a pass over the token stream to produce a temporary sort vector index,

means for sorting the temporary sort vector file on a run by run basis to produce an inverse lexicographic permutation index,

means for making a pass over the temporary sort vector index to generate the sort vector index on a run by run basis by rearranging the entries within each run in the temporary sort vector index according to the permutation, and

means for taking the sort vector index as input and following chains of pointers within the sort vector index to resolve equality of attribute entries to generate the join bit index.

5. A method for indexing structured or semi-structured source data, the source data being capable of being represented by a relational data view, the source data comprising data subsets which in the relational view correspond to attributes in one or more tables, each table comprising columns and rows, the method of indexing comprising

accepting the source data and generating data tokens in a token stream representing the source data,

generating identifier tokens identifying the table and column of the relational view for the data subsets of the source data, the identifier tokens being inserted in the token stream to precede the data tokens for the data subsets to which the identifier tokens correspond, and

creating token stream indexes which comprise

a set of positional indexes for indicating the position of data tokens in the source data,

a set of lexicographical indexes for indicating the lexicographical ordering of all tokens, the set of lexicographical indexes comprising a sort vector index and an associated join bit index, and

a set of data structures mapping between the lexicographical indexes and the positional indexes, comprising a lexicographic permutation data structure.

6. A computer program product tangibly embodying a program of instructions executable by a computer to perform the method steps of claim 5.

7. The method of claim 5 in which the step of creating token stream indexes further comprises:

making a pass over the token stream to produce a temporary sort vector index,

sorting the temporary sort vector file on a run by run basis to produce an inverse lexicographic permutation index,

making a pass over the temporary sort vector index to generate the sort vector index on a run by run basis by rearranging the entries within each run in the temporary sort vector index according to the permutation, and

taking the sort vector index as input and following chains of pointers within the sort vector index to resolve equality of attribute entries to generate the join bit index.

8. The method of claim 5 further comprising steps for carrying out a join operation comprising:

selecting a first join column and a second join column in the relational view of the source data,

accessing the sort vector index entries for identifier tokens corresponding to the first join column and accessing the sort vector index entries for identifier tokens corresponding to the second join column,

determining a relational join data set for the first join column and the second join column, by accessing the sort vector index and the associated join bit index and identifying the token values for each of the attributes in the first join table column which are matched by token values for attributes in the second join column, and

accessing the source data by the positional indexes to retrieve the set of rows in the tables of the first join column and the second join column which correspond to the relational join data set.

9. The method of claim 5 further comprising the step of carrying out a relational constrained query operation for a column constant on the source data, the column constant having a column identifier and an attribute value, the query operation comprising the steps of:

representing the column constant as a constant token stream comprising an identifier token corresponding to the column constant column identifier and data tokens corresponding to the column constant attribute value,

accessing the sort vector index entries for identifier tokens corresponding to the column identifier,

determining a query return data set by accessing the sort vector index and the associated join bit index to identify token values in the sort vector index which are matched by data token values in the constant column token stream, and

accessing the source data by the positional indexes to retrieve the set of rows in the tables of the relational view of the source data which correspond to the query return data set.

10. A computer program product tangibly embodying a program of instructions executable by a computer to perform the method steps of claim 7, 8, or 9.

11. An indexing system for structured or semi-structured source data, the source data being capable of being represented by a relational data view, the source data comprising data subsets which in the relational view correspond to attributes in one or more tables, each table comprising columns and rows, the indexing system comprising

a tokenizer for accepting the source data and generating data tokens in a token stream representing the source data,

the tokenizer comprising means for generating identifier tokens identifying the table and column of the relational view for the data subsets of the source data, the identifier tokens being inserted in the token stream to be contiguous with the data tokens for the data subsets to which the identifier tokens correspond, and

an index builder for building indexes based on the token stream, the index builder creating token stream indexes which comprise

a set of positional indexes for indicating the position of data tokens in the source data,

a set of lexicographical indexes for indicating the lexicographical ordering of all tokens in the token stream, and

a set of data structures mapping between the lexicographical indexes and the positional indexes.

12. The indexing system of claim 11 in which the set of positional indexes comprises an inverted file for mapping unique tokens in the token stream to their position in the source data, a word list strings file comprising a sorted list of all unique tokens in the token stream, a word list file for mapping each token from the word list strings file to the inverted file, each entry in the word list file comprising a location in the inverted file and a run length, and a keys file.

13. The indexing system of claim 11 in which the set of lexicographical indexes comprises a sort vector index and a join bit index.

14. The indexing system of claim 11 in which the the set of data structures mapping between the lexicographical indexes and the positional indexes comprises a lexicographic permutation data structure.

15. A computer-implemented method for the indexing of structured or semi-structured source data, the source data being capable of being represented by a relational data view, the source data comprising data subsets which in the relational view correspond to attributes in one or more tables, each table comprising columns and rows, the method comprising

accepting the source data and generating data tokens in a token stream representing the source data,

generating identifier tokens identifying the table and column of the relational view for the data subsets of the source data,

inserting the identifier tokens in the token stream to be contiguous with the data tokens for the data subsets to which the identifier tokens correspond, and building indexes based on the token stream by creating token stream indexes which comprise

a set of positional indexes for indicating the position of data tokens in the source data,

a set of lexicographical indexes for indicating the lexicographical ordering of all tokens in the token stream, and

a set of data structures mapping between the lexicographical indexes and the positional indexes.

16. The method of claim 15 in which the set of positional indexes comprises an inverted file for mapping unique tokens in the token stream to their position in the source data, a word list strings file comprising a sorted list of all unique tokens in the token stream, a word list file for mapping each token from the word list strings file to the inverted file, each entry in the word list file comprising a location in the inverted file and a run length, and a keys file.

17. The method of claim 15 in which the the set of lexicographical indexes comprises a sort vector file and a join bit file.

18. The method of claim 15 in which the the set of data structures mapping between the lexicographical indexes and the positional indexes comprises a lexicographic permutation data structure.

20. A computer program product tangibly embodying a program of instructions executable by a computer to perform the method steps of claim 15, 16, 17, 18 or 19.

19. A computer-implemented method for the indexing of structured or semi-structured source data, the source data being capable of being represented by a relational data view, the source data comprising data subsets which in the relational view correspond to attributes in one or more tables, each table comprising columns and rows, the method comprising

accepting the source data and generating data tokens in a token stream representing the source data,

generating identifier tokens identifying the table and column of the relational view for the data subsets of the source data,

inserting the identifier tokens in the token stream to be contiguous with the data tokens for the data subsets to which the identifier tokens correspond, and

building indexes based on the token stream by creating token stream indexes which comprise

a set of positional indexes for indicating the position of data tokens in the source data, the set of positional indexes comprising an inverted file for mapping unique tokens in the token stream to their position in the source data, a word list strings file comprising a sorted list of all unique tokens in the token stream, a word list file for mapping each token from the word list strings file to the inverted file, each entry in the word list file comprising a location in the inverted file and a run length, and a keys file

a set of lexicographical indexes for indicating the lexicographical ordering of all tokens in the token stream, comprising a sort vector index and a join bit index, and

a set of data structures mapping between the lexicographical indexes and the positional indexes comprising a lexicographic permutation data structure,

the step of creating token stream indexes further comprising:

making a pass over the token stream to produce a temporary sort vector index,

sorting the temporary sort vector file on a run by run basis to produce an inverse lexicographic permutation index,

making a pass over the temporary sort vector index to generate the sort vector index on a run by run basis by rearranging the entries within each run in the temporary sort vector index according to the permutation, and

taking the sort vector index as input and following chains of pointers within the sort vector index to resolve equality of attribute entries to generate the join bit index.