A thought on Index Organized Tables

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

Heikki,
I had a quick look at the discussion on visibility map design. The
main differences as i see it are
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.

Are we going to ignore these differences?

Thanks,
Gokul.

On Mon, Feb 22, 2010 at 12:21 PM, Heikki Linnakangas <
heikki.linnakangas@enterprisedb.com> 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. 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

Forgot to include the group...

On Mon, Feb 22, 2010 at 4:31 PM, Gokulakannan Somasundaram <
gokul007@gmail.com> wrote:

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 Tue, Feb 23, 2010 at 10:42 AM, 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" ?
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.

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

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.