Re: [HACKERS] A thought on Index Organized Tables
I think you have to take up a simpler project as a first project. This is a major overhaul of transaction information and it depends on understanding how a lot of different areas work -- all of which are very complex tricky areas to understand. Greg, I just feel the fast full index scan may not be of much value, if we have to go to the table for visibility information. I think the feature needs the visibility map to get completed. Please let me know, if you feel otherwise. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
a) We are already going from table to index to do unique checks. This is the same thing, which we will do to go and update the snapshot in the indexes. No, it is not the same thing. Updating index snapshots requires being able to *re-find* a previously made index entry for the current row. And it has to be done 100% reliably. The worst that happens if an index entry is not found when it should be during a uniqueness check is that the uniqueness constraint is not enforced properly; which is bad but it doesn't lead to internally-inconsistent data structures. Tom, We are also going to indexes to maintain the referential integrity constraints like foreign keys. Say there are constraints like 'On Delete Cascade' and 'On Delete Restrict', they are maintained through the indexes and if we say that indexes can return wrong results, then the referential integrity is lost and we no longer are ACID compliant. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
On Sun, Feb 28, 2010 at 6:02 AM, Gokulakannan Somasundaram gokul...@gmail.com wrote: So just with a addition of 8 bytes per tuple, we can have the snapshot stored with the index. Can someone please comment on this? The transaction information on tuples take 18 bytes plus several info bits. It's possible just storing a subset of that would be useful but it's unclear. And I think it would complicate the code if it had to sometimes fetch the heap tuple to get the rest and sometimes doesn't. I think you have to take up a simpler project as a first project. This is a major overhaul of transaction information and it depends on understanding how a lot of different areas work -- all of which are very complex tricky areas to understand. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Gokulakannan Somasundaram gokul...@gmail.com writes: a) We are already going from table to index to do unique checks. This is the same thing, which we will do to go and update the snapshot in the indexes. No, it is not the same thing. Updating index snapshots requires being able to *re-find* a previously made index entry for the current row. And it has to be done 100% reliably. The worst that happens if an index entry is not found when it should be during a uniqueness check is that the uniqueness constraint is not enforced properly; which is bad but it doesn't lead to internally-inconsistent data structures. b) The way, it should work would be to have a check on whether the operator is broken / function is volatile and put the onus on the user to make sure that they are updated correctly. Pretending the problem doesn't exist doesn't make it go away ... regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
No, it is not the same thing. Updating index snapshots requires being able to *re-find* a previously made index entry for the current row. And it has to be done 100% reliably. The worst that happens if an index entry is not found when it should be during a uniqueness check is that the uniqueness constraint is not enforced properly; which is bad but it doesn't lead to internally-inconsistent data structures. Hmmm... OK Fine... I am leaving this proposal once and for all. Pretending the problem doesn't exist doesn't make it go away ... Because this is how it is done in other databases Ref: .http://www.akadia.com/services/ora_function_based_index_2.html Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
The transaction information on tuples take 18 bytes plus several info bits. It's possible just storing a subset of that would be useful but it's unclear. And I think it would complicate the code if it had to sometimes fetch the heap tuple to get the rest and sometimes doesn't. Visibility map had a similar proposal and it got accepted. Fine... I think, if you guys are going to stress so hard, then there might be some issues, which i am not foreseeing right now. I think you have to take up a simpler project as a first project. This is a major overhaul of transaction information and it depends on understanding how a lot of different areas work -- all of which are very complex tricky areas to understand. Yep.. i would start by just joining in someone's project to help them out. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
If i have got over excited in the previous update, please ignore that. a) We are already going from table to index to do unique checks. This is the same thing, which we will do to go and update the snapshot in the indexes. b) The way, it should work would be to have a check on whether the operator is broken / function is volatile and put the onus on the user to make sure that they are updated correctly. c) In the ItemId, instead of removing the size field completely, we can store the size as size/4(since it is MaxAligned). This will save us 2 bits. In index we only need 13 bits to store the complete size in the tuple, but we use 15 bits in the iid, so again we can have two more bit savings there. That's sufficient for us to express the hint fields in a index. I think Karl's way of expressing it requires only one bit, which looks very efficient. So we can check the hint bits from the iid itself. So just with a addition of 8 bytes per tuple, we can have the snapshot stored with the index. Can someone please comment on this? Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
To be a bit more concrete: the typical sort of failure that you could get from broken btree operators is failure of transitivity, that is the comparators report A B and B C for some A, B, C, but do not say that A C when those two values are compared directly. I don't see any convenient way to detect that as a byproduct of normal index operations, because you wouldn't typically have a reason to make all three comparisons in close proximity. Indeed, the searching and sorting algorithms do their best to avoid making redundant comparisons of that kind. This is interesting Tom, but i am unable to understand, why it won't affect the current indexes. While insertion it might get inserted in a block and offset, and while searching it might either return no results / show a wrong place. Because ordering is required for searching also right? I definitely feel, i am missing something here. Gokul.
Re: [HACKERS] A thought on Index Organized Tables
On Fri, Feb 26, 2010 at 12:36 AM, Gokulakannan Somasundaram gokul...@gmail.com wrote: To be a bit more concrete: the typical sort of failure that you could get from broken btree operators is failure of transitivity, that is the comparators report A B and B C for some A, B, C, but do not say that A C when those two values are compared directly. I don't see any convenient way to detect that as a byproduct of normal index operations, because you wouldn't typically have a reason to make all three comparisons in close proximity. Indeed, the searching and sorting algorithms do their best to avoid making redundant comparisons of that kind. This is interesting Tom, but i am unable to understand, why it won't affect the current indexes. While insertion it might get inserted in a block and offset, and while searching it might either return no results / show a wrong place. Because ordering is required for searching also right? I definitely feel, i am missing something here. It definitely affects current indexes. We can't completely avoid bad user functions. That is why it is important to put limits on how much damage they can do. That's the motivation for the idea I mentioned before, of double-checking visibility data in an IndexTuple before letting it survive a VACUUM.
Re: [HACKERS] A thought on Index Organized Tables
On Fri, Feb 26, 2010 at 4:47 AM, Tom Lane t...@sss.pgh.pa.us wrote: I feel the other one is easy. To store the hint bits inside the ItemId, in the place of size. No, we're not going there. That breaks the fundamental page content manipulation algorithms, and falls down for tuples not yet stored in a page (or being examined without a pointer to the page readily at hand), and has no redeeming social value anyway compared to doing it in the proven fashion. Well we were already talking about moving the hint bits to someplace else to enable CRC checking. My favourite place was the line pointer, but you wanted a separate area -- either of which would have these problems. But this is all irrelevant to the particular issue at hand. The bigger point is that you've chosen a change that requires massive changes to all different parts of the system and causes problems for all different situations. You might be able to come up with solutions for some of them but I bet there are some you realize later are insoluble. And a lot of the solutions themselves have problems or impose limitations that we won't be able to live with. Much better to take on a simple project like enabling full sequential index scans which you claimed you had a solution for and which is in any case an important sub-problem for IOT. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
It definitely affects current indexes. We can't completely avoid bad user functions. That is why it is important to put limits on how much damage they can do. That's the motivation for the idea I mentioned before, of double-checking visibility data in an IndexTuple before letting it survive a VACUUM. No i don't say it would affect Vacuum, but i am suspecting that it would affect Index based select. Since Vacuum uses a sequential scan of tuples, it doesn't require the ordering operator, but any index based search would require a ordering operator for binary search and for comparing with the right most key. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
Much better to take on a simple project like enabling full sequential index scans which you claimed you had a solution for and which is in any case an important sub-problem for IOT. Greg, Well i don't think i am ready to take up a project of this size. But at the same time some important features are lagging in postgres and someone should start working on them to make the database compete with other databases effectively. So i would request people like Tom, Heikki, Simon and you to take up a major project like this and provide the necessary impetus to the adoption of the database. I have never written much code in C, and even if write it, i am sure i will receive the comment that it is a unmaintainable code.(eg: Thick index code and trailing nulls code) So its better i start working with one of you guys to get a hang of developing maintainable code. So i would request one of you to initiate the development and provide the necessary directions to me, if possible. That will save my development effort and your reviewing effort. At the sametime, features like IOT, index only scans are features which are very necesary for postgres to atleast make it get inside my company. So i am putting forward all my arguments as a DB user. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
On Fri, Feb 26, 2010 at 2:38 PM, Gokulakannan Somasundaram gokul...@gmail.com wrote: I have never written much code in C, and even if write it, i am sure i will receive the comment that it is a unmaintainable code.(eg: Thick index code and trailing nulls code) I definitely think thick indexes were too ambitious of a target for a first time patch. Sequential index scans is very ambitious itself despite being significantly simpler (if you have a solution which works -- we haven't had one thus far). Can you point me to the thread on trailing nulls? I think trimming off any null columns from the ends of tuples when forming them should be a cheap and easy optimization which just nobody's gotten around to doing. If that's what you mean then I'm surprised you had any trouble getting buy-in for it. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Greg Stark gsst...@mit.edu writes: On Fri, Feb 26, 2010 at 4:47 AM, Tom Lane t...@sss.pgh.pa.us wrote: I feel the other one is easy. To store the hint bits inside the ItemId, in the place of size. No, we're not going there. Well we were already talking about moving the hint bits to someplace else to enable CRC checking. My favourite place was the line pointer, but you wanted a separate area -- either of which would have these problems. IIRC, what was being talked about was shoehorning some hint bits into the line pointers by assuming that size and offset are multiples of 4. I'm not thrilled with having mutable status bits there for reliability reasons, but it could be done without breaking a lot of existing code. What I was reacting to above was a suggestion that we could delete the itempointer size field altogether, which seems unworkable for the reasons I mentioned. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Missed the group.. On Sat, Feb 27, 2010 at 12:00 AM, Gokulakannan Somasundaram gokul...@gmail.com wrote: I definitely think thick indexes were too ambitious of a target for a first time patch. Sequential index scans is very ambitious itself despite being significantly simpler (if you have a solution which works -- we haven't had one thus far). The point, i am trying to bring out is that i want to work with one of the senior persons of the community to do my first few patches. Can you point me to the thread on trailing nulls? I think trimming off any null columns from the ends of tuples when forming them should be a cheap and easy optimization which just nobody's gotten around to doing. If that's what you mean then I'm surprised you had any trouble getting buy-in for it. http://archives.postgresql.org/pgsql-hackers/2008-03/msg00682.php I think, the buy-in became difficult because of the code quality. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
IIRC, what was being talked about was shoehorning some hint bits into the line pointers by assuming that size and offset are multiples of 4. I'm not thrilled with having mutable status bits there for reliability reasons, but it could be done without breaking a lot of existing code. What I was reacting to above was a suggestion that we could delete the itempointer size field altogether, which seems unworkable for the reasons I mentioned. I think then we can pursue on using the IndexTuple structure similar to HeapTuple(as you have suggested in an earlier update). This would involve(i believe) a) Making the current IndexTuple into IndexTupleHeader b) Creating a new structure called IndexTuple which will store the size and the have a pointer to IndexTupleHeader. But Tom, can you please explain me why that broken ordering example doesn't affect the current index scans. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
Gokulakannan Somasundaram gokul...@gmail.com writes: But Tom, can you please explain me why that broken ordering example doesn't affect the current index scans. It does. The point is that the system is set up to limit the bad consequences. You might (will) get wrong query answers, but the heap data won't get corrupted. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
It does. The point is that the system is set up to limit the bad consequences. You might (will) get wrong query answers, but the heap data won't get corrupted. Again Tom, if there is an update based on index scan, then it takes the tupleid and updates the wrong heap data right? The only difference between normal index and thick index is to reach back to the same index tuple to update the snapshot. How will that corrupt the heap data? Did you intend to say that it corrupts the index data? Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
On Fri, Feb 26, 2010 at 6:30 PM, Gokulakannan Somasundaram gokul...@gmail.com wrote: http://archives.postgresql.org/pgsql-hackers/2008-03/msg00682.php I think, the buy-in became difficult because of the code quality. Er, yeah. That's something we need to work on a bit. You should probably expect your first few attempts to just be completely wrong. Tom did give a very brief hint what was wrong with the patch but it wasn't a point by point howto either. It looks like your patch was unnecessarily complex. slot_deform_tuple/heap_deform_tuple should handle missing columns automatically already so they shouldn't need any modification. All you need to do is check in heap_form_tuple whether there's a block of nulls at the end and trim them off. If you can do this in a cpu-efficient way it would be valuable because this is a very critical path in the code. Tom's concerns about benchmarking are interesting but I'm not sure there's much we can do. We're talking about spending cpu time for space gains which is usually worthwhile. I guess the best to hope for is that on any macro benchmark there's no measurable performance penalty even with a lot of nulls at the end of a very narrow row. Or that in a microbenchmark there's a negligable penalty, perhaps under 10% for trimming 100+ trailing null columns. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
It does. The point is that the system is set up to limit the bad consequences. You might (will) get wrong query answers, but the heap data won't get corrupted. Tom, if this is our goal - *can return wrong query answers, but should not corrupt the heap data.* and if we make Thick indexes capable of that, can i consider that as a thumbs up from your side? As you may already know, this will only happen when there is a volatile function based index. Heikki, Please let me know, if you feel otherwise. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
Gokulakannan Somasundaram gokul...@gmail.com writes: It does. The point is that the system is set up to limit the bad consequences. You might (will) get wrong query answers, but the heap data won't get corrupted. Again Tom, if there is an update based on index scan, then it takes the tupleid and updates the wrong heap data right? No, what generally happens is it fails to find a matching index entry at all, because the search algorithm concludes there can be no match based on the limited set of comparisons it's done. Transitivity failures lead to searching the wrong subset of the index. The case you're thinking about could arise if VACUUM failed to clean out an index entry; after some unrelated tuple is inserted at the just-cleared TID, searches finding that index entry would mistakenly process the new tuple. This is why we insist on VACUUM not assuming very much about the consistency of the index. It's also a problem for thick indexes, because if you try to do a normal index search for the index tuple to update its copy of the tuple xmin/xmax data, you might fail to find it --- but that doesn't mean it's not there. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
No, what generally happens is it fails to find a matching index entry at all, because the search algorithm concludes there can be no match based on the limited set of comparisons it's done. Transitivity failures lead to searching the wrong subset of the index. Actually Tom, i am not able to understand that completely. But what you are saying that in the current scenario, when there is a broken data type based index, then it will return no results, but never will return wrong results. So never the update will corrupt the heap data. But i take it as you say (please, correct me, if i am wrong). But even returning no results might lead to failures in unqiue checks. While i inserting, i try to check whether a particular data is already inserted and if it returns no results, then it will go ahead and insert the data assuming that the unique check has passed, while in reality it has failed. Wait a minute. Bingo So for unique checks we are already going to index from Heap. So it is the same thing i am doing with Thick index. So if we can trust our current unique checks, then we should trust the Thick index. Thanks Tom!!! for having this good conversation I think this broken data type problem / volatile function issue has to be resolved for the current index, if we advocate to stop the thick index. WOW!!! Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
Wait a minute. Bingo So for unique checks we are already going to index from Heap. So it is the same thing i am doing with Thick index. So if we can trust our current unique checks, then we should trust the Thick index. Thanks Tom!!! for having this good conversation I think this broken data type problem / volatile function issue has to be resolved for the current index, if we advocate to stop the thick index. WOW!!! I think, this opens up lot of opportunities for improvement in Postgres. a) HOT can now extend its reach beyond page boundaries b) If a heap has three indexes and the update is going to affect only one index, then we need not update the other two indexes. HOT can have more cleaner and fresh approach. If we have both normal index without snapshot and the thick index, Postgres can boast itself of having a very rich index family, in which it has some index structures for update/delete intensive transactions(normal index) and the thick index for select based transactions. Marketing folks can easily advertise the product.: Gokul.
Re: [HACKERS] A thought on Index Organized Tables
Actually Tom, i am not able to understand that completely. But what you are saying that in the current scenario, when there is a broken data type based index, then it will return no results, but never will return wrong results. So never the update will corrupt the heap data. But i take it as you say (please, correct me, if i am wrong). But even returning no results might lead to failures in unqiue checks. While i inserting, i try to check whether a particular data is already inserted and if it returns no results, then it will go ahead and insert the data assuming that the unique check has passed, while in reality it has failed. Wait a minute. Bingo So for unique checks we are already going to index from Heap. So it is the same thing i am doing with Thick index. So if we can trust our current unique checks, then we should trust the Thick index. Thanks Tom!!! for having this good conversation I think this broken data type problem / volatile function issue has to be resolved for the current index, if we advocate to stop the thick index. WOW!!! Can i get a feedback from Tom / Heikki regarding my observation? Regards, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
Yes. When a bit is cleared, that's OK, because a cleared bit just means you need to check visibility in the heap tuple. When a bit is set, however, it's important that it doesn't hit the disk before the corresponding heap page update. That's why visibilitymap_set() sets the LSN on the page. OK. Say a session doing the update, which is the fist update on the page, resets the PD_ALL_VISIBLE and just before updating the visibility map crashes. The subsequent inserts/updates/deletes, will see the PD_ALL_VISIBLE flag cleared and never care to update the visibility map, but actually it would have created tuples in index and table. So won't this return wrong results? Again it is not clear from your documentation, how you have handled this situation? Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
The replay of the heap insert/update/delete record updates the visibility map. So are you planning to make that section, which writes the xlog and updates the visibility map inside a PANIC section right?
Re: [HACKERS] A thought on Index Organized Tables
The replay of the heap insert/update/delete record updates the visibility map. Say a checkpoint has occured in between and flushed the dirty pages into disk, while the updater waits to update the visibility map. Now there will be no replay for the insert/update/delete right?
Re: [HACKERS] A thought on Index Organized Tables
Gokulakannan Somasundaram wrote: OK. Say a session doing the update, which is the fist update on the page, resets the PD_ALL_VISIBLE and just before updating the visibility map crashes. The subsequent inserts/updates/deletes, will see the PD_ALL_VISIBLE flag cleared and never care to update the visibility map, but actually it would have created tuples in index and table. The replay of the heap insert/update/delete record updates the visibility map. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Gokulakannan Somasundaram wrote: The replay of the heap insert/update/delete record updates the visibility map. So are you planning to make that section, which writes the xlog and updates the visibility map inside a PANIC section right? The xlog record is already written in a critical section. Yeah, perhaps the critical section needs to be extended to cover the visibility map updates. The indexes haven't been changed at that point yet, so an index-only scan still produces the right result, but a subsequent update would fail to update the visibility map because the flag on the heap page was already cleared. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Gokulakannan Somasundaram wrote: Say a checkpoint has occured in between and flushed the dirty pages into disk, while the updater waits to update the visibility map. Now there will be no replay for the insert/update/delete right? Yeah, good catch, that could happen. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
1) transaction information in index This seems like a lot of bloat in indexes. It also means breaking a lot of other optimizations such as being able to read the tuples directly from the heap page without locking. I'm not sure how much those are worth though. But adding 24 bytes to every index entry seems pretty unlikely to be a win anyways. Greg, I think, somewhere things have been misunderstood. we only need 8 bytes more per index entry. I thought Postgres has a 8 byte transaction id, but it is only 4 bytes, so we only need to save the insertion and deletion xids. So 8 bytes more per tuple. Gokul.
Re: [HACKERS] A thought on Index Organized Tables
Gokulakannan Somasundaram gokul...@gmail.com writes: I think, somewhere things have been misunderstood. we only need 8 bytes more per index entry. I thought Postgres has a 8 byte transaction id, but it is only 4 bytes, so we only need to save the insertion and deletion xids. So 8 bytes more per tuple. What makes you think you can get away without cmin/cmax? regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
On Thu, Feb 25, 2010 at 8:09 PM, Gokulakannan Somasundaram gokul...@gmail.com wrote: I think, somewhere things have been misunderstood. we only need 8 bytes more per index entry. I thought Postgres has a 8 byte transaction id, but it is only 4 bytes, so we only need to save the insertion and deletion xids. So 8 bytes more per tuple. Well in the heap we need 4 bytes: xmin 4 bytes: xmax 4 bytes: cid 6 bytes: ctid 6 bytes: various info bits including natts In indexes we currently get away with a reduced header which has few of the 6 bytes of info bits. However the only reason we can do is because we impose arbitrary limitations that work for indexes but wouldn't be reasonable for tables. Such as a lower maximum number of columns, inability to add new columns or drop columns later, etc. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Greg Stark gsst...@mit.edu writes: In indexes we currently get away with a reduced header which has few of the 6 bytes of info bits. However the only reason we can do is because we impose arbitrary limitations that work for indexes but wouldn't be reasonable for tables. Such as a lower maximum number of columns, inability to add new columns or drop columns later, etc. Wait a second, which idea are we currently talking about? No heap at all, or just the ability to check visibility without visiting the heap? If it's a genuine IOT (ie no separate heap), then you are not going to be able to get away without a full heap tuple header. We've sweated blood to get that struct down to where it is; there's no way to make it smaller without giving up some really fundamental things, for example the ability to do UPDATE :-( If you just want to avoid a heap visit for visibility checks, I think you'd only need to add xmin/xmax/cmin plus the hint bits for same. This is going to end up costing 16 bytes in practice --- you might think you could squeeze into 12 but on 64-bit machines (MAXALIGN 8) you'll save nothing. So that's effectively a doubling of index size for common cases such as a single int4 or int8 index column. The other problem is the extra write load created by needing to update the index's copies of the hint bits; not to mention extra writes to freeze the xids when they get old enough. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Wait a second, which idea are we currently talking about? No heap at all, or just the ability to check visibility without visiting the heap? I was talking about the indexes with snapshot If it's a genuine IOT (ie no separate heap), then you are not going to be able to get away without a full heap tuple header. We've sweated blood to get that struct down to where it is; there's no way to make it smaller without giving up some really fundamental things, for example the ability to do UPDATE :-( Of course, as i said, the leaf pages will have HeapTuples in IOT. As a Postgres user, definitely i am thankful for what has been done. If you just want to avoid a heap visit for visibility checks, I think you'd only need to add xmin/xmax/cmin plus the hint bits for same. This is going to end up costing 16 bytes in practice --- you might think you could squeeze into 12 but on 64-bit machines (MAXALIGN 8) you'll save nothing. So that's effectively a doubling of index size for common cases such as a single int4 or int8 index column. Yes but currently we are storing the size of index in IndexTuple, which is also stored in ItemId. If we can somehow make it use that info, then we have 13 bits of flag for free and we can reduce it to 8 bytes of extra info. But we need you to sweat some more blood for that :). But again, unless we resolve the volatile functions issue, there is no use in worrying about this. The other problem is the extra write load created by needing to update the index's copies of the hint bits; not to mention extra writes to freeze the xids when they get old enough. But Tom, i remember that the vacuum was faster when index had visibility info, since we need not touch the table. But maybe i am wrong. Atleast i remember that was the case, when the relation had only thick indexes. Oh..Yeah... visibility map might have changed the equation. Thanks, Gokul
Re: [HACKERS] A thought on Index Organized Tables
The other problem is the extra write load created by needing to update the index's copies of the hint bits; not to mention extra writes to freeze the xids when they get old enough. But Tom, i remember that the vacuum was faster when index had visibility info, since we need not touch the table. But maybe i am wrong. I disagree with that, Gokul -- if the ordering operators are volatile or just incorrect, during DELETE, you could set xmax in the wrong IndexTuple. Then there will be another IndexTuple that says it's visible, but it points to a non-visible heap tuple. I think you should follow the pointers to the heap before you decide to let an index tuple remain in the index during vacuum. This would ensure that all references from an index to a heap tuple are removed before vacuuming the heap tuple. I would be worried about what might break if this invariant doesn't hold. Tom is right about all the extra overhead involved with keeping visibility info in the index. But it can be a good trade-off in some cases. Karl
Re: [HACKERS] A thought on Index Organized Tables
On Thu, Feb 25, 2010 at 9:25 PM, Tom Lane t...@sss.pgh.pa.us wrote: We've sweated blood to get that struct down to where it is; there's no way to make it smaller without giving up some really fundamental things, for example the ability to do UPDATE :-( Oh, this is a tangent but I think there are some more gains there, at least now that we've eliminated vacuum full. The more we save the more complex the code and data structure becomes so there may be a point where it's not worthwhile any more. And of course if we do try to do any of these then it wouldn't be part of IOT it would be a general improvement which would help tables as well. For future reference, here are some items that have come up in the past: 1) We've talked about having a common xmin in the page header and then a bit indicating that the xmin is missing from the tuple header because it matches the value in the page header. This would save a lot of space in the common case where data was all loaded in a single transaction and all the tuples have the same xmin. 2) Now that we don't have vacuum full the command-id is kind of a waste. We could replace it with some kind of local memory data structure which is capable of spilling to disk. When the transaction commits it can be thrown away and no other session needs to be able to see it. This could have an impact on future work on parallel query but I think our phantom-command-id already has such issues anyways. 3) xmax and ctid are unavoidable since we never know when a tuple might be deleted or updated in the future. But if we allowed the user to mark a table insert-only then it could be left out and any operation which tries to delete, update, or select for update a row in the table would throw an error. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Greg Stark gsst...@mit.edu writes: 2) Now that we don't have vacuum full the command-id is kind of a waste. Not really. We could replace it with some kind of local memory data structure which is capable of spilling to disk. The performance costs of that would probably outweigh any space savings. I think our phantom-command-id already has such issues anyways. It can, but it's relatively uncommon to update a large number of tuples more than once in a transaction. What you're suggesting would move that bottleneck into mainstream cases. And it would be a bigger bottleneck since you would have no lookup key available within the tuple header. You'd have to use ctid as the lookup key which means no ability to use one table entry for multiple rows, not to mention what do you do before the tuple has a ctid assigned? 3) xmax and ctid are unavoidable since we never know when a tuple might be deleted or updated in the future. But if we allowed the user to mark a table insert-only then it could be left out and any operation which tries to delete, update, or select for update a row in the table would throw an error. Anything with this field is optional is going to be a complete disaster for mapping C structs over tuple headers... regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
If it's of any interest, I can say something about the hint bits in the index tuple header. In my implementation, my decision was to use only one hint bit. It went into the unused 13th bit of the IndexTuple header. When the hint bit is set, it means that (xmin is committed OR xmin = InvalidTransactionId) AND (xmax is committed OR xmax = InvalidTransactionId) Then there are 12 bytes for xmin/xmax/cid. I did sweat something over this decision... but maybe it was a wasted effort if the 12 bytes end up occupying 16 bytes anyway. Karl On Thu, Feb 25, 2010 at 1:25 PM, Tom Lane t...@sss.pgh.pa.us wrote: Greg Stark gsst...@mit.edu writes: In indexes we currently get away with a reduced header which has few of the 6 bytes of info bits. However the only reason we can do is because we impose arbitrary limitations that work for indexes but wouldn't be reasonable for tables. Such as a lower maximum number of columns, inability to add new columns or drop columns later, etc. Wait a second, which idea are we currently talking about? No heap at all, or just the ability to check visibility without visiting the heap? If it's a genuine IOT (ie no separate heap), then you are not going to be able to get away without a full heap tuple header. We've sweated blood to get that struct down to where it is; there's no way to make it smaller without giving up some really fundamental things, for example the ability to do UPDATE :-( If you just want to avoid a heap visit for visibility checks, I think you'd only need to add xmin/xmax/cmin plus the hint bits for same. This is going to end up costing 16 bytes in practice --- you might think you could squeeze into 12 but on 64-bit machines (MAXALIGN 8) you'll save nothing. So that's effectively a doubling of index size for common cases such as a single int4 or int8 index column. The other problem is the extra write load created by needing to update the index's copies of the hint bits; not to mention extra writes to freeze the xids when they get old enough. regards, tom lane
Re: [HACKERS] A thought on Index Organized Tables
I disagree with that, Gokul -- if the ordering operators are volatile or just incorrect, during DELETE, you could set xmax in the wrong IndexTuple. Then there will be another IndexTuple that says it's visible, but it points to a non-visible heap tuple. I think you should follow the pointers to the heap before you decide to let an index tuple remain in the index during vacuum. This would ensure that all references from an index to a heap tuple are removed before vacuuming the heap tuple. I would be worried about what might break if this invariant doesn't hold. Well, Karl, if we have to support function based indexes/IOT, one thing is for sure. We can't support them for volatile functions / broken data types. Everyone agrees with that. But the question is how we identify something is not a volatile function. Only way currently is to let the user make the decision( Or we should consult some mathematician ). So we need not consult the heaptuple. Gokul.
Re: [HACKERS] A thought on Index Organized Tables
On Thu, Feb 25, 2010 at 3:59 PM, Gokulakannan Somasundaram gokul...@gmail.com wrote: I disagree with that, Gokul -- if the ordering operators are volatile or just incorrect, during DELETE, you could set xmax in the wrong IndexTuple. Then there will be another IndexTuple that says it's visible, but it points to a non-visible heap tuple. I think you should follow the pointers to the heap before you decide to let an index tuple remain in the index during vacuum. This would ensure that all references from an index to a heap tuple are removed before vacuuming the heap tuple. I would be worried about what might break if this invariant doesn't hold. Well, Karl, if we have to support function based indexes/IOT, one thing is for sure. We can't support them for volatile functions / broken data types. Everyone agrees with that. But the question is how we identify something is not a volatile function. Only way currently is to let the user make the decision( Or we should consult some mathematician ). So we need not consult the heaptuple. First of all, volatility is not the only issue. The ordering ops could also be incorrect, e.g., violate the transitivity property. there is no reliable way to determine if a function is volatile and/or incorrectly specified. Of course, PG can't support indexing with incorrect functions. However, it's worthwhile to guard against too much damage being done if the user's function has a bug. Maybe I'm wrong? Maybe an index tuple with a dangling pointer is actually harmless? Karl
Re: [HACKERS] A thought on Index Organized Tables
Karl Schnaitter karl...@gmail.com writes: If it's of any interest, I can say something about the hint bits in the index tuple header. In my implementation, my decision was to use only one hint bit. It went into the unused 13th bit of the IndexTuple header. When the hint bit is set, it means that (xmin is committed OR xmin = InvalidTransactionId) AND (xmax is committed OR xmax = InvalidTransactionId) Then there are 12 bytes for xmin/xmax/cid. I did sweat something over this decision... but maybe it was a wasted effort if the 12 bytes end up occupying 16 bytes anyway. Actually, if you need to squeeze a few more bits into that word, the thing to do would be to get rid of storing the tuple length there. This would involve adding the same type of indirection header that we use for HeapTuples, so that the length would be available at need without going back to the item pointer. It'd be an invasive code change but reasonably straightforward, and then you'd have room for normal hint bits. Squeezing cmin in there is just fantasy though. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Karl Schnaitter karl...@gmail.com writes: Of course, PG can't support indexing with incorrect functions. However, it's worthwhile to guard against too much damage being done if the user's function has a bug. Maybe I'm wrong? Maybe an index tuple with a dangling pointer is actually harmless? No, it's far from harmless. As soon as that heap TID gets filled with an unrelated tuple, you run the risk of indexscans alighting on and perhaps modifying the wrong tuple. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Tom, Actually, if you need to squeeze a few more bits into that word, the thing to do would be to get rid of storing the tuple length there. This would involve adding the same type of indirection header that we use for HeapTuples, so that the length would be available at need without going back to the item pointer. I I feel the other one is easy. To store the hint bits inside the ItemId, in the place of size. We have 16 bits there.Whenever the size is required, we need to follow the offset and goto the corresponding tuple and then take the size from there. The change seems to be minimal, but please bear with me, if i am very ignorant about something. Squeezing cmin in there is just fantasy though. I think we can get away with this, by making the person, who inserts and selects in the same transaction to go and find the visibility through heap. In the Index tuple hint bits, we can note down, if the command is a simple insert/update/delete. By Simple insert, i mean that it doesn't have a select. So if that is the case, it can be made visible to statements within the same transaction. We can even document, that people can just insert a savepoint between their insert and select. This would increase the xid and make that tuple visible within the same transaction. All that seems to be possible. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
First of all, volatility is not the only issue. The ordering ops could also be incorrect, e.g., violate the transitivity property. there is no reliable way to determine if a function is volatile and/or incorrectly specified. No it is the only issue. If you create a datatype with volatile function for ordering ops, then you have the broken data type(the one you are referring to). So they are one and the same. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
No, it's far from harmless. As soon as that heap TID gets filled with an unrelated tuple, you run the risk of indexscans alighting on and perhaps modifying the wrong tuple. Tom, In the Function based indexes on those functions, which we are suspecting to be a volatile one Or in the datatypes, which we suspect to be broken, can we have additional checks to ensure that to ensure that this does not happen? I mean, do you think, that would solve the issue? Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
On Fri, Feb 26, 2010 at 9:54 AM, Gokulakannan Somasundaram gokul...@gmail.com wrote: No, it's far from harmless. As soon as that heap TID gets filled with an unrelated tuple, you run the risk of indexscans alighting on and perhaps modifying the wrong tuple. Tom, i think this will never happen. The only issue is when we need to go back to the index from heap. This is to update the timestamps of update/delete. Gokul.
Re: [HACKERS] A thought on Index Organized Tables
Gokulakannan Somasundaram gokul...@gmail.com writes: Actually, if you need to squeeze a few more bits into that word, the thing to do would be to get rid of storing the tuple length there. This would involve adding the same type of indirection header that we use for HeapTuples, so that the length would be available at need without going back to the item pointer. I I feel the other one is easy. To store the hint bits inside the ItemId, in the place of size. No, we're not going there. That breaks the fundamental page content manipulation algorithms, and falls down for tuples not yet stored in a page (or being examined without a pointer to the page readily at hand), and has no redeeming social value anyway compared to doing it in the proven fashion. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Gokulakannan Somasundaram gokul...@gmail.com writes: In the Function based indexes on those functions, which we are suspecting to be a volatile one Or in the datatypes, which we suspect to be broken, can we have additional checks to ensure that to ensure that this does not happen? I mean, do you think, that would solve the issue? Proving that a set of comparison operators are consistent just by examining their runtime behavior is probably equivalent to solving the halting problem. I can't see us doing it, or wanting to accept the overhead of checking it even if it could be done. To be a bit more concrete: the typical sort of failure that you could get from broken btree operators is failure of transitivity, that is the comparators report A B and B C for some A, B, C, but do not say that A C when those two values are compared directly. I don't see any convenient way to detect that as a byproduct of normal index operations, because you wouldn't typically have a reason to make all three comparisons in close proximity. Indeed, the searching and sorting algorithms do their best to avoid making redundant comparisons of that kind. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
No, we're not going there. That breaks the fundamental page content manipulation algorithms, and falls down for tuples not yet stored in a page (or being examined without a pointer to the page readily at hand), and has no redeeming social value anyway compared to doing it in the proven fashion. Tom, I was also concerned regarding that, but just thought of informing you about the option. But i think it will never fall down for tuples not stored in the page. As we have the offset and the hint bits to mention whether a tuple is there or not. Only the two byte size field will move down by my suggestion. But your intuition has the most probability of success. My concern was that it would make the page of a heap different from page of a b-tree index. Gokul.
Re: [HACKERS] A thought on Index Organized Tables
Proving that a set of comparison operators are consistent just by examining their runtime behavior is probably equivalent to solving the halting problem. I can't see us doing it, or wanting to accept the overhead of checking it even if it could be done. The overhead of checking is very minimal. When we update, we have to just carry the tuple id of the heaptuple and insert transaction id. We check whether they are same with the index snapshot. If it is not same, then we will go ahead and start treating this index as either dropped / as a normal index ( without snapshot ). Since the overhead of dropping / marking it as normal index will occur very rarely, we need not be concerned about that performance impact ( i suppose). The overhead of checking is going to be there only on suspicious user defined functions. ( We can have a flag for is_suspicious ) To be a bit more concrete: the typical sort of failure that you could get from broken btree operators is failure of transitivity, that is the comparators report A B and B C for some A, B, C, but do not say that A C when those two values are compared directly. I don't see any convenient way to detect that as a byproduct of normal index operations, because you wouldn't typically have a reason to make all three comparisons in close proximity. Indeed, the searching and sorting algorithms do their best to avoid making redundant comparisons of that kind. I am not saying that we should do analysis of runtime behavior. I am saying that, we would provide a set of built-in functions which will be always stable (with some flag in pg_proc) . We will scan the provided function for any functions that are not in the stable set provided, when it gets created. Now if the function has one such function, then it is declared as suspicious to be broken/volatile. Thanks for the reply, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
I think Gokul was asking because he wanted to work on it, but wanted to check community approval first. Yes the problem is that we need to come to a consensus on broken data types. As Heikki pointed out, those data types, which is based on a unstable function like time, date, random etc. This is definitely a theoretical possibility, but still we want to continue building indexes which supports these features. If we can take a decision regarding this, we can have a feature like IOT.. There's many tricks like column-oriented storage, compression, index-organised-tables etc. that would be nice to have. Whether any particular feature is worthwhile in the end, the devil is in the details. Please consider my following statements from a database tuner perspective. I don't want to discourage the visibility map feature, but it has the disadvantages, which we already discussed. While i do a explain analyze and i see 300 reads, but the same query in production might lead to 400 reads(with all the extra 100 being random i/os), because of the state of the visibility map. If there is a long batch job running somewhere in the database, it will affect almost all the visibility maps of the relation. So how can a person, tune and test a query in dev and put it in production and be confident about the i/o performance ? Say Visibility map goes into core after 9.x, the performance of those databases will be less compared to the previous release in these circumstances. All i am trying to say is that the visibility map has cases, where it will be ineffective and are we deciding to find solutions in those cases. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
On Wed, 2010-02-24 at 13:50 +0530, Gokulakannan Somasundaram wrote: Please consider my following statements from a database tuner perspective. I don't want to discourage the visibility map feature, but it has the disadvantages, which we already discussed. While i do a explain analyze and i see 300 reads, but the same query in production might lead to 400 reads(with all the extra 100 being random i/os), because of the state of the visibility map. If there is a long batch job running somewhere in the database, it will affect almost all the visibility maps of the relation. So how can a person, tune and test a query in dev and put it in production and be confident about the i/o performance ? Say Visibility map goes into core after 9.x, the performance of those databases will be less compared to the previous release in these circumstances. I would add that both Heikki and Greg Stark have argued at length that the visibility map cannot be relied upon in production systems. Those arguments were deployed when considering the use of the VM for partitioning, yet they apply equally to use of the VM in other contexts. The fragility there is not an issue in a mostly read-only application, but it definitely would be a concern in other cases. -- Simon Riggs www.2ndQuadrant.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Simon Riggs wrote: I would add that both Heikki and Greg Stark have argued at length that the visibility map cannot be relied upon in production systems. It cannot be relied on *in its current form*. There's a hole in crash recovery where it can be left in an inconsistent state. That obviously needs to be fixed before it is relied on for index-only-scans or similar purposes, but it's not an insurmountable problem. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
On Wed, 2010-02-24 at 10:40 +0200, Heikki Linnakangas wrote: Simon Riggs wrote: I would add that both Heikki and Greg Stark have argued at length that the visibility map cannot be relied upon in production systems. It cannot be relied on *in its current form*. There's a hole in crash recovery where it can be left in an inconsistent state. That obviously needs to be fixed before it is relied on for index-only-scans or similar purposes, but it's not an insurmountable problem. I was referring to earlier discussions around the use of that information for use in partitioning. At that time it was argued the technique would be fragile and unusable in production systems, even assuming the information was accurate. Regrettably, I agree: even a light write workload is sufficient to render the technique useless and designing systems that relied upon that would be risky. -- Simon Riggs www.2ndQuadrant.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
The fragility there is not an issue in a mostly read-only application, but it definitely would be a concern in other cases. While we accept that visibility map is good for read only application, why can't we make it optional? Atleast if there is a way for a person to drop the visibility map for a table(if it gets created by default), the application need not incur the overhead for those tables, when it knows it is update intensive / with batch jobs. Again not to deviate from my initial question, can we make a decision regarding unstable/mutable functions / broken data types ? Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
On Wed, Feb 24, 2010 at 12:53 AM, Gokulakannan Somasundaram gokul...@gmail.com wrote: Again not to deviate from my initial question, can we make a decision regarding unstable/mutable functions / broken data types ? I second this question. A year or two ago, Gokul and I both proposed a feature that put visibility metadata into the index tuples and supported index-only scans, and the idea was dismissed because a user might choose incorrect ordering operators. I tried to ask for a clear explanation of the issue, but never got it. Incorrect operators and mutable functions will surely lead to incorrect query results, but that is already a possibility with any index. It's also possible that a heap tuple is deleted, but the deletion is not recorded in the index because the tuple wasn't found. This is okay because (1) the heap tuple will remain where it is until vacuuming, and (2) during vacuuming, the visibility metadata in the index should be ignored when determining whether an index tuple points to a dead heap tuple. This ensures that all references to a heap tuple are removed before wiping it out. The bottom line is that the visibility metadata is a good thing if you know when to trust it. It's fine to trust it when evaluating a SELECT. But not during a more dangerous operation like VACUUM. Karl
Re: [HACKERS] A thought on Index Organized Tables
On Wed, 2010-02-24 at 14:23 +0530, Gokulakannan Somasundaram wrote: can we make a decision regarding unstable/mutable functions / broken data types ? You need to take about 5 steps back. Diving straight into a particular technical detail is not the right approach. Nobody will confirm a decision on anything without first understanding the whole question and how it relates to something they care about. -- Simon Riggs www.2ndQuadrant.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Gokulakannan Somasundaram wrote: While we accept that visibility map is good for read only application, why can't we make it optional? Atleast if there is a way for a person to drop the visibility map for a table(if it gets created by default), the application need not incur the overhead for those tables, when it knows it is update intensive / with batch jobs. If you have a scenario where the visibility map incurs a measurable overhead, let's hear it. I didn't see any in the tests I performed, but it's certainly possible that if the circumstances are just right it makes a difference. Again not to deviate from my initial question, can we make a decision regarding unstable/mutable functions / broken data types ? *Sigh*. Yes. You need to deal with them. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Forgot to include the group.. On Wed, Feb 24, 2010 at 5:38 PM, Gokulakannan Somasundaram gokul...@gmail.com wrote: I am not familiar with this term broken data types, and I just looked for it in the source code and couldn't find it. What exactly are you referring to? cheers andrew Sorry i missed this. Actually if we create a function A which uses functions like time(), date() and random(), then this function A won't give the same output, even if we give the same input. So if a person has created a data type, which uses these functions, then it can't be made as a primary key in an Index organized table, because i need to reach the same tuple by applying the function on the supplied values. But since the function is mutable, we can't reach the same tuple. If we decide to support only datatypes containing immutable functions, then there might be people who have created these kind of functions and marked it as immutable( while they are mutable functions). So those functions will result in index-corruption / failed operation. Only if we resolve this issue we can have data structures like IOT. Hope, i was clear. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
If you have a scenario where the visibility map incurs a measurable overhead, let's hear it. I didn't see any in the tests I performed, but it's certainly possible that if the circumstances are just right it makes a difference. Heikki, The obvious one, i could observe is that it would increase the WAL contention. Am i missing something? All i am suggesting is to reduce the unnecessary work required in those tables, where the visibility map is not required. For example, in data warehouses, people might even have a tables without any indexes. Why do we ask them to incur the overhead of visibility map? Also since you have made the visibility maps without any page level locking, have you considered whether it would make sure the correct order of inserts into the WAL? i have looked at some random threads, but i couldn't get the complete design of visibility map to be used for index only scans. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
On Wed, Feb 24, 2010 at 9:41 AM, Gokulakannan Somasundaram gokul...@gmail.com wrote: If you have a scenario where the visibility map incurs a measurable overhead, let's hear it. I didn't see any in the tests I performed, but it's certainly possible that if the circumstances are just right it makes a difference. Heikki, The obvious one, i could observe is that it would increase the WAL contention. Am i missing something? All i am suggesting is to reduce the unnecessary work required in those tables, where the visibility map is not required. For example, in data warehouses, people might even have a tables without any indexes. Why do we ask them to incur the overhead of visibility map? I think you're a barking up the wrong tree. AFAIUI, the need for the visibility map has not very much to do with whether the table has indices, and everything to do with avoiding unnecessary VACUUMs. In any event, you've not shown that the visibility map HAS any overhead, so talking about skipping it seems entirely premature. Keep in mind that the visibility map is quite small. The point of the visibility map as far as index-only scans are concerned is that if all the needed column values can be extracted from the index, we still need to read the heap page to check tuple visibility - unless, of course, we already know from the visibility map that all the tuples on that heap page are guaranteed to be visible to all transactions. On a read-only or read-mostly table, this will reduce the cost of checking tuple visibility by several orders of magnitude. ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Karl Schnaitter karl...@gmail.com writes: On Wed, Feb 24, 2010 at 12:53 AM, Gokulakannan Somasundaram gokul...@gmail.com wrote: Again not to deviate from my initial question, can we make a decision regarding unstable/mutable functions / broken data types ? I second this question. A year or two ago, Gokul and I both proposed a feature that put visibility metadata into the index tuples and supported index-only scans, and the idea was dismissed because a user might choose incorrect ordering operators. I tried to ask for a clear explanation of the issue, but never got it. The fundamental point IMHO is that indexes are more complex and much more fragile than heaps. This is obviously true theoretically and we have years of experience that proves it to be true in the field as well. Broken comparison functions are just one of the possible hazards; there are many others. Now with standard indexes you can always recover from any problem via REINDEX; no matter how badly the index is messed up, your data is still there and not damaged. (Well, maybe it will fail a unique constraint check or something, but at least it's still there.) With an IOT I don't understand how you get out of index corruption without data loss. That's a showstopper for practical use, I think. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Tom Lane t...@sss.pgh.pa.us wrote: The fundamental point IMHO is that indexes are more complex and much more fragile than heaps. This is obviously true theoretically and we have years of experience that proves it to be true in the field as well. Broken comparison functions are just one of the possible hazards; there are many others. Now with standard indexes you can always recover from any problem via REINDEX; no matter how badly the index is messed up, your data is still there and not damaged. (Well, maybe it will fail a unique constraint check or something, but at least it's still there.) With an IOT I don't understand how you get out of index corruption without data loss. That's a showstopper for practical use, I think. Having used the IOT implementation (clustered indexes) in SQL Server and then Sybase ASE starting with SQL Server 1.0, I can relate my experiences on that. In about 18 years with over 100 databases we had maybe five or ten times that such damage made it difficult to recover data -- typically the result of hardware problems. This implementation had a double linked list of pointers through the leaf level pages, so normally a query which generated a full table scan would follow these and work. When said pointers were damaged we would query through the index tree to see what we could reach. There were usually other indexes on tables, which would give us other paths to the data in these leaf pages. It was sometimes necessary to subdivide a range in which we were getting an error to find the edges of the damaged area. There were sometimes small areas we could not reach, for which we had to look to backups or source documents. There's clearly no database technology which guarantees you will never have to do that in the face of a hardware failure. To the extent that such a technique reduces the redundant storage of values, it clearly affects recovery options. All in all, I suspect that it would be underrating the talent pool available for PostgreSQL development to say we can't get to a feature which SQL server had in version 1.0 and maintains through their conversion to MVCC. Where it fits in the scheme of priorities and cost/benefit is certainly a valid question. It does provide significant benefits for some use cases, but it's certainly not trivial to implement. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
On Wed, Feb 24, 2010 at 3:12 PM, Tom Lane t...@sss.pgh.pa.us wrote: With an IOT I don't understand how you get out of index corruption without data loss. That's a showstopper for practical use, I think. That doesn't seem insurmountable to me. You could always allow a REINDEX to scan the index sequentially, ignoring any index structure, just using the tuples it finds. However it seems to me this discussion has several only barely related issues being covered. 1) transaction information in index This seems like a lot of bloat in indexes. It also means breaking a lot of other optimizations such as being able to read the tuples directly from the heap page without locking. I'm not sure how much those are worth though. But adding 24 bytes to every index entry seems pretty unlikely to be a win anyways. 2) Index organized tables This seems like a non-starter to me. We would lose the option of doing sequential scans and the ability to have any other indexes on the table. That would be comparable to Oracle circa 1985. We can do better with stuff like Heikki's grouped index tuple and the visibility map which don't interfere with other features as much. 3) Depending on refinding keys in the index for basic operatoin Currently if your index procedure/operator is ill-behaved then your index searches might fail to return matching keys. But vacuum will work correctly and you will never have an index pointer pointing to a dead tuple or a tuple different from the one that was originally inserted. Things like retail vacuum were proposed in the past but were rejected because the consequences of an incorrect index procedure become much worse. You could get dangling index pointers pointing to nonexistent tuples or even pointing to new tuples that have been inserted into the same slot later. I don't think these three are actually related. Afaict neither IOT nor visibility information in indexes depend on refinding keys in the index. But it's possible I'm missing something. Even so they're still three separate issues. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
I think you're a barking up the wrong tree. AFAIUI, the need for the visibility map has not very much to do with whether the table has indices, and everything to do with avoiding unnecessary VACUUMs. In any event, you've not shown that the visibility map HAS any overhead, so talking about skipping it seems entirely premature. Keep in mind that the visibility map is quite small. OK! i am not saying to remove the visibility map, if i am misunderstood. All i am saying here is to remove the index only scan processing of visibility map. If it is being used only for vacuums, you need not make it crash safe and no WAL comes into picture. The point of the visibility map as far as index-only scans are concerned is that if all the needed column values can be extracted from the index, we still need to read the heap page to check tuple visibility - unless, of course, we already know from the visibility map that all the tuples on that heap page are guaranteed to be visible to all transactions. On a read-only or read-mostly table, this will reduce the cost of checking tuple visibility by several orders of magnitude. I understand that. As i suggested above, if you have no indexes for a table, why do you need to spend the extra effort in making it crash safe for that table? Hope i am clear. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
But adding 24 bytes to every index entry seems pretty unlikely to be a win anyways. We actually wanted to make it optional. Not every index will be like that. More than that we can make it into 16 bytes. Only commands within the same transaction will not be able to do a index only scan. This seems like a non-starter to me. We would lose the option of doing sequential scans and the ability to have any other indexes on the table. That would be comparable to Oracle circa 1985. We can do better with stuff like Heikki's grouped index tuple and the visibility map which don't interfere with other features as much. Sequential scans can be done on IOTs, just scan through the leaf pages. I think you are talking about IOTs with overflow regions. As i said already, this serves a different set of options to the DB Designer. I don't think these three are actually related. Afaict neither IOT nor visibility information in indexes depend on refinding keys in the index. But it's possible I'm missing something. Even so they're still three separate issues. If we have visibility information in a heap, we need to goto the same index tuple, whenever there is a update/delete. Now if there is a broken function, it won't let us reach the index from the heap tuple . Hope you are able to get it. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
With an IOT I don't understand how you get out of index corruption without data loss. That's a showstopper for practical use, I think. For simplicity, say we are storing all the non-leaf pages of the index in a seperate file, then the leaf pages are nothing but the table. So if we can replicate the table, then we can replicate the non-leaf pages (say by some modified version of reindex). Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
On Wed, Feb 24, 2010 at 11:05 AM, Gokulakannan Somasundaram gokul...@gmail.com wrote: I think you're a barking up the wrong tree. AFAIUI, the need for the visibility map has not very much to do with whether the table has indices, and everything to do with avoiding unnecessary VACUUMs. In any event, you've not shown that the visibility map HAS any overhead, so talking about skipping it seems entirely premature. Keep in mind that the visibility map is quite small. OK! i am not saying to remove the visibility map, if i am misunderstood. All i am saying here is to remove the index only scan processing of visibility map. If it is being used only for vacuums, you need not make it crash safe and no WAL comes into picture. So basically you want to have index-only scans, but you want them to be really slow? The point of the visibility map as far as index-only scans are concerned is that if all the needed column values can be extracted from the index, we still need to read the heap page to check tuple visibility - unless, of course, we already know from the visibility map that all the tuples on that heap page are guaranteed to be visible to all transactions. On a read-only or read-mostly table, this will reduce the cost of checking tuple visibility by several orders of magnitude. I understand that. As i suggested above, if you have no indexes for a table, why do you need to spend the extra effort in making it crash safe for that table? Hope i am clear. Tables without indices don't need to be crash safe? News to me. ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Gokulakannan Somasundaram gokul...@gmail.com wrote: With an IOT I don't understand how you get out of index corruption without data loss. That's a showstopper for practical use, I think. For simplicity, say we are storing all the non-leaf pages of the index in a seperate file, then the leaf pages are nothing but the table. So if we can replicate the table, then we can replicate the non-leaf pages (say by some modified version of reindex). So you are essentially proposing that rather than moving the heap data into the leaf tuples of the index in the index file, you will move the leaf index data into the heap tuples? The pages in such a IOT heap file would still need to look a lot like index pages, yes? I'm not saying it's a bad idea, but I'm curious what benefits you see to taking that approach. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Kevin Grittner kevin.gritt...@wicourts.gov writes: So you are essentially proposing that rather than moving the heap data into the leaf tuples of the index in the index file, you will move the leaf index data into the heap tuples? The pages in such a IOT heap file would still need to look a lot like index pages, yes? I'm not saying it's a bad idea, but I'm curious what benefits you see to taking that approach. Isn't that just a variant on Heikki's grouped index tuples idea? regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Gokulakannan Somasundaram wrote: If you have a scenario where the visibility map incurs a measurable overhead, let's hear it. I didn't see any in the tests I performed, but it's certainly possible that if the circumstances are just right it makes a difference. Heikki, The obvious one, i could observe is that it would increase the WAL contention. Am i missing something? Yes. The visibility map doesn't need any new WAL records to be written. We probably will need to add some WAL logging to close the holes with crash recovery, required for relying on it for index-only-scans, but AFAICS only for VACUUM and probably only one WAL record for a whole bunch of heap pages, so it should be pretty insignificant. All i am suggesting is to reduce the unnecessary work required in those tables, where the visibility map is not required. For example, in data warehouses, people might even have a tables without any indexes. Why do we ask them to incur the overhead of visibility map? To make it possible to do partial VACUUMs. That's why the visibility map was put into 8.4. Let me repeat myself: if you think the overhead of a visibility map is noticeable or meaningful in any scenario, the onus is on you to show what that scenario is. I am not aware of such a scenario, which doesn't mean that it doesn't exist, of course, but hand-waving is not helpful. Also since you have made the visibility maps without any page level locking, have you considered whether it would make sure the correct order of inserts into the WAL? i have looked at some random threads, but i couldn't get the complete design of visibility map to be used for index only scans. I'm not sure what you mean with without any page level locking. Whenever a visibility map page is read or modified, a lock is taken on the buffer. I believe the current visibility map is free of race conditions, even if it was used for index-only-scans, if that's what you mean. The critical part is when a bit is cleared in the visibility map. It is done just after inserting/deleting the heap tuple, which is OK because in the window between modifying the heap page and clearing bit in the visibility map, no other backend could see the actions of the modifying transaction yet anyway. The index updates have not been made yet, so the information in the indexes are still valid for the other transaction's snapshot. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Tom Lane t...@sss.pgh.pa.us wrote: Isn't that just a variant on Heikki's grouped index tuples idea? With apologies to Heikki for having forgotten that effort, yes. With the simplifying technique of keeping the leaf level in a separate file, it becomes hard to distinguish from Heikki's Grouped Index Tuples approach when you include the maintain cluster order patch. That really looks like where anyone should work from for any IOT effort. It appears to have been largely completed years ago. For those who missed or forgot it, this is the latest I could find: http://community.enterprisedb.com/git/ Heikki, any thoughts on what it would take, beside cleaning up bit rot? -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Kevin Grittner wrote: With the simplifying technique of keeping the leaf level in a separate file, it becomes hard to distinguish from Heikki's Grouped Index Tuples approach when you include the maintain cluster order patch. That really looks like where anyone should work from for any IOT effort. It appears to have been largely completed years ago. For those who missed or forgot it, this is the latest I could find: http://community.enterprisedb.com/git/ Heikki, any thoughts on what it would take, beside cleaning up bit rot? There was discussion on the indexam API changes required, I don't recall the details right now. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
On Wed, Feb 24, 2010 at 4:12 PM, Gokulakannan Somasundaram gokul...@gmail.com wrote: Sequential scans can be done on IOTs, just scan through the leaf pages. That doesn't work because when you split an index page any sequential scan in progress will either see the same tuples twice or will miss some tuples depending on where the new page is allocated. Vacuum has a clever trick for solving this but it doesn't work for arbitrarily many concurrent scans. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Greg Stark gsst...@mit.edu wrote: Gokulakannan Somasundaram gokul...@gmail.com wrote: scan through the leaf pages. That doesn't work because when you split an index page any sequential scan in progress will either see the same tuples twice or will miss some tuples depending on where the new page is allocated. Vacuum has a clever trick for solving this but it doesn't work for arbitrarily many concurrent scans. It sounds like you're asserting that Index Scan nodes are inherently unreliable, so I must be misunderstanding you. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
On Wed, 2010-02-24 at 15:52 +, Greg Stark wrote: We can do better with stuff like Heikki's grouped index tuple and the visibility map which don't interfere with other features as much. Yes, much better plan. More practical, nearly there. -- Simon Riggs www.2ndQuadrant.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Kevin Grittner kevin.gritt...@wicourts.gov writes: Greg Stark gsst...@mit.edu wrote: That doesn't work because when you split an index page any sequential scan in progress will either see the same tuples twice or will miss some tuples depending on where the new page is allocated. Vacuum has a clever trick for solving this but it doesn't work for arbitrarily many concurrent scans. It sounds like you're asserting that Index Scan nodes are inherently unreliable, so I must be misunderstanding you. We handle splits in a manner that insures that concurrent index-order scans remain consistent. I'm not sure that it's possible to scale that to ensure that both index-order and physical-order scans would remain consistent. It might be soluble but it's certainly something to worry about. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
On Wed, Feb 24, 2010 at 5:46 PM, Tom Lane t...@sss.pgh.pa.us wrote: Kevin Grittner kevin.gritt...@wicourts.gov writes: Greg Stark gsst...@mit.edu wrote: That doesn't work because when you split an index page any sequential scan in progress will either see the same tuples twice or will miss some tuples depending on where the new page is allocated. Vacuum has a clever trick for solving this but it doesn't work for arbitrarily many concurrent scans. It sounds like you're asserting that Index Scan nodes are inherently unreliable, so I must be misunderstanding you. We handle splits in a manner that insures that concurrent index-order scans remain consistent. I'm not sure that it's possible to scale that to ensure that both index-order and physical-order scans would remain consistent. It might be soluble but it's certainly something to worry about. It might be slightly easier given the assumption that you only want to scan leaf tuples. But there's an additional problem I didn't think of before. Currently we optimize index scans by copying all relevant tuples to local memory so we don't need to hold an index lock for an extended time or spend a lot of time relocking and rechecking the index for changes. That wouldn't be possible if we needed to get visibility info from the page since we would need up-to-date information. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
On Wed, Feb 24, 2010 at 10:09 PM, Tom Lane t...@sss.pgh.pa.us wrote: Kevin Grittner kevin.gritt...@wicourts.gov writes: So you are essentially proposing that rather than moving the heap data into the leaf tuples of the index in the index file, you will move the leaf index data into the heap tuples? The pages in such a IOT heap file would still need to look a lot like index pages, yes? I'm not saying it's a bad idea, but I'm curious what benefits you see to taking that approach. Isn't that just a variant on Heikki's grouped index tuples idea? regards, tom lane No Tom, Grouped index tuple doesn't use the B+ Tree data structure to achieve the sorting, so it will not guarantee 100% clustering of data. Gokul.
Re: [HACKERS] A thought on Index Organized Tables
Yes. The visibility map doesn't need any new WAL records to be written. We probably will need to add some WAL logging to close the holes with crash recovery, required for relying on it for index-only-scans, but AFAICS only for VACUUM and probably only one WAL record for a whole bunch of heap pages, so it should be pretty insignificant. Hmmm So whenever the update transaction changes a page, it will update the visibility map, but won't enter the WAL record. So after the crash we have a visibility map, which has false positives. Isn't that wrong? Let me repeat myself: if you think the overhead of a visibility map is noticeable or meaningful in any scenario, the onus is on you to show what that scenario is. I am not aware of such a scenario, which doesn't mean that it doesn't exist, of course, but hand-waving is not helpful. Well as a DB Tuner, i am requesting to make it a optional feature. If you and everyone else feel convinced, consider my request. I'm not sure what you mean with without any page level locking. Whenever a visibility map page is read or modified, a lock is taken on the buffer. OK. I thought you are following some kind of lock-less algorithm there. Then updaters/deleters of multiple pages might be waiting on the same lock and hence there is a chance of a contention there right? Again correct me, if i am wrong ( i might have understood things incorrectly ) Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
Missed the group... On Thu, Feb 25, 2010 at 12:34 AM, Gokulakannan Somasundaram gokul...@gmail.com wrote: On Thu, Feb 25, 2010 at 12:28 AM, Gokulakannan Somasundaram gokul...@gmail.com wrote: That doesn't work because when you split an index page any sequential scan in progress will either see the same tuples twice or will miss some tuples depending on where the new page is allocated. Vacuum has a clever trick for solving this but it doesn't work for arbitrarily many concurrent scans. Consider how the range scans are working today, while the page split happens. The Seq scan should follow the right sibling to do the seq scan. Gokul. Actually thinking about what you suggested for a while, i think it should be possible, because the Oracle Fast Full Index scan essentially scans the index like that. I will try to think a way of doing that with Lehman and Yao... Gokul.
Re: [HACKERS] A thought on Index Organized Tables
Gokulakannan Somasundaram wrote: Hmmm So whenever the update transaction changes a page, it will update the visibility map, but won't enter the WAL record. So after the crash we have a visibility map, which has false positives. The WAL record of the heap insert/update/delete contains a flag indicating that the visibility map needs to be updated too. Thus no need for a separate WAL record. Let me repeat myself: if you think the overhead of a visibility map is noticeable or meaningful in any scenario, the onus is on you to show what that scenario is. I am not aware of such a scenario, which doesn't mean that it doesn't exist, of course, but hand-waving is not helpful. Well as a DB Tuner, i am requesting to make it a optional feature. There is no point in making something optional, if there is no scenarios where you would want to turn it off. I'm not sure what you mean with without any page level locking. Whenever a visibility map page is read or modified, a lock is taken on the buffer. OK. I thought you are following some kind of lock-less algorithm there. Then updaters/deleters of multiple pages might be waiting on the same lock and hence there is a chance of a contention there right? Yeah, there is some potential for contention. But again it doesn't seem to be a problem in any real-life scenario; I didn't see any in the test I performed, and IIRC I did try to invoke that case, and there has been no reports of contention from users. If it ever becomes a problem, maybe you could indeed switch to a lock-less algorithm, but there doesn't seem to be any need for that. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
It might be slightly easier given the assumption that you only want to scan leaf tuples. But there's an additional problem I didn't think of before. Currently we optimize index scans by copying all relevant tuples to local memory so we don't need to hold an index lock for an extended time or spend a lot of time relocking and rechecking the index for changes. That wouldn't be possible if we needed to get visibility info from the page since we would need up-to-date information. We should solve this issue in the same way, of how we proceed with the index only quals, in current index-only scans. Gokul.
Re: [HACKERS] A thought on Index Organized Tables
That doesn't work because when you split an index page any sequential scan in progress will either see the same tuples twice or will miss some tuples depending on where the new page is allocated. Vacuum has a clever trick for solving this but it doesn't work for arbitrarily many concurrent scans. Consider how the range scans are working today, while the page split happens. The Seq scan should follow the right sibling to do the seq scan. Gokul. Actually thinking about what you suggested for a while, i think it should be possible, because the Oracle Fast Full Index scan essentially scans the index like that. I will try to think a way of doing that with Lehman and Yao... Gokul. OK I think, i can think of a solution to achieve fast full index scan like oracle. a) Issue ids to every block that gets created inside the index. we are already doing that b) Now before the fast full index scan starts, note down the max id that got issued. c) Now do a scan similar to Full Table Scan till that max id. Now, while we are scanning the blocks, note down the right siblings in a list, if the right sibling block id is greater than the max id that got issued. These are the ones, which have got split after the scan started d) Now after we reach that max block, try to range scan on missing links till we hit the end / get a right sibling less than the max block id noted. Once we do this for all the missing links, we have scanned through the entire chain. So this will definitely be faster than range scan. Thanks to you, i have thought about an important issue and also a solution for it. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
On Wed, Feb 24, 2010 at 8:04 PM, Gokulakannan Somasundaram gokul...@gmail.com wrote: OK I think, i can think of a solution to achieve fast full index scan like oracle. a) Issue ids to every block that gets created inside the index. we are already doing that b) Now before the fast full index scan starts, note down the max id that got issued. c) Now do a scan similar to Full Table Scan till that max id. Now, while we are scanning the blocks, note down the right siblings in a list, if the right sibling block id is greater than the max id that got issued. These are the ones, which have got split after the scan started d) Now after we reach that max block, try to range scan on missing links till we hit the end / get a right sibling less than the max block id noted. Once we do this for all the missing links, we have scanned through the entire chain. So this will definitely be faster than range scan. Thanks to you, i have thought about an important issue and also a solution for it. I haven't thought about whether this is sufficient but if it is then an initial useful thing to add would be to use it for queries where we have a qual that can be checked using the index key even though we can't do a range scan. For example if you have a btree index on a,b,c and you have a WHERE clause like WHERE c=0 That would be a much smaller change than IOT but it would still be a pretty big project. Usually the hardest part is actually putting the logic in the planner to determine whether it's advantageous. I would suggest waiting until after 9.0 is out the door to make sure you have the attention of Heikki or Tom or someone else who can spend the time to check that it will actually work before putting lots of work coding it. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Gokulakannan Somasundaram wrote: OK I think, i can think of a solution to achieve fast full index scan like oracle. a) Issue ids to every block that gets created inside the index. we are already doing that b) Now before the fast full index scan starts, note down the max id that got issued. c) Now do a scan similar to Full Table Scan till that max id. Now, while we are scanning the blocks, note down the right siblings in a list, if the right sibling block id is greater than the max id that got issued. These are the ones, which have got split after the scan started d) Now after we reach that max block, try to range scan on missing links till we hit the end / get a right sibling less than the max block id noted. Once we do this for all the missing links, we have scanned through the entire chain. So this will definitely be faster than range scan. You also need to avoid scanning the same tuple twice. That's not a problem for VACUUM, but it is for full index scans. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
You also need to avoid scanning the same tuple twice. That's not a problem for VACUUM, but it is for full index scans. Heikki, Actually the logic, which i have explained earlier is to avoid scanning tuples twice. Gokul.
Re: [HACKERS] A thought on Index Organized Tables
I haven't thought about whether this is sufficient but if it is then an initial useful thing to add would be to use it for queries where we have a qual that can be checked using the index key even though we can't do a range scan. For example if you have a btree index on a,b,c and you have a WHERE clause like WHERE c=0 That would be a much smaller change than IOT but it would still be a pretty big project. Usually the hardest part is actually putting the logic in the planner to determine whether it's advantageous. I would suggest waiting until after 9.0 is out the door to make sure you have the attention of Heikki or Tom or someone else who can spend the time to check that it will actually work before putting lots of work coding it. I will try that. Thanks ...
Re: [HACKERS] A thought on Index Organized Tables
The WAL record of the heap insert/update/delete contains a flag indicating that the visibility map needs to be updated too. Thus no need for a separate WAL record. Heikki, Have you considered these cases? a) The current WAL architecture makes sure that the WAL Log is written before the actual page flush( i believe ). But you are changing that architecture for Visibility maps. Visibility map might get flushed out before the corresponding WAL gets written. I think you would then suggest full page writes here b) Say for a large table, you have multiple buffers of visibility map, then there is a chance that one buffer gets flushed to the disk and the other doesn't. If the WAL records are not in place, then this leads to a time inconsistent visibility map. c) If you are going to track all the WAL linked with a buffer of visibility map, then you need to introduce another synchronization in the critical path. May be i am missing something? I am asking these questions only out of curiosity. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
On Thu, Feb 25, 2010 at 3:16 AM, Gokulakannan Somasundaram gokul...@gmail.com wrote: I haven't thought about whether this is sufficient but if it is then an initial useful thing to add would be to use it for queries where we have a qual that can be checked using the index key even though we can't do a range scan. For example if you have a btree index on a,b,c and you have a WHERE clause like WHERE c=0 That would be a much smaller change than IOT but it would still be a pretty big project. Usually the hardest part is actually putting the logic in the planner to determine whether it's advantageous. I would suggest waiting until after 9.0 is out the door to make sure you have the attention of Heikki or Tom or someone else who can spend the time to check that it will actually work before putting lots of work coding it. I will try that. Thanks ... Some more ideas popped up. I am just recording those. a) In place of block id( this has to be issued for every new/recycled block and it is not there in postgres), we can even have SnapshotNow's transaction id. I just feel the synchronization effect will be more here. b) We can just record the currentTimestamp in the page. While this is without any synch, it might create problems, when we decide to go for Master-Master replication and Distributed databases. So when such things happens, the clock on the various systems have to be synched. Gokul.
Re: [HACKERS] A thought on Index Organized Tables
Gokulakannan Somasundaram wrote: a) The current WAL architecture makes sure that the WAL Log is written before the actual page flush( i believe ). But you are changing that architecture for Visibility maps. Visibility map might get flushed out before the corresponding WAL gets written. Yes. When a bit is cleared, that's OK, because a cleared bit just means you need to check visibility in the heap tuple. When a bit is set, however, it's important that it doesn't hit the disk before the corresponding heap page update. That's why visibilitymap_set() sets the LSN on the page. b) Say for a large table, you have multiple buffers of visibility map, then there is a chance that one buffer gets flushed to the disk and the other doesn't. If the WAL records are not in place, then this leads to a time inconsistent visibility map. Huh? c) If you are going to track all the WAL linked with a buffer of visibility map, then you need to introduce another synchronization in the critical path. Double huh? I'd suggest that you take some time to read the code and comments in visibilitymap.c and the call sites of those functions, to get a better picture of how it works. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
On Tue, Feb 23, 2010 at 10:42 AM, Tom Lane t...@sss.pgh.pa.us wrote: Takahiro Itagaki itagaki.takah...@oss.ntt.co.jp writes: Instead, how about excluding columns in primary keys from table data? How will you implement select * from mytable ? Or even select * from mytable where non_primary_key = something ? If you can't do either of those without great expense, I think a savings on primary-key lookups is not going to be adequate recompense. Tom, I am talking things more from the perspective of how things have got implemented in Oracle/SQL Server. Both Oracle and SQL Server store the snapshot info with indexes and hence can do index-only scans with their indexes. But still they have the concept of Index Organized Tables / Clustered Indexes. Apart from the disk footprint, it will have an impact on the cache efficiency also. In Oracle IOT and SQL Server Clustered Indexes, you have an option to store some of the columns in the leaf pages( but not in the non-leaf pages) and hence the tuples won't get sorted based on them, but you don't require an extra i/o to access them. This optimization is again to reduce the size of IOT. Oracle IOT has a concept called overflow regions, which is more like a heap and will store a few columns. There will be a pointer from main b-tree structure to this secondary structure. Accessing these columns are costly, but the idea is that the database designer has taken this into account while deciding on the columns to be put in the overflow regions. We can design secondary indexes to make the access faster for non-primary key based searches. But since the Secondary indexes store primary key in the place of HeapTuple Pointer, the access will usually take 2-3 more i/os. But the idea is that the IOT is for those kind of data. which will be 99% queried based on primary keys. The database provides that extra performance for that kind of access patterns. So to answer your question, full table scans(if overflow regions are involved) and search based on non-primary keys will be slow in an IOT. I looked at the postgres nbtree code. From my analysis(which might be wrong!), we can implement IOTs, provided we make a decision on broken data types issue. Thanks, Gokul.
Re: [HACKERS] A thought on Index Organized Tables
Hi all, On Mon, 2010-02-22 at 10:29 +, Greg Stark wrote: On Mon, Feb 22, 2010 at 8:18 AM, Gokulakannan Somasundaram gokul...@gmail.com wrote: a) IOT has both table and index in one structure. So no duplication of data b) With visibility maps, we have three structures a) Table b) Index c) Visibility map. So the disk footprint of the same data will be higher in postgres ( 2x + size of the visibility map). These sound like the same point to me. I don't think we're concerned with footprint -- only with how much of that footprint actually needs to be scanned. For some data the disk foot-print would be actually important: on our data bases we have one table which has exactly 2 fields, which are both part of it's primary key, and there's no other index. The table is write-only, never updated and rarely deleted from. The disk footprint of the table is 30%-50% of the total disk space used by the DB (depending on the other data). This amounts to about 1.5-2TB if I count it on all of our DBs, and it has to be fast disk too as the table is heavily used... so disk space does matter for some. And yes, I put the older entries in some archive partition on slower disks, but I just halve the problem - the data is growing exponentially, and about half of it is always in use. I guess our developers are just ready to get this table out of postgres and up to hadoop... Cheers, Csaba. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
On Mon, 2010-02-22 at 08:51 +0200, Heikki Linnakangas wrote: Gokulakannan Somasundaram wrote: May i get a little clarification on this issue? Will we be supporting the IOT feature in postgres in future? What seems like the best path to achieve the kind of performance benefits that IOTs offer is allowing index-only-scans using the visibility map. I don't agree with that. Could you explain why you think that would be the case? It would be a shame to have everybody think you can solve a problem if it turned out not to be the case. -- Simon Riggs www.2ndQuadrant.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Gokulakannan Somasundaram wrote: I looked at the postgres nbtree code. From my analysis(which might be wrong!), we can implement IOTs, provided we make a decision on broken data types issue. I am not familiar with this term broken data types, and I just looked for it in the source code and couldn't find it. What exactly are you referring to? cheers andrew -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Simon Riggs wrote: On Mon, 2010-02-22 at 08:51 +0200, Heikki Linnakangas wrote: Gokulakannan Somasundaram wrote: May i get a little clarification on this issue? Will we be supporting the IOT feature in postgres in future? What seems like the best path to achieve the kind of performance benefits that IOTs offer is allowing index-only-scans using the visibility map. I don't agree with that. Could you explain why you think that would be the case? It would be a shame to have everybody think you can solve a problem if it turned out not to be the case. I'm thinking of a scan based on the index key. With an index-organised-table, you can skip the heap access because the heap and the index are the same structure. An index-only-scan likewise allows you to skip the heap access. I grant you that an index-organised-table can have other benefits, like reduced disk space usage (which is good cache efficiency), or less random I/O required for updates. The question was if PostgreSQL will be supporting index-organised-tables in the future. The answer is not in the foreseeable future. No-one has come up with a plausible plan for how to do it, and no-one working on it at the moment. I don't want to discourage thinking about pie-in-the-sky features. There's many tricks like column-oriented storage, compression, index-organised-tables etc. that would be nice to have. Whether any particular feature is worthwhile in the end, the devil is in the details. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Andrew Dunstan wrote: Gokulakannan Somasundaram wrote: I looked at the postgres nbtree code. From my analysis(which might be wrong!), we can implement IOTs, provided we make a decision on broken data types issue. I am not familiar with this term broken data types, and I just looked for it in the source code and couldn't find it. What exactly are you referring to? I believe he's referring to the fact that once a key is inserted to an index, it might not be possible to re-find it, if the datatype is broken in such a way that e.g comparison operator returns a different value. For example, today 1 2 returns true, but tomorrow it returns false. The decision on that is that you need to deal with it. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
Simon Riggs si...@2ndquadrant.com wrote: On Mon, 2010-02-22 at 08:51 +0200, Heikki Linnakangas wrote: Gokulakannan Somasundaram wrote: May i get a little clarification on this issue? Will we be supporting the IOT feature in postgres in future? What seems like the best path to achieve the kind of performance benefits that IOTs offer is allowing index-only-scans using the visibility map. I don't agree with that. Could you explain why you think that would be the case? It would be a shame to have everybody think you can solve a problem if it turned out not to be the case. I'd like to be clear on what feature we're discussing. There has been mention of an organization where there is no heap per se, but all columns are stored in the leaf node of one of the table's indexes (which is the structure referred to as a CLUSTERED INDEX in some other popular products). There has been some mention of storing some of the data out-of-line, which could be considered to be already covered by TOAST. I know that one of the things which makes this technique particularly effective with such things as name columns for a clustered index is that these other products store index entries after the first in a page with a length that matches the previous entry and the differing data at the tail, which we don't yet have. Clearly it's not trivial, but there are certainly cases where it can be a big performance win. Besides the obvious issues around having a relation which functions like both an index and a heap (at the leaf level), there are the details of having other indexes point to these leaf nodes, creating and dropping clustered indexes, impact on vacuums, etc. Situations where clustered indexes tended to help: (1) Most access through a particular index -- often one less random read per access. (2) Frequent sequential access through a range of values in an index -- turn random access into mostly sequential. (3) Index values comprise a large portion of each tuple -- avoid redundant storage, reducing disk footprint, thereby improving cache hits. Points 1 and 2 could be covered to some degree by index-only scans, particularly if additional columns are added to indexes to make them covering indexes. Index-only scans don't help with 3 at all; in fact, adding the additional columns to indexes to allow that optimization tends to work against it. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] A thought on Index Organized Tables
On Tue, 2010-02-23 at 17:08 +0200, Heikki Linnakangas wrote: Simon Riggs wrote: On Mon, 2010-02-22 at 08:51 +0200, Heikki Linnakangas wrote: Gokulakannan Somasundaram wrote: May i get a little clarification on this issue? Will we be supporting the IOT feature in postgres in future? What seems like the best path to achieve the kind of performance benefits that IOTs offer is allowing index-only-scans using the visibility map. I don't agree with that. Could you explain why you think that would be the case? It would be a shame to have everybody think you can solve a problem if it turned out not to be the case. I'm thinking of a scan based on the index key. With an index-organised-table, you can skip the heap access because the heap and the index are the same structure. An index-only-scan likewise allows you to skip the heap access. I grant you that an index-organised-table can have other benefits, like reduced disk space usage (which is good cache efficiency), or less random I/O required for updates. The question was if PostgreSQL will be supporting index-organised-tables in the future. The answer is not in the foreseeable future. No-one has come up with a plausible plan for how to do it, and no-one working on it at the moment. I think Gokul was asking because he wanted to work on it, but wanted to check community approval first. I don't want to discourage thinking about pie-in-the-sky features. Planning, is what I would call that. Calling them pie in the sky is just a negative label, as much as if someone else called them obvious next steps is a positive label. There's many tricks like column-oriented storage, compression, index-organised-tables etc. that would be nice to have. Whether any particular feature is worthwhile in the end, the devil is in the details. I agree that the way to improve things is to focus on a particular architectural technique and then a design for doing that. Going straight to the design and naming it doesn't help at all. That was why I named an earlier project Frequent Update Optimisation rather than any of the names that referred to a design. The devil is in the details, I agree. The important part is analysis though, not coding. Which is why I was asking why you were working on index-only scans, though do not doubt your ability to make them work. And also why I would say to Gokul: the right approach isn't to ask will we be supporting IOTs and then go and build them. The right approach is to work out what you want to improve and give a clear justification of why, come up with a proposal to do that with analysis of how the proposal will improve the situation and then think about coding. -- Simon Riggs www.2ndQuadrant.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
