Thread: A thought on Index Organized Tables

Hi,<br />    As you all know, Index Organized tables are a way by which we can automatically cluster the data based on
theprimary key. While i was thinking about an implementation for postgres, it looks like an impossible with the current
ideologies.In an IOT, if a record gets updated, we need to mark the old row as deleted immediately, as we do with any
othertable. But since Postgres supports user defined data types and if they happen to be a broken data type, then we
havean unstable IOT.(as there is no guarantee, we might hit the same record)<br />     This was the reason for which,
theproposal on creating  indexes with snapshot was rejected. <br />    May i get a little clarification on this issue?
Willwe be supporting the IOT feature in postgres in future?<br /><br /> Thanks,<br />Gokul.<br /><br /> 

Gokulakannan Somasundaram wrote:
> Hi,
>     As you all know, Index Organized tables are a way by which we can
> automatically cluster the data based on the primary key. While i was
> thinking about an implementation for postgres, it looks like an impossible
> with the current ideologies. In an IOT, if a record gets updated, we need to
> mark the old row as deleted immediately, as we do with any other table. But
> since Postgres supports user defined data types and if they happen to be a
> broken data type, then we have an unstable IOT.(as there is no guarantee, we
> might hit the same record)
>     This was the reason for which, the proposal on creating  indexes with
> snapshot was rejected.
>     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 worked on that last summer, but unfortunately didn't
have the time to finish anything.

--  Heikki Linnakangas EnterpriseDB   http://www.enterprisedb.com

On Mon, Feb 22, 2010 at 8:18 AM, Gokulakannan Somasundaram
<gokul007@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. So if we have a solution allowing the scan to only need
to look at the index then the extra footprint of the table doesn't
cost anything at run-time. And the visibility map is very small.


I think you would be better off looking for incremental improvements
rather than major architectural changes like having no heap for a
table. There are so many design decisions hinged on having a heap that
it would be impractical to rethink them all.

-- 
greg

Greg Stark escribió:
> On Mon, Feb 22, 2010 at 8:18 AM, Gokulakannan Somasundaram
> <gokul007@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. So if we have a solution allowing the scan to only need
> to look at the index then the extra footprint of the table doesn't
> cost anything at run-time. And the visibility map is very small.

Moreover, the visibility map is already there.

-- 
Alvaro Herrera                                http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

Gokulakannan Somasundaram <gokul007@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).
> c) More than that, inserts and updates will incur two extra random i/os
> every time. - one for updating the table and one for updating the visibility
> map.

I think IOT is a good match for overwrite storage systems, but postgres
is a non-overwrite storage systems. If we will update rows in IOT, we need
much more initial page free spaces than index-only scans where we can avoid
key updates with HOT.

Instead, how about excluding columns in primary keys from table data?
We cannot drop those primary keys and cannot seqscan the tables, but
there are no duplication of data, only small overheads (index tuple
headers and ctid links), and would work well with HOT and index-only
scans. If we don't have any non-key columns, that behaves just as IOT.

Regards,
---
Takahiro Itagaki
NTT Open Source Software Center

Takahiro Itagaki <itagaki.takahiro@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.
        regards, tom lane

Tom Lane <tgl@sss.pgh.pa.us> wrote:

> Takahiro Itagaki <itagaki.takahiro@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" ?

Use index full scans. We can do it even for now with enable_seqscan = off.
Of course, it requires an additional step to merge index keys and heap tuples.

Also, we're using the same technique for TOASTed values. The cost can be
compared with "select * from mytable where toasted_value = something", no?

> 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.

I don't think it will be the default, but it would be a reasonable trade-off
for users who want IOTs, unless they often scan the whole table.

Regards,
---
Takahiro Itagaki
NTT Open Source Software Center

Takahiro Itagaki <itagaki.takahiro@oss.ntt.co.jp> writes:
> Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Takahiro Itagaki <itagaki.takahiro@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" ?

> Also, we're using the same technique for TOASTed values. The cost can be
> compared with "select * from mytable where toasted_value = something", no?

No, because toast pointers point in the direction you need to traverse.
AFAICS, this proposal involves scanning the whole index to find the
matching entry, because the available pointers link from the wrong end,
that is from the index to the table.

