Bug in autovacuum.c?

On Thu, Mar 31, 2011 at 12:17 PM, Bruce Momjian <bruce@momjian.us> wrote:

Looking over the autovacuum.c code, I see:

   /*
    * Determine the oldest datfrozenxid/relfrozenxid that we will allow to
    * pass without forcing a vacuum.  (This limit can be tightened for
    * particular tables, but not loosened.)
    */
   recentXid = ReadNewTransactionId();
   xidForceLimit = recentXid - autovacuum_freeze_max_age;
   /* ensure it's a "normal" XID, else TransactionIdPrecedes misbehaves */
   if (xidForceLimit < FirstNormalTransactionId)
       xidForceLimit -= FirstNormalTransactionId;

This last line doesn't look right to me;  should it be:

       xidForceLimit = FirstNormalTransactionId;

That would probably work, but the existing coding actually makes more
sense. It's essentially trying to scan backwards by
autovacuum_freeze_max_age XIDs through the circular XID space. But
the XID space isn't actually circular, because there are 3 special
values. So if we land on one of those values we want to skip backward
by 3. Here FirstNormalTransactionId doesn't represent itself, but
rather the number of special XIDs that exist.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Excerpts from Robert Haas's message of jue mar 31 13:58:41 -0300 2011:

On Thu, Mar 31, 2011 at 12:17 PM, Bruce Momjian <bruce@momjian.us> wrote:

Looking over the autovacuum.c code, I see:

   /*
    * Determine the oldest datfrozenxid/relfrozenxid that we will allow to
    * pass without forcing a vacuum.  (This limit can be tightened for
    * particular tables, but not loosened.)
    */
   recentXid = ReadNewTransactionId();
   xidForceLimit = recentXid - autovacuum_freeze_max_age;
   /* ensure it's a "normal" XID, else TransactionIdPrecedes misbehaves */
   if (xidForceLimit < FirstNormalTransactionId)
       xidForceLimit -= FirstNormalTransactionId;

This last line doesn't look right to me;  should it be:

       xidForceLimit = FirstNormalTransactionId;

That would probably work, but the existing coding actually makes more
sense. It's essentially trying to scan backwards by
autovacuum_freeze_max_age XIDs through the circular XID space. But
the XID space isn't actually circular, because there are 3 special
values. So if we land on one of those values we want to skip backward
by 3. Here FirstNormalTransactionId doesn't represent itself, but
rather the number of special XIDs that exist.

Yeah, I think this change would have the effect of moving the freeze
limit by one (or two?) counts. Given the moving nature of values
returned by ReadNewTransactionId this would probably have no practical
effect. Still, the code as is seems more natural to me (Tom wrote this
bit IIRC, not me).

--
Álvaro Herrera <alvherre@commandprompt.com>
The PostgreSQL Company - Command Prompt, Inc.
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

Alvaro Herrera wrote:

That would probably work, but the existing coding actually makes more
sense. It's essentially trying to scan backwards by
autovacuum_freeze_max_age XIDs through the circular XID space. But
the XID space isn't actually circular, because there are 3 special
values. So if we land on one of those values we want to skip backward
by 3. Here FirstNormalTransactionId doesn't represent itself, but
rather the number of special XIDs that exist.

Yeah, I think this change would have the effect of moving the freeze
limit by one (or two?) counts. Given the moving nature of values
returned by ReadNewTransactionId this would probably have no practical
effect. Still, the code as is seems more natural to me (Tom wrote this
bit IIRC, not me).

I am now thinking the code is correct --- it maps values from 0 to
FirstNormalTransactionId into the top of the (unsigned) xid range.
Unless someone objects, I will add a C comment about this behavior so
future readers are not confused.

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +

Bruce Momjian wrote:

Yeah, I think this change would have the effect of moving the freeze
limit by one (or two?) counts. Given the moving nature of values
returned by ReadNewTransactionId this would probably have no practical
effect. Still, the code as is seems more natural to me (Tom wrote this
bit IIRC, not me).

