Recovery of a database system by taking the database system offline is initiated. Thereafter, recovery operations specified by a redo log of the database system are replayed. A cleanup log is generated that identifies cleanup operations occurring during the replay of the recovery operations for garbage collection. Concurrent with the startup of the database, garbage collection of the cleanup operations as specified in the database savepoint is initiated. In addition, concurrent with the replay of the recovery operations, garbage collection of the cleanup operations specified by the cleanup log is initiated. The amount of parallelization of the garbage collection can be varied based on utilized processor resources. The database system is later brought online after all of the recovery operations are replayed.