So, is COUNT(*) fast now?

Robert Haas <robertmhaas@gmail.com> writes:

That's a bit disappointing - it's now more than a third faster to do
the sequential scan, even though the sequential scan has to touch six
times as many blocks (at scale factor 20, index is 43 MB, table is 256
MB) all of which are in cache. Of course, touching that many fewer
blocks does have some advantages if there is concurrent activity on
the system, but it still seems unfortunate that the ratio of runtime
to blocks touched is more than 8x higher for the index-only case.

I don't know why you'd imagine that touching an index is free, or even
cheap, CPU-wise. The whole point of the index-only optimization is to
avoid I/O. When you try it on a case where there's no I/O to be saved,
*and* no shared-buffers contention to be avoided, there's no way it's
going to be a win.

regards, tom lane

On Fri, Oct 21, 2011 at 1:18 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

That's a bit disappointing - it's now more than a third faster to do
the sequential scan, even though the sequential scan has to touch six
times as many blocks (at scale factor 20, index is 43 MB, table is 256
MB) all of which are in cache.  Of course, touching that many fewer
blocks does have some advantages if there is concurrent activity on
the system, but it still seems unfortunate that the ratio of runtime
to blocks touched is more than 8x higher for the index-only case.

I don't know why you'd imagine that touching an index is free, or even
cheap, CPU-wise.  The whole point of the index-only optimization is to
avoid I/O.  When you try it on a case where there's no I/O to be saved,
*and* no shared-buffers contention to be avoided, there's no way it's
going to be a win.

Well, call me naive, but I would have thought touching six times less
data would make the operation run faster, not slower.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:

On Fri, Oct 21, 2011 at 1:18 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I don't know why you'd imagine that touching an index is free, or even
cheap, CPU-wise. �The whole point of the index-only optimization is to
avoid I/O. �When you try it on a case where there's no I/O to be saved,
*and* no shared-buffers contention to be avoided, there's no way it's
going to be a win.

Well, call me naive, but I would have thought touching six times less
data would make the operation run faster, not slower.

It's not "touching six times less data". It's touching the exact same
number of tuples either way, just index tuples in one case and heap
tuples in the other. You've arranged the test case so that all these
tuples are in shared buffers already, so there's no data movement to be
avoided. What this test case proves is that btree's overhead per index
tuple touched is significantly more than the cost of the fastest path
through HeapTupleSatisfiesMVCC, which I don't find surprising
considering how much sweat has been expended on that code path over the
years.

(It may well be that it's not even btree at fault but the per-tuple
visits to the visibility map ... did you do any oprofiling yet?)

regards, tom lane

On Fri, Oct 21, 2011 at 2:08 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

On Fri, Oct 21, 2011 at 1:18 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I don't know why you'd imagine that touching an index is free, or even
cheap, CPU-wise.  The whole point of the index-only optimization is to
avoid I/O.  When you try it on a case where there's no I/O to be saved,
*and* no shared-buffers contention to be avoided, there's no way it's
going to be a win.

Well, call me naive, but I would have thought touching six times less
data would make the operation run faster, not slower.

It's not "touching six times less data".  It's touching the exact same
number of tuples either way, just index tuples in one case and heap
tuples in the other.

Yeah, but it works out to fewer pages.

You've arranged the test case so that all these
tuples are in shared buffers already, so there's no data movement to be
avoided.  What this test case proves is that btree's overhead per index
tuple touched is significantly more than the cost of the fastest path
through HeapTupleSatisfiesMVCC, which I don't find surprising
considering how much sweat has been expended on that code path over the
years.

I think HeapTupleSatisfiesMVCC is probably being skipped anyway in
this case, since all the heap pages should be PD_ALL_VISIBLE.

(It may well be that it's not even btree at fault but the per-tuple
visits to the visibility map ... did you do any oprofiling yet?)

No, but I think that might be a good idea. Maybe I'll go do that.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:

On Fri, Oct 21, 2011 at 2:08 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

What this test case proves is that btree's overhead per index
tuple touched is significantly more than the cost of the fastest path
through HeapTupleSatisfiesMVCC, which I don't find surprising
considering how much sweat has been expended on that code path over the
years.

I think HeapTupleSatisfiesMVCC is probably being skipped anyway in
this case, since all the heap pages should be PD_ALL_VISIBLE.

Proves my point ;-) ... you're comparing a code path that's been beat on
for *years* with one that just got written.

regards, tom lane

On Fri, Oct 21, 2011 at 2:33 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I think HeapTupleSatisfiesMVCC is probably being skipped anyway in
this case, since all the heap pages should be PD_ALL_VISIBLE.