I am now thinking the code is correct --- it maps values from 0 to
FirstNormalTransactionId into the top of the (unsigned) xid range.
Unless someone objects, I will add a C comment about this behavior so
future readers are not confused.

OK, now I think it is wrong. :-)

The effect is to map max xid + 1 to max xid -
FirstNormalTransactionId(3) + 1, which makes the xid look like it is
going backwards, less than max xid --- not good.

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +

On Thu, Mar 31, 2011 at 2:59 PM, Bruce Momjian <bruce@momjian.us> wrote:

Bruce Momjian wrote:

Yeah, I think this change would have the effect of moving the freeze
limit by one (or two?) counts.  Given the moving nature of values
returned by ReadNewTransactionId this would probably have no practical
effect.  Still, the code as is seems more natural to me (Tom wrote this
bit IIRC, not me).

I am now thinking the code is correct --- it maps values from 0 to
FirstNormalTransactionId into the top of the (unsigned) xid range.
Unless someone objects, I will add a C comment about this behavior so
future readers are not confused.

OK, now I think it is wrong.   :-)

The effect is to map max xid + 1 to max xid -
FirstNormalTransactionId(3) + 1, which makes the xid look like it is
going backwards, less than max xid --- not good.

The XID space is *circular*.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas wrote:

On Thu, Mar 31, 2011 at 2:59 PM, Bruce Momjian <bruce@momjian.us> wrote:

Bruce Momjian wrote:

Yeah, I think this change would have the effect of moving the freeze
limit by one (or two?) counts. ?Given the moving nature of values
returned by ReadNewTransactionId this would probably have no practical
effect. ?Still, the code as is seems more natural to me (Tom wrote this
bit IIRC, not me).

I am now thinking the code is correct --- it maps values from 0 to
FirstNormalTransactionId into the top of the (unsigned) xid range.
Unless someone objects, I will add a C comment about this behavior so
future readers are not confused.

OK, now I think it is wrong. ? :-)

The effect is to map max xid + 1 to max xid -
FirstNormalTransactionId(3) + 1, which makes the xid look like it is
going backwards, less than max xid --- not good.

The XID space is *circular*.

Right but you would think that as the xid moves forward, the caculation
of how far back to vacuum should move only forward. In this case,
incrementing the xid by one would cause the vacuum horizon to move
backward by two.

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +

On Thu, Mar 31, 2011 at 4:16 PM, Bruce Momjian <bruce@momjian.us> wrote:

Robert Haas wrote:

On Thu, Mar 31, 2011 at 2:59 PM, Bruce Momjian <bruce@momjian.us> wrote:

Bruce Momjian wrote:

Yeah, I think this change would have the effect of moving the freeze
limit by one (or two?) counts. ?Given the moving nature of values
returned by ReadNewTransactionId this would probably have no practical
effect. ?Still, the code as is seems more natural to me (Tom wrote this
bit IIRC, not me).

I am now thinking the code is correct --- it maps values from 0 to
FirstNormalTransactionId into the top of the (unsigned) xid range.
Unless someone objects, I will add a C comment about this behavior so
future readers are not confused.

OK, now I think it is wrong. ? :-)

The effect is to map max xid + 1 to max xid -
FirstNormalTransactionId(3) + 1, which makes the xid look like it is
going backwards, less than max xid --- not good.

The XID space is *circular*.

Right but you would think that as the xid moves forward, the caculation
of how far back to vacuum should move only forward.  In this case,
incrementing the xid by one would cause the vacuum horizon to move
backward by two.

I don't see how that would happen. The XID immediately preceding
FirstNormalTransactionId is 2^32-1, and that's exactly what this
calculation produces.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas wrote:

The effect is to map max xid + 1 to max xid -
FirstNormalTransactionId(3) + 1, which makes the xid look like it is
going backwards, less than max xid --- not good.

The XID space is *circular*.

