[HACKERS] Search from newer tuples first, vs older tuples first?
At 02:10 PM 5/1/02 -0400, Tom Lane wrote: >Lincoln Yeoh <[EMAIL PROTECTED]> writes: > > My limited understanding of current behaviour is the search for a valid > > row's tuple goes from older tuples to newer ones via forward links > >No. Each tuple is independently indexed and independently visited. >Given the semantics of MVCC I think that's correct --- after all, what's >dead to you is not necessarily dead to someone else. But does Postgresql visit the older tuples first moving to the newer ones, or the newer ones first? From observation it seems to be starting from the older ones. I'm thinking visiting the newer ones first would be better. Would that reduce the slowing down effect? Anyway, are you saying: Index row X entry #1 -> oldest tuple ... Index row X entry #2 -> older tuple ... Index row X entry #3 -> old tuple ... Index row X entry #4 -> just inserted tuple And a search for a valid tuple goes through each index entry and visits each tuple to see if it is visible. That seems like a lot of work to do, any docs/urls which explain this? Are the index tuples for the same row generally in the same physical location? Whereas the following still looks like less work and still compatible with MVCC: index tuple -> new tuple -> rolled back tuple -> old tuple -> older tuple. Just one index tuple per row. The tuples are checked from newer to older for visibility via backward links. The docs I mentioned say updates use the forward links. Repeated updates definitely slow down, so backward links might help? Regards, Link. ---(end of broadcast)--- TIP 2: you can get off all lists at once with the unregister command (send "unregister YourEmailAddressHere" to [EMAIL PROTECTED])
Re: [HACKERS] Search from newer tuples first, vs older tuples first?
Lincoln Yeoh <[EMAIL PROTECTED]> writes: > But does Postgresql visit the older tuples first moving to the newer ones, > or the newer ones first? It's going to visit them *all*. Reordering won't improve the performance. FWIW I think that with the present implementation of btree, the newer tuples actually will be visited first --- when inserting a duplicate key, the new entry will be inserted to the left of the equal key(s) already present. But it doesn't matter. The only way to speed this up is to eliminate some of the visitings, which requires keeping more info in the index than we presently do. regards, tom lane ---(end of broadcast)--- TIP 4: Don't 'kill -9' the postmaster
Re: [HACKERS] Search from newer tuples first, vs older tuples first?
At 12:49 AM 5/2/02 -0400, Tom Lane wrote: >Lincoln Yeoh <[EMAIL PROTECTED]> writes: > > But does Postgresql visit the older tuples first moving to the newer ones, > > or the newer ones first? > >It's going to visit them *all*. Reordering won't improve the >performance. Ack! I thought it went through them till the first valid tuple and was just going the wrong way. >FWIW I think that with the present implementation of btree, the newer >tuples actually will be visited first --- when inserting a duplicate >key, the new entry will be inserted to the left of the equal key(s) >already present. But it doesn't matter. The only way to speed this >up is to eliminate some of the visitings, which requires keeping more >info in the index than we presently do. OK I'm starting to get it :). Will the index behaviour be changed soon? Hmm, then what are the row tuple forward links for? Why forward? Regards, Link. ---(end of broadcast)--- TIP 3: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] Search from newer tuples first, vs older tuples first?
Lincoln Yeoh <[EMAIL PROTECTED]> writes: > OK I'm starting to get it :). Will the index behaviour be changed soon? When someone steps up and does it. I've learned not to predict schedules for this project. > Hmm, then what are the row tuple forward links for? Why forward? Updates in READ COMMITTED mode have to be able to find the newest version of a tuple they've already found. regards, tom lane ---(end of broadcast)--- TIP 2: you can get off all lists at once with the unregister command (send "unregister YourEmailAddressHere" to [EMAIL PROTECTED])
Re: [HACKERS] Search from newer tuples first, vs older tuples first?
Tom Lane wrote: > Lincoln Yeoh <[EMAIL PROTECTED]> writes: > > OK I'm starting to get it :). Will the index behaviour be changed soon? > > When someone steps up and does it. I've learned not to predict > schedules for this project. It is not that hard to implement, just messy. When the index returns a heap row and the heap row is viewed for visibility, if _no_one_ can see the row, the index can be marked as expired. It could be a single bit in the index tuple, and doesn't need to be flushed to disk, though the index page has to be marked as dirty. However, we are going to need to flush a pre-change image to WAL so it may as well be handled as a normal index page change. -- Bruce Momjian| http://candle.pha.pa.us [EMAIL PROTECTED] | (610) 853-3000 + If your life is a hard drive, | 830 Blythe Avenue + Christ can be your backup.| Drexel Hill, Pennsylvania 19026 ---(end of broadcast)--- TIP 3: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] Search from newer tuples first, vs older tuples first?
Bruce Momjian <[EMAIL PROTECTED]> writes: > It is not that hard to implement, just messy. When the index returns a > heap row and the heap row is viewed for visibility, if _no_one_ can see > the row, the index can be marked as expired. It could be a single bit > in the index tuple, and doesn't need to be flushed to disk, though the > index page has to be marked as dirty. However, we are going to need to > flush a pre-change image to WAL so it may as well be handled as a normal > index page change. This did actually get done while you were on vacation. It does *not* need a WAL entry, on the same principle that setting XMIN_COMMITTED, XMAX_ABORTED, etc hint bits do not need WAL entries --- namely the bits can always get set again if they are lost in a crash. regards, tom lane ---(end of broadcast)--- TIP 6: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] Search from newer tuples first, vs older tuples first?
Tom Lane wrote: > Bruce Momjian <[EMAIL PROTECTED]> writes: > > It is not that hard to implement, just messy. When the index returns a > > heap row and the heap row is viewed for visibility, if _no_one_ can see > > the row, the index can be marked as expired. It could be a single bit > > in the index tuple, and doesn't need to be flushed to disk, though the > > index page has to be marked as dirty. However, we are going to need to > > flush a pre-change image to WAL so it may as well be handled as a normal > > index page change. > > This did actually get done while you were on vacation. It does *not* > need a WAL entry, on the same principle that setting XMIN_COMMITTED, > XMAX_ABORTED, etc hint bits do not need WAL entries --- namely the > bits can always get set again if they are lost in a crash. Oh, thanks. That is great news. I am having trouble determining when a thread ends so please be patient with me. -- Bruce Momjian| http://candle.pha.pa.us [EMAIL PROTECTED] | (610) 853-3000 + If your life is a hard drive, | 830 Blythe Avenue + Christ can be your backup.| Drexel Hill, Pennsylvania 19026 ---(end of broadcast)--- TIP 2: you can get off all lists at once with the unregister command (send "unregister YourEmailAddressHere" to [EMAIL PROTECTED])
Re: [HACKERS] Search from newer tuples first, vs older tuples first?
Tom Lane wrote: > Bruce Momjian <[EMAIL PROTECTED]> writes: > > It is not that hard to implement, just messy. When the index returns a > > heap row and the heap row is viewed for visibility, if _no_one_ can see > > the row, the index can be marked as expired. It could be a single bit > > in the index tuple, and doesn't need to be flushed to disk, though the > > index page has to be marked as dirty. However, we are going to need to > > flush a pre-change image to WAL so it may as well be handled as a normal > > index page change. > > This did actually get done while you were on vacation. It does *not* > need a WAL entry, on the same principle that setting XMIN_COMMITTED, > XMAX_ABORTED, etc hint bits do not need WAL entries --- namely the > bits can always get set again if they are lost in a crash. TODO item marked as done: * -Add deleted bit to index tuples to reduce heap access -- Bruce Momjian| http://candle.pha.pa.us [EMAIL PROTECTED] | (610) 853-3000 + If your life is a hard drive, | 830 Blythe Avenue + Christ can be your backup.| Drexel Hill, Pennsylvania 19026 ---(end of broadcast)--- TIP 1: subscribe and unsubscribe commands go to [EMAIL PROTECTED]
