From: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
---|---|
To: | Edmund Mergl <E(dot)Mergl(at)bawue(dot)de>, PostgreSQL Hackers Mailinglist <pgsql-hackers(at)postgreSQL(dot)org> |
Subject: | Re: [HACKERS] strange behavior of UPDATE |
Date: | 1999-05-25 02:16:38 |
Message-ID: | 2022.927598598@sss.pgh.pa.us |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
I wrote:
> then a possible explanation for the problem would be that our
> btree index code isn't very fast when there are large numbers of
> identical keys.
Ah-hah, a lucky guess! I went back and looked at the profile stats
I'd extracted from Edmund's "update" example. This Linux box has
the same semi-functional gprof as someone else was using a while
ago --- the timings are bogus, but the call counts seem right.
And what I find are entries like this:
0.00 0.00 284977/284977 _bt_binsrch [3174]
[3177] 0.0 0.00 0.00 284977 _bt_firsteq [3177]
0.00 0.00 21784948/24713758 _bt_compare [3169]
0.00 0.00 426/35632 _bt_split [53]
0.00 0.00 35206/35632 _bt_insertonpg [45]
[3185] 0.0 0.00 0.00 35632 _bt_findsplitloc [3185]
0.00 0.00 5093972/8907411 _bt_itemcmp [3171]
In other words, _bt_firsteq is averaging almost 100 comparisons per
call, _bt_findsplitloc well over that. Both of these routines are
evidently designed on the assumption that there will be relatively
few duplicate keys --- they reduce to linear scans when there are
many duplicates.
_bt_firsteq shouldn't exist at all; the only routine that calls it
is _bt_binsrch, which does a fast binary search of the index page.
_bt_binsrch should be fixed so that the binary search logic does the
right thing for equal-key cases, rather than degrading to a linear
search. I am less confident that I understand _bt_findsplitloc's place
in the great scheme of things, but it could certainly be revised to use
a binary search rather than linear scan.
This benchmark is clearly overemphasizing the equal-key case, but
I think it ought to be fixed independently of whether we want to
look good on a dubious benchmark ... equal keys are not uncommon in
real-world scenarios after all.
Next question is do we want to risk twiddling this code so soon before
6.5, or wait till after?
regards, tom lane
From | Date | Subject | |
---|---|---|---|
Next Message | D'Arcy J.M. Cain | 1999-05-25 03:17:23 | Re: [HACKERS] Open 6.5 items |
Previous Message | Thomas Lockhart | 1999-05-25 01:47:19 | Re: [HACKERS] Article for Daemon News |