Proves my point ;-) ... you're comparing a code path that's been beat on
for *years* with one that just got written.

I know. I wrote a chunk of it. :-) My point is just that it'd be
nice to make it better.

Anyhow, here's the scoop. On my desktop machine running F14, running
SELECT sum(1) FROM pgbench_accounts in a tight loop, 60 s worth of
oprofile data:

176830 13.0801 postgres postgres ExecProject
170028 12.5770 postgres postgres
IndexOnlyNext
96631 7.1478 postgres postgres
visibilitymap_test
86019 6.3628 postgres postgres
advance_aggregates
74366 5.5009 postgres postgres ExecScan
72428 5.3575 postgres postgres
ExecClearTuple
68483 5.0657 postgres postgres btgettuple
60614 4.4836 postgres postgres
advance_transition_function
59680 4.4145 postgres postgres ExecProcNode
52295 3.8683 postgres postgres
_bt_checkkeys
52078 3.8522 libc-2.12.90.so libc-2.12.90.so
__memcpy_sse2
49548 3.6651 postgres postgres
index_getnext_tid
48265 3.5702 postgres postgres
ExecEvalConst
42989 3.1799 postgres postgres _bt_next
40544 2.9990 postgres postgres _bt_readpage
35162 2.6009 no-vmlinux no-vmlinux /no-vmlinux
33639 2.4883 postgres postgres
MemoryContextReset

And without index-only scans. but everything in shared_buffers:

169515 18.4261 postgres postgres ExecProject
94827 10.3076 postgres postgres
heapgettup_pagemode
84850 9.2231 postgres postgres
advance_aggregates
57998 6.3043 postgres postgres
advance_transition_function
55638 6.0478 postgres postgres
ExecEvalConst
53684 5.8354 postgres postgres heapgetpage
51411 5.5883 postgres postgres ExecScan
48387 5.2596 postgres postgres ExecProcNode
44129 4.7968 postgres postgres
ExecStoreTuple
30759 3.3435 postgres postgres heap_getnext
25923 2.8178 postgres postgres SeqNext
24145 2.6245 postgres postgres
CheckForSerializableConflictOut
23155 2.5169 postgres postgres ExecAgg
18864 2.0505 postgres postgres
heap_page_prune_opt
18784 2.0418 no-vmlinux no-vmlinux /no-vmlinux

The index-only scan takes about 385 ms, while the non-index-only
version takes about 284 ms.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Fri, Oct 21, 2011 at 3:07 PM, Robert Haas <robertmhaas@gmail.com> wrote:

[ oprofile results ]

*grovels through the line-by-line results*

Hmm, I guess there is a bit of a hotspot in StoreIndexTuple, which is
probably being folded into IndexOnlyNext in the per-function timings:

ExecClearTuple(slot);
for (i = 0; i < nindexatts; i++)
values[i] = index_getattr(itup, i + 1, itupdesc, &isnull[i]);
ExecStoreVirtualTuple(slot);

If I'm reading these results right, that section is about 3% of the
total number of samples.

Also, this line is kind of expensive:

if (!visibilitymap_test(scandesc->heapRelation,
ItemPointerGetBlockNumber(tid),
&node->ioss_VMBuffer))

Around 2%. But I don't see any way to avoid that, or even make it cheaper.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:

Anyhow, here's the scoop. On my desktop machine running F14, running
SELECT sum(1) FROM pgbench_accounts in a tight loop, 60 s worth of
oprofile data:

176830 13.0801 postgres postgres ExecProject

Hm, that's weird. In both these cases, I'd have expected that
ExecProject would get optimized away thanks to selection of a physical
tlist for the scan node. Wonder if that got broken ...

regards, tom lane

Robert Haas <robertmhaas@gmail.com> writes:

Hmm, I guess there is a bit of a hotspot in StoreIndexTuple, which is
probably being folded into IndexOnlyNext in the per-function timings:

ExecClearTuple(slot);
for (i = 0; i < nindexatts; i++)
values[i] = index_getattr(itup, i + 1, itupdesc, &isnull[i]);
ExecStoreVirtualTuple(slot);

I had wondered whether it'd be worth optimizing that along the lines of
slot_getallattrs(). But most indexes probably have only one column,
or anyway not enough to make for a useful savings.

regards, tom lane

On Fri, Oct 21, 2011 at 3:55 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

Anyhow, here's the scoop.  On my desktop machine running F14, running
SELECT sum(1) FROM pgbench_accounts in a tight loop, 60 s worth of
oprofile data:

176830   13.0801  postgres                 postgres                 ExecProject

Hm, that's weird.  In both these cases, I'd have expected that
ExecProject would get optimized away thanks to selection of a physical
tlist for the scan node.  Wonder if that got broken ...