There are also some fairly fatal problems associated with commands like
ALTER TABLE DROP PRIMARY KEY, but I see no need to worry about that
because you haven't even made a case that there's a net performance
gain possible here.
        regards, tom lane

Tom Lane <tgl@sss.pgh.pa.us> wrote:

> > Also, we're using the same technique for TOASTed values. The cost can be
> > compared with "select * from mytable where toasted_value = something", no?
> 
> No, because toast pointers point in the direction you need to traverse.
> AFAICS, this proposal involves scanning the whole index to find the
> matching entry, because the available pointers link from the wrong end,
> that is from the index to the table.

Ah, I see there are differences if we have secondary indexes.
I misunderstood that the toast case requires scanning the whole *table* to
find the matching entry and should be compared with the whole *index* scans,
but there is another story if we have secondary indexes.

We can have indexes on toasted values, and find the related tuples
directly with CTIDs, but scans on secondary indexes on PK-excluded
tables requires not only heap tuples but also primary key values.

The secondary index issue should be considered also with the original
IOT proposal also has the same issue. Using PK-values instead of CTIDs
might require many changes in index access methods and/or the executor.

Regards,
---
Takahiro Itagaki
NTT Open Source Software Center

Hi all,

On Mon, 2010-02-22 at 10:29 +0000, Greg Stark wrote:
> On Mon, Feb 22, 2010 at 8:18 AM, Gokulakannan Somasundaram
> <gokul007@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.

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

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

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

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

Simon Riggs <simon@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

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

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

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

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

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

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

On Wed, Feb 24, 2010 at 9:41 AM, Gokulakannan Somasundaram
<gokul007@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

Karl Schnaitter <karlsch@gmail.com> writes:
> On Wed, Feb 24, 2010 at 12:53 AM, Gokulakannan Somasundaram <
> gokul007@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

Tom Lane <tgl@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

On Wed, Feb 24, 2010 at 3:12 PM, Tom Lane <tgl@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

<div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt
0pt0pt 0.8ex; padding-left: 1ex;"><br /> With an IOT I don't understand how you get out of index corruption<br />
withoutdata loss.  That's a showstopper for practical use, I think.<br /></blockquote></div><br />For simplicity, say
weare storing all the non-leaf pages of the index in a seperate file, then the leaf pages are nothing but the table. So
ifwe can replicate the table, then we can replicate the non-leaf pages (say by some modified version of reindex).<br
/><br/>Thanks,<br />Gokul.<br /> 

On Wed, Feb 24, 2010 at 11:05 AM, Gokulakannan Somasundaram
<gokul007@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

Gokulakannan Somasundaram <gokul007@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

"Kevin Grittner" <Kevin.Grittner@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

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

Tom Lane <tgl@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

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

On Wed, Feb 24, 2010 at 4:12 PM, Gokulakannan Somasundaram
<gokul007@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

Greg Stark <gsstark@mit.edu> wrote:
> Gokulakannan Somasundaram <gokul007@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

On Wed, 2010-02-24 at 15:52 +0000, 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

"Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:
> Greg Stark <gsstark@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

On Wed, Feb 24, 2010 at 5:46 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> "Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:
>> Greg Stark <gsstark@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

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

On Wed, Feb 24, 2010 at 8:04 PM, Gokulakannan Somasundaram
<gokul007@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

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

<br /><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204);
margin:0pt 0pt 0pt 0.8ex; padding-left: 1ex;">I haven't thought about whether this is sufficient but if it is then<br
/>an initial useful thing to add would be to use it for queries where we<br /> have a qual that can be checked using
theindex key even though we<br /> can't do a range scan. For example if you have a btree index on<br /> <a,b,c>
andyou have a WHERE clause like "WHERE c=0"<br /><br /> That would be a much smaller change than IOT but it would still
bea<br /> pretty big project. Usually the hardest part is actually putting the<br /> logic in the planner to determine
whetherit's advantageous. I would<br /> suggest waiting until after 9.0 is out the door to make sure you have<br /> the
attentionof Heikki or Tom or someone else who can spend the time<br /> to check that it will actually work before
puttinglots of work coding<br /> it.<br /><br /></blockquote></div>I will try that. Thanks ...<br /> 

