Re: Constant time insertion into highly non-unique indexes

I wrote:
> So the theory does work, at least for small index entries. Currently
> repeating with wider ones ...

I tried the same test with the row width extended to 100 characters and
then 500 characters. The runtime and number of _bt_compare calls is
still about the same for the all-different-key and all-same-key cases.
I'm a bit surprised at that --- with only a dozen index entries per
page, you'd expect a lot more moverights --- but I sure do not see any
evidence here that there's anything broken about our handling of equal
keys.

The top profile entries with 500-character keys are

decreasing keys:
% cumulative self self total
time seconds seconds calls Ks/call Ks/call name
33.43 440.48 440.48 2163283 0.00 0.00 XLogInsert
13.45 617.65 177.17 501000004 0.00 0.00 CopyGetData
7.74 719.64 101.99 501000003 0.00 0.00 pq_copymsgbytes
6.72 808.18 88.55 1000001 0.00 0.00 CopyReadLine
4.03 861.24 53.05 501000004 0.00 0.00 CopyGetChar
3.82 911.55 50.31 1000000 0.00 0.00 CopyReadAttribute
2.71 947.29 35.74 23116181 0.00 0.00 LWLockAcquire
2.57 981.11 33.81 11462122 0.00 0.00 hash_search
2.16 1009.53 28.43 23345281 0.00 0.00 LWLockRelease
1.72 1032.18 22.64 31306616 0.00 0.00 _bt_compare
1.42 1050.94 18.76 8779022 0.00 0.00 PinBuffer
1.08 1065.22 14.28 7452454 0.00 0.00 _bt_moveright
1.06 1079.17 13.95 1000000 0.00 0.00 textin
0.98 1092.06 12.88 11462142 0.00 0.00 hash_any

equal keys:
% cumulative self self total
time seconds seconds calls Ks/call Ks/call name
25.21 326.87 326.87 2083931 0.00 0.00 XLogInsert
13.59 503.09 176.22 501000004 0.00 0.00 CopyGetData
7.96 606.32 103.23 501000003 0.00 0.00 pq_copymsgbytes
6.97 696.63 90.31 1000001 0.00 0.00 CopyReadLine
4.06 749.28 52.65 35592024 0.00 0.00 LWLockAcquire
3.97 800.73 51.45 501000004 0.00 0.00 CopyGetChar
3.73 849.10 48.37 1000000 0.00 0.00 CopyReadAttribute
3.40 893.13 44.04 17223947 0.00 0.00 hash_search
3.33 936.37 43.23 35736377 0.00 0.00 LWLockRelease
2.34 966.76 30.40 1083913 0.00 0.00 _bt_insertonpg
2.29 996.49 29.72 15477642 0.00 0.00 PinBuffer
1.98 1022.13 25.64 32383797 0.00 0.00 _bt_compare
1.45 1040.98 18.86 15628296 0.00 0.00 UnpinBuffer
1.40 1059.11 18.12 33256782 0.00 0.00 LockBuffer
1.28 1075.69 16.58 17223967 0.00 0.00 hash_any
1.19 1091.12 15.43 6832956 0.00 0.00 _bt_moveright
1.06 1104.89 13.77 1000000 0.00 0.00 textin
0.82 1115.52 10.63 15628296 0.00 0.00 ReadBuffer

regards, tom lane