Performance of the 2.4.x mapping views

Timing runs from examples/mapped.tcl (PIII/650, SuSE Lunix 7.3). These results are based on the Metakit 2.4.3+ release in CVS as of 27-03-2002 (performance is several times that of 2.4.1+ on 18-10-2001).

Plain: This is a straight/flat view
Hash: The same, but with hashing on top
Ordered: This view maintains its rows in key order
Both: Hashing with rows also stored in key order
Blocked: Use "blocked" (segmented) views underneath

Some comments:

Data consists of the standard "/usr/dict/words" file on Unix (45407 items)
Plain view adds are fastest, but finds bog down due to the O(N) slowdown
Blocked files can be smaller (less wasted space, better reuse after commit)
Hash find performance is O(1), ordered is O(log N) because of bsearch
Slow inserts in ordered-without-blocking due to insertions in the middle
The "both" mode is terribly slow because re-order causes hash map updates
It might be fine if hashing were added after filling up, and not stored
The final entries on this page are somewhat larger runs to show trends

Hashing is implemented as a second view, containing a "hash map": rows with a hash key and a row index into the actual data view itself. The size of the hash map is a power of two, with empty slots to keep collisions low. A consequence of this approach is that ordering and hashing can be combined.

Blocked views are a special case of B-trees, using a fixed 2-level scheme to hold the rows. The root node is "row" 0, rows 1..n are the leaves. Block sizes are balanced, keeping the blocks between 50 and 100% filled, but unlike B-trees they adapt based on the total number of rows. Blocking does not affect the semantics of views, it merely "segments" their physical storage in views on the disk (column-wise, as always).

*** Plain ***

 filldb 100 ... 15584 adds/sec (0..45407 rows)
     Fill           1x -> 2.92 seconds
     Commit         1x -> 80.42 mSec
     Find          10x -> 61.57 mSec
 filldb 101 ... 16052 adds/sec (45407..90814 rows)
     Fill           1x -> 2.83 seconds
     Commit         1x -> 132.74 mSec
     Find          10x -> 183.50 mSec
 filldb 102 ... 16134 adds/sec (90814..136221 rows)
     Fill           1x -> 2.82 seconds
     Commit         1x -> 193.74 mSec
     Find          10x -> 302.08 mSec
 136221 rows, ? hash slots, file size = 2999624
     ? data blocks, ? map blocks

*** Plain - data is blocked ***

 filldb 100 ... 15391 adds/sec (0..45407 rows)
     Fill           1x -> 2.95 seconds
     Commit         1x -> 84.64 mSec
     Find          10x -> 92.89 mSec
 filldb 101 ... 15365 adds/sec (45407..90814 rows)
     Fill           1x -> 2.96 seconds
     Commit         1x -> 79.47 mSec
     Find          10x -> 288.26 mSec
 filldb 102 ... 15238 adds/sec (90814..136221 rows)
     Fill           1x -> 2.98 seconds
     Commit         1x -> 84.68 mSec
     Find          10x -> 499.45 mSec
 136221 rows, ? hash slots, file size = 1785737
     138 data blocks, ? map blocks

*** Hash ***

 filldb 100 ... 11190 adds/sec (0..45407 rows)
     Fill           1x -> 4.06 seconds
     Commit         1x -> 99.85 mSec
     Find        1000x -> 68 uS
 filldb 101 ... 11369 adds/sec (45407..90814 rows)
     Fill           1x -> 3.99 seconds
     Commit         1x -> 174.82 mSec
     Find        1000x -> 70 uS
 filldb 102 ... 12880 adds/sec (90814..136221 rows)
     Fill           1x -> 3.53 seconds
     Commit         1x -> 218.25 mSec
     Find        1000x -> 67 uS
 136221 rows, 262145 hash slots, file size = 7287780
     ? data blocks, ? map blocks

*** Hash - map is blocked ***

 filldb 100 ... 6901 adds/sec (0..45407 rows)
     Fill           1x -> 6.58 seconds
     Commit         1x -> 103.93 mSec
     Find        1000x -> 92 uS
 filldb 101 ... 6330 adds/sec (45407..90814 rows)
     Fill           1x -> 7.17 seconds
     Commit         1x -> 181.51 mSec
     Find        1000x -> 108 uS
 filldb 102 ... 8973 adds/sec (90814..136221 rows)
     Fill           1x -> 5.06 seconds
     Commit         1x -> 217.90 mSec
     Find        1000x -> 114 uS
 136221 rows, ? hash slots, file size = 7156221
     ? data blocks, 263 map blocks