<br /><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204);
margin:0pt 0pt 0pt 0.8ex; padding-left: 1ex;">The WAL record of the heap insert/update/delete contains a flag<br />
indicatingthat the visibility map needs to be updated too. Thus no need<br /> for a separate WAL record.<br /><div
class="im"><br/></div></blockquote></div><br />Heikki,<br />        Have you considered these cases?<br />a) The
currentWAL architecture makes sure that the WAL Log is written before the actual page flush( i believe ). But you are
changingthat 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<br /> b) Say for a large table, you have multiple buffers
ofvisibility map, then there is a chance that one buffer gets flushed to the disk and the other doesn't. If the WAL
recordsare not in place, then this leads to a time inconsistent visibility map.<br /> c) If you are going to track all
theWAL linked with a buffer of visibility map, then you need to introduce another synchronization in the critical
path.<br/><br />May be i am missing something? I am asking these questions only out of curiosity. <br /><br
/>Thanks,<br/>Gokul.<br /> 

<br /><br /><div class="gmail_quote">On Thu, Feb 25, 2010 at 3:16 AM, Gokulakannan Somasundaram <span dir="ltr"><<a
href="mailto:gokul007@gmail.com">gokul007@gmail.com</a>></span>wrote:<br /><blockquote class="gmail_quote"
style="border-left:1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="im"><br
/><divclass="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt
0pt0pt 0.8ex; padding-left: 1ex;">I haven't thought about whether this is sufficient but if it is then<br /> an initial
usefulthing to add would be to use it for queries where we<br /> have a qual that can be checked using the index key
eventhough we<br /> can't do a range scan. For example if you have a btree index on<br /> <a,b,c> and you have a
WHEREclause like "WHERE c=0"<br /><br /> That would be a much smaller change than IOT but it would still be a<br />
prettybig project. Usually the hardest part is actually putting the<br /> logic in the planner to determine whether
it'sadvantageous. I would<br /> suggest waiting until after 9.0 is out the door to make sure you have<br /> the
attentionof Heikki or Tom or someone else who can spend the time<br /> to check that it will actually work before
puttinglots of work coding<br /> it.<br /><br /></blockquote></div></div>I will try that. Thanks ...<br
/></blockquote></div><br/>Some more ideas popped up. I am just recording those.<br />a) In place of block id( this has
tobe 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.<br /> 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
Distributeddatabases. So when such things happens, the clock on the various systems have to be synched.<br /><br
/>Gokul.<br/> 

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

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

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

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

<br /><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204);
margin:0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> 1) transaction information in index<br /><br />    This seems like a lot
ofbloat in indexes. It also means breaking<br /> a lot of other optimizations such as being able to read the tuples<br
/>directly from the heap page without locking. I'm not sure how much<br /> those are worth though. But adding 24 bytes
toevery index entry seems<br /> pretty unlikely to be a win anyways.<br /><br /></blockquote></div><br />Greg,<br
/>         I think, somewhere things have been misunderstood. we only need 8 bytes more per index entry. I thought
Postgreshas a 8 byte transaction id, but it is only 4 bytes, so we only need to save the insertion and deletion xids.
So8 bytes more per tuple.<br /><br />Gokul.<br /> 

Gokulakannan Somasundaram <gokul007@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

On Thu, Feb 25, 2010 at 8:09 PM, Gokulakannan Somasundaram
<gokul007@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

Greg Stark <gsstark@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

<br /><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204);
margin:0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="gmail_quote"><div class="im"><blockquote class="gmail_quote"
style="border-left:1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> The other<br />
problemis the extra write load created by needing to update the index's<br /> copies of the hint bits; not to mention
extrawrites to freeze the xids<br /> when they get old enough.<br /></blockquote></div></div>But Tom, i remember that
thevacuum was faster when index had visibility info, since we need not touch the table. But maybe i am wrong. <br
/></blockquote></div><br/>I disagree with that, Gokul -- if the ordering operators are volatile or just incorrect,
duringDELETE, you could set xmax in the wrong IndexTuple. Then there will be another IndexTuple that says it's visible,
butit points to a non-visible heap tuple. I think you should follow the pointers to the heap before you decide to let
anindex tuple remain in the index during vacuum. This would ensure that all references from an index to a heap tuple
areremoved before vacuuming the heap tuple. I would be worried about what might break if this invariant doesn't
hold.<br/><br />Tom is right about all the extra overhead involved with keeping visibility info in the index. But it
canbe a good trade-off in some cases. <br /><br />Karl<br /> 

