Method and system for effectively representing query results in a limited amount of memory

• US 5,926,807 A
• Filed: 05/08/1997
• Issued: 07/20/1999
• Est. Priority Date: 05/08/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Milewski, Bartosz, Peltonen, Kyle Gordon, Whitney, Alan, Shoroff, Srikanth
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/853,312
• Time in Patent Office: 803 Days
• Field of Search: 707/5, 707/4, 707/1, 707/3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method and system for effectively representing a result set in a limited amount of memory is provided. The result set is made up of a number of ordered rows. At least some of the rows contain row data, while each of the rows contains a bookmark that may be used to retrieve row data for the row. When it is determined that the size of the result set should be reduced, a subset of the rows of the result set is identified. The identified subset of rows is contiguous within the order of the results set and includes rows that contain row data. For each row of the identified subset, the row data is removed from the result set while retaining in the result set the bookmarks of the rows in the identified subset. As the result of the removal of row data, the size of the result set is reduced. In a further embodiment of the invention, when a request is received to return the row data for a row among the identified subset of rows, the retained bookmarks for the identified subset of rows are used to retrieve row data for the rows back into the result set. The requested row data is then returned from the result set in response to the request.

Claims

1. A method in a computer system for managing the size of a result set produced in response to a database query, the result set comprising a plurality of rows each having information including a sort key, the sort keys of all of the rows of the result set together comprising a sort key range, the method comprising the steps of:

dividing the rows of the result set into a plurality of segments, each segment being either a full segment containing complete information for each of its rows or an abridged segment containing incomplete information for each of its rows, the sort keys of the rows of each segment comprising a sort key subrange within the sort key range, such that the sort key subranges of the segments are non-overlapping;

selecting a segment to abridge based on a likelihood of receiving a request for complete information for one of the rows in the segment; and

abridging the selected segment by discarding at least a portion of the information for each row of the selected segment, such that the size of the selected segment and the size of the result set as a whole are both reduced.

2. The method of claim 1 wherein the selecting and abridging steps are performed in response to the addition of a new row to one of the segments.

3. The method of claim 1 wherein the selecting and abridging steps are performed in response to a request to reduce the size of the result set.

4. The method of claim 1 wherein the selected segment contains summary information generally characterizing the rows of the segment as a group in addition to row information relating to specific rows, and wherein the abridging step discards all the row information in the selected segment, such that only the summary information remains in the selected segment.

5. The method of claim 4 wherein the selected segment is a full segment containing complete information for each of its rows.

6. The method of claim 4 wherein the selected segment is an abridged segment containing incomplete information for each of its rows.

7. The method of claim 1 wherein the selecting and abridging steps are performed in response to the step of determining that the size of the result set as a whole has exceeded a predetermined maximum size.

8. The method of claim 1 wherein the selecting step selects the selected segment based on a comparison of the likelihood of receiving a request for complete information for one of the rows in the selected segment to a threshold likelihood.

9. The method of claim 1 wherein the information for all of the rows of the selected segment is divided into a plurality of columns, and wherein the abridging step discards a subset of the columns for all of the rows in the selected segment.

11. The method of claim 1 wherein the likelihood is based on recency in which complete information for a row of the selected segment has been requested.

12. The method of claim 1 wherein the selecting step selects a segment from which complete information for a row has been requested less recently than at least a predetermined number of other segments.

13. The method of claim 1 wherein the selecting step selects a segment, such that, after the selected segment is abridged in the abridging step, the sort key subranges of the full segments are substantially evenly distributed within the sort key range.

14. The method of claim 1 wherein the selecting step selects a full segment whose sort key subrange is the middle of three consecutive subranges each corresponding to a full segment.

15. The method of claim 1 wherein the plurality of segments includes a first segment whose sort key subrange contains sort keys less than or equal to the sort keys contained by the other sort key subranges and a last segment whose sort key subrange contains sort keys greater than or equal to the sort keys contained by the other sort key subranges, and wherein the selecting step selects a segment other than the first and the last segments.

16. The method of claim 1 wherein the selecting step selects a segment containing more than a predetermined minimum number of rows.

17. The method of claim 1, further including the step of determining that an identified segment will not be the subject of future requests for complete information, and wherein the selecting step selects the identified segment.

18. The method of claim 1, further comprising the steps of:

identifying a segment that has exceeded a predetermined size; and

