New Index Optimization Makes v5.4 up to x3 times faster of v5.3

Description of Bench

Prepare Steps:

  • We have table T1 and field f1 of ULONG type: CREATE TABLE T1(f1 ULONG).
  • We insert N records with values [1 .. N].

Benches:

  • FORWARD – do N searches of values 1, 2, 3, … N
  • REVERSE – do N searches of values N, N-1, … 1
  • 2 Direction – do N searches of random values 1, N, 2, N-1, 3, N-2, … N/2

Each search returns 1 found record.

 

Bench Hardware

MacBook Pro 2.2 GHz Intel Core i7 (Early 2011),
RAM 8GB 1333 MHz,
HDD 500GB 7200 rpm, about 45-50 Mb/sec.

 

Bench using v5.3

=========================================================
Count = 10 000 000 Opt1 = 1 Opt2 = 0
=========================================================

ADD inCount Records = 5 450 ms = 5.45 sec
Build Index f1 = 1 877 ms

Count searches FORWARD = 30 310 ms
Count searches REVERSE   = 28 821 ms
Count searches 2 directions = 85 018 ms

 

Bench using v5.4

=========================================================
Count = 10 000 000 Opt1 = 0 Opt2 = 0
No optimizations. We see pure speed of BinarySearch.
=========================================================

ADD inCount Records = 4 543 ms
Build Index f1 = 1 922 ms

Count searches FORWARD = 124220 ms
Count searches REVERSE = 128918 ms
Count searches 2 directions = 134173 ms

 

=========================================================
Count = 10000000 Opt1 = 1 Opt2 = 0

Enabled Opt1, i.e. Optimisation using the current page.
We see that forward and reverse sequental searches becomes x6 times better.
Random search also becomes better almost x2 times. NOT CLEAR WHY.
TODO: find explain why using debug/profile. Set breakpoint and see when it works.
=========================================================

ADD inCount Records = 4 458 ms
Build Index f1 = 1 823 ms

Count searches FORWARD = 19 849 ms
Count searches REVERSE = 20 848 ms
Count searches 2 directions = 74 005 ms

 

=========================================================
Count = 10000000 Opt1 = 0 Opt2 = 1

This combination have no many sense. Just for interest.
We see that times for all 3 benches becomes good,
but forward and reverse are not so fast as with Opt1.
=========================================================

ADD inCount Records = 4508 ms
Build Index f1 = 1715 ms

Count searches FORWARD = 23 951 ms
Count searches REVERSE = 24 875 ms
Count searches 2 directions = 28 200 ms

 

=========================================================
Count = 10000000 Opt1 = 1 Opt2 = 1

ALL optimizations ENABLED.
We see that again forward and reverse have the best times AND
RANDOM search becomes about x3 times better comparing to Opt1=1 only case.
=========================================================

ADD inCount Records = 4 373 ms
Build Index f1 = 1 729 ms

Count searches FORWARD = 20 950 ms
Count searches REVERSE = 19 002 ms
Count searches 2 directions = 24 981 ms

 

Published by

Ruslan Zasukhin

VP Engineering and New Technology Paradigma Software, Inc

Leave a Reply