US5706495A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Encoded-vector indices for decision support and warehousing
Assignee: International Business Machines Corp
•
Filing: 1996-05-07
•
Granted: 1998-01-06
•
Expires: 2016-05-07
Abstract
Abstract A method, apparatus, and article of manufacture for optimizing SQL queries in a relational database management system using a vectorized index. The vectorized index represents values in one or more of the columns of a particular table in the relational database. The vectorized index is comprised of a plurality of positions, wherein each of the positions comprises a linear array that represents a value for the specified columns in a corresponding row of the particular table in the relational database. To use the vectorized index, SQL operations are converted to a series of bit-vector operations on that index, where the result of the bit-vector operations is a list of row positions in the table.
Inventors
- 👤 Atul Chadha
- 👤 Ashish Gupta
- 👤 Piyush Goel
- 👤 Venkatesh Harinarayan
- 👤 Balakrishna Raghavendra Iyer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 09:30
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2237; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933
Claims Analysis
Total Claims: 76
Claim 1
Independent Claim
144 words
A method of optimizing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in the memory, the relational database comprising one or more tables of data, each of the tables comprising one or more intersecting rows and columns of data, the method comprising the steps of: (a) storing a vectorized index in the memory of the computer for values in one or more of the columns of a particular table in the relational database, wherein the vectorized index comprises a plurality of positions, and each of the positions comprises a linear array that represents a value for the specified columns in a corresponding row of the particular table in the relational database; and (b) performing the query in the memory of the computer using the stored vectorized index.
Claim 2
Independent Claim
144 words
A method of optimizing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in the memory, the relational database comprising one or more tables of data, each of the tables comprising one or more intersecting rows and columns of data, the method comprising the steps of: (a) storing a vectorized index in the memory of the computer for values in one or more of the columns of a particular table in the relational database, wherein the vectorized index comprises a plurality of positions, and each of the positions comprises a linear array that represents a value for the specified columns in a corresponding row of the particular table in the relational database; and (b) performing the query in the memory of the computer using the stored vectorized index.
Claim 3
Dependent Claim
30 words
The method of claim 1, wherein an active domain for the vectorized index comprises a set of all distinct values of the specified columns that occur in the particular table.
Claim 4
Dependent Claim
36 words
The method of claim 1, wherein the storing step further comprises the step of modifying the vectorized index using a function selected from a group comprising an insertion function, a deletion function, and a modification function.
Claim 5
Dependent Claim
39 words
The method of claim 1, wherein the performing step comprises the step of converting the query into a series of vector operations, wherein a result of the vector operations is a list of the positions in the vectorized index.
Claim 6
Dependent Claim
52 words
The method of claim 1, wherein the query is selected from a group comprising a point query on a single column, a point query on multiple columns, a range query on a single column, a join query, a hash join query, a nested loop join query, and a sort merge join query.
Claim 7
Dependent Claim
94 words
The method of claim 5, wherein the point query on a single column, the point query on multiple columns, and the range query on a single column, each comprise the steps of: (1) examining, in the computer, each of the positions in the vectorized index that represent a value in the specified columns; (2) determining, in the computer, whether the examined positions meet selection criteria for the value in the specified columns as specified in the point query; and (3) generating, in the computer, a signal that represents a result from the determining step.
Claim 8
Dependent Claim
11 words
The method of claim 6, wherein the signal is a vector.
Claim 9
Dependent Claim
172 words
The method of claim 5, wherein the join query and the hash join query each comprise the steps of: (1) retrieving, in the computer, a value from the active domain for a first vectorized index of a first table; (2) examining, in the computer, positions in the first vectorized index that represent a value in one or more columns of the first table; (3) determining, in the computer, whether the examined positions from step (2) match the retrieved value from step (1); (4) generating, in the computer, a first signal that represents a result from the determining step (3); and (5) examining, in the computer, positions from a second vectorized index that represent a value in one or more columns of a second table; (6) determining, in the computer, whether the examined positions from step (5) match the retrieved value from step (1); (7) generating, in the computer, a second signal that represents a result from the determining step (6); and (8) repeating steps (1)-(8) for all values in the active domain.
Claim 10
Dependent Claim
13 words
The method of claim 8, wherein the first and second signals are vectors.
Claim 11
Dependent Claim
20 words
The method of claim 9, further comprising the step of combining the first and second vectors into a result vector.
Claim 12
Dependent Claim
56 words
The method of claim 10, wherein the result vector comprises one or more pairs of values such that a first one of the values indicates whether a row in the first table matches the retrieved value and a second one of the values indicates that a corresponding row in the second table matches the retrieved value.
Claim 13
Dependent Claim
42 words
The method of claim 11, further comprising the step of joining a row from the first table to a row from the second table when a corresponding pair of values in the result vector indicates that both rows match the retrieved value.
Claim 14
Dependent Claim
19 words
The method of claim 8, further comprising the step of matching unequal vectors for the first and second tables.
Claim 15
Dependent Claim
97 words
The method of claim 5, wherein the nested loop join comprises the steps of: (1) examining, in the computer, position from a first vectorized index that represent a value in one or more columns of a first table; (2) examining, in the computer, positions from a second vectorized index that represent a value in one or more columns of a second table; (3) determining, in the computer, whether the examined positions from step (1) matches the examined positions from step (2); (4) generating, in the computer, a signal that represents a result from the determining step (3).
Claim 16
Dependent Claim
11 words
The method of claim 14, wherein the signal is a vector.
Claim 17
Dependent Claim
84 words
The method of claim 1, wherein the vectorized index comprises a vector of |R|*K bits, |R| is a count of rows in the particular table, K is equal to CEILING(LOG(N)), N is a count of unique values in an active domain for the specified columns, CEILING() is a ceiling function that returns a next highest integer value for LOG(N), and each respective K bits from the encoded vector index represent a value for the specified column in a corresponding row of the particular table.
Claim 18
Dependent Claim
26 words
The method of claim 16, wherein the active domain is a set of all distinct values of the specified columns that occur in the particular table.
Claim 19
Dependent Claim
25 words
The method of claim 17, further comprising the step of mapping each distinct value in the set to a unique K-bit code representing that value.
Claim 20
Dependent Claim
16 words
The method of claim 1, wherein each of the linear arrays comprise a reflected grey code.
Claim 21
Dependent Claim
28 words
The method of claim 19, wherein the performing step comprises the step of retrieving a group of values from the vectorized index using codes constructed using boolean minimization.
Claim 22
Dependent Claim
11 words
The method of claim 20, wherein the group comprises a hierarchy.
Claim 23
Dependent Claim
23 words
The method of claim 20, wherein the codes are intelligently assigned so that a parent code can be identified from its child codes.
Claim 24
Independent Claim
148 words
An apparatus for optimizing an SQL query, comprising: (a) a computer having a memory and a data storage device coupled thereto, wherein the data storage device stores a relational database, the relational database comprising one or more tables of data, each of the tables comprising one or more intersecting rows and columns of data; (b) means, performed by the computer, for storing a vectorized index in the memory of the computer for values in one or more of the columns of a particular table in the relational database, wherein the vectorized index comprises a plurality of positions, and each of the positions comprises a linear array that represents a value for the specified columns in a corresponding row of the particular table in the relational database; and (c) means, performed by the computer, for executing the query in the memory of the computer using the stored vectorized index.
Claim 25
Independent Claim
148 words
An apparatus for optimizing an SQL query, comprising: (a) a computer having a memory and a data storage device coupled thereto, wherein the data storage device stores a relational database, the relational database comprising one or more tables of data, each of the tables comprising one or more intersecting rows and columns of data; (b) means, performed by the computer, for storing a vectorized index in the memory of the computer for values in one or more of the columns of a particular table in the relational database, wherein the vectorized index comprises a plurality of positions, and each of the positions comprises a linear array that represents a value for the specified columns in a corresponding row of the particular table in the relational database; and (c) means, performed by the computer, for executing the query in the memory of the computer using the stored vectorized index.
Claim 26
Dependent Claim
171 words
A program storage medium readable by a computer having a memory, the medium tangibly embodying one or more programs of instructions executable by the computer to perform method steps for optimizing an SQL query, the SQL query being performed by the computer to retrieve data from a relational database stored in an data storage device coupled to the computer, the relational database comprising one or more tables of data, each of the tables comprising one or more intersecting rows and columns of data the method comprising the steps of: (a) storing a vectorized index in the memory of the computer for values in one or more of the columns of a particular table in the relational database, wherein the vectorized index comprises a plurality of positions, and each of the positions comprises a linear array that represents a value for the specified columns in a corresponding row of the particular table in the relational database; and (b) performing the query in the memory of the computer using the stored vectorized index.
Claim 27
Dependent Claim
171 words
A program storage medium readable by a computer having a memory, the medium tangibly embodying one or more programs of instructions executable by the computer to perform method steps for optimizing an SQL query, the SQL query being performed by the computer to retrieve data from a relational database stored in an data storage device coupled to the computer, the relational database comprising one or more tables of data, each of the tables comprising one or more intersecting rows and columns of data the method comprising the steps of: (a) storing a vectorized index in the memory of the computer for values in one or more of the columns of a particular table in the relational database, wherein the vectorized index comprises a plurality of positions, and each of the positions comprises a linear array that represents a value for the specified columns in a corresponding row of the particular table in the relational database; and (b) performing the query in the memory of the computer using the stored vectorized index.
Claim 28
Dependent Claim
120 words
A memory for storing data for access by an SQL query executed by a computer, the SQL query being performed by the computer to retrieve data from a relational database stored in the computer, the relational database comprising one or more tables of data, each of the tables comprising one or more intersecting rows and columns of data, the memory comprising: a vectorized index representative of values in one or more of the columns of a particular table in the relational database, wherein the vectorized index comprises a plurality of positions, and each of the positions comprises a linear array that represents a value for the specified columns in a corresponding row of the particular table in the relational database.
Claim 29
Dependent Claim
120 words
A memory for storing data for access by an SQL query executed by a computer, the SQL query being performed by the computer to retrieve data from a relational database stored in the computer, the relational database comprising one or more tables of data, each of the tables comprising one or more intersecting rows and columns of data, the memory comprising: a vectorized index representative of values in one or more of the columns of a particular table in the relational database, wherein the vectorized index comprises a plurality of positions, and each of the positions comprises a linear array that represents a value for the specified columns in a corresponding row of the particular table in the relational database.
Claim 30
Dependent Claim
30 words
The apparatus of claim 23, wherein an active domain for the vectorized index comprises a set of all distinct values of the specified columns that occur in the particular table.
Claim 31
Dependent Claim
36 words
The apparatus of claim 23, wherein the means for storing further comprises means for modifying the vectorized index using a function selected from a group comprising an insertion function, a deletion function, and a modification function.
Claim 32
Dependent Claim
39 words
The apparatus of claim 23, wherein the means for executing comprises means for converting the query into a series of vector operations, wherein a result of the vector operations is a list of the positions in the vectorized index.
Claim 33
Dependent Claim
52 words
The apparatus of claim 23, wherein the query is selected from a group comprising a point query on a single column, a point query on multiple columns, a range query on a single column, a join query, a hash join query, a nested loop join query, and a sort merge join query.
Claim 34
Dependent Claim
98 words
The apparatus of claim 29, wherein the point query on a single column, the point query on multiple columns, and the range query on a single column, each comprise: (1) means for examining, in the computer, each of the positions in the vectorized index that represent a value in the specified columns; (2) means for determining, in the computer, whether the examined positions meet selection criteria for the value in the specified columns as specified in the point query; and (3) means for generating, in the computer, a signal that represents a result from the means for determining.
Claim 35
Dependent Claim
11 words
The apparatus of claim 30, wherein the signal is a vector.
Claim 36
Dependent Claim
200 words
The apparatus of claim 29, wherein the join query and the hash join query each comprise: (1) means for retrieving, in the computer, a value from the active domain for a first vectorized index of a first table; (2) means for examining, in the computer, positions in the first vectorized index that represent a value in one or more columns of the first table; (3) means for determining, in the computer, whether the examined positions from the means for examining (2) match the retrieved value from the means for retrieving (1); (4) means for generating, in the computer, a first signal that represents a result from the means for determining (3); and (5) means for examining, in the computer, positions from a second vectorized index that represent a value in one or more columns of a second table; (6) means for determining, in the computer, whether the examined positions from the means for examining (5) match the retrieved value from the means for retrieving (1); (7) means for generating, in the computer, a second signal that represents a result from the means for determining (6); and (8) means for performing the means (1)-(8) for all values in the active domain.
Claim 37
Dependent Claim
13 words
The apparatus of claim 32, wherein the first and second signals are vectors.
Claim 38
Dependent Claim
19 words
The apparatus of claim 33, further comprising means for combining the first and second vectors into a result vector.
Claim 39
Dependent Claim
56 words
The apparatus of claim 34, wherein the result vector comprises one or more pairs of values such that a first one of the values indicates whether a row in the first table matches the retrieved value and a second one of the values indicates that a corresponding row in the second table matches the retrieved value.
Claim 40
Dependent Claim
41 words
The apparatus of claim 35, further comprising means for joining a row from the first table to a row from the second table when a corresponding pair of values in the result vector indicates that both rows match the retrieved value.
Claim 41
Dependent Claim
18 words
The apparatus of claim 32, further comprising means for matching unequal vectors for the first and second tables.
Claim 42
Dependent Claim
109 words
The apparatus of claim 29, wherein the nested loop join comprises: (1) means for examining, in the computer, positions from a first vectorized index that represent a value in one or more columns of a first table; (2) means for examining, in the computer, positions from a second vectorized index that represent a value in one or more columns of a second table; (3) means for determining, in the computer, whether the examined positions from the means for examining (1) matches the examined positions from the means for examining (2); (4) means for generating, in the computer, a signal that represents a result from the means for determining (3).
Claim 43
Dependent Claim
11 words
The apparatus of claim 38, wherein the signal is a vector.
Claim 44
Dependent Claim
84 words
The apparatus of claim 23, wherein the vectorized index comprises a vector of |R|*K Bits, |R| is a count of rows in the particular table, K is equal to CEILING(LOG(N)), N is a count of unique values in an active domain for the specified columns, CEILING() is a ceiling function that returns a next highest integer value for LOG(N), and each respective K bits from the encoded vector index represent a value for the specified column in a corresponding row of the particular table.
Claim 45
Dependent Claim
26 words
The apparatus of claim 40, wherein the active domain is a set of all distinct values of the specified columns that occur in the particular table.
Claim 46
Dependent Claim
24 words
The apparatus of claim 41, further comprising means for mapping each distinct value in the set to a unique K-bit code representing that value.
Claim 47
Dependent Claim
16 words
The apparatus of claim 23, wherein each of the linear arrays comprise a reflected grey code.
Claim 48
Dependent Claim
28 words
The apparatus of claim 43, wherein the means for executing comprises means for retrieving a group of values from the vectorized index using codes constructed using boolean minimization.
Claim 49
Dependent Claim
11 words
The apparatus of claim 44, wherein the group comprises a hierarchy.
Claim 50
Dependent Claim
23 words
The apparatus of claim 44, wherein the codes are intelligently assigned so that a parent code can be identified from its child codes.
Claim 51
Dependent Claim
30 words
The method of claim 24, wherein an active domain for the vectorized index comprises a set of all distinct values of the specified columns that occur in the particular table.
Claim 52
Dependent Claim
36 words
The method of claim 24, wherein the storing step further comprises the step of modifying the vectorized index using a function selected from a group comprising an insertion function, a deletion function, and a modification function.
Claim 53
Dependent Claim
39 words
The method of claim 24, wherein the performing step comprises the step of converting the query into a series of vector operations, wherein a result of the vector operations is a list of the positions in the vectorized index.
Claim 54
Dependent Claim
52 words
The method of claim 24, wherein the query is selected from a group comprising a point query on a single column, a point query on multiple columns, a range query on a single column, a join query, a hash join query, a nested loop join query, and a sort merge join query.
Claim 55
Dependent Claim
94 words
The method of claim 50, wherein the point query on a single column, the point query on multiple columns, and the range query on a single column, each comprise the steps of: (1) examining, in the computer, each of the positions in the vectorized index that represent a value in the specified columns; (2) determining, in the computer, whether the examined positions meet selection criteria for the value in the specified columns as specified in the point query; and (3) generating, in the computer, a signal that represents a result from the determining step.
Claim 56
Dependent Claim
11 words
The method of claim 51, wherein the signal is a vector.
Claim 57
Dependent Claim
172 words
The method of claim 50, wherein the join query and the hash join query each comprise the steps of: (1) retrieving, in the computer, a value from the active domain for a first vectorized index of a first table; (2) examining, in the computer, positions in the first vectorized index that represent a value in one or more columns of the first table; (3) determining, in the computer, whether the examined positions from step (2) match the retrieved value from step (1); (4) generating, in the computer, a first signal that represents a result from the determining step (3); and (5) examining, in the computer, positions from a second vectorized index that represent a value in one or more columns of a second table; (6) determining, in the computer, whether the examined positions from step (5) match the retrieved value from step (1); (7) generating, in the computer, a second signal that represents a result from the determining step (6); and (8) repeating steps (1)-(8) for all values in the active domain.
Claim 58
Dependent Claim
13 words
The method of claim 53, wherein the first and second signals are vectors.
Claim 59
Dependent Claim
20 words
The method of claim 54, further comprising the step of combining the first and second vectors into a result vector.
Claim 60
Dependent Claim
56 words
The method of claim 55, wherein the result vector comprises one or more pairs of values such that a first one of the values indicates whether a row in the first table matches the retrieved value and a second one of the values indicates that a corresponding row in the second table matches the retrieved value.
Claim 61
Dependent Claim
42 words
The method of claim 56, further comprising the step of joining a row from the first table to a row from the second table when a corresponding pair of values in the result vector indicates that both rows match the retrieved value.
Claim 62
Dependent Claim
19 words
The method of claim 53, further comprising the step of matching unequal vectors for the first and second tables.
Claim 63
Dependent Claim
97 words
The method of claim 50, wherein the nested loop join comprises the steps of: (1) examining, in the computer, positions from a first vectorized index that represent a value in one or more columns of a first table; (2) examining, in the computer, positions from a second vectorized index that represent a value in one or more columns of a second table; (3) determining, in the computer, whether the examined positions from step (1) matches the examined positions from step (2); (4) generating, in the computer, a signal that represents a result from the determining step (3).
Claim 64
Dependent Claim
11 words
The method of claim 59, wherein the signal is a vector.
Claim 65
Dependent Claim
84 words
The method of claim 24, wherein the vectorized index comprises a vector of |R|*K bits, |R| is a count of rows in the particular table, K is equal to CEILING(LOG(N)), N is a count of unique values in an active domain for the specified columns, CEILING() is a ceiling function that returns a next highest integer value for LOG(N), and each respective K bits from the encoded vector index represent a value for the specified column in a corresponding row of the particular table.
Claim 66
Dependent Claim
26 words
The method of claim 61, wherein the active domain is a set of all distinct values of the specified columns that occur in the particular table.
Claim 67
Dependent Claim
25 words
The method of claim 62, further comprising the step of mapping each distinct value in the set to a unique K-bit code representing that value.
Claim 68
Dependent Claim
16 words
The method of claim 24, wherein each of the linear arrays comprise a reflected grey code.
Claim 69
Dependent Claim
28 words
The method of claim 64, wherein the performing step comprises the step of retrieving a group of values from the vectorized index using codes constructed using boolean minimization.
Claim 70
Dependent Claim
11 words
The method of claim 65, wherein the group comprises a hierarchy.
Claim 71
Dependent Claim
23 words
The method of claim 65, wherein the codes are intelligently assigned so that a parent code can be identified from its child codes.
Claim 72
Dependent Claim
30 words
The memory of claim 25, wherein an active domain for the vectorized index comprises a set of all distinct values of the specified columns that occur in the particular table.
Claim 73
Dependent Claim
84 words
The memory of claim 25, wherein the vectorized index comprises a vector of |R|*K bits, |R| is a count of rows in the particular table, K is equal to CEILING(LOG(N)), N is a count of unique values in an active domain for the specified columns, CEILING() is a ceiling function that returns a next highest integer value for LOG(N), and each respective K bits from the encoded vector index represent a value for the specified column in a corresponding row of the particular table.
Claim 74
Dependent Claim
26 words
The memory of claim 69, wherein the active domain is a set of all distinct values of the specified columns that occur in the particular table.
Claim 75
Dependent Claim
21 words
The memory of claim 70, wherein each distinct value in the set maps to a unique K-bit code representing that value.
Claim 76
Dependent Claim
16 words
The memory of claim 25, wherein each of the linear arrays comprise a reflected grey code.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-01-05 | 2001-07-07 | 2002-01-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-01-05 | 2005-07-07 | 2006-01-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-01-05 | 2009-07-07 | 2010-01-06 | $7700.00 | Window Closed / Lapsed |