Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-11-03
2003-04-08
Homere, Jean R. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06546382
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to executing queries, and in particular, executing queries to generate the TOP N in order values from a set of data.
BACKGROUND OF THE INVENTION
Users of database systems retrieve data through the use of queries. A query is a request for data. Typically, queries must conform to the rules of a particular query language, such as the ANSI Structured Query Language (SQL). For example, query B
1
:
SELECT salary FROM payroll WHERE salary>10000 retrieves values from the salary column of those rows of table payroll whose value in salary is greater than 10000. The above query includes a SELECT clause (i.e. “SELECT salary”), a FROM clause (i.e. “FROM payroll”), and a WHERE clause (i.e. “salary>10000”). The FROM clause specifies one or more tables or views from which to retrieve values. The tables or views identified in the FROM clause are referred to as the FROM list. The SELECT clause specifies one or more columns in the items in the FROM list from which to retrieve values. The one or more columns identified in the SELECT clause are referred to as the SELECT list. The WHERE clause specifies the rows from which the values are to be retrieved. Specifically, the WHERE clause contains one or more logical expressions defining criteria that must be met by the rows from which values are retrieved.
When a database system executes an SQL query, the database system returns results in the form of a set of rows. Each row contains the columns specified in the SELECT list of the query. Users often desire that the data requested by a query be returned in a particular order. A user may specify an order by including an ORDER BY clause in a query. For example, query B
2
follows:
SELECT salary FROM payroll ORDER BY salary DESC The ORDER BY clause in query B
2
references salary. The columns referenced by an ORDER BY clause are referred to as sort columns. The values in the sort columns are referred to as sort values. Query B
1
specifies that the rows returned by query B
1
are to be returned in a descending order based on the sort values in sort column salary. The keyword DESC specifies the order to be descending.
Rows may be returned in ascending or descending order. The default is ascending. The return order may be specified using the keyword ASC for ascending or DESC for descending.
A user that requests ordered data may desire only the TOP N rows in order. The term “TOP N” refers to the first N data items in an ordered set of data items. For example, the first 10 rows from payroll in ascending order based on salary. An operation or process that returns the TOP N data items based on an order is referred to as a TOP N operation.
To retrieve the top 10 salary values stored in the salary column of the payroll table, a user process issues a query to the database system that contains payroll. To the get rows with the top 10 salary values, the user issues the query B
2
to the database system. The database system returns to the user all the rows from payroll in an order according to the values in salary. The user then retains the first 10 rows received, and discards the rest.
To generate the results, data from all the rows in payroll may have to be scanned, stored, and sorted. Thus, the work to store and sort all the rows is wasted because only a subset of rows are needed by the user. Based on the foregoing, it is clearly desirable to provide a mechanism for retrieving the TOP N rows in an order without wasting work to store and sort all the rows in a table.
SUMMARY OF THE INVENTION
A method and mechanism is described for executing a query that includes a subquery, where the subquery includes an ORDER BY clause. The result set generated by executing the subquery is ordered as specified by the ORDER BY clause. When the result set of the subquery is referenced by a restriction in the outer query, each row in the result set generated for the subquery satisfies the restriction. For example, the restriction may limit the result set generated for a subquery to rows that have values for the row number pseudo-column that are less than a threshold. In response, a TOP N operation is performed to return the rows that are TOP N in order. The order is based on the ORDER BY clause.
REFERENCES:
patent: 5897632 (1999-04-01), Dar et al.
patent: 5956706 (1999-09-01), Carey et al.
patent: 6125360 (2000-09-01), Witkowski et al.
patent: 6134543 (2000-10-01), Witkowski et al.
patent: 6199063 (2001-03-01), Colby et al.
Carey M et al., “Reducing the Braking Distance of an SQL Query Engine”, Proceedings of 24thInternational Conference on Very Large Databases, Aug. 24-27, 1998, pp. 158-169.*
Chaudhuri et al., “Evaluating Top k Selection Queries”, Proceedings of 25th International Conference on Very Large Databases, Sep. 7-10, 1999, pp. 399-410.*
Carey et al. “On Saying Enough already!” in SQL, Proceeding of the ACM SIGMOD International conference on Management of data, 1997, pp. 219-230.*
Koch et al “Oracle 8, the Complete Reference” Osborne/McGraw-Hill, 1997, pp. 415, 919-920.*
Chaudhuri, Surajit et al., “Optimizing Queries with Materialized Views”, Proceedings of the Eleventh International Conference on Data Engineering, Mar. 6-10, 1995, pp. 190-200.
Gopalkrishnan Vivekanand et al., “Issues of Object-Relational View in Data Warehousing Environment”, 1998 IEEE International Conference on Systems, Man, and Cybernetics, Oct. 11-14, 1998, vol. 3, pp. 2732-2737.
Kuno, Harumi et al., “Augmented Inherited Multi-Index Structure for Maintenance of Materialized Path Query Views”, Proceedings of the Sixth International Conference on Research Issues in Data Engineering, Feb. 26-27, 1996, pp. 128-137.
Segev, Arie et al., “Maintaining Materialized Views in Distributed Databases”, Proceedings of the Fifth International Conference on Data Engineering, Feb. 6-10, 1989, pp. 262-270.
Amor Angela
Ozbutun Cetin
Bingham Marcel K.
Hickman Palermo & Truong & Becker LLP
Homere Jean R.
Oracle Corporation
Pham Khanh
LandOfFree
Finding the TOP N values through the execution of a query does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Finding the TOP N values through the execution of a query, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding the TOP N values through the execution of a query will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3062400