in response to the identifying step, dividing the rows of the identified segment into a plurality of segments.

19. The method of claim 18 wherein the dividing step divides the rows of the identified segment into two segments.

20. The method of claim 19 wherein the identifying step is performed in response to a step of adding a new row to the identified segment, and wherein the step of dividing the rows of the identified segment into two segments assigns the new row to a first of the two segments and assigns the other rows of the identified segment to a second of the two segments.

21. The method of claim 18 wherein the identifying step identifies a segment having greater than a predetermined maximum number of rows.

22. The method of claim 1, further comprising the steps of:

receiving a request for the complete information of a specified row in a specified segment;

if the specified segment is incomplete, retrieving into the specified segment the complete information for the rows of the specified segment; and

in response to the received request, returning the complete information for the specified row from the specified segment.

24. The method of claim 22 wherein the selected segment contains summary information generally characterizing the rows of the segment in addition to row information, and wherein the abridging step discards all the row information in the selected segment, such that only the summary information remains in the selected segment, and wherein the retrieving step includes reexecuting the database query for the sort key subrange of the specified segment.

25. The method of claim 1, further comprising the steps of:

receiving a request for the complete information of a specified row in a specified segment whose sort keys cumulatively approach the sort key subrange of an adjacent segment;

determining whether the adjacent segment is incomplete; and

if the adjacent segment is incomplete, retrieving into the adjacent segment the complete information for the rows of the adjacent segment in response to the request for complete information for rows of the specified segment.

26. The method of claim 25, further comprising the step of processing the received request, and wherein the retrieving step is performed asynchronously with the processing step.

27. The method of claim 1, further comprising the steps of:

receiving a request for the complete information of a specified number of rows beginning in a specified row of a specified segment and proceeding in a specified direction; and

in response to the receiving step;

returning complete information for the rows from the specified row to the last row of the specified segment in the specified direction of retrieval,

determining that the number of rows returned from the specified segment is smaller than the specified number of rows, and that the segment adjacent to the specified segment in the specified direction of retrieval is incomplete,

retrieving into the adjacent segment the complete information for the rows of the adjacent segment, and

after the retrieving step, returning complete information for rows of the adjacent segment in order to complete the received request.

10. A method in a computer system for managing the size of a result set produced in response to a database query, the result set comprising a plurality of rows each having information including a sort key, the sort keys of all of the rows of the result set together comprising a sort key range, the method comprising the steps of:

dividing the rows of the result set into a plurality of segments, each segment being either a full segment containing complete information for each of its rows or an abridged segment containing incomplete information for each of its rows, the sort keys of the rows of each segment comprising a sort key subrange within the sort key range, such that the sort key subranges of the segments are non-overlapping;

selecting a segment to abridge based on a likelihood of receiving a request for complete information for one of the rows in the segment; and

abridging the selected segment by discarding at least a portion of the information for each row of the selected segment, such that the size of the selected segment and the size of the result set as a whole are both reduced,

wherein the information for all of the rows of the selected segment is divided into a plurality of columns including a bookmark column containing, for each row, information usable to efficiently obtain complete information for the row, and wherein the abridging step discards, for each row in the selected segment, all of the columns except the bookmark column.

23. A method in a computer system for managing the size of a result set produced in response to a database query, the result set comprising a plurality of rows each having information including a sort key, the sort keys of all of the rows of the result set together comprising a sort key range, the method comprising the steps of:

dividing the rows of the result set into a plurality of segments, each segment being either a full segment containing complete information for each of its rows or an abridged segment containing incomplete information for each of its rows, the sort keys of the rows of each segment comprising a sort key subrange within the sort key range, such that the sort key subranges of the segments are non-overlapping;

selecting a segment to abridge based on a likelihood of receiving a request for complete information for one of the rows in the segment;

abridging the selected segment by discarding at least a portion of the information for each row of the selected segment, such that the size of the selected segment and the size of the result set as a whole are both reduced;

receiving a request for the complete information of a specified row in a specified segment;

if the specified segment is incomplete, retrieving into the specified segment the complete information for the rows of the specified segment; and

in response to the received request, returning the complete information for the specified row from the specified segment,

wherein the information for the rows of the specified segment contained in the specified segment includes, for each row, a bookmark usable to efficiently obtain complete information for the row, and wherein the retrieving step includes the step of using the bookmarks to efficiently obtain complete information for the rows of the specified segment.