*** Hash - data is blocked ***

 filldb 100 ... 10252 adds/sec (0..45407 rows)
     Fill           1x -> 4.43 seconds
     Commit         1x -> 105.53 mSec
     Find        1000x -> 77 uS
 filldb 101 ... 9953 adds/sec (45407..90814 rows)
     Fill           1x -> 4.56 seconds
     Commit         1x -> 125.66 mSec
     Find        1000x -> 85 uS
 filldb 102 ... 11764 adds/sec (90814..136221 rows)
     Fill           1x -> 3.86 seconds
     Commit         1x -> 113.78 mSec
     Find        1000x -> 84 uS
 136221 rows, 262145 hash slots, file size = 6432256
     138 data blocks, ? map blocks

*** Hash - data is blocked - map is blocked ***

 filldb 100 ... 6592 adds/sec (0..45407 rows)
     Fill           1x -> 6.89 seconds
     Commit         1x -> 104.70 mSec
     Find        1000x -> 100 uS
 filldb 101 ... 5894 adds/sec (45407..90814 rows)
     Fill           1x -> 7.70 seconds
     Commit         1x -> 125.86 mSec
     Find        1000x -> 114 uS
 filldb 102 ... 8373 adds/sec (90814..136221 rows)
     Fill           1x -> 5.42 seconds
     Commit         1x -> 118.97 mSec
     Find        1000x -> 107 uS
 136221 rows, ? hash slots, file size = 5988308
     138 data blocks, 263 map blocks

*** Ordered ***

 filldb 100 ... 9290 adds/sec (0..45378 rows)
     Fill           1x -> 4.89 seconds
     Commit         1x -> 77.77 mSec
     Find        1000x -> 105 uS
 filldb 101 ... 971 adds/sec (45378..90756 rows)
     Fill           1x -> 46.73 seconds
     Commit         1x -> 129.99 mSec
     Find        1000x -> 106 uS
 filldb 102 ... 407 adds/sec (90756..136134 rows)
     Fill           1x -> 111.29 seconds
     Commit         1x -> 184.97 mSec
     Find        1000x -> 112 uS
 136134 rows, ? hash slots, file size = 2997908
     ? data blocks, ? map blocks

*** Ordered - data is blocked ***

 filldb 100 ... 7668 adds/sec (0..45378 rows)
     Fill           1x -> 5.92 seconds
     Commit         1x -> 81.56 mSec
     Find        1000x -> 138 uS
 filldb 101 ... 5946 adds/sec (45378..90756 rows)
     Fill           1x -> 7.63 seconds
     Commit         1x -> 133.49 mSec
     Find        1000x -> 149 uS
 filldb 102 ... 5739 adds/sec (90756..136134 rows)
     Fill           1x -> 7.91 seconds
     Commit         1x -> 179.18 mSec
     Find        1000x -> 164 uS
 136134 rows, ? hash slots, file size = 2862483
     195 data blocks, ? map blocks

*** Both ***

 filldb 100 ... 6777 adds/sec (0..45378 rows)
     Fill           1x -> 6.70 seconds
     Commit         1x -> 97.57 mSec
     Find        1000x -> 118 uS
 filldb 101 ... [abandoned]

*** Plain - data is blocked ***

 filldb 100 ... 15447 adds/sec (0..45407 rows)
     Fill           1x -> 2.94 seconds
     Commit         1x -> 81.13 mSec
     Find          10x -> 92.06 mSec
 filldb 101 ... 15359 adds/sec (45407..90814 rows)
     Fill           1x -> 2.96 seconds
     Commit         1x -> 77.36 mSec
     Find          10x -> 287.60 mSec
 filldb 102 ... 15244 adds/sec (90814..136221 rows)
     Fill           1x -> 2.98 seconds
     Commit         1x -> 80.25 mSec
     Find          10x -> 504.10 mSec
 filldb 103 ... 14796 adds/sec (136221..181628 rows)
     Fill           1x -> 3.07 seconds
     Commit         1x -> 85.22 mSec
     Find          10x -> 727.73 mSec
 filldb 104 ... 15050 adds/sec (181628..227035 rows)
     Fill           1x -> 3.02 seconds
     Commit         1x -> 86.58 mSec
     Find          10x -> 971.60 mSec
 filldb 105 ... 14978 adds/sec (227035..272442 rows)
     Fill           1x -> 3.03 seconds
     Commit         1x -> 90.28 mSec
     Find          10x -> 1.24 seconds
 filldb 106 ... 14873 adds/sec (272442..317849 rows)
     Fill           1x -> 3.05 seconds
     Commit         1x -> 94.06 mSec
     Find          10x -> 1.51 seconds
 filldb 107 ... 14791 adds/sec (317849..363256 rows)
     Fill           1x -> 3.07 seconds
     Commit         1x -> 99.07 mSec
     Find          10x -> 1.80 seconds
 filldb 108 ... 14718 adds/sec (363256..408663 rows)
     Fill           1x -> 3.09 seconds
     Commit         1x -> 100.21 mSec
     Find          10x -> 2.11 seconds
 filldb 109 ... 14583 adds/sec (408663..454070 rows)
     Fill           1x -> 3.11 seconds
     Commit         1x -> 107.36 mSec
     Find          10x -> 2.43 seconds
 454070 rows, ? hash slots, file size = 5936018
     456 data blocks, ? map blocks