On Thu, Feb 25, 2010 at 9:25 PM, Tom Lane <tgl@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.

Greg Stark <gsstark@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

If it's of any interest, I can say something about the hint bits in the index tuple header. In my implementation, my
decisionwas 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<br /><br />(xmin is committed OR xmin = InvalidTransactionId)<br />AND (xmax is committed OR xmax =
InvalidTransactionId)<br/><br />Then there are 12 bytes for xmin/xmax/cid. I did sweat something over this decision...
butmaybe it was a wasted effort if the 12 bytes end up occupying 16 bytes anyway.<br /><br />Karl<br /><br /><div
class="gmail_quote">OnThu, Feb 25, 2010 at 1:25 PM, Tom Lane <span dir="ltr"><<a
href="mailto:tgl@sss.pgh.pa.us">tgl@sss.pgh.pa.us</a>></span>wrote:<br /><blockquote class="gmail_quote"
style="border-left:1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="im">Greg
Stark<<a href="mailto:gsstark@mit.edu">gsstark@mit.edu</a>> writes:<br /> > In indexes we currently get away
witha reduced header which has few<br /> > of the 6 bytes of info bits. However the only reason we can do is<br />
>because we impose arbitrary limitations that work for indexes but<br /> > wouldn't be reasonable for tables.
Suchas a lower maximum number of<br /> > columns, inability to add new columns or drop columns later, etc.<br /><br
/></div>Waita second, which idea are we currently talking about?  No heap at<br /> all, or just the ability to check
visibilitywithout visiting the heap?<br /><br /> If it's a genuine IOT (ie no separate heap), then you are not going
to<br/> be able to get away without a full heap tuple header.  We've sweated<br /> blood to get that struct down to
whereit is; there's no way to make it<br /> smaller without giving up some really fundamental things, for example<br />
theability to do UPDATE :-(<br /><br /> If you just want to avoid a heap visit for visibility checks, I think<br />
you'donly need to add xmin/xmax/cmin plus the hint bits for same.<br /> This is going to end up costing 16 bytes in
practice--- you might<br /> think you could squeeze into 12 but on 64-bit machines (MAXALIGN 8)<br /> you'll save
nothing. So that's effectively a doubling of index size<br /> for common cases such as a single int4 or int8 index
column. The other<br /> problem is the extra write load created by needing to update the index's<br /> copies of the
hintbits; not to mention extra writes to freeze the xids<br /> when they get old enough.<br /><br />                  
    regards, tom lane<br /></blockquote></div><br /> 

Karl Schnaitter <karlsch@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

Karl Schnaitter <karlsch@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

Gokulakannan Somasundaram <gokul007@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

Gokulakannan Somasundaram <gokul007@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

<div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt
0pt0pt 0.8ex; padding-left: 1ex;"> To be a bit more concrete: the typical sort of failure that you could<br /> get from
brokenbtree operators is failure of transitivity, that is<br /> the comparators report A < B and B < C for some
A,B, C, but do not say<br /> that A < C when those two values are compared directly.  I don't see any<br />
convenientway to detect that as a byproduct of normal index operations,<br /> because you wouldn't typically have a
reasonto make all three<br /> comparisons in close proximity.  Indeed, the searching and sorting<br /> algorithms do
theirbest to avoid making "redundant" comparisons of that<br /> kind.<br /></blockquote></div><br />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
blockand offset, and while searching it might either return no results / show a wrong place. Because ordering is
requiredfor searching also right? I definitely feel, i am missing something here.<br /><br />Gokul.<br /> 

<br /><br /><div class="gmail_quote">On Fri, Feb 26, 2010 at 12:36 AM, Gokulakannan Somasundaram <span dir="ltr"><<a
href="mailto:gokul007@gmail.com">gokul007@gmail.com</a>></span>wrote:<br /><blockquote class="gmail_quote"
style="border-left:1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="im"><div
class="gmail_quote"><blockquoteclass="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt
0pt0.8ex; padding-left: 1ex;"> To be a bit more concrete: the typical sort of failure that you could<br /> get from
brokenbtree operators is failure of transitivity, that is<br /> the comparators report A < B and B < C for some
A,B, C, but do not say<br /> that A < C when those two values are compared directly.  I don't see any<br />
convenientway to detect that as a byproduct of normal index operations,<br /> because you wouldn't typically have a
reasonto make all three<br /> comparisons in close proximity.  Indeed, the searching and sorting<br /> algorithms do
theirbest to avoid making "redundant" comparisons of that<br /> kind.<br /></blockquote></div><br /></div>This is
interestingTom, but i am unable to understand, why it won't affect the current indexes. While insertion it might get
insertedin a block and offset, and while searching it might either return no results / show a wrong place. Because
orderingis required for searching also right? I definitely feel, i am missing something here.<br
/></blockquote></div><br/>It definitely affects current indexes. We can't completely avoid bad user functions. That is
whyit is important to put limits on how much damage they can do. That's the motivation for the idea I mentioned before,
ofdouble-checking visibility data in an IndexTuple before letting it survive a VACUUM. <br /> 

On Fri, Feb 26, 2010 at 4:47 AM, Tom Lane <tgl@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

On Fri, Feb 26, 2010 at 2:38 PM, Gokulakannan Somasundaram
<gokul007@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

Greg Stark <gsstark@mit.edu> writes:
> On Fri, Feb 26, 2010 at 4:47 AM, Tom Lane <tgl@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

<br /><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204);
margin:0pt 0pt 0pt 0.8ex; padding-left: 1ex;">IIRC, what was being talked about was shoehorning some hint bits into<br
/>the line pointers by assuming that size and offset are multiples of 4.<br /> I'm not thrilled with having mutable
statusbits there for reliability<br /> reasons, but it could be done without breaking a lot of existing code.<br />
WhatI was reacting to above was a suggestion that we could delete the<br /> itempointer size field altogether, which
seemsunworkable for the<br /> reasons I mentioned.<br /></blockquote></div><br />I think then we can pursue on using
theIndexTuple structure similar to HeapTuple(as you have suggested in an earlier update). This would involve(i
believe)<br/>a) Making the current IndexTuple  into IndexTupleHeader<br /> b) Creating a new structure called
IndexTuplewhich will store the size and the have a pointer to IndexTupleHeader. <br /><br />But Tom, can you please
explainme why that broken ordering example doesn't affect the current index scans. <br /><br />Thanks,<br />Gokul.<br
/>

