Обсуждение: TODO item: Allow data to be pulled directly from indexes
Sometime last year, a discussion started about including visibility metadata to avoid heap fetches during an index scan: http://archives.postgresql.org/pgsql-patches/2007-10/msg00166.php http://archives.postgresql.org/pgsql-patches/2008-01/msg00049.php I think the last discussion on this was in April: http://archives.postgresql.org/pgsql-hackers/2008-04/msg00618.php (last item) I have worked with the current patch, and I have some thoughts about that approach and the approaches listed in the TODO item. The TODO lists three approaches, in short (1) Add a bit for an index tuple that indicates "visible" or "maybe visible." (2) Use a per-table bitmap that indicates which pages have at least one tuple that is not visible to all transactions. (3) Same as (2) but at the granularity of one bit per table. The approach in the patch is different: (4) Add transaction ids, etc to the index tuple (totaling 16 bytes) I would group (1) & (4) together and (2) & (3) together. I think the time and space trade-offs are pretty obvious, so I won't waste time on those. (1) & (4) require an UPDATE or DELETE to twiddle the old index tuple. Tom has noted (in the linked message) that this is not reliable if the index has any expression-valued columns, because it is not always possible to find the old index entry. For this reason, the proposed patch does not keep visibility metadata for indexes on expressions. This seems like a reasonable limitation --- indexed expressions are just less efficient. The main difference between (1) & (4) is that (1) will sometimes require heap lookups and (4) never will. Moreover, the heap lookups in (1) will be difficult for the optimizer to estimate, unless some special statistics can be maintained for this purpose. I should mention there is a major flaw in the patch, because it puts pointers to HOT tuples in the index, in order to capture the different transaction ids in the chain. I think this can be fixed by only pointing to the root of the HOT chain, and setting xmin/xmax to the entire range of transaction ids spanned by the chain. I'm not sure about all the details (the ctid and some other bits also need to be set). (2) & (3) can work for any index, and they are quite elegant in the way that the overhead does not change with the number of indexes. The TODO also notes the benefit of (2) for efficient vacuuming. Thus, I think that (2) is a great idea in general, but it does not serve the intended purpose of this TODO item. Once a page gets marked as requiring visibility checks, it cannot be unmarked until the next VACUUM. The whole point of this feature is that we are willing to be more proactive during updates in order to make index access more efficient. So in summary, I think that (2) would be nice as a separate feature, with (1) and (4) being more favorable for index-only scans. The obvious trouble with (4) is the extra space overhead. There are also issues with correctness that I mentioned (any thoughts here would be appreciated). Other than that, I would favor (4) because it offers the most stable performance. Please let me know if you agree/disagree with anything here. I need to get this feature implemented for my research, but I would also love to contribute it to the community so your opinions matter a lot.
"Karl Schnaitter" <karlsch@soe.ucsc.edu> writes: "Karl Schnaitter" <karlsch@soe.ucsc.edu> writes: > (1) & (4) require an UPDATE or DELETE to twiddle the old index tuple. Tom has > noted (in the linked message) that this is not reliable if the index has any > expression-valued columns, because it is not always possible to find the old > index entry. For this reason, the proposed patch does not keep visibility > metadata for indexes on expressions. This seems like a reasonable limitation > --- indexed expressions are just less efficient. Or if the index operators and btproc aren't nearly as immutable as they claim. Probably less likely than non-immutable index expressions but also possible. > I should mention there is a major flaw in the patch, because it puts pointers > to HOT tuples in the index, in order to capture the different transaction ids > in the chain. I think this can be fixed by only pointing to the root of the HOT > chain, and setting xmin/xmax to the entire range of transaction ids spanned by > the chain. I'm not sure about all the details (the ctid and some other bits > also need to be set). I think you can think of a HOT chain as a single tuple. The xmin of the head is the xmin of the chain and the xmax of the tail is the xmax of the chain. The xmin/xmax of the intermediate versions are only interesting for determining *which* of the HOT versions to look at, but the index pointer points to the whole chain. > (2) & (3) can work for any index, and they are quite elegant in the way that > the overhead does not change with the number of indexes. The TODO also notes > the benefit of (2) for efficient vacuuming. Thus, I think that (2) is a great > idea in general, but it does not serve the intended purpose of this TODO item. > Once a page gets marked as requiring visibility checks, it cannot be unmarked > until the next VACUUM. The whole point of this feature is that we are willing > to be more proactive during updates in order to make index access more > efficient. Well I think that's precisely the point. If you're trading off work done at update time against work done for index accesses then you're only going to win if the tuples are relatively static and have lots of accesses done against them between updates. In which case having the optimization only kick in when the page has been static for long enough that all the tuples are globally visible should be good enough. The case where index visibility info might win over a visibility map might be if the tuples are being heavily updated by long-lived transactions. In which case they never sit globally visible for very long but having the xmin/xmax in the index might avoid having to do a heap access for tuples which haven't been committed yet. As you seem to realize there has been a lot of discussion in this area already. The visibility map looks like a much more popular direction. -- Gregory Stark EnterpriseDB http://www.enterprisedb.com Ask me about EnterpriseDB's RemoteDBA services!
Gregory Stark wrote: >> (1) & (4) require an UPDATE or DELETE to twiddle the old index tuple. Tom has >> noted (in the linked message) that this is not reliable if the index has any >> expression-valued columns, because it is not always possible to find the old >> index entry. For this reason, the proposed patch does not keep visibility >> metadata for indexes on expressions. This seems like a reasonable limitation >> --- indexed expressions are just less efficient. >> > > Or if the index operators and btproc aren't nearly as immutable as they claim. > Probably less likely than non-immutable index expressions but also possible. > > Your point is well taken... I'll have to look into that more. >> (2) & (3) can work for any index, and they are quite elegant in the way that >> the overhead does not change with the number of indexes. The TODO also notes >> the benefit of (2) for efficient vacuuming. Thus, I think that (2) is a great >> idea in general, but it does not serve the intended purpose of this TODO item. >> Once a page gets marked as requiring visibility checks, it cannot be unmarked >> until the next VACUUM. The whole point of this feature is that we are willing >> to be more proactive during updates in order to make index access more >> efficient. >> > > Well I think that's precisely the point. If you're trading off work done at > update time against work done for index accesses then you're only going to win > if the tuples are relatively static and have lots of accesses done against > them between updates. In which case having the optimization only kick in when > the page has been static for long enough that all the tuples are globally > visible should be good enough I really don't understand this point. The way I see the visibility map working is as follows: we set a page to "requires visibility check" when a tuple on the page is inserted, deleted, or non-HOT updated. If the only modifications have been inserts, we can reset the status to "all tuples visible" when these tuples become universally visible, which matches your description. But in the presence of deletes and updates, we can only reset the status of a page after a VACUUM (I know that dead HOT tuples can be pruned without VACUUM, but I don't think that's the case for indexed tuples). We can't reset the status earlier because we don't know what indexes still have pointers to the dead tuples. So a page can be static indefinitely (after a single modification) without ever getting to enjoy the optimization. This is a really important point, so please let me know if I'm missing something. Thanks for your response! Karl
Karl Schnaitter wrote: > The main difference between (1) & (4) is that (1) will sometimes require > heap lookups and (4) never will. Moreover, the heap lookups in (1) will > be difficult for the optimizer to estimate, unless some special > statistics can be maintained for this purpose. Yeah, we certainly should maintain a statistic for it. > (2) & (3) can work for any index, and they are quite elegant in the way > that the overhead does not change with the number of indexes. The TODO > also notes the benefit of (2) for efficient vacuuming. Thus, I think > that (2) is a great idea in general, but it does not serve the intended > purpose of this TODO item. Once a page gets marked as requiring > visibility checks, it cannot be unmarked until the next VACUUM. The > whole point of this feature is that we are willing to be more proactive > during updates in order to make index access more efficient. In some cases we can mark a page earlier, as soon as we see that the condition is true. Most importantly, when new tuples are inserted, we can mark the page as soon as the inserting transaction is visible to all. Also, the visibility map ought to make vacuums cheaper, as you only need to scan the parts of the table that have beem modified since last vacuum. You still need to scan all indexes, though. But assuming that you somehow solve the correctness issues in the "add visibility fields to index tuples" approach, we can use the same solution to perform retail vacuums, which would bring vacuuming and the visibility map approach on par with that approach anyway. > Please let me know if you agree/disagree with anything here. I need to get this feature implemented for my research, butI would also love to contribute it to the community so your opinions matter a lot. Well, I think the visibility map is a much better approach. This has been discussed many times before, so I don't really have anything new to add. I've been working adding support for so-called "relation forks" (http://archives.postgresql.org/message-id/48651722.8020600@enterprisedb.com), to allow attaching metadata to relations, like the visibility map. I'm going to use the facility for a new FSM implementation, which I'm working on at the moment, but after that's done I'm going to start working on the visibility map. And after that's done and working for VACUUM, I'm going to work on using it for index-only-scans. I'm not sure I have enough time to get all that done for 8.4, it's looking bad at the moment, so help would be much appreciated. If you don't agree with taking the visibility map approach, I would suggest working on the indexam API changes first, to allow returning index tuples from an index. I believe that part is the same regardless of how we check the visibility. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com
"Heikki Linnakangas" <heikki@enterprisedb.com> writes: > I'm not sure I have enough time to get all that done for 8.4, it's looking bad > at the moment, so help would be much appreciated. If you don't agree with > taking the visibility map approach, I would suggest working on the indexam API > changes first, to allow returning index tuples from an index. I believe that > part is the same regardless of how we check the visibility. That part is the elephant in the room in all these discussions. I wonder if we want to have a new plan node for the heap accesses so they can be postponed up above a join or other quals. Even for tuples which are of questionable visibility we ought to be able to check cheap quals first before checking visibility (though we might need a new function property to indicate it's safe to call extra times on data which doesn't really exist -- immutable doesn't mean it might not throw errors, for example). -- Gregory Stark EnterpriseDB http://www.enterprisedb.com Ask me about EnterpriseDB's PostGIS support!
I have added this email's URL to TODO under tuple visibility. --------------------------------------------------------------------------- Karl Schnaitter wrote: > Sometime last year, a discussion started about including visibility > metadata to avoid heap fetches during an index scan: > > http://archives.postgresql.org/pgsql-patches/2007-10/msg00166.php > http://archives.postgresql.org/pgsql-patches/2008-01/msg00049.php > > I think the last discussion on this was in April: > > http://archives.postgresql.org/pgsql-hackers/2008-04/msg00618.php (last > item) > > I have worked with the current patch, and I have some thoughts about > that approach and the approaches listed in the TODO item. The TODO lists > three approaches, in short > > (1) Add a bit for an index tuple that indicates "visible" or "maybe > visible." > (2) Use a per-table bitmap that indicates which pages have at least one > tuple that is not visible to all transactions. > (3) Same as (2) but at the granularity of one bit per table. > > The approach in the patch is different: > > (4) Add transaction ids, etc to the index tuple (totaling 16 bytes) > > I would group (1) & (4) together and (2) & (3) together. I think the > time and space trade-offs are pretty obvious, so I won't waste time on > those. > > (1) & (4) require an UPDATE or DELETE to twiddle the old index tuple. > Tom has noted (in the linked message) that this is not reliable if the > index has any expression-valued columns, because it is not always > possible to find the old index entry. For this reason, the proposed > patch does not keep visibility metadata for indexes on expressions. This > seems like a reasonable limitation --- indexed expressions are just less > efficient. > > The main difference between (1) & (4) is that (1) will sometimes require > heap lookups and (4) never will. Moreover, the heap lookups in (1) will > be difficult for the optimizer to estimate, unless some special > statistics can be maintained for this purpose. > > I should mention there is a major flaw in the patch, because it puts > pointers to HOT tuples in the index, in order to capture the different > transaction ids in the chain. I think this can be fixed by only pointing > to the root of the HOT chain, and setting xmin/xmax to the entire range > of transaction ids spanned by the chain. I'm not sure about all the > details (the ctid and some other bits also need to be set). > > (2) & (3) can work for any index, and they are quite elegant in the way > that the overhead does not change with the number of indexes. The TODO > also notes the benefit of (2) for efficient vacuuming. Thus, I think > that (2) is a great idea in general, but it does not serve the intended > purpose of this TODO item. Once a page gets marked as requiring > visibility checks, it cannot be unmarked until the next VACUUM. The > whole point of this feature is that we are willing to be more proactive > during updates in order to make index access more efficient. > > So in summary, I think that (2) would be nice as a separate feature, > with (1) and (4) being more favorable for index-only scans. The obvious > trouble with (4) is the extra space overhead. There are also issues with > correctness that I mentioned (any thoughts here would be appreciated). > Other than that, I would favor (4) because it offers the most stable > performance. > > Please let me know if you agree/disagree with anything here. I need to > get this feature implemented for my research, but I would also love to > contribute it to the community so your opinions matter a lot. > > > -- > Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) > To make changes to your subscription: > http://www.postgresql.org/mailpref/pgsql-hackers -- Bruce Momjian <bruce@momjian.us> http://momjian.us EnterpriseDB http://enterprisedb.com + If your life is a hard drive, Christ can be your backup. +