I suspect that the following O(n) iteration in a critical section of buf_pool.flush_list_mutex in page_cleaner_flush_pages_recommendation() could be replaced with an O(log n) binary search when we switch to a priority queue:

	for (buf_page_t* b = UT_LIST_GET_LAST(buf_pool.flush_list);

	     b != NULL;

	     b = UT_LIST_GET_PREV(list, b)) {

		if (b->oldest_modification() > target_lsn) {

			break;

		}

		++pages_for_lsn;

	}

STL priority_queue does not have an interface to iterate over it. you can access the top element though. Although, it is probably possible to derive from STL priority_queue and rely on the fact that underlying container is organized as heap structure. then I guess it would be possible to iterate

We could ‘manually’ create something similar to std::priority_queue, possibly by making use of std::make_heap, which works with random access iterators.

In a perf record trace of the server with some work-in-progress MDEV-23399 changes, the page cleaner seems to be spending most of its CPU cycles in that page_cleaner_flush_pages_recommendation() loop and also some in buf_flush_check_neighbors(). For neighbor flushing (which is always disabled on SSD), we cannot entirely avoid buf_pool.page_hash lookups, but we might reduce their amount by checking if the neighbor pages happen to be adjacent elements in the priority queue (with the same oldest_modification, which could be rare).

We might solve MDEV-12227 as part of this task by ensuring that pages of the temporary tablespace will be added at the end of the priority queue (pretending that oldest_modification=LSN_MAX).

But, I would still think that we’d better write the pages of temporary tables solely via the LRU eviction mechanism, that is, keep them entirely out of the buf_pool.flush_list or its replacement. So, it might be better to implement MDEV-12227 before this task.

It turns out that the buf_pool.flush_list actually is already ORDER BY oldest_modification DESC (most recently dirtied blocks are added first). Blocks are added by mtr_t::commit(), and the LSN would always be incremented between mtr_t::commit(), unless we have several mini-transactions that only modified pages in the temporary tablespace (which per MDEV-12227 maybe should not reside in the buf_pool.flush_list at all). So, the ORDER BY oldest_modification DESC is guaranteed by design.

What we can do is the following:

1. MDEV-23399 will remove the buf_pool.flush_rbt and relax the debug assertion in buf_flush_validate_low() so that random ordering will be allowed when applying redo log records.
2. At the end of redo log processing, we will flush the buffer pool and re-enable the check. (This is unchanged from earlier, where we had to flush the buffer pool in order to empty the recovery-time buf_pool.flush_rbt.)
3. In MDEV-14481 we will remove that extra flush by adding a step where the last recovery batch will sort the buf_pool.flush_list.
4. After MDEV-12227, pages of temporary tablespaces should not be added to buf_pool.flush_list, and both buf_flush_wait_flushed() and buf_pool_t::get_oldest_modification() can simply access the last element.
5. As part of this task, mtr_t::commit() might add the dirty pages to the buf_pool.flush_list ordered by page number.

Currently it looks like there is not much that can be done as part of this task. The doubly-linked list should remain an optimal data structure for this purpose.

Sorry, I should have done more research before filing this.