A data store maintaining data may implement memory-based on-demand data page generation. Log records may be maintained in system memory according to a version threshold for data pages of data stored in persistent storage. When a request for a version of a particular data page is received that is within the version threshold, the data page may be obtained from persistent storage and log records associated with the data page may be applied to the data page to generate the requested version of the data page. The version threshold for the data pages may change, and log records in system memory may be identified for coalesce operations. The coalesce operations may be efficiently performed (e.g., in the background), updating the data pages in persistent storage to include the changes of the identified log records and space in system memory for the identified log records may be reclaimed.