Temporal clones to identify valid items from a set of items

Patent metadata

Field	Value
Publication number	US-9639468-B2
Application number	US-201414506613-A
Country	US
Kind code	B2
Filing date	Oct 4, 2014
Priority date	Sep 21, 2013
Publication date	May 2, 2017
Grant date	May 2, 2017

Abstract

Techniques are provided for using bitmaps to indicate which items, in a set of items, are invalid. The bitmaps include an “active” bitmap and one or more “temporal clones”. The active bitmap indicates which items in the set are currently valid. The temporal clones are outdated versions of the active bitmap that indicate which items in the set were invalid at previously points in time. Temporal clones may not be very different from each other. Therefore, temporal clones may be efficiently compressed. For example, a bitmap may be selected as a “base bitmap”, and one or more other bitmaps are encoded using delta encoding. Run length encoding may then be applied to further compress the bitmap information. These bitmaps may then be used to determine which items are valid relative to past-version requests.

First claim

What is claimed is:

1. A method comprising:
maintaining both primary copies and cached copies of a plurality of items;
maintaining, in volatile memory, particular invalidity data that indicates which items in a set of items are invalid;
wherein the set of items whose invalidity is indicated by the particular invalidity data are the cached copies of the plurality of items;
wherein the particular invalidity data is associated with a current time;
wherein each item indicated as being invalid in the particular invalidity data is an out-of-date copy of an item, wherein the out-of-date copy became out-of-date as a result of one or more updates that were made to the primary copy of the item before the current time;
generating a plurality of temporal clones of said particular invalidity data;
wherein each temporal clone:
has a respective clone time;
indicates which items in the set of items were invalid as of the clone time of the temporal clone;

wherein each item indicated as being invalid in each temporal clone is an out-of-date copy of an item, wherein the out-of-date copy became out-of-date as a result of one or more updates that were made to the primary copy of the item before the respective clone time of the temporal clone;
receiving a past-version request that requires a determination of which items, within the set of items, were valid as of a particular time that is before the current time;
selecting a particular temporal clone based on comparisons between the particular time and the respective clone times of the plurality of clones; and
determining which items, within the set of items, were valid as of the particular time based, at least in part, on the particular temporal clone;
wherein the method is performed by one or more computing devices.

2. The method of claim 1 wherein selecting the particular temporal clone is performed by selecting a temporal clone with a respective clone time that matches the particular time.

3. The method of claim 1 wherein:
selecting the particular temporal clone is performed by selecting a temporal clone with a respective clone time that is close to but does not match the particular time; and
the method further comprises modifying the temporal clone to reflect the state of the particular invalidity data as of the particular time.

4. The method of claim 1 wherein the particular invalidity data is a bitmap, wherein each bit in the bitmap indicates whether a corresponding item in the set of items is valid.

5. The method of claim 1 further comprising compressing the plurality of temporal clones to create a compressed version of the temporal clones, wherein the compressed version of the temporal clones is pre-computed and stored in the volatile memory prior to receiving the past-version request.

6. The method of claim 5 wherein compressing the plurality of temporal clones includes selecting a given temporal clone as a base temporal clone and performing delta encoding on the temporal clones, from the plurality of temporal clones, other than the base temporal clone.

7. The method of claim 6 wherein compressing the plurality of temporal clones further comprises, after performing delta encoding, performing run-length compression to further compress the plurality of temporal clones.

8. The method of claim 1 wherein the set of items are rows contained in an in-memory compression unit.

9. The method of claim 8 wherein the in-memory compression unit is compressed, and contains an in-memory copy of items that are stored on non-volatile memory.

10. The method of claim 9 wherein the in-memory compression unit stores the items in a column-major format and the items are stored on disk in a row-major format.

11. One or more non-transitory computer-readable media storing instructions which, when executed by one or more computing devices, causes performance of a method comprising:
maintaining both primary copies and cached copies of a plurality of items;
maintaining, in volatile memory, particular invalidity data that indicates which items in a set of items are invalid;
wherein the set of items whose invalidity is indicated by the particular invalidity data are the cached copies of the plurality of items;
wherein the particular invalidity data is associated with a current time;
wherein each item indicated as being invalid in the particular invalidity data is an out-of-date copy of an item, wherein the out-of-date copy became out-of-date as a result of one or more updates that were made to the primary copy of the item before the current time;
generating a plurality of temporal clones of said particular invalidity data;
wherein each temporal clone:
has a respective clone time;
indicates which items in the set of items were invalid as of the clone time of the temporal clone;

wherein each item indicated as being invalid in each temporal clone is an out-of-date copy of an item, wherein the out-of-date copy became out-of-date as a result of one or more updates that were made to the primary copy of the item before the respective clone time of the temporal clone;
receiving a past-version request that requires a determination of which items, within the set of items, were valid as of a particular time that is before the current time;
selecting a particular temporal clone based on comparisons between the particular time and the respective clone times of the plurality of clones; and
determining which items, within the set of items, were valid as of the particular time based, at least in part, on the particular temporal clone.

12. The one or more non-transitory computer-readable media of claim 11 wherein selecting the particular temporal clone is performed by selecting a temporal clone with a respective clone time that matches the particular time.

13. The one or more non-transitory computer-readable media of claim 11 wherein:
selecting the particular temporal clone is performed by selecting a temporal clone with a respective clone time that is close to but does not match the particular time; and
the method further comprises revising the temporal clone to reflect the state of the particular invalidity data as of the particular time.

14. The one or more non-transitory computer-readable media of claim 11 wherein the particular invalidity data is a bitmap, wherein each bit in the bitmap indicates whether a corresponding item in the set of items is valid.

15. The one or more non-transitory computer-readable media of claim 11 , wherein the method further comprises compressing the plurality of temporal clones to create a compressed version of the temporal clones, wherein the compressed version of the temporal clones is pre-computed and stored in the volatile memory prior to receiving the past-version request.

16. The one or more non-transitory computer-readable media of claim 15 wherein compressing the plurality of temporal clones includes selecting a given temporal clone as a base temporal clone and performing delta encoding on the temporal clones, from the plurality of temporal clones, other than the base temporal clone.

17. The one or more non-transitory computer-readable media of claim 16 wherein compressing the plurality of temporal clones further comprises, after performing delta encoding, performing run-length compression to further compress the plurality of temporal clones.

18. The one or more non-transitory computer-readable media of claim 11 wherein the set of items are rows contained in an in-memory compression unit.

19. The one or more non-transitory computer-readable media of cla

Assignees

• Oracle Int Corp

Inventors

• Raja Vivekanandhan
• Hase Sanket
• Ganesh Amit
• Marwah Vineet

Classifications

• G06F17/30477

  Physics · mapped topic

• G06F15/78

  comprising a single central processing unit · CPC title

• G06F2212/1032

  Reliability improvement, data loss prevention, degraded operation etc · CPC title

• G06F2212/2542

  Non-uniform memory access [NUMA] architecture · CPC title

• G06F17/30315

  Physics · mapped topic