Patent Publication Number: US-11379433-B2

Title: Persistent version storage for relational database management system

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is related to and claims the benefit of U.S. Provisional Patent Application Ser. No. 62/676,868, filed May 25, 2018, titled “Persistent Version Store for Relational Database System,” which is expressly incorporated herein by reference in its entirety. 
    
    
     BACKGROUND 
     A relational database is a collection of data items organized as a set of formally described tables from which data can be accessed. The values within each table may be related to each other, and tables may also be related to other tables. The relational structure makes it possible to run queries across multiple tables at once. Relational databases are a common choice for the storage of various types of information, such as financial records, manufacturing and logistical information, personnel data, and the like. 
     A database management system (DBMS) controls the storage, retrieval, deletion, security, and integrity of data within a database. A relational database management system (RDBMS) is a DBMS that manages and facilitates access to a relational database. The most common use of RDBMSs is to provide the functions of creating, reading, updating, and deleting (CRUD). An RDBMS may facilitate access to a relational database by receiving queries from users, applications, or other entities, executing such queries against the relational database to produce a results dataset, and returning the results dataset to the entities that submitted the queries. The queries may be represented using Structured Query Language (SQL) or another suitable database query language. 
     The fundamental unit of storage in an RDBMS is typically referred to as a database page (or simply a page). The disk space allocated to a data file in a database is logically divided into database pages, which may be numbered contiguously from 0 to N. Disk input/output operations are typically performed at the database page level. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates an example of a relational database management system that implements persistent version storage in accordance with the present disclosure. 
         FIGS. 2A and 2B  illustrate an example showing how a page free space (PFS) page may be utilized to facilitate tracking of in-row previous version information. 
         FIG. 3  illustrates an example showing different types of in-row previous version information that may be stored and also how in-row previous version information may be cleaned up. 
         FIG. 4  illustrates an example showing how off-row previous version information may be cleaned up. 
         FIGS. 5A-G  illustrate an example showing how persistent version storage may be implemented in accordance with the present disclosure. 
         FIG. 6  illustrates an example of a method for implementing persistent version storage in accordance with the present disclosure. 
         FIG. 7  illustrates certain components that may be included within a computer system. 
     
    
    
     DETAILED DESCRIPTION 
     The present disclosure is generally related to a relational database management system (RDBMS) that implements persistent version storage, which is a mechanism for storing previous versions of data as active transactions modify data. Implementing persistent version storage may provide various advantages, such as instant (or near-instant) transaction rollback, accelerated database crash recovery, instant (or near-instant) logical reversion of entities in a database, time travel queries, better resource and security isolation, and better overall performance of the RDBMS. 
       FIG. 1  illustrates an example of an RDBMS  100  that is configured to implement persistent version storage in accordance with the present disclosure. The RDBMS  100  stores data in database pages  102 . Each database page  102  may include one or more rows  110 . The RDBMS  100  includes modules  104  that perform various operations on the data within the database pages  102  to implement persistent version storage. These modules  104  may be referred to herein as persistent version storage (PVS) modules  104 . 
     The PVS modules  104  may include one or more in-row modules  106  that are configured to implement an in-row scheme. In accordance with the in-row scheme, previous version information  114  about a particular row  110  within a database page  102  may be stored within the row  110  itself. Previous version information  114  that is stored within a row  110  may be referred to herein as in-row previous version information  114 . The in-row previous version information  114  that is stored within a particular row  110  may be stored within a payload  111  of the row  110 , along with the current version  142  of the row  110 . Under some circumstances, the in-row previous version information  114  may include the difference between the current version  142  of the row  110  and the previous version of the row  110 . Alternatively, the in-row previous version information  114  may include the entire previous version of the row  110 . 
     The PVS modules  104  may also include one or more off-row modules  108  that are configured to implement an off-row scheme. In accordance with the off-row scheme, previous version information  115  about a particular row  110  within a database page  102  may be stored in a separate location (i.e., a location somewhere other than within the row  110  itself). Previous version information  115  that is stored somewhere other than within a row  110  may be referred to herein as off-row previous version information  115 . The off-row previous version information  115  that is stored for a row  110  within a database page  102  may be stored in an off-row page  132  that is separate from the database page  102 . The off-row previous version information  115  may include the entire previous version of the row  110 . There may be multiple off-row pages  132  within the RDBMS  100 . The off-row pages  132  may be similar to other database pages  102  in the RDBMS  100 , except that the off-row pages  132  may be dedicated for off-row storage. 
     The RDBMS  100  may also include a storage policy  116  that defines when an in-row scheme is utilized and when an off-row scheme is utilized. In other words, the storage policy  116  may define when in-row previous version information  114  is stored in accordance with an in-row scheme and when off-row previous version information  115  is stored in accordance with an off-row scheme. 
     The storage policy  116  may include at least one rule  134  indicating when an in-row scheme is utilized and at least one rule  136  indicating when an off-row scheme is utilized. In some implementations, the in-row scheme rule(s)  134  may indicate that the in-row scheme should be utilized when the difference between the previous version of a row  110  and the current version  142  of the row  110  is less than a defined threshold  138 . The off-row scheme rule(s)  136  may indicate that the off-row scheme should be utilized when the difference between the previous version of a row  110  and the current version  142  of the row  110  is greater than the threshold  138 . The off-row scheme rule(s)  136  may also indicate that the off-row scheme should be utilized when additional metadata of the row needs to be stored that cannot be stored within the row  110  in accordance with the in-row scheme. There may be various reasons why such additional metadata cannot be stored within the row  110 . These reasons may be defined by the storage policy  116 . 
     The PVS modules  104  may also include one or more cleanup modules  113 . Older versions of data may not be needed after some period of time. The cleanup module  113  may facilitate deletion of the previous version information (both in-row previous version information  114  and off-row previous version information  115 ) that is no longer needed by the RDBMS  100 . In some implementations, the cleanup module  113  may take the form of one or more background processes within the RDBMS  100 . 
     To facilitate cleanup of older versions of data that are no longer needed, different types of tracking may be implemented. For example, the RDBMS  100  may track where the in-row previous version information  114  is created. Since the in-row previous version information  114  is stored within particular rows  110 , and the database can include a very large number (e.g., millions) of database pages  102 , the RDBMS  100  may track which database pages  102  have older in-row previous version information  114  that may be cleaned up. 
     The database may include one or more special pages referred to as page free space (PFS) pages  118 . PFS pages  118  may store metadata about database pages  102 . In some implementations, every database page  102  that is managed by the RDBMS  100  may be tracked in a PFS page  118 . For example, each database page  102  may have a record  120  that is associated with that database page  102  and that is included within a PFS page  118 . A record  120  within a PFS page  118  that is associated with a particular database page  102  may include an indicator  122  that provides information about whether that database page  102  includes in-row previous version information  114 . In some implementations, the indicator  122  may take the form of a single bit. Whenever a transaction produces new in-row previous version information  114  for a particular row  110  within a particular database page  102 , the transaction may update the indicator  122  within the corresponding PFS page  118  to indicate that there is in-row previous version information  114  for that database page  102 . 
     Another type of tracking may be related to what types of transactions are still interesting or useful to the RDBMS  100 . Every version of a row  110  may be tagged or otherwise associated with a transaction identifier (ID)  146 . Transaction IDs  146  may be monotonically increasing values. By considering which transactions and scans are considered active by the RDBMS  100 , it may be possible to determine the minimum useful transaction identifier (ID)  144  that is still interesting or useful to the RDBMS  100 . As long as the transaction ID  146  that is associated with a particular version of a row  110  exceeds the minimum useful transaction ID  144 , then that version of the row  110  may be maintained by the RDBMS  100 . 
     To facilitate cleanup, a cleanup module  113  may review the indicators  122  within the PFS pages  118  to identify what database pages  102  have in-row previous version information  114  associated with them. For each instance of in-row previous version information  114  that it finds, the cleanup module  113  may compare the transaction ID  146  that is associated with the in-row previous version information  114  with the minimum useful transaction ID  144  in order to determine whether the in-row previous version information  114  is still of interest to the RDBMS  100 . If the transaction ID  146  of the in-row previous version information  114  is less than the minimum useful transaction ID  144  (which indicates that the in-row previous version information  114  is not of interest to the RDBMS  100  and is therefore no longer needed), then the cleanup module  113  may delete the in-row previous version information  114 , thereby reclaiming the space on the database page  102  that was occupied by the in-row previous version information  114 . In addition to the cleanup module  113 , updates (e.g., transaction updates) to a database page  102  may also contribute to the cleanup of in-row previous version information  114 . 
     Cleanup of off-row previous version information  115  will now be discussed. The off-row pages  132  may store older versions from different objects (e.g., different tables) that are managed by the RDBMS  100 . Consequently, a single off-row page  132  may store off-row previous version information  115  corresponding to different rows  110  from different database pages  102 . 
     When a database transaction causes off-row previous version information  115  to be pushed to an off-row page  132 , the transaction may contribute its transaction ID  148  to the off-row page  132 . The RDBMS  100  may maintain off-row page tracking information  150  to track the off-row pages  132 . In some implementations, the off-row page tracking information  150  may take the form of a hash map. The off-row page tracking information  150  may indicate the maximum transaction identifier (ID) that is associated with each off-row page  132 . 
     For each off-row page  132 , the cleanup module  113  may compare the maximum transaction ID for the off-row page  132  with the minimum useful transaction ID  144 . When the maximum transaction ID associated with a particular off-row page  132  is less than the minimum useful transaction ID  144  (meaning that the off-row previous version information  115  stored on that off-row page  132  is no longer of interest to the RDBMS  100 ), that off-row page  132  can be reclaimed. In other words, the off-row previous version information  115  that is stored on that off-row page  132  can be deleted. 
     The cleanup of in-row previous version information  114  and off-row previous version information  115  may be different in some respects. For example, whereas specific instances of in-row previous version information  114  may be cleaned up, this may not be the case for off-row previous version information  115 . Instead, entire off-row pages  132  containing off-row previous version information  115  may be cleaned up. In other words, off-row previous version information  115  may be cleaned up at a page-level granularity, which may be beneficial both in terms of faster cleanup and reducing the amounts of log entries needed for cleanup. 
     There are a variety of factors that may contribute to determining the minimum useful transaction ID  144 . There may be various components that are each associated with some minimum useful transaction ID. For example, whenever a transaction is started (e.g., by a user or by the RDBMS  100  itself), the transaction may be tracked in a transaction map  152 . Every transaction may have a transaction ID, which may be a monotonically increasing number. Thus, each new transaction may be associated with a new, higher transaction ID. The minimum of all of the transaction IDs in the transaction map  152  is one component that may be used to determine the overall minimum useful transaction ID  144 . 
     As an example of another component, the RDBMS  100  may have user queries  154  may be reading data. The RDBMS  100  may include dependency tracking mechanisms that determine what the minimum useful transaction ID  144  is for these user queries  154 . In some implementations, there may be user queries  154  that are scanning the data not just on the local database but also on one or more remote database replicas. Dependency tracking mechanisms may be provided for these remote scanners as well. The minimum useful transaction ID  144  may be determined by taking the minimum of all of the various components. 
       FIGS. 2A and 2B  illustrate an example showing how a PFS page  218  may be utilized to facilitate tracking of in-row previous version information. Reference is initially made to  FIG. 2A . An RDBMS  200  may manage a plurality of database pages  202 , including a first database page  202   a , a second database page  202   b , and a third database page  202   c . The RDBMS  200  may also manage at least one PFS page  218 . The PFS page  218  may include a plurality of records  220 , each record  220  corresponding to a particular database page  202 . For example, the PFS page  218  may include a first record  220   a  corresponding to the first database page  202   a , a second record  220   b  corresponding to the second database page  202   b , and a third record  220   c  corresponding to the third database page  202   c.    
     In the depicted example, the first record  220   a  includes an indicator  222   a  that provides information about whether the first database page  202   a  includes any in-row previous version information. The indicator  222   b  in the second record  220   b  and the indicator  222   c  in the third record  220   c  provide similar information about the second database page  202   b  and the third database page  202   c , respectively. In some implementations, the indicators  222   a - c  may each be single bits. The RDBMS  200  may be configured such that when an indicator is set to a first value (e.g., “0”), this indicates that the corresponding database page  202  does not include in-row previous version information. Conversely, when an indicator is set to a second value (e.g., “1”), this indicates that the corresponding database page  202  includes in-row previous version information. In  FIG. 2A , the indicators  222   a - c  are each shown as having a value of “0”. For purposes of the present example, it will be assumed that this means that none of the corresponding database pages  202   a - c  include any in-row previous version information. 
     Reference is now made to  FIG. 2B . Suppose that a process  256  performs a transaction on the first database page  202   a , and that the transaction causes a row  210   a  within the first database page  202   a  to be updated to include in-row previous version information  214   a . To facilitate subsequent cleanup of the in-row previous version information  214   a , the process  256  that performs the transaction may also update the indicator  222   a  in the first record  220   a  (which corresponds to the first database page  202   a ) to reflect the fact that the first database page  202   a  includes in-row previous version information  214   a.    
       FIG. 3  illustrates an example showing different types of in-row previous version information that may be stored. A database page  302  may include a plurality of rows  310 , including a first row  310   a  and a second row  310   b . In the depicted example, both of the rows  310   a - b  include in-row previous version information  314   a - b  stored within the respective payloads  311   a - b , along with the current versions  342   a - b  of the rows  310   a - b . However, the in-row previous version information  314   a  that is stored within the first row  310   a  is the difference  358  between the current version  342   a  of the first row  310   a  and the previous version of the first row  310   a . In contrast, the in-row previous version information  314   b  that is stored within the second row  310   b  is the entire previous version  360  of the second row  310   b.    
     The example shown in  FIG. 3  also illustrates how in-row previous version information may be cleaned up. As indicated above, every version of a row  310  may be tagged or otherwise associated with a transaction ID. In the depicted example, the first row  310   a  is associated with a transaction ID  346   a  having a value of “4,” and the second row  310   b  is associated with a transaction ID  346   b  having a value of “5.” A cleanup module  313  may use the transaction IDs  346   a - b  to identify particular instances of in-row previous version information that may be cleaned up. 
     More specifically, the cleanup module  313  may determine (by referring to one or more PFS pages  118 , for example) that the first row  310   a  and the second row  310   b  include in-row previous version information  314   a - b . To determine whether the in-row previous version information  314   a  in the first row  310   a  may be cleaned up, the cleanup module  313  may compare the transaction ID  346   a  that is associated with the first row  310   a  with a minimum useful transaction ID  344  that is associated with the entire RDBMS  300 . If the transaction ID  346   a  associated with the first row  310   a  is greater than or equal to the minimum useful transaction ID  344 , this means that the previous version information  314   a  is still useful to the RDBMS  300  and should not be cleaned up. If, however, the transaction ID  346   a  associated with the first row  310   a  is less than the minimum useful transaction ID  344 , this means that the previous version information  314   a  is no longer useful to the RDBMS  300  and may be cleaned up. 
     In the depicted example, it will be assumed that the minimum useful transaction ID  344  for the entire RDBMS  300  is “5.” Because the transaction ID  346   a  associated with the first row  310   a  has a value of “4” and is therefore less than the minimum useful transaction ID  344  for the RDBMS  300 , the cleanup module  313  may delete the in-row previous version information  314   a  that is associated with the first row  310   a . To indicate this, the in-row previous version information  314   a  associated with the first row  310   a  is shown in dotted lines in  FIG. 3 . 
     On the other hand, the transaction ID  346   b  associated with the second row  310   b  has a value of “5,” which is equal to the minimum useful transaction ID  344 . Therefore, in this example the in-row previous version information  314   b  associated with the second row  310   b  is not eligible for cleanup. 
     Of course, the specific values (e.g., values of transaction IDs  346   a - b ) that are shown in this and other examples described herein should not be interpreted as limiting the scope of the present disclosure. Transaction IDs and other parameters may be assigned in a variety of different ways in accordance with the present disclosure. 
       FIG. 4  illustrates an example showing how off-row previous version information may be cleaned up. An off-row page  432  may include a plurality of different instances of off-row previous version information  415   a - b , which may be associated with different rows  410   a - b  and may correspond to different database pages  402   a - b . In the depicted example, the off-row page  432  includes a first instance of off-row previous version information  415   a  corresponding to a first row  410   a  in a first database page  402   a . The off-row page  432  also includes a second instance of off-row previous version information  415   b  corresponding to a second row  410   b  in a second database page  402   b.    
     As indicated above, when a database transaction causes off-row previous version information to be pushed to an off-row page  432 , the transaction may contribute its transaction ID to the off-row page  432 . In other words, the transaction ID that is associated with the transaction may also be associated with the off-row version information. Thus, each instance of off-row previous version information that is stored in the off-row page  432  may be associated with a different transaction identifier (ID). In the depicted example, the first off-row previous version information  415   a  is associated with a transaction ID  448   a  having a value of “8,” and the second off-row previous version information  415   b  is associated with a transaction ID  448   b  having a value of “3.” 
     The RDBMS  400  may utilize off-row page tracking information  450 , which may indicate the maximum transaction ID that is associated with each off-row page that is managed by the RDBMS  400 . For example, with respect to the off-row page  432  that is shown in  FIG. 4 , the off-row page tracking information  450  may include an identifier  464  that is associated with the off-row page  432 . This identifier  464  may be associated with the maximum transaction ID  466  that is included within the off-row page  432  (which is “8” in this example). 
     As indicated above, off-row previous version information may be cleaned up at a page-level granularity. In other words, a cleanup module  413  may be configured so that it either deletes all of the off-row previous version information  415   a - b  stored in a particular off-row page  432  (instead of deleting individual instances of the off-row previous version information  415   a - b ), or it does not delete any of the off-row previous version information  415   a - b  stored in the off-row page  432 . When a cleanup module  413  deletes all of the off-row previous version information  415   a - b  stored in an off-row page  432 , this may be referred to as deallocating the off-row page  432 . To determine whether a particular off-row page  432  should be deallocated, a cleanup module  413  may refer to the off-row page tracking information  450  to determine the maximum transaction ID  466  that is associated with the off-row page  432 . The maximum transaction ID  466  for the off-row page  432  may be compared with the minimum useful transaction ID  444  for the entire RDBMS  400 . If the maximum transaction ID  466  for the off-row page  432  is greater than or equal to the minimum useful transaction ID  444 , this means that the off-row page  432  includes at least some off-row previous version information  415   a - b  that is still useful to the RDBMS  400  and should not be cleaned up. If, however, the maximum transaction ID  466  for the off-row page  432  is less than the minimum useful transaction ID  444 , this means that none of the off-row previous version information  415   a - b  stored in the off-row page  432  is still useful to the RDBMS  400 , and as a result the off-row page  432  may be deallocated. In the depicted example, because the maximum transaction ID  466  for the off-row page  432  (“8”) is greater than the minimum useful transaction ID  444  for the RDBMS  400  (“5”), the cleanup module  413  may determine that the off-row page  432  should not be deallocated. 
       FIGS. 5A-G  illustrate an example showing how persistent version storage may be implemented in accordance with the present disclosure. The example involves a database page  502 . To facilitate the implementation of persistent version storage, an off-row page  532  and off-row page tracking information  550  may be utilized. 
     Reference is initially made to  FIG. 5A . Suppose that transaction T 1  inserts a first row  510   a  into the database page  502  and then commits. The current version of the first row  510   a  at this point in time may be designated as R 1 . Next, suppose that transaction T 2  (not shown) starts a snapshot scan and queries all rows within the system. 
     Reference is now made to  FIG. 5B . While transaction T 2  is still active, suppose that transaction T 3  updates the first row  510   a  and commits. The current version of the first row  510   a  at this point in time may be designated as R 1 ′. In-row previous version information  514   b  may be stored within the payload of the first row  510   a . The in-row previous version information  514   b  may be the difference between the current version of the first row  510   a  and the previous version of the first row  510   a  (i.e., R 1 ′−R 1 ). 
     Reference is now made to  FIG. 5C . Suppose that transaction T 4  updates the first row  510   a  such that the current version of the first row  510   a  at this point in time may be designated as R 1 ″. Further suppose that transaction T 4  commits. In response to this update, based on a storage policy that has been defined for the system, off-row previous version information  515   c  may be stored in the off-row page  532 . The off-row previous version information  515   c  may be associated with the transaction ID T 4  and may include the previous contents of the first row  510   a . The first row  510   a  still includes in-row previous version information  514   c , in the form of a pointer to the off-row previous version information  515   c.    
     The off-row page tracking information  550  indicates that the off-row page  532  is not eligible for cleanup. This may be because the off-row page  532  still has space to store additional off-row previous version information. 
     Next, suppose that transaction T 2  queries all rows within the system again, and then commits (or rolls back). Further suppose that transaction T 6  starts, and that T 6  is the minimum useful transaction ID for the system. A version cleaner (e.g., a cleanup module) may wake up at this point. The version cleaner may perform a scan of all PFS pages in the system, and as a result it may determine that the database page  502  includes in-row previous version information  514   c  (in the form of a pointer to the off-row previous version information  515   c ). 
     Reference is now made to  FIG. 5D . Because the first row  510   a  is associated with transaction T 4  (since transaction T 4  updated the first row  510   a  to R 1 ″), and because transaction T 4  is less than the minimum useful transaction ID for the system (which is T 6 ), the version cleaner deletes the in-row previous version information  514   c  (the pointer) from the first row  510   a . However, the version cleaner may choose not to deallocate the off-row page  532  because the off-row page  532  still has space to store additional off-row previous version information. 
     Next, suppose that transaction T 6  commits. Then, referring to  FIG. 5E , suppose that transaction T 7  inserts a second row  510   b  into the database page  502  and commits. The current version of the second row  510   b  at this point in time may be designated as R 2 . 
     Reference is now made to  FIG. 5F . Suppose that transaction T 8  updates R 2  to R 2 ′, and R 2  is pushed to the off-row page  532  as off-row previous version information  515   f . The second row  510   b  includes in-row previous version information  514   f  in the form of a pointer to the off-row previous version information  515   f . Further suppose that, due to the size of R 2 , the off-row page  532  is determined to be full with the addition of R 2 , such that the off-row page tracking information  550  indicates that the off-row page  532  is eligible for cleanup. Transaction T 8  then commits. 
     Reference is now made to  FIG. 5G . The background thread version cleaner wakes up and cleans the stale versions on the database page  502 . More specifically, it deletes the in-row previous version information  514   f  (the pointer) in the second row  510   b  because the transaction ID associated with the second row  510   b  is less than the minimum useful transaction ID for the system (T 9 ). The version cleaner also deallocates the off-row page  532  because the off-row page tracking information  550  indicates that the off-row page  532  is eligible for cleanup. 
       FIG. 6  illustrates an example of a method  600  for implementing persistent version storage in accordance with the present disclosure. The method  600  includes providing  602  a storage policy  116 . The storage policy  116  may include at least one rule  134  that defines when an in-row scheme is utilized to store in-row previous version information  114 . The storage policy  116  may also include at least one rule  136  that defines when an off-row scheme is utilized to store off-row previous version information  115 . As indicated above, the in-row scheme rule(s)  134  may indicate that the in-row scheme should be utilized when the difference between the previous version of a row  110  and the current version  142  of the row  110  is less than a defined threshold  138 . The off-row scheme rule(s)  136  may indicate that the off-row scheme should be utilized when the difference between the previous version of a row  110  and the current version  142  of the row  110  is greater than the threshold  138 . 
     When it is determined  604  that a database transaction has produced previous version information corresponding to a row  110  of a database page  102 , the method  600  may include evaluating  606  the in-row scheme rule(s)  134  and the off-row scheme rule(s)  136  to determine whether the previous version information should be stored as in-row previous version information  114  or off-row previous version information  115 . If at least one in-row scheme rule  134  is satisfied, the method  600  may include storing  608  the previous version information as in-row previous version information  114  within a payload  111  of the row  110  of the database page  102 . In contrast, if at least one off-row scheme rule  136  is satisfied, the method  600  may include storing  610  the previous version information as off-row previous version information  115  in a separate location, such as an off-row page  132 . 
     Persistent version storage, as described herein, may facilitate additional capabilities in a database system. For example, persistent version storage may facilitate instant transaction rollback and accelerated database crash recovery. Instead of walking the transaction log to rollback a transaction and restore original data in the database pages, persisted versions may be used to rollback transactions instantly by simply marking the current version as invalid, and using a lazy revert process to lazily move previously committed data from version store to database page. This also allows database crash recovery durations to be independent of the durations of long-running customer transactions since it removes the need to replay transaction logs from the point of the oldest active transaction. 
     As another example, persistent version storage may facilitate instant logical reversion of entities in the database. By allowing users to persist previous versions of data for a long time, logical objects such as rows, tables, and indexes can be instantly reverted to a previous version. This may be a beneficial alternative for users who have accidentally performed a wrong operation on their data and want to undo it. In current implementations it may be necessary to take a lengthy down time as they restore their database from backups through point-in-time restore. 
     As another example, persistent version storage may facilitate time travel queries. Persisted versions of data may be used to allow customers to query their tables as of a particular point in time, or query the historical values of rows to perform trend analysis. 
     As another example, persistent version storage may facilitate better resource and security isolation. In currently known implementations, the module(s) that provide version storage may be shared by all databases in a particular instance of the system. With persistent version storage functionality, each database may have its own version store. This may provide benefits for resource boundary and security isolation. 
     As another example, persistent version storage may facilitate better performance. As discussed above, persistent version storage may include two storage parts, an in-row part and off-row part. The in-row part may be located at the same data page. It may not require additional input/output for version access. In-row version applies to delete operations and row updates with certain limited size, such as the size of the difference between the current version of the row and the previous version of the row. If the size difference in the update is greater than the limit of in-row storage, it may be stored in the off-row version store. Some special usage of versioning may also push the version to the off-row store. 
       FIG. 7  illustrates certain components that may be included within a computer system  700 . One or more computer systems  700  may be used to implement the various devices, components, and systems described herein. 
     The computer system  700  includes a processor  701 . The processor  701  may be a general purpose single- or multi-chip microprocessor (e.g., an Advanced RISC (Reduced Instruction Set Computer) Machine (ARM)), a special purpose microprocessor (e.g., a digital signal processor (DSP)), a microcontroller, a programmable gate array, etc. The processor  701  may be referred to as a central processing unit (CPU). Although just a single processor  701  is shown in the computer system  700  of  FIG. 7 , in an alternative configuration, a combination of processors (e.g., an ARM and DSP) could be used. 
     The computer system  700  also includes memory  703  in electronic communication with the processor  701 . The memory  703  may be any electronic component capable of storing electronic information. For example, the memory  703  may be embodied as random access memory (RAM), read-only memory (ROM), magnetic disk storage media, optical storage media, flash memory devices in RAM, on-board memory included with the processor, erasable programmable read-only memory (EPROM), electrically erasable programmable read-only memory (EEPROM) memory, registers, and so forth, including combinations thereof. 
     Instructions  705  and data  707  may be stored in the memory  703 . The instructions  705  may be executable by the processor  701  to implement some or all of the functionality disclosed herein. Executing the instructions  705  may involve the use of the data  707  that is stored in the memory  703 . Any of the various examples of modules and components described herein may be implemented, partially or wholly, as instructions  705  stored in memory  703  and executed by the processor  701 . Any of the various examples of data described herein may be among the data  707  that is stored in memory  703  and used during execution of the instructions  705  by the processor  701 . 
     A computer system  700  may also include one or more communication interfaces  709  for communicating with other electronic devices. The communication interface(s)  709  may be based on wired communication technology, wireless communication technology, or both. Some examples of communication interfaces  709  include a Universal Serial Bus (USB), an Ethernet adapter, a wireless adapter that operates in accordance with an Institute of Electrical and Electronics Engineers (IEEE) 802.11 wireless communication protocol, a Bluetooth wireless communication adapter, and an infrared (IR) communication port. 
     A computer system  700  may also include one or more input devices  711  and one or more output devices  713 . Some examples of input devices  711  include a keyboard, mouse, microphone, remote control device, button, joystick, trackball, touchpad, and lightpen. Some examples of output devices  713  include a speaker and a printer. One specific type of output device that is typically included in a computer system  700  is a display device  715 . Display devices  715  used with embodiments disclosed herein may utilize any suitable image projection technology, such as liquid crystal display (LCD), light-emitting diode (LED), gas plasma, electroluminescence, or the like. A display controller  717  may also be provided, for converting data  707  stored in the memory  703  into text, graphics, and/or moving images (as appropriate) shown on the display device  715 . 
     The various components of the computer system  700  may be coupled together by one or more buses, which may include a power bus, a control signal bus, a status signal bus, a data bus, etc. For the sake of clarity, the various buses are illustrated in  FIG. 8  as a bus system  719 . 
     In accordance with an aspect of the present disclosure, a relational database system that implements persistent version storage is disclosed. The relational database system may include one or more processors and memory in electronic communication with the one or more processors. The relational database system may also include an in-row module, an off-row module, and a storage policy stored in the memory. The in-row module may be executable by the one or more processors to implement an in-row scheme by storing in-row previous version information within a payload of a row within a database page. The off-row module may be executable by the one or more processors to implement an off-row scheme by storing off-row previous version information in an off-row page that is separate from the database page. The storage policy may define when previous version information is stored in accordance with the in-row scheme and when the previous version information is stored in accordance with the off-row scheme. 
     In some implementations, the in-row previous version information may include a difference between a current version of the row and a previous version of the row. As another example, the in-row previous version information may include a previous version of the row. 
     The storage policy may include at least one in-row scheme rule indicating that the in-row scheme is utilized when a difference between a previous version of the row and a current version of the row is less than a defined threshold. The storage policy may additionally include at least one off-row scheme rule indicating that the off-row scheme is utilized when the difference between the previous version of the row and the current version of the row is greater than the defined threshold, or when additional metadata of the row needs to be stored that cannot be stored in the row. 
     A cleanup module may be stored in the memory. The cleanup module may be executable by the one or more processors to delete the previous version information that is no longer needed. In some implementations, the cleanup module may be additionally executable by the one or more processors to determine a minimum useful transaction identifier for the relational database system, compare a transaction identifier associated with the row with the minimum useful transaction identifier, and delete the in-row previous version information if the transaction identifier is less than the minimum useful transaction identifier. 
     The relational database system may further include an off-row page stored in the memory. The off-row page may store a plurality of different instances of the off-row previous version information. The plurality of different instances of the off-row previous version information may correspond to different rows. Each instance of the off-row previous version information may be associated with a different transaction identifier. The cleanup module may be executable by the one or more processors to determine a minimum useful transaction identifier for the relational database system, determine a maximum transaction identifier for the off-row page, compare the minimum useful transaction identifier for the relational database system with the maximum transaction identifier for the off-row page, and deallocate the off-row page if the maximum transaction identifier for the off-row page is less than the minimum useful transaction identifier for the relational database system. 
     The relational database system may further include a plurality of database pages stored in the memory, at least one page free space (PFS) page stored in the memory, and instructions stored in the memory. The at least one PFS page may include a record for each of the plurality of database pages. The record associated with a database page may indicate whether the database page is associated with any in-row previous version information. The instructions may be executable by the one or more processors to update the indicator corresponding to the database page when a database transaction produces new in-row previous version information for the database page. 
     In accordance with another aspect of the present disclosure, a method for implementing persistent version storage is disclosed. The method may include providing a storage policy. The storage policy may include at least one in-row scheme rule that defines when an in-row scheme is utilized to store in-row previous version information. The storage policy may further include at least one off-row scheme rule that defines when an off-row scheme is utilized to store off-row previous version information. The method may further include storing the in-row previous version information within a payload of a row of a database page in accordance with the in-row scheme when an in-row scheme rule is satisfied, and storing the off-row previous version information in a separate off-row page in accordance with the off-row scheme when an off-row scheme rule is satisfied. The method may further include deleting previous version information that is no longer needed. 
     The in-row previous version information may include at least one of a difference between a current version of the row and a previous version of the row, or the previous version of the row. 
     The at least one in-row scheme rule may indicate that the in-row scheme is utilized when a difference between a previous version of the row and a current version of the row is less than a defined threshold. The at least one off-row scheme rule may indicate that the off-row scheme is utilized when the difference between the previous version of the row and the current version of the row is greater than the defined threshold, or when additional metadata of the row needs to be stored that cannot be stored in the row. 
     The method may further include determining a minimum useful transaction identifier, comparing a transaction identifier associated with the row with the minimum useful transaction identifier, and deleting the in-row previous version information if the transaction identifier is less than the minimum useful transaction identifier. 
     The method may further include determining a minimum useful transaction identifier, determining a maximum transaction identifier for the off-row page, comparing the minimum useful transaction identifier with the maximum transaction identifier for the off-row page, and deallocating the off-row page if the maximum transaction identifier for the off-row page is less than the minimum useful transaction identifier. 
     In accordance with another aspect of the present disclosure, a relational database system that implements persistent version storage is disclosed. The relational database system may include one or more processors and memory in electronic communication with the one or more processors. The relational database system may also include a plurality of database pages and a storage policy stored in the memory. The storage policy may include at least one in-row scheme rule that defines when an in-row scheme is utilized to store in-row previous version information. The storage policy may further include at least one off-row scheme rule that defines when an off-row scheme is utilized to store off-row previous version information. Instructions may also be stored in the memory. The instructions may be executable by the one or more processors to store the in-row previous version information within a payload of a row of a database page in accordance with the in-row scheme when an in-row scheme rule is satisfied, and store the off-row previous version information in a separate off-row page in accordance with the off-row scheme when the an off-row scheme rule is satisfied. The instructions may be additionally executable by the one or more processors to delete previous version information that is no longer needed. 
     The in-row previous version information may include at least one of a difference between a current version of the row and a previous version of the row, or the previous version of the row. 
     The at least one in-row scheme rule may indicate that the in-row scheme is utilized when a difference between a previous version of the row and a current version of the row is less than a defined threshold. The at least one off-row scheme rule may indicate that the off-row scheme is utilized when the difference between the previous version of the row and the current version of the row is greater than the defined threshold, or when additional metadata of the row needs to be stored that cannot be stored in the row. 
     The instructions may be additionally executable by the one or more processors to determine a minimum useful transaction identifier, compare a transaction identifier associated with the row with the minimum useful transaction identifier, and delete the in-row previous version information if the transaction identifier is less than the minimum useful transaction identifier. 
     The instructions may be additionally executable by the one or more processors to determine a minimum useful transaction identifier, determine a maximum transaction identifier for the off-row page, compare the minimum useful transaction identifier with the maximum transaction identifier for the off-row page, and deallocate the off-row page if the maximum transaction identifier for the off-row page is less than the minimum useful transaction identifier. 
     The techniques described herein may be implemented in hardware, software, firmware, or any combination thereof, unless specifically described as being implemented in a specific manner. Any features described as modules, components, or the like may also be implemented together in an integrated logic device or separately as discrete but interoperable logic devices. If implemented in software, the techniques may be realized at least in part by a non-transitory processor-readable storage medium comprising instructions that, when executed by at least one processor, perform one or more of the methods described herein. The instructions may be organized into routines, programs, objects, components, data structures, etc., which may perform particular tasks and/or implement particular data types, and which may be combined or distributed as desired in various embodiments. 
     The steps and/or actions of the methods described herein may be interchanged with one another without departing from the scope of the claims. In other words, unless a specific order of steps or actions is required for proper operation of the method that is being described, the order and/or use of specific steps and/or actions may be modified without departing from the scope of the claims. 
     The term “determining” encompasses a wide variety of actions and, therefore, “determining” can include calculating, computing, processing, deriving, investigating, looking up (e.g., looking up in a table, a database or another data structure), ascertaining and the like. Also, “determining” can include receiving (e.g., receiving information), accessing (e.g., accessing data in a memory) and the like. Also, “determining” can include resolving, selecting, choosing, establishing and the like. 
     The terms “comprising,” “including,” and “having” are intended to be inclusive and mean that there may be additional elements other than the listed elements. Additionally, it should be understood that references to “one embodiment” or “an embodiment” of the present disclosure are not intended to be interpreted as excluding the existence of additional embodiments that also incorporate the recited features. For example, any element or feature described in relation to an embodiment herein may be combinable with any element or feature of any other embodiment described herein, where compatible. 
     The present disclosure may be embodied in other specific forms without departing from its spirit or characteristics. The described embodiments are to be considered as illustrative and not restrictive. The scope of the disclosure is, therefore, indicated by the appended claims rather than by the foregoing description. Changes that come within the meaning and range of equivalency of the claims are to be embraced within their scope.