Hi, Thomas! > 31 авг. 2018 г., в 2:40, Thomas Munro <thomas.mu...@enterprisedb.com> > написал(а): > > [1] https://arxiv.org/pdf/1509.05053.pdf
I've implemented all of the strategies used in that paper. On a B-tree page we have a line pointers ordered in key order and tuples residing at the end of the page. Tuples at the end are mostly "appended", i.e. they usually are accommodated at the end of the free space. The ides of the attached patch is to try to order tuples in different strategies. This ordering happens during VACUUM and can be easily broken with single insert. Strategies are switched by #define: 1. USE_SEQ_ORDER - just order tuples in order of line pointers. This strategy has no idea behind and is expected to work similar to baseline (no changes to code at all) 2. USE_EYZINGER_ORDER - depth-first topological search. If you always choose lower branch - your search is just a sequential read of bytes. 3. USE_VEB_ORDER - Van Emde Boas layout - try to pack 3 tuples (mid and two sub-mids) together. The key ideas is that you cache-miss when read mid, but tuples of both next steps are already fetched by that cache miss. 4. USE_BT_ORDER - order two sub-mids together so that you can prefetch both two possible next mids in a single cache prefetch. Cache prefetches of B-tree binsearch are controlled by USE_PREFETCH. I've tested all these strategies on my laptop (2.2GHz Intel i7, 16GB RAM, MacOS 10.14.1) ./pgbench -i -s 25 postgres && ./pgbench -T 100 postgres No changes in configs. Here are results in tps: without prefetch baseline 1448.331199 seq 1433.737204 bt 1463.701527 veb 1457.586089 eyz 1483.654765 with prefetch baseline 1486.585895 seq 1471.757042 bt 1480.169967 veb 1464.834678 eyz 1460.323392 This numbers are not statistically cleared, just one run was done for every number, experiment needs to be tuned anyway. From this I can conclude: 1. It is hard to observe significant performance influence on pgbench. Maybe I should use some more representative B-tree performance tests? 2. Cache prefetches seem to increase performance without any layout strategies. But the difference is hair-splitting 2.6% 3. For implemented strategies my preliminary results corresponds to the result in a paper: Eyzinger layout is the best. 4. Among layout strategies with prefetch, bt-order strategy seems to be winner. How can I improve experimental evaluation of these layout strategies? Other thoughts? I'd be happy to hear any comment on this. Best regards, Andrey Borodin.
0001-Implement-different-B-tree-page-layouts.patch
Description: Binary data
