I'm trying to understand how Transaction IDs are compared in Postgres

I have a two questions

  1. Transaction IDs (XIDs) are represented in 32 bits. Therefore there can be a maximum of 4,294,967,296 XIDs. Why is a wraparound possible at two billion XIDs?

  2. How are XIDs compared?

Consider that there are only 3 bits to represent XIDs allowing the following values for XID - 0,1,2,3,4,5,6,7.

Before a wraparound XIDs can be simply compared x < y.

However after a wraparound, say the last XID was 7 and the next XID would be 1. How will these be compared to establish that XID 1 is greater than XID 7 (to allow visibility of the row with xmin as 7)

In my research I came across the following but I'm at a loss how the comparison works

From the Postgres docs

Normal XIDs are compared using modulo-2^32 arithmetic. This means that for every normal XID, there are two billion XIDs that are “older” and two billion that are “newer”; another way to say it is that the normal XID space is circular with no endpoint

From a post by Tom Lane

Ordered comparisons on XIDs are no longer simply "x < y", but need to be expressed as a macro. We consider x < y if (y - x) % WRAPLIMIT < WRAPLIMIT/2. This comparison will work as long as the range of interesting XIDs never exceeds WRAPLIMIT/2

  • Are you asking conceptually, or the actual implementation? Your first quote seems to exactly answer your question conceptually. For the implementation, you should see the actual code, not very old proposal which was not adopted verbatim. git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=bc7d37a5 – jjanes Apr 19 at 14:54
  • Thanks @jjanes. I was not able to understand the modulo arithmetic operations. Using the formula in the second quote x < y if (y - x) % WRAPLIMIT < WRAPLIMIT/2 I can now understand how order is preserved between XIDs even after a wraparound. – dsinecos Apr 20 at 9:30
  • Thanks for sharing the code commit. I'll have a look :) – dsinecos Apr 20 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.