*** Hash - data is blocked ***

 filldb 100 ... 10288 adds/sec (0..45407 rows)
     Fill           1x -> 4.41 seconds
     Commit         1x -> 98.16 mSec
     Find        1000x -> 78 uS
 filldb 101 ... 10177 adds/sec (45407..90814 rows)
     Fill           1x -> 4.46 seconds
     Commit         1x -> 115.79 mSec
     Find        1000x -> 77 uS
 filldb 102 ... 11939 adds/sec (90814..136221 rows)
     Fill           1x -> 3.80 seconds
     Commit         1x -> 109.52 mSec
     Find        1000x -> 79 uS
 filldb 103 ... 8345 adds/sec (136221..181628 rows)
     Fill           1x -> 5.44 seconds
     Commit         1x -> 154.29 mSec
     Find        1000x -> 81 uS
 filldb 104 ... 11568 adds/sec (181628..227035 rows)
     Fill           1x -> 3.93 seconds
     Commit         1x -> 149.06 mSec
     Find        1000x -> 91 uS
 filldb 105 ... 11297 adds/sec (227035..272442 rows)
     Fill           1x -> 4.02 seconds
     Commit         1x -> 125.83 mSec
     Find        1000x -> 88 uS
 filldb 106 ... 10988 adds/sec (272442..317849 rows)
     Fill           1x -> 4.13 seconds
     Commit         1x -> 150.06 mSec
     Find        1000x -> 101 uS
 filldb 107 ... 5891 adds/sec (317849..363256 rows)
     Fill           1x -> 7.71 seconds
     Commit         1x -> 207.90 mSec
     Find        1000x -> 92 uS
 filldb 108 ... 10839 adds/sec (363256..408663 rows)
     Fill           1x -> 4.19 seconds
     Commit         1x -> 215.68 mSec
     Find        1000x -> 96 uS
 filldb 109 ... 10715 adds/sec (408663..454070 rows)
     Fill           1x -> 4.24 seconds
     Commit         1x -> 221.63 mSec
     Find        1000x -> 99 uS
 454070 rows, 1048577 hash slots, file size = 27403948
     456 data blocks, ? map blocks

*** Ordered - data is blocked ***

 filldb 100 ... 7683 adds/sec (0..45378 rows)
     Fill           1x -> 5.91 seconds
     Commit         1x -> 78.95 mSec
     Find        1000x -> 136 uS
 filldb 101 ... 5995 adds/sec (45378..90756 rows)
     Fill           1x -> 7.57 seconds
     Commit         1x -> 133.08 mSec
     Find        1000x -> 149 uS
 filldb 102 ... 5701 adds/sec (90756..136134 rows)
     Fill           1x -> 7.96 seconds
     Commit         1x -> 194.77 mSec
     Find        1000x -> 167 uS
 filldb 103 ... 5273 adds/sec (136134..181513 rows)
     Fill           1x -> 8.61 seconds
     Commit         1x -> 229.43 mSec
     Find        1000x -> 179 uS
 filldb 104 ... 4940 adds/sec (181513..226892 rows)
     Fill           1x -> 9.19 seconds
     Commit         1x -> 269.68 mSec
     Find        1000x -> 187 uS
 filldb 105 ... 5019 adds/sec (226892..272270 rows)
     Fill           1x -> 9.04 seconds
     Commit         1x -> 274.53 mSec
     Find        1000x -> 190 uS
 filldb 106 ... 4926 adds/sec (272270..317648 rows)
     Fill           1x -> 9.21 seconds
     Commit         1x -> 341.73 mSec
     Find        1000x -> 194 uS
 filldb 107 ... 4555 adds/sec (317648..363027 rows)
     Fill           1x -> 9.96 seconds
     Commit         1x -> 386.48 mSec
     Find        1000x -> 204 uS
 filldb 108 ... 3991 adds/sec (363027..408405 rows)
     Fill           1x -> 11.37 seconds
     Commit         1x -> 434.24 mSec
     Find        1000x -> 229 uS
 filldb 109 ... 4061 adds/sec (408405..453783 rows)
     Fill           1x -> 11.17 seconds
     Commit         1x -> 453.30 mSec