Right but you would think that as the xid moves forward, the caculation
of how far back to vacuum should move only forward. ?In this case,
incrementing the xid by one would cause the vacuum horizon to move
backward by two.

I don't see how that would happen. The XID immediately preceding
FirstNormalTransactionId is 2^32-1, and that's exactly what this
calculation produces.

OK, let me see if I understand --- the caculation is below:

xidForceLimit = recentXid - autovacuum_freeze_max_age;
if (xidForceLimit < FirstNormalTransactionId)
xidForceLimit -= FirstNormalTransactionId;

The values:

xidForceLimit Result
---------------------------
max_xid-2 max_xid-2
max_xid-1 max_xid-1
max_xid max_xid
0 max_xid-3 <- backward here
1 max_xid-2
2 max_xid-1
3 3

With the -= change to =, we get:

xidForceLimit Result
---------------------------
max_xid-2 max_xid-2
max_xid-1 max_xid-1
max_xid max_xid
0 3
1 3
2 3
3 3

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +

On Thu, Mar 31, 2011 at 4:35 PM, Bruce Momjian <bruce@momjian.us> wrote:

Robert Haas wrote:

The effect is to map max xid + 1 to max xid -
FirstNormalTransactionId(3) + 1, which makes the xid look like it is
going backwards, less than max xid --- not good.

The XID space is *circular*.

Right but you would think that as the xid moves forward, the caculation
of how far back to vacuum should move only forward. ?In this case,
incrementing the xid by one would cause the vacuum horizon to move
backward by two.

I don't see how that would happen.   The XID immediately preceding
FirstNormalTransactionId is 2^32-1, and that's exactly what this
calculation produces.

OK, let me see if I understand --- the caculation is below:

   xidForceLimit = recentXid - autovacuum_freeze_max_age;
   if (xidForceLimit < FirstNormalTransactionId)
       xidForceLimit -= FirstNormalTransactionId;

The values:

       xidForceLimit   Result
       ---------------------------
       max_xid-2       max_xid-2
       max_xid-1       max_xid-1
       max_xid         max_xid
       0               max_xid-3       <- backward here
       1               max_xid-2
       2               max_xid-1
       3               3

You have to consider those three lines all of a piece. Suppose
autovacuum_freeze_age is 100. Then:

105 -> 5
104 -> 4
103 -> 3
102 -> max_xid
101 -> max_xid - 1
100 -> max_xid - 2

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas wrote:

? ?xidForceLimit = recentXid - autovacuum_freeze_max_age;
? ?if (xidForceLimit < FirstNormalTransactionId)
? ? ? ?xidForceLimit -= FirstNormalTransactionId;

The values:

? ? ? ?xidForceLimit ? Result
? ? ? ?---------------------------
? ? ? ?max_xid-2 ? ? ? max_xid-2
? ? ? ?max_xid-1 ? ? ? max_xid-1
? ? ? ?max_xid ? ? ? ? max_xid
? ? ? ?0 ? ? ? ? ? ? ? max_xid-3 ? ? ? <- backward here
? ? ? ?1 ? ? ? ? ? ? ? max_xid-2
? ? ? ?2 ? ? ? ? ? ? ? max_xid-1
? ? ? ?3 ? ? ? ? ? ? ? 3

You have to consider those three lines all of a piece. Suppose
autovacuum_freeze_age is 100. Then:

105 -> 5
104 -> 4
103 -> 3
102 -> max_xid
101 -> max_xid - 1
100 -> max_xid - 2

OK, just keep going below 100:

105 -> 5
104 -> 4
103 -> 3
102 -> max_xid
101 -> max_xid - 1
100 -> max_xid - 2
99 -> max_id
98 -> max_id -1

Wouldn't you rather:

105 -> 5
104 -> 4
103 -> 3
102 -> 3
101 -> 3
100 -> 3
99 -> max_id
98 -> max_id -1

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +

On Thu, Mar 31, 2011 at 10:59 PM, Bruce Momjian <bruce@momjian.us> wrote:

OK, just keep going below 100:

       105 -> 5
       104 -> 4
       103 -> 3
       102 -> max_xid
       101 -> max_xid - 1
       100 -> max_xid - 2
        99 -> max_id
        98 -> max_id -1

Yeah, I think this is what the code is doing.

Wouldn't you rather:

       105 -> 5
       104 -> 4
       103 -> 3
       102 -> 3
       101 -> 3
       100 -> 3
        99 -> max_id
        98 -> max_id -1

I think I would expect

       105 -> 5
       104 -> 4
       103 -> 3
       102 -> max_id
       101 -> max_id-1
       100 -> max_id-2
        99 -> max_id-3

But it doesn't really matter either way, does it? We don't even allow
setting vacuum_max_freeze_age to 2^31-1 or any value that would be
close to triggering a problem here.

--
greg

Greg Stark wrote:

On Thu, Mar 31, 2011 at 10:59 PM, Bruce Momjian <bruce@momjian.us> wrote:

OK, just keep going below 100:

? ? ? ?105 -> 5
? ? ? ?104 -> 4
? ? ? ?103 -> 3
? ? ? ?102 -> max_xid
? ? ? ?101 -> max_xid - 1
? ? ? ?100 -> max_xid - 2
? ? ? ? 99 -> max_id
? ? ? ? 98 -> max_id -1

Yeah, I think this is what the code is doing.

Wouldn't you rather:

? ? ? ?105 -> 5
? ? ? ?104 -> 4
? ? ? ?103 -> 3
? ? ? ?102 -> 3
? ? ? ?101 -> 3
? ? ? ?100 -> 3
? ? ? ? 99 -> max_id
? ? ? ? 98 -> max_id -1

I think I would expect

? ? ? ?105 -> 5
? ? ? ?104 -> 4
? ? ? ?103 -> 3
? ? ? ?102 -> max_id
? ? ? ?101 -> max_id-1
? ? ? ?100 -> max_id-2
? ? ? ? 99 -> max_id-3

But it doesn't really matter either way, does it? We don't even allow
setting vacuum_max_freeze_age to 2^31-1 or any value that would be
close to triggering a problem here.

It doesn't need to be that high because it is subtracted from the
current xid counter, so if vacuum_max_freeze_age is 100, and the xid
counter is 101, we see the problem.

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +

On Thu, Mar 31, 2011 at 5:59 PM, Bruce Momjian <bruce@momjian.us> wrote:

OK, just keep going below 100:

       105 -> 5
       104 -> 4
       103 -> 3
       102 -> max_xid
       101 -> max_xid - 1
       100 -> max_xid - 2
        99 -> max_id
        98 -> max_id -1

Wouldn't you rather:

       105 -> 5
       104 -> 4
       103 -> 3
       102 -> 3
       101 -> 3
       100 -> 3
        99 -> max_id
        98 -> max_id -1

Oh, quite right. Sorry I missed that. I suppose if we wanted to fix
this for real, we'd want to get:

105->5
104->4
103->3
102->max_xid
101->max_xid-1
100->max_xid-2
99->max_xid-3
98->max_xid-4

But it doesn't seem worth getting excited about.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas wrote:

Oh, quite right. Sorry I missed that. I suppose if we wanted to fix
this for real, we'd want to get:

105->5
104->4
103->3
102->max_xid
101->max_xid-1
100->max_xid-2
99->max_xid-3
98->max_xid-4

But it doesn't seem worth getting excited about.

I think (?) the problem with that is the every time you wrap around you
get more out of sync. :-O

Thinking more, the problem is that when the xid counter wraps around
from max_xid to 3, we jump the freeze horizon by three, e.g 5000 to
5003. So when, the freeze horizon wraps, we can either have that jump
by three, e.g set it to FirstNormalTransactionId, or delay by three,
e.g. set it to MaxTransactionId.

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +

On Fri, Apr 1, 2011 at 11:18 AM, Bruce Momjian <bruce@momjian.us> wrote:

Robert Haas wrote:

Oh, quite right.  Sorry I missed that.  I suppose if we wanted to fix
this for real, we'd want to get:

105->5
104->4
103->3
102->max_xid
101->max_xid-1
100->max_xid-2
99->max_xid-3
98->max_xid-4

But it doesn't seem worth getting excited about.

I think (?) the problem with that is the every time you wrap around you
get more out of sync.  :-O

It's not clear to me that it matters a bit, though.

Thinking more, the problem is that when the xid counter wraps around
from max_xid to 3, we jump the freeze horizon by three, e.g 5000 to
5003.  So when, the freeze horizon wraps, we can either have that jump
by three, e.g set it to FirstNormalTransactionId, or delay by three,
e.g. set it to MaxTransactionId.

So what? :-)

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas wrote:

On Fri, Apr 1, 2011 at 11:18 AM, Bruce Momjian <bruce@momjian.us> wrote:

Robert Haas wrote:

Oh, quite right. ?Sorry I missed that. ?I suppose if we wanted to fix
this for real, we'd want to get:

105->5
104->4
103->3
102->max_xid
101->max_xid-1
100->max_xid-2
99->max_xid-3
98->max_xid-4

But it doesn't seem worth getting excited about.

I think (?) the problem with that is the every time you wrap around you
get more out of sync. ?:-O

It's not clear to me that it matters a bit, though.

To do the right thing every computation that passes over the xid
wraparound bounary should subtract FirstNormalTransactionId, not just
those that fall in the boundry. That would prevent the value from going
backward and still allow the mapping you liked; it isn't worth it, but
that is the right answer.

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +

Excerpts from Bruce Momjian's message of vie abr 01 16:50:29 -0300 2011:

To do the right thing every computation that passes over the xid
wraparound bounary should subtract FirstNormalTransactionId, not just
those that fall in the boundry. That would prevent the value from going
backward and still allow the mapping you liked; it isn't worth it, but
that is the right answer.

This code is only concerned calculating an immediate the wrap horizon
for the autovacuuming run that's about to take place. If it's wrong in
one or three counts doesn't mean much. Consider what would happen if
load was high and it would have taken 100 extra milliseconds to get to
that bit: ReadNewTransactionId would have returned a value 3
transactions later. Furthermore, before this value is even used at all
for vacuuming, there has to be a whole lot of inter-process signalling,
a fork, and a new backend startup.

I think this should be left alone. As you said, it isn't worth it.

--
Álvaro Herrera <alvherre@commandprompt.com>
The PostgreSQL Company - Command Prompt, Inc.
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

Alvaro Herrera wrote:

Excerpts from Bruce Momjian's message of vie abr 01 16:50:29 -0300 2011:

To do the right thing every computation that passes over the xid
wraparound bounary should subtract FirstNormalTransactionId, not just
those that fall in the boundry. That would prevent the value from going
backward and still allow the mapping you liked; it isn't worth it, but
that is the right answer.

This code is only concerned calculating an immediate the wrap horizon
for the autovacuuming run that's about to take place. If it's wrong in
one or three counts doesn't mean much. Consider what would happen if
load was high and it would have taken 100 extra milliseconds to get to
that bit: ReadNewTransactionId would have returned a value 3
transactions later. Furthermore, before this value is even used at all
for vacuuming, there has to be a whole lot of inter-process signalling,
a fork, and a new backend startup.

I think this should be left alone. As you said, it isn't worth it.

Agreed it is not worth it but I think we should at least C comment
something. I think at a minimum we should set it to
FirstNormalTransactionId.

I am not so concerned about this case but about other cases where we are
computing xid distances across the invalid range.

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +

Bruce Momjian wrote:

I think this should be left alone. As you said, it isn't worth it.

Agreed it is not worth it but I think we should at least C comment
something. I think at a minimum we should set it to
FirstNormalTransactionId.

I am not so concerned about this case but about other cases where we are
computing xid distances across the invalid range.

Please ignore the patch I had attached. I realize it just moves the
problem around.

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +