A relational database system that implements persistent version storage may include an in-row module that is executable by 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 relational database system may additionally include 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. The relational database system may additionally include a storage policy that defines 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. The relational database system may additionally include a cleanup module that cleans up older versions when they are deemed unnecessary by the system.