Gokulakannan Somasundaram <gokul007@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

On Fri, Feb 26, 2010 at 6:30 PM, Gokulakannan Somasundaram
<gokul007@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

Gokulakannan Somasundaram <gokul007@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

If i have got over excited in the previous update, please ignore that.<br /><br />a) We are already going from table to
indexto do unique checks. This is the same thing, which we will do to go and update the snapshot in the indexes.  <br
/>b) The way, it should work would be to have a check on whether the operator is broken / function is volatile and put
theonus on the user to make sure that they are updated correctly. <br />c) In the ItemId, instead of removing the size
fieldcompletely, we can store the size as size/4(since it is MaxAligned). This will save us 2 bits. In index we only
need13 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
savingsthere. That's sufficient for us to express the hint fields in a index. I think Karl's way of expressing it
requiresonly one bit, which looks very efficient. So we can check the hint bits from the iid itself.<br /><br />So just
witha addition of 8 bytes per tuple, we can have the snapshot stored with the index. Can someone please comment on
this?<br/><br />Thanks,<br />Gokul.<br /><br /><br /> 

On Sun, Feb 28, 2010 at 6:02 AM, Gokulakannan Somasundaram
<gokul007@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

Gokulakannan Somasundaram <gokul007@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

<div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt
0pt0pt 0.8ex; padding-left: 1ex;"><br /> I think you have to take up a simpler project as a first project. This<br />
isa major overhaul of transaction information and it depends on<br /> understanding how a lot of different areas work
--all of which are<br /> very complex tricky areas to understand.<br /><br /><br /></blockquote></div><br />Greg,<br
/>         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.<br/><br />Thanks,<br />Gokul.<br />