https://xmpp.org/extensions/xep-0313.html presents messages as an ordered list which the client can fetch partially. However when it comes to storing these messages there are various considerations around how to sort them for various purposes.
When Syncing Forwards
When syncing forwards from a previously known ID (or from a chosen time in the past / number of messages into the past forwards into an otherwise empty storage) an incrementing counter suffices. The last message (and thus the one to sync from in the future) is the one with the highest counter. For display purposes you may or may not want to order by other factors instead (delayed time sent, etc)
When Syncing Backwards
When syncing backwards from a previously known ID, a decrementing counter suffices. The counter must be signed so that if you sync back further than you did when you initially filled your storage from empty you can use negative counts to keep sort order correct.
When Syncing Forwards From a Hole
A "hole" can be created forwards when the client chooses to sync from a chosen time in the past (or number of messages in the past) into a non-empty store. If the results overlap with existing messages this will not create a hole and we are back in regular Syncing Forwards. If the results do not overlap, then there may be messages unaccounted for between what was previously known and what is now being stored. Simply incrementing the counter from what was previously there would erase the ability to insert messages in this space (and thus "fill the hole"). So instead, introduce a second counter, call it a "generation counter". When filling an empty storage set this generation to zero. When creating a hole going forwards, increment the generation and start the regular counter over from zero. In this way one can still sync forwards from the known messages before the hole, and increment inside their generation, and backwards from the start of the messages after the hole, and decrement inside the new generation.
When Syncing Backwards From a Hole
A "hole" can be created backwards when the client chooses to sync from a chosen time (or other point) before all known messages into a non-empty store. Decrement the generation counter and reset the regular counter to zero.
When Syncing Inside a Hole
If you fetch messages in the middle of an existing hole (that is, not starting from either end of the hole) you may end up "splitting" the hole into two holes. An integer generation counter is no longer sufficient as we would have no way to insert a generation between two existing generations to delineate the new holes. Instead we can compute a fractional generation counter this way:
f(beforeHoleG, afterHoleG) = (beforeHoleG + afterHoleG) / 2
Alternatively, we can avoid both using fractions and needing to know about both ends of the hole if we instead renumber all bigger holes, for example in SQL one could:
UPDATE messages SET generation = generation + 1 WHERE generation > hole_generation;