28. A computer-readable medium whose contents cause a computer system to manage the size of a result set, the result set comprising a plurality of rows each having information including a sort key, the sort keys of all of the rows of the result set together comprising a sort key range, by performing the steps of:

dividing the rows of the result set into a plurality of segments, each segment being either a full segment containing complete information for each of its rows or an abridged segment containing incomplete information for each of its rows, the sort keys of the rows of each segment comprising a distinct sort key subrange within the sort key range;

when each new row is received for the result set, adding the new row to a segment whose subrange encompasses the sort key of the new row;

in response to the adding step, selecting a segment to abridge based on the relative likelihood of, for each segment, receiving a request for complete information for one of the rows in the segment, which corresponds to the likelihood of, for each segment, receiving a request for complete information for a row whose sort key is encompassed by the sort key subrange of the segment; and

abridging the selected segment by discarding at least a portion of the information for each row of the selected segment, such that the size of the selected segment and the size of the result set as a whole are both reduced.

29. The computer-readable medium of claim 28 wherein the information for all of the rows of the selected segment is divided into a plurality of columns, and wherein the abridging step discards a subset of the columns for all of the rows in the selected segment.

30. A computer-readable medium whose contents cause a computer system to manage the size of a result set, the result set comprising a plurality of rows each having information including a sort key, the sort keys of all of the rows of the result set together comprising a sort key range, by performing the steps of:

dividing the rows of the result set into a plurality of segments, each segment being either a full segment containing complete information for each of its rows or an abridged segment containing incomplete information for each of its rows, the sort keys of the rows of each segment comprising a distinct sort key subrange within the sort key range;

when each new row is received for the result set, adding the new row to a segment whose subrange encompasses the sort key of the new row;

in response to the adding step, selecting a segment to abridge based on the relative likelihood of, for each segment, receiving a request for complete information for one of the rows in the segment, which corresponds to the likelihood of, for each segment, receiving a request for complete information for a row whose sort key is encompassed by the sort key subrange of the segment; and

abridging the selected segment by discarding at least a portion of the information for each row of the selected segment, such that the size of the selected segment and the size of the result set as a whole are both reduced,

wherein the information for all of the rows of the selected segment is divided into a plurality of columns including a bookmark column containing, for each row, information usable to efficiently obtain complete information for the row, and wherein the abridging step discards, for each row in the selected segment, all of the columns except the bookmark column.

31. A method in a computer system for managing the size of a representation of a result set produced by a row source program, the representation of the result set comprising an ordered plurality of rows, at least some of the rows containing row data, each of the rows containing a bookmark usable to retrieve row data for the row, the method comprising the steps of:

determining that the size of the representation of the result set should be reduced;

in response to the determining step, identifying a subset of the rows of the representation of the result set that is contiguous within the order of the representation of the result set, at least some of the rows in the identified subset containing row data; and

removing from the representation of the result set any row data contained by rows among the identified subset while retaining in the representation of the result set the bookmarks contained by rows among the identified subset, such that the size of the representation of the result set is reduced.

32. The method of claim 31 wherein the row source program is a database query engine.

33. The method of claim 31 wherein the row source program is an operating system file system.

34. The method of claim 31, further comprising the steps of:

receiving a request to return the row data for a specified row of the identified subset; and

in response to the receiving step;

using the bookmarks retained in the representation of the result set for rows of the identified subset to restore into the representation of the result set the row data for each row of the identified subset, and

returning the restored row data for the specified row.

35. The method of claim 34 wherein the received request specifies a direction of retrieval and wherein the removing step further removes from the representation of the result set any row data contained by rows among a second identified subset while retaining in the representation of the result set the bookmarks contained by rows among the identified subset, the method further comprising the steps of, in response to the receiving step:

determining, based on the received request, that future receipt of a request to return the row data for a row in a second identified segment is likely, and

in response to the determining step, using the bookmarks retained in the representation of the result set for the rows of the second identified subset to restore into the representation of the result set for the row data for each row of the second identified subset.

36. The method of claim 35 wherein the determining step determines that future receipt of a request to return the row data for a row in the second identified segment is likely because the second identified subset is adjacent to the first identified subset in the direction of retrieval.

37. The method of claim 31, further comprising the steps of:

receiving a request to return the row data for a specified row of the identified subset; and

in response to the receiving step;

