Fast select for fetch first n rows with order by

Abstract

Fetching an ordered first N rows of a table, includes: reading a row in the table; determining that the read row qualifies as the first N rows of the table for rows read so far, and storing data of the read row; and determining an order of data of qualifying rows and storing the order. Only data in rows that qualify to be among the first N rows are ordered and stored. This provides a significantly more efficient processing. It eliminates tournament tree sorts, corresponding work file read and write I/O's, and associated CPU time. This reduces the time for the running of a query and improves the performance of other applications sharing the use of work files. Further, the improved performance is particular significant when the buffer sizes are within a page of records or rows, although multiple pages may be used.

1 . A computer readable medium encoded with program instructions for fetching an ordered first N rows of a table, wherein N is a number of rows to the fetched, the program instructions configured for:
 (a) reading a row in the table;   (b) determining that the read row qualifies as the first N rows of the table for rows read so far, and storing data of the read row; and   (c) determining an order of data of qualifying rows and storing the order, comprising:
 (c1) searching an order buffer to determine a new order of keys for the qualifying rows, wherein the order buffer stores position numbers corresponding to data and keys of the qualifying rows, and 
 (c2) shifting the position numbers in the order buffer to reflect the new order. 
   
   
   
       2 . The computer readable medium of  claim 1 , wherein the reading (a) comprises:
 (a1) setting up a data buffer for storing data and keys for the qualifying rows;   (a2) storing in an offset buffer offsets to a base address of the data buffer corresponding to the data and the keys stored in the data buffer; and   (a3) setting up an order buffer for storing position numbers corresponding to the data and the keys stored in the data buffer.   
   
   
       3 . The computer readable medium of  claim 2 , wherein a length of the data buffer is equal to the lengths of the data and the key for a qualifying row multiplied by N. 
   
   
       4 . The computer readable medium of  claim 1 , wherein the determining (b) comprises:
 (b1) determining that a data buffer is not full, wherein the data buffer stores data and keys for the qualifying rows; and   (b2) storing the data and a key of the read row in the data buffer.   
   
   
       5 . The computer readable medium of  claim 1 , wherein the determining (b) comprises:
 (b1) determining that a data buffer is full, wherein the data buffer stores data and keys for the qualifying rows;   (b2) comparing a key of the read row with a key of a last element in an order buffer, wherein the order buffer stores position numbers corresponding to the data and the keys stored in the data buffer; and   (b3) replacing a data and the key in the data buffer corresponding to the last element with the data and the key of the read row, if the key of the read row is lower than the key of the last element.   
   
   
       6 . The computer readable medium of  claim 5 , wherein the determining (b) further comprises:
 (b4) discarding the read row if the key of the read row is higher than the key of the last element.   
   
   
       7 . The computer readable medium of  claim 1 , wherein the determining (c) comprises:
 (c1) determining a position number is a first or second entry in an order buffer, wherein the position number corresponds to the data and a key of the read row, wherein the order buffer stores position numbers corresponding to data and keys of the qualifying rows; and   (c2) storing the position number in the order buffer.   
   
   
       8 . The computer readable medium of  claim 1 , further comprising:
 (d) discarding the read row if the read row does not qualify as the first N rows of the table for rows read so far.