If it did, it looks like it wasn't recent. I set up the same test
case on my MacBook using REL9_1_STABLE and REL9_0_STABLE and set a
breakpoint on ExecProject(). Both back-branches appear to also call
ExecProject() for every tuple.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Fri, Oct 21, 2011 at 11:14 AM, Robert Haas <robertmhaas@gmail.com> wrote:

On Fri, Oct 21, 2011 at 2:08 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

On Fri, Oct 21, 2011 at 1:18 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I don't know why you'd imagine that touching an index is free, or even
cheap, CPU-wise.  The whole point of the index-only optimization is to
avoid I/O.  When you try it on a case where there's no I/O to be saved,
*and* no shared-buffers contention to be avoided, there's no way it's
going to be a win.

Well, call me naive, but I would have thought touching six times less
data would make the operation run faster, not slower.

It's not "touching six times less data".  It's touching the exact same
number of tuples either way, just index tuples in one case and heap
tuples in the other.

Yeah, but it works out to fewer pages.

But since those pages are already in RAM, why would it matter all that
much? (Other than in the case of highly concurrent access, which you
don't seem to be testing?)

One of Tom's commits that made it not lock the same index page over
and over again (once for each tuple on it) made me think it should be
much faster than the seq scan, but a bit of random flailing about
convinced me that any saving from this were compensated for by the
high over head of FunctionCall2Coll and all of the hokey-pokey that
that call entails, which a seqscan can skip entirely.

If count(*) could cause the index-only scan to happen in physical
order of the index, rather than logical order, that might be a big
win. Both for all in memory and for not-all-in-memory.

Cheers,

Jeff

On Friday, October 21, 2011 08:14:12 PM Robert Haas wrote:

On Fri, Oct 21, 2011 at 2:08 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

On Fri, Oct 21, 2011 at 1:18 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I don't know why you'd imagine that touching an index is free, or even
cheap, CPU-wise. The whole point of the index-only optimization is to
avoid I/O. When you try it on a case where there's no I/O to be saved,
and no shared-buffers contention to be avoided, there's no way it's
going to be a win.

Well, call me naive, but I would have thought touching six times less
data would make the operation run faster, not slower.

It's not "touching six times less data". It's touching the exact same
number of tuples either way, just index tuples in one case and heap
tuples in the other.

Yeah, but it works out to fewer pages.

But access to those is not sequential. I guess if you measure cache hit ratios
the index scan will come out significantly worse.

Andres

2011/10/22 Andres Freund <andres@anarazel.de>

On Friday, October 21, 2011 08:14:12 PM Robert Haas wrote:

On Fri, Oct 21, 2011 at 2:08 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

On Fri, Oct 21, 2011 at 1:18 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I don't know why you'd imagine that touching an index is free, or

even

cheap, CPU-wise. The whole point of the index-only optimization is

to

avoid I/O. When you try it on a case where there's no I/O to be

saved,

and no shared-buffers contention to be avoided, there's no way it's
going to be a win.

Well, call me naive, but I would have thought touching six times less
data would make the operation run faster, not slower.

It's not "touching six times less data". It's touching the exact same
number of tuples either way, just index tuples in one case and heap
tuples in the other.

Yeah, but it works out to fewer pages.

But access to those is not sequential. I guess if you measure cache hit
ratios
the index scan will come out significantly worse.

Andres

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

"But access to those is not sequential" yes, I am agree.
In my opinion the problem is that. If the query needs to scan all the b-tree
index without to
access the table rows, the better way to read the index is like sequential
one,
in fact , query like count(*) or other not need the data are in "order" so I
think we
could read all blocks (better, "only" the leaf blocks) without to touching
too much the branch blocks.

For example query like this :

select column_a from table ;

is better to read the data from indexes like sequential

For query like this :

select column_a from table order by column_a ;

is better to read the data from indexes in range scan from root block to
first branch blocks and their leaf blocks, so we could "save"
the sorting.

Mat

Andres Freund <andres@anarazel.de> writes:

On Friday, October 21, 2011 08:14:12 PM Robert Haas wrote:

On Fri, Oct 21, 2011 at 2:08 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

It's not "touching six times less data". It's touching the exact same
number of tuples either way, just index tuples in one case and heap
tuples in the other.

Yeah, but it works out to fewer pages.

But access to those is not sequential. I guess if you measure cache hit ratios
the index scan will come out significantly worse.

Huh? In the case he's complaining about, the index is all in RAM.
Sequentiality of access is not an issue (at least not at the page
level --- within a page I suppose there could be cache-line effects).

regards, tom lane

On Saturday, October 22, 2011 05:20:26 PM Tom Lane wrote:

Andres Freund <andres@anarazel.de> writes:

On Friday, October 21, 2011 08:14:12 PM Robert Haas wrote:

On Fri, Oct 21, 2011 at 2:08 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

It's not "touching six times less data". It's touching the exact same
number of tuples either way, just index tuples in one case and heap
tuples in the other.

Yeah, but it works out to fewer pages.

But access to those is not sequential. I guess if you measure cache hit
ratios the index scan will come out significantly worse.

Huh? In the case he's complaining about, the index is all in RAM.
Sequentiality of access is not an issue (at least not at the page
level --- within a page I suppose there could be cache-line effects).

I was talking about L2/L3 caches...

Andres

Andres Freund <andres@anarazel.de> writes:

On Saturday, October 22, 2011 05:20:26 PM Tom Lane wrote:

Huh? In the case he's complaining about, the index is all in RAM.
Sequentiality of access is not an issue (at least not at the page
level --- within a page I suppose there could be cache-line effects).

I was talking about L2/L3 caches...

Yeah, but unless you think cache lines cross page boundaries (and we do
take pains to align the buffers on 8K addresses), there's not going to
be any sequentiality effect. Even if there were, it would only apply
if the pages chanced to be adjacent in the buffer array, and there is no
reason to expect that to be the case, for either seqscans or indexscans.

regards, tom lane

On Fri, Oct 21, 2011 at 10:57 PM, Jeff Janes <jeff.janes@gmail.com> wrote:

Yeah, but it works out to fewer pages.

But since those pages are already in RAM, why would it matter all that
much?  (Other than in the case of highly concurrent access, which you
don't seem to be testing?)

Well, because memory access takes time, and accessing more memory
takes more time. In the testing that I've done recently, performance
on in-memory workloads seems to be extremely sensitive to memory
speed, so you'd think that cutting down on memory access would be a
win.

One of Tom's commits that made it not lock the same index page over
and over again (once for each tuple on it) made me think it should be
much faster than the seq scan, but a bit of random flailing about
convinced me that any saving from this were compensated for by the
high over head of FunctionCall2Coll and all of the hokey-pokey that
that call entails, which a seqscan can skip entirely.

Huh. Not sure whether that's significant or not.

If count(*) could cause the index-only scan to happen in physical
order of the index, rather than logical order, that might be a big
win.  Both for all in memory and for not-all-in-memory.

That's an interesting point. I sort of assumed that would only help
for not-all-in-memory, but maybe not. The trouble is that I think
there are some problematic concurrency issues there.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

----- Цитат от Tom Lane (tgl@sss.pgh.pa.us), на 22.10.2011 в 19:19 -----

Andres Freund <andres@anarazel.de> writes:

On Saturday, October 22, 2011 05:20:26 PM Tom Lane wrote:

Huh? In the case he's complaining about, the index is all in RAM.
Sequentiality of access is not an issue (at least not at the page
level --- within a page I suppose there could be cache-line effects).

I was talking about L2/L3 caches...

Yeah, but unless you think cache lines cross page boundaries (and we do
take pains to align the buffers on 8K addresses), there's not going to
be any sequentiality effect. Even if there were, it would only apply
if the pages chanced to be adjacent in the buffer array, and there is no
reason to expect that to be the case, for either seqscans or indexscans.

regards, tom lane

I worked on in-memory hash stables of parrot project. It is not the same as
btrees but the structure and memory layout are not that different - tupples are
going into pages etc.

I have benchmarked iterating over such hash tables - sequential scan
of the same table comes 20-30% faster than scan ordered by the hash value
of the key. And this is overhead only of CPU cache lines - the numbers of
instructions executed on the processor are pretty much the same (counted by
valgrind).

So I do think that if we have sequential scan of indexes (physical order) it
will help even when all the data is in the buffercache.

Best regards

--
Luben Karavelov

Robert Haas <robertmhaas@gmail.com> writes:

On Fri, Oct 21, 2011 at 10:57 PM, Jeff Janes <jeff.janes@gmail.com> wrote:

If count(*) could cause the index-only scan to happen in physical
order of the index, rather than logical order, that might be a big
win. �Both for all in memory and for not-all-in-memory.

That's an interesting point. I sort of assumed that would only help
for not-all-in-memory, but maybe not. The trouble is that I think
there are some problematic concurrency issues there.

Yeah. We managed to make physical-order scanning work for VACUUM
because it's okay if VACUUM sometimes sees the same index tuple twice;
it'll just make the same decision about (not) deleting it. That will
not fly for regular querying.

regards, tom lane