Re: Index only scan paving the way for "auto" clustered tables?

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> Alternatively, we could try to graft the concept of a self-clustering
> table on top of the existing heap implementation. But I'm having
> trouble seeing how that would work. The TODO describes it as
> something like "maintain CLUSTER ordering", but that's a gross
> oversimplification, because we have no structure that would allow us
> to sensibly do any such thing... the current heap implementation is
> just that: a pile of stuff.

I currently think that's the way to go, with some coarser granularity
than tuple or page. Picture HOT inserts, if you will. That would be at
the page level, but do we need that level of precision?

I'm thinking that we need something more like segment based here, or
maybe some intermediate value would be good between a page of 8Kb and a
segment of 1GB, but I'm not so sure. We would have to track the bounds
of each segment for the indexed columns, and maintain them, and the
planner would have to exercise pruning at the segment level.

So going down too much in granularity would have negative impacts on
planning performances (too many data to play with), and anyway a server
that needs that kind of optimization can certainly handle a couple of GB
in its file system cache.

So, it's quite hand wavy still, but Segment Exclusion has been discussed
here already, and it seems to me that's the next thing we need. Call it
partial Seq Scan and HOT inserts if new names are your thing :)

Regards,
--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support