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  XLogInsert13.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
LWLockRelease1.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  XLogInsert13.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
LWLockRelease2.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.5817223967     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