using the bookmark retained in the representation of the result set for the specified row to retrieve from the row source program the row data for the specified row, and

returning the retrieved row data.

38. A computer-readable medium whose contents cause a computer system to manage the size of a representation of a result, the representation of the result set comprising an ordered plurality of rows, at least some of the rows containing row data, each of the rows containing a bookmark usable to retrieve row data for the row, by performing the steps of:

determining that the size of the representation of the result set should be reduced;

in response to the determining step, identifying a subset of the rows of the representation of the result set that is contiguous within the order of the representation of the result set, at least some of the rows in the identified subset containing row data; and

removing from the representation of the result set any row data contained by rows among the identified subset while retaining in the representation of the result set the bookmarks contained by rows among the identified subset, such that the size of the representation of the result set is reduced.

39. The computer-readable medium of claim 38 wherein the contents of the computer-readable medium further cause the computer system to perform the steps of:

receiving a request to return the row data for a specified row of the identified subset; and

in response to the receiving step;

using the bookmarks retained in the representation of the result set for rows of the identified subset to restore into the representation of the result set the row data for each row of the identified subset, and

returning the restored row data for the specified row.

40. The computer-readable medium of claim 38 wherein the contents of the computer-readable medium further cause the computer system to perform the steps of:

receiving a request to return the row data for a specified row of the identified subset; and

in response to the receiving step;

using the bookmark retained in the representation of the result set for the specified row to retrieve the row data for the specified row, and

returning the retrieved row data.

41. A method in a computer system for responding to requests each requesting the contents of a specified row of a query result set, the method comprising the steps of:

receiving a first request requesting the contents of a first specified row;

in response to receiving the first request;

determining that the first specified row is among a subset of the rows of the result set whose row contents have been partially discarded, but whose remaining row contents include, for each row, a bookmark usable to efficiently retrieve complete contents for the row,

retrieving the contents of each row of the subset using the bookmarks, and

returning the retrieved contents of the first specified row;

receiving a second request requesting the contents of a second specified row that is also among the subset; and

in response to receiving the second request, returning the retrieved contents of the second specified row.

42. A computer-readable medium whose contents cause a computer system to respond to requests each requesting the contents of a specified row of a query result set by performing the steps of:

receiving a first request requesting the contents of a first specified row;

in response to receiving the first request;

determining that the first specified row is among a subset of the rows of the result set whose row contents have been partially discarded, but whose remaining row contents include, for each row, a bookmark usable to efficiently retrieve complete contents for the row,

retrieving the contents of each row of the subset using the bookmarks, and

returning the retrieved contents of the specified row;

receiving a second request requesting the contents of a second specified row that is also among the subset; and

in response to receiving the second request, returning the retrieved contents of the second specified row.

43. A computer-readable medium whose contents cause a computer system to respond to requests each requesting the contents of a specified row of a query result set by performing the steps of:

receiving a first request requesting the contents of a first specified row;

in response to receiving the first request;

determining that the first specified row is among a subset of the rows of the result set whose row contents have been completely discarded,

retrieving the contents of each row of the subset by reexecuting the query for the subset, and

returning the retrieved contents of the specified row;

receiving a second request requesting the contents of a second specified row that is also among the subset; and

in response to receiving the second request, returning the retrieved contents of the second specified row.

44. A method in a computer system for responding to requests each requesting the contents of a specified row of a query result set, the method comprising the steps of:

receiving a first request requesting the contents of a first specified row;

in response to receiving the first request;

determining that the first specified row is among a subset of the rows of the result set whose row contents have been completely discarded,

retrieving the contents of each row of the subset by reexecuting the query for the subset, and

returning the retrieved contents of the specified row;

receiving a second request requesting the contents of a second specified row that is also among the subset; and

in response to receiving the second request, returning the retrieved contents of the second specified row.

45. A computer-readable medium whose contents cause a computer system to instantiate the following programmatic objects for managing a database query result set in a limited amount of memory:

a table object having the following methods;

a method invocable by a row source program to supply to the table with rows of the result set,

a method invocable by a row sink program to request row data for rows in the result set provided by the row source program,

a method for checking and adjusting overall memory usage, and

a segment type changing method for changing the type of a segment object to a type that maintains less information for the rows it manages when the table object determines that the size of the segment should be reduced, the segment type changing method being invoked by the method of the table object for checking and adjusting overall memory usage; and

a plurality of segment objects, each segment object for managing the row data for a portion of the rows in the result set, each segment object being of one of a range of two or more types, each type of segment object maintaining a different level of information about the rows whose row data it manages, the segment objects each having the following methods;

a method invocable by the table to add rows to the segment object,

a method invocable by the table for requesting the row data for rows managed by the segment object, and

a method invocable by the segment type changing method of the table to transfer the row data for rows of the segment object to the segment object of the new type, such that the table and segment objects can be employed to expeditiously service row data requests from the row sink program while utilizing a limited amount of memory.

46. An apparatus for managing a query result set comprising an ordered series of rows produced in response to a database query, each row having contents, the apparatus comprising:

a memory for containing the query result set, the query result set being divided in the memory into a plurality of segments each containing a distinct subset of the rows of the result set that is contiguous within the ordered series of rows;

a result set size monitor that determines when the amount of the memory occupied by the result set should be reduced; and

a result set size reduction subsystem that, in response to a determination by the result set size monitor that the size of the result set should be reduced, reduces the amount of the memory occupied by the result set by;

selecting a segment for which row contents are relatively unlikely to be requested, and

for each row of the selected segment, deleting at least a portion of the contents of the row.

47. The apparatus of claim 46 wherein the result set size reduction subsystem deletes the entire contents of each row of the selected segment.

48. The apparatus of claim 46, further comprising:

a request receiver for receiving requests each requesting the contents of a specified row of the result set; and

a segment restoration subsystem that, when a request is received by the request receiver for the contents of a row within the selected segment, restores the deleted contents of the rows of the selected segment to the selected segment stored in the memory.

49. A method in a computer system for responding to requests each requesting the contents of a specified row of a query result set, each row of the query result set having row information, the method comprising the steps of:

dividing the rows of the query result set into a plurality of segments;

discarding at least a portion of the row information of each row of a selected segment in order to reduce the amount of memory used to store the result set;

after the discarding step, receiving a request for a specified row of the selected segment; and

in response to the receiving step;

subdividing the rows of the selected segment into a plurality of subsegments,

for each row of the subsegment containing the specified row, but for none of the rows of the subsegments not containing the specified row, retrieving the row data of the row discarded in the discarding step, and

returning the row data for the specified row, including the retrieved row data.

50. A method in a computer system for maintaining a query result set using a plurality of row information segments, the query result set comprised of rows each comprised of row information, each segment representing a portion of the rows of the result set, the row information segments being coordinated by a primary table, the method comprising the steps of:

for each row of the result set;

receiving the row information for the row,

under the control of the primary table, identifying a segment in which to represent the row, and

storing at least a portion of the received row information for the row in the identified segment of the primary table;

under the control of the primary table, discarding at least a portion of the row information stored for each row of a selected segment of the primary table in order to reduce the amount of memory used to store the result set;

after the discarding step, receiving a request for a specified row of the selected segment of the primary table; and

in response to the step of receiving a request;

creating a secondary table having its own segments,

for each row represented by the selected segment;

retrieving the row information for the row;

under the control of the secondary table, identifying a segment of the secondary table in which to represent the row; and

storing at least a portion of the retrieved row information for the row in the identified segment of the secondary table, and

replacing the selected segment of the primary table with the segments of the secondary table.

51. The method of claim 50 wherein the step of receiving row information for a portion of the rows of the result set occurs after the step of receiving a request.

52. The method of claim 50, further comprising the steps of:

receiving a request to delete a row of the result set for which row information has been received; and

in response to the step of receiving a request to delete the row, deleting the row from the segment in which the row is represented.

53. A method in a computer system for maintaining the state of a result set produced in response to a database query, the result set being comprised of rows, the method comprising the steps of:

receiving a plurality of row addition requests from a row source program each specifying a row to be added to the result set;

for each received row addition request, processing the row addition request to modify the state of the result set established by processing earlier-processed row addition requests to reflect the addition of the row specified by the row addition request;

receiving a plurality of row retrieval requests each specifying a row to be retrieved from the result set from a row sink program that is distinct from and that operates asynchronously with respect to the row source program, such that receipt of at least one row retrieval request is succeeded by receipt of at least one row addition request; and

for each received row retrieval request, processing the received row retrieval request to retrieve the row specified by the row retrieval request in accordance with the state of the result set established by processing earlier-processed row addition requests.