Method and apparatus for accessing previous rows of data in a table

• US 6,457,000 B1
• Filed: 07/29/1999
• Issued: 09/24/2002
• Est. Priority Date: 07/29/1999
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Witkowski, Andrew, Ghosh, Bhaskar
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): HWANG, JOON H
• Application Number:
  US09/363,996
• Time in Patent Office: 1,153 Days
• Field of Search: 707/1-4, 707/100, 707/200-204, 707/101, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/24553 of query operations
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method and apparatus is disclosed for allowing access to one or more previously generated rows of data. A server receives a statement that requires delivery of one or more rows of data to a client, and designates a particular row of data as a current row within a generation sequence. As the rows of data are being delivered to the client, the server accesses select previously generated rows of data that has already been delivered to the client without designating a new particular row of data as the current row. Once the previously generated row is accessed, data is retrieved from predetermined columns. The data retrieved may be used to perform various calculations that will insert values into the current row prior to delivery of the current row to the client. The statement transmitted by the client may include various parameters, including a default parameter, that specifies a default value to be used by the server. The previously generated row is then retrieved based on an offset parameter specified by the client. If the location determined is outside a predetermined range of addressable rows in the generation sequence, then the default value specified by the default parameter is returned. The present invention may also be configured to use a buffer and manage dynamic memory allocated to the buffer.

Claims

1. A method for providing access to a previous row of data comprising the steps:

receiving a statement that requires generation of one or more rows of data and contains a function call that returns a column value of a previously generated row of data;

while generating a current row of said one or more rows of data, accessing the previously generated row of said one or more rows of data to obtain the column value specified in the function call; and

generating at least one value for said current row based on the column value obtained from the previously generated row.

2. The method of claim 1 wherein:

the step of receiving a statement that requires generation of one or more rows of data includes receiving said statement from a client that requires delivery of said one or more rows of data to said client from a server;

the step of accessing a previously generated row of said one or more rows of data includes accessing a buffered copy of a previously delivered row of said one or more rows of data; and

after generating said at least one value for said current row, delivering said current row to said client.

3. The method of claim 1 wherein the function call further specifies a location, in the generation sequence, of the previously generated row relative to the current row.

4. The method of claim 3 wherein:

the received statement includes a default parameter that specifies a default column value for the previously generated row, relative to the current row, in the generation sequence; and

the step of accessing the previously generated row further includes the steps;

determining the location of the previously generated row within the generation sequence based on the location specified in the function call, and

if the location determined is outside a predetermined range of addressable rows in the generation sequence, then employing the default column value as the column value for the row specified by the location.

5. The method of claim 3 further comprising the steps:

creating a buffer in a dynamic memory of the server, said buffer having a size in rows based on the location specified in the function call; and

storing a sequence of rows of data in said buffer, said rows including said current row and the previously generated row specified by the location.

6. The method of claim 5 further comprising the steps:

if the number of previously generated rows of data specified by the location requires less memory than the size of the buffer, then performing the steps;

creating a free row location within the buffer, and

storing the current row into the free row location of the buffer; and

if the number of previously generated rows of data specified by the location requires more memory than the size of the buffer, then performing the steps;

deleting a first row of data stored in the buffer,

creating a free row location by shifting each subsequent row of data one location within the buffer, and

storing the current row of data into the free row location of the buffer.

7. The method of claim 6 further comprising the step:

if the number of previously generated rows of data specified by the location requires more memory than the size of the buffer, then storing the current row of data into the oldest row location of the buffer, thereby erasing the previous contents of the oldest row location of the buffer.

8. The method of claim 5 further comprising a step of freeing up dynamic memory by performing the steps:

determining a selected number of previously generated rows of data in the generation sequence that will be accessed;

storing only the selected previously generated rows of data into the buffer; and

deallocating dynamic memory in the buffer which does not contain the selected previously generated rows of data.

9. The method of claim 5 further comprising the steps:

selecting at least one pair of useable previously generated rows of data from the predetermined number of previously delivered rows of data stored in the buffer;

identifying a plurality of non-useable previously generated rows of data located between each selected pair of useable previously generated rows of data;

selecting a pair of useable previously generated rows of data having a maximum distance therebetween; and

freeing up dynamic memory allocated to the buffer for storing non-useable previously generated rows of data.

10. The method of claim 9 wherein the step of selecting at least one pair of useable previously generated rows of data further includes the steps:

evaluating a distance between each pair of useable previously generated rows of data stored in the buffer; and

comparing the evaluated distances between all pairs of useable previously generated rows of data.

11. The method of claim 9 wherein the step of freeing up dynamic memory comprises the steps:

comparing the maximum distance to a predetermined distance; and

if the maximum distance exceeds the predetermined distance, then performing the steps;

creating a second buffer in the dynamic memory of the server,

segmenting data stored in the buffer into a first portion and a second portion, each of the portions storing a useable previously generated row from the pair of useable previously generated rows of data having the maximum distance therebetween, and none of the nonuseable previously generated rows of data,

storing the second portion of data into the second buffer,

indicating the location in dynamic memory where the second buffer is located, and

deallocating dynamic memory in the buffer that was previously allocated to the second portion of data and the non-useable previously generated rows of data.

12. The method of claim 1 wherein the step of generating at least one value further includes the steps of:

transforming the received statement into one or more prefix sums; and

evaluating the one or more prefix sums.

13. The method of claim 12 wherein the step of evaluating the one or more prefix sums includes the step of applying an asymptotically optimal parallel operation to evaluate the one or more prefix sums.

14. A computer-readable medium carrying one or more sequences of instructions for providing access to one or more previously generated rows of data, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving a statement that requires delivery of one or more rows of data and contains a function call that returns a column value of a previously generated row of data;

while generating a current row of said one or more rows of data, accessing the previously generated row of said one or more rows of data to obtain the column value specified in the function call; and

generating at least one value for said current row based on the column value obtained from the previously generated row.

15. The computer-readable medium of claim 14 wherein:

the function call further specifies a location in the generation sequence of the previously generated row relative the current row; and

execution of the one or more sequences of instructions by one or more processors further causes the one or more processors to perform the steps of;

creating a buffer in a dynamic memory of the server, said buffer having a size in rows based on the location specified in the function call; and

storing a sequence of rows of data in said buffer, said rows including said current row and the previously generated row specified by the location.

16. The computer-readable medium of claim 15 wherein the one or more processors further perform the steps:

if the number of previously generated rows of data specified by the location requires less memory than the size of the buffer, then performing the steps;

creating a free row location within the buffer, and

storing the current row into the free row location of the buffer; and

if the number of previously generated rows of data specified by the location requires more memory than the size of the buffer, then performing the steps;

deleting a first row of data stored in the buffer,

creating a free row location by shifting each subsequent row of data one location within the buffer, and

storing the current row of data into the free row location of the buffer.

17. The computer-readable medium of claim 15 wherein the one or more processors further perform the step:

if the number of previously generated rows of data specified by the location requires more memory than the size of the buffer, then storing the current row of data into the oldest row location of the buffer, thereby erasing the previous contents of the oldest row location of the buffer.

18. The computer-readable medium of claim 14 where in the one or more processor free up dynamic memory by performing the steps:

determining a selected number of previously generated rows of data in the generation sequence that will be accessed;

storing only the selected previously generated rows of data into the buffer; and

deallocating dynamic memory in the buffer which does not contain the selected previously generated rows of data.

19. The computer-readable medium of claim 14 further comprising the steps:

selecting at least one pair of useable previously generated rows of data from the predetermined number of previously generated rows of data stored in the buffer;

identifying a plurality of non-useable previously generated rows of data located between each selected pair of useable previously generated rows of data;

selecting a pair of useable previously generated rows of data having a maximum distance therebetween; and

freeing up dynamic memory allocated to the buffer for storing non-useable previously generated rows of data.

20. The computer-readable medium of claim 19 wherein the step of selecting at least one pair of useable previously generated rows of data further includes the steps:

evaluating a distance between each pair of useable previously generated rows of data stored in the buffer; and

comparing the evaluated distances between all pairs of useable previously generated rows of data.

21. The computer-readable medium of claim 19 wherein the step of freeing up dynamic memory comprises the steps:

comparing the maximum distance to a predetermined distance; and

if the maximum distance exceeds the predetermined distance, then performing the steps;

creating a second buffer in the dynamic memory of the server,

segmenting data stored in the buffer into a first portion and a second portion, each of the portions storing a useable previously generated row from the pair of useable previously generated rows of data having the maximum distance therebetween, and none of the non-useable previously generated rows of data,

storing the second portion of data into the second buffer,

indicating the location in dynamic memory where the second buffer is located, and

deallocating dynamic memory in the buffer that was previously allocated to the second portion of data and the non-useable previously generated rows of data.

22. A system for providing access to one or more previously generated rows of data, the system comprising:

a server configured to;

receive a statement that requires delivery of one or more rows of data, said statement specifying the location of the one or more previously generated rows of data, relative to the current row, in a generation sequence,

create a buffer in dynamic memory, said buffer having a size in rows based on the location specified in the statement,

while generating a current row of said one or more rows of data, accessing a previously generated row of said one or more rows of data specified by the location;

store a sequence of rows of data in said buffer, said rows including said current row and the previously generated row; and

generate at least one value for said current row based on the data from the previously generated row.

23. The system of claim 22 further comprising a client configured to transmit said statement to said server.

24. The system of claim 22 wherein:

said statement further includes a default parameter that specifies a default column value for the previously generated row, relative to the current row, in the generation sequence; and

said server is further configured to access the one or more previous rows of data by performing the steps;

determining the location of the one or more previously generated rows of data within the within the generation sequence based on the location specified in the function call, and

if the location determined is outside a predetermined range of addressable rows in the generation sequence, then employing the default column value for the row specified by the location.

25. The system of claim 22 wherein said server is further configured to:

determine the amount of memory required to store the one or more previously generated rows of data specified by the location;

if the number of previously generated rows of data specified by the location requires less memory than the size of the buffer, then performing the steps;

creating a free row location within the buffer, and

storing the current row into the free row location of the buffer; and

if the number of previously generated rows of data specified by the location requires more memory than the size of the buffer, then storing the current row of data into the oldest row location of the buffer, thereby erasing the previous contents of the oldest row location of the buffer.

26. The system of claim 22, wherein said database server is further configured to:

determine a selected number of previously generated rows of data in the generation sequence that will be accessed;

store only the selected previously generated rows of data into the buffer; and

deallocate dynamic memory in the buffer which does not contain the selected previously generated rows of data.

27. The system of claim 22, wherein said server is further configured to:

select at least one pair of useable previously generated rows of data from the predetermined number of previously delivered previously generated rows of data stored in the buffer;

identify a plurality of non-useable previously generated rows of data located between each selected pair of useable previously generated rows of data;

evaluate a distance between each pair of useable previously generated rows of data stored in the buffer;

compare the evaluated distances between all pairs of useable previously generated rows of data;

select a pair of useable previously generated rows of data having a maximum distance therebetween;

if the maximum distance exceeds the predetermined distance, then performing the steps;

creating a second buffer in dynamic memory,

segmenting data stored in the buffer into a first portion and a second portion, each of the portions storing a useable previously generated row from the pair of useable previously generated rows of data having the maximum distance therebetween and none of the non-useable previously generated rows of data,

storing the second portion of data into the second buffer,

indicating the location in dynamic memory where the second buffer is located, and

deallocating dynamic memory in the buffer that was previously allocated to the second portion of data and the non-useable previously generated rows of data.