US5819256A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for processing count statements in a database system
Assignee: Oracle International Corp
•
Filing: 1996-11-20
•
Granted: 1998-10-06
•
Expires: 2016-11-20
Abstract
Abstract A method and apparatus for processing count queries in a database system is provided. The database server determines whether it is possible for the target data specified in a count query to contain null values. If the target data cannot contain null values, the count query is converted into a count star query. Count star queries are executed by counting the number of records that store the target data without actually reading and evaluating the target data. If an index for the table that stores the target data exists, then the number of records are counted without accessing the table itself by counting record identifiers in the index. If the index is a bitmap index, the number of bits that are set in bitmaps from the index are counted without actually generating record identifiers from the bitmaps. Many processes are used to generate intermediate count values from the bitmaps. The intermediate count values are summed to produce a total count value. For count queries that contain group by clauses, intermediate count values are generated for each distinct key value. The intermediate count values are summed to produce a total count value for each distinct key value.
Inventors
- 👤 Cetin Ozbutun
- 👤 Michael Depledge
- 👤 Hakan Jakobsson
- 👤 Jeffrey I. Cohen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 10:20
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2455; G06F16/24553; G06F16/24554; G06F16/24556; G06F16/22; G06F16/2228; G06F16/2237; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
123 words
A method for processing count queries in a database system that includes a data container having a plurality of records, the method comprising the steps of: receiving a count query that specifies target data within said data container; determining, without evaluating the target data, whether the target data can possibly include null values; if the target data cannot possibly include null values, then, without evaluating the target data, processing the count query by determining how many records in the data container contain the target data; and if the target data can possibly include null values, then processing the count query by determining how many records in the data container contain non-null values for the target data by reading and evaluating the target data.
Claim 2
Independent Claim
123 words
A method for processing count queries in a database system that includes a data container having a plurality of records, the method comprising the steps of: receiving a count query that specifies target data within said data container; determining, without evaluating the target data, whether the target data can possibly include null values; if the target data cannot possibly include null values, then, without evaluating the target data, processing the count query by determining how many records in the data container contain the target data; and if the target data can possibly include null values, then processing the count query by determining how many records in the data container contain non-null values for the target data by reading and evaluating the target data.
Claim 3
Dependent Claim
35 words
The method of claim 1 further comprising the step of, if the target data cannot possibly include null values, then transforming the count query into a count star query and executing the count star query.
Claim 4
Dependent Claim
133 words
The method of claim 1 wherein, if the target data cannot possibly include null values, then the step of processing said count query includes the steps of: determining whether an index exists that is associated with said data container and that contains identifiers for said plurality of records; if an index exists that is associated with said data container and that contains identifiers for said plurality of records, then determining how many records in the data container contain the target data based on the identifiers stored in said index; and if an index does not exist that is associated with said data container and that contains identifiers for said plurality of records, then determining how many records in the data container contain the target data based on identifiers stored in said data container.
Claim 5
Dependent Claim
69 words
The method of claim 3 wherein: a bitmap index exists that is associated with said data container and that contains identifiers for said plurality of records; and the step of determining how many records in the data container contain the target data based on identifiers stored in said index includes the step of counting how many bits are set in one or more bitmaps contained in said bitmap index.
Claim 6
Dependent Claim
89 words
The method of claim 4 wherein the step of counting how many bits are set in one or more bitmaps comprises the steps of: assigning to each of a plurality of processes a task of counting how many bits are set in a subset of said one or more bitmaps; causing each of said plurality of processes to generate an intermediate count based on said subset of said one or more bitmaps; and summing the intermediate counts generated by said plurality of processes to generate a total count value.
Claim 7
Dependent Claim
106 words
The method of claim 5 wherein: the count query includes a group by clause; the step of causing each of said plurality of processes to generate an intermediate count based on said subset of said one or more bitmaps includes causing each of said plurality of processes to generate a separate intermediate count for each distinct key value associated with said subset of said one or more bitmaps; and the step of summing the intermediate counts includes separately summing the intermediate counts for each of the key values associated with said one or more bitmaps to generate a total count for each of said key values.
Claim 8
Independent Claim
52 words
A method for processing a count query in a database system, the method comprising the steps of: determining that the count query specifies target data that cannot include null values; transforming the count query to a count star query; and executing the count star query without reading and evaluating the target data.
Claim 9
Independent Claim
52 words
A method for processing a count query in a database system, the method comprising the steps of: determining that the count query specifies target data that cannot include null values; transforming the count query to a count star query; and executing the count star query without reading and evaluating the target data.
Claim 10
Dependent Claim
30 words
The method of claim 7 wherein the step of executing the count star query includes the step of determining how many records in a data container contain the target data.
Claim 11
Dependent Claim
64 words
The method of claim 8 wherein: a bitmap index exists that is associated with said data container and that contains identifiers for the records in the data container; and the step of determining how many records in the data container contain the target data includes the step of counting how many bits are set in one or more bitmaps contained in said bitmap index.
Claim 12
Dependent Claim
89 words
The method of claim 9 wherein the step of counting how many bits are set in one or more bitmaps comprises the steps of: assigning to each of a plurality of processes a task of counting how many bits are set in a subset of said one or more bitmaps; causing each of said plurality of processes to generate an intermediate count based on said subset of said one or more bitmaps; and summing the intermediate counts generated by said plurality of processes to generate a total count value.
Claim 13
Dependent Claim
105 words
The method of claim 10 wherein: the count query includes a group by clause; the step of causing each of said plurality of processes to generate an intermediate count based on said subset of said one or more bitmaps includes causing each of said plurality of processes to generate a separate intermediate count for each distinct key value associated with said subset of said one or more bitmaps; and the step of summing the intermediate counts includes separately summing the intermediate counts for each of the key values associated with said one or more bitmaps to generate a total count for each of said key/values.
Claim 14
Dependent Claim
41 words
The method of claim 7 wherein the step of executing the count star query without reading and evaluating the target data includes the step of counting record identifiers from an index associated with a data container that contains the target data.
Claim 15
Dependent Claim
54 words
The method of claim 7 wherein the step of executing the count star query without reading and evaluating the target data includes the step of counting how many bits are set to a particular value in one or more bitmaps in a bitmap index associated with a data container that contains the target data.
Claim 16
Dependent Claim
89 words
The method of claim 13 wherein the step of counting how many bits are set to a particular value in one or more bitmaps includes the steps of: assigning said one or more bitmaps to a plurality of processes, wherein each of said plurality of processes is assigned a subset of said one or more bitmaps; causing each process of said plurality of processes to generate an intermediate value based on a subset of said one or more bitmaps; and summing intermediate values generated by said plurality of processes.
Claim 17
Independent Claim
70 words
A method for processing a count star query in a database system, the method comprising the steps of: identifying a bitmap index associated with a data container, said data container containing target data specified in said count star query; and counting how many bits are set to a particular value in one or more bitmaps in said bitmap index without generating record identifiers based on said one or more bitmaps.
Claim 18
Independent Claim
70 words
A method for processing a count star query in a database system, the method comprising the steps of: identifying a bitmap index associated with a data container, said data container containing target data specified in said count star query; and counting how many bits are set to a particular value in one or more bitmaps in said bitmap index without generating record identifiers based on said one or more bitmaps.
Claim 19
Dependent Claim
84 words
The method of claim 15 wherein the step of counting how many bits are set to a particular value includes the steps of: assigning said one or more bitmaps to a plurality of processes, wherein each of said plurality of processes is assigned a subset of said one or more bitmaps; causing each process of said plurality of processes to generate an intermediate value based on a subset of said one or more bitmaps; and summing intermediate values generated by said plurality of processes.
Claim 20
Dependent Claim
115 words
The method of claim 15 wherein: the count star query includes a group by clause; the step of counting how many bits are set to a particular value includes the steps of: assigning said one or more bitmaps to a plurality of processes, wherein each of said plurality of processes is assigned a subset of said one or more bitmaps; causing each process of said plurality of processes to generate one intermediate value for each distinct key value in said subset of said one or more bitmaps; and summing the intermediate values for each distinct key value to produce a single count value for each distinct key value associated with said one or more bitmaps.
Claim 21
Dependent Claim
146 words
A computer-readable medium having stored thereon sequences of instructions for processing count queries in a database system that includes a data container having a plurality of records, the sequences of instructions including sequences of instructions which, when executed by a processor, cause said processor to perform the steps of: receiving a count query that specifies target data within said data container; determining, without evaluating the target data, whether the target data can possibly include null values; if the target data cannot possibly include null values, then, without evaluating the target data, processing the count query by determining how many records in the data container contain the target data; and if the target data can possibly include null values, then processing the count query by determining how many records in the data container contain non-null values for the target data by reading and evaluating the target data.
Claim 22
Dependent Claim
146 words
A computer-readable medium having stored thereon sequences of instructions for processing count queries in a database system that includes a data container having a plurality of records, the sequences of instructions including sequences of instructions which, when executed by a processor, cause said processor to perform the steps of: receiving a count query that specifies target data within said data container; determining, without evaluating the target data, whether the target data can possibly include null values; if the target data cannot possibly include null values, then, without evaluating the target data, processing the count query by determining how many records in the data container contain the target data; and if the target data can possibly include null values, then processing the count query by determining how many records in the data container contain non-null values for the target data by reading and evaluating the target data.
Claim 23
Dependent Claim
41 words
The computer-readable medium of claim 18 further comprising sequences of instructions form performing the step of, if the target data cannot possibly include null values, then transforming the count query into a count star query and executing the count star query.
Claim 24
Dependent Claim
134 words
The computer-readable medium of claim 18 wherein, if the target data cannot possibly include null values, then the step of processing said count query includes the steps of: determining whether an index exists that is associated with said data container and that contains identifiers for said plurality of records; if an index exists that is associated with said data container and that contains identifiers for said plurality of records, then determining how many records in the data container contain the target data based on the identifiers stored in said index; and if an index does not exist that is associated with said data container and that contains identifiers for said plurality of records, then determining how many records in the data container contain the target data based on identifiers stored in said data container.
References Cited (Backward Citations)
US5379419A
Cited
US5412804A
Cited
US5561793A
Cited
US5634019A
Cited
US5542078A
Cited
US5590324A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-10-05 | 2002-04-06 | 2002-10-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-10-05 | 2006-04-06 | 2006-10-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-10-05 | 2010-04-06 | 2010-10-06 | $7700.00 | Window Closed / Lapsed |