A relational database system that implements persistent version storage, comprising: one or more processors; memory in electronic communication with the one or more processors; a plurality of database pages stored in the memory; an in-row module that is 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 of the plurality of database pages; an off-row module that is 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; and a storage policy stored in the memory, the storage policy defining 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, wherein the relational database system further comprises: at least one page free space, PFS, page stored in the memory, wherein the at least one PFS page comprises a record for each of the plurality of database pages, and wherein each record includes an indicator that indicates whether the respective associated database page includes any in-row previous version information; and instructions stored in the memory, the instructions being 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, wherein the relational database system further comprises a cleanup module stored in the memory, wherein the cleanup module is executable by the one or more processors to delete in-row previous version information that is no longer needed, and wherein deleting the in-row previous version information includes reviewing the indicators within the at least one PFS page to identify what database pages of the plurality of database pages have in-row previous version information associated with them. one or more processors; memory in electronic communication with the one or more processors; a plurality of database pages stored in the memory; an in-row module that is 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 of the plurality of database pages; an off-row module that is 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; and a storage policy stored in the memory, the storage policy defining 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, wherein the relational database system further comprises: at least one page free space, PFS, page stored in the memory, wherein the at least one PFS page comprises a record for each of the plurality of database pages, and wherein each record includes an indicator that indicates whether the respective associated database page includes any in-row previous version information; and instructions stored in the memory, the instructions being 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, wherein the relational database system further comprises a cleanup module stored in the memory, wherein the cleanup module is executable by the one or more processors to delete in-row previous version information that is no longer needed, and wherein deleting the in-row previous version information includes reviewing the indicators within the at least one PFS page to identify what database pages of the plurality of database pages have in-row previous version information associated with them. at least one page free space, PFS, page stored in the memory, wherein the at least one PFS page comprises a record for each of the plurality of database pages, and wherein each record includes an indicator that indicates whether the respective associated database page includes any in-row previous version information; and instructions stored in the memory, the instructions being 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, wherein the relational database system further comprises a cleanup module stored in the memory, wherein the cleanup module is executable by the one or more processors to delete in-row previous version information that is no longer needed, and wherein deleting the in-row previous version information includes reviewing the indicators within the at least one PFS page to identify what database pages of the plurality of database pages have in-row previous version information associated with them.