Thread

1. Prefetch index pages for B-Tree index scans

   Claudio Freire <klaussfreire@gmail.com> — 2012-10-18T20:30:26Z

   I've noticed, doing some reporting queries once, that index scans fail
   to saturate server resources on compute-intensive queries.
   
   Problem is, just after fetching a page, postgres starts computing
   stuff before fetching the next. This results in I/O - compute - I/O -
   compute alternation that results in idle CPU and disk, both.
   
   I've also noticed earlier patches attempted to implement prefetch of
   index pages, yet they don't seem to be committed. I'm wondering why.
   
   The patches themselves were quite complex, attempting to prefetch heap
   tuples in addition to index tuples. I can see how this would be
   beneficial, but heap prefetch is notoriously more complicated, and
   with the advent of index-only scans, maybe index-page-only prefetching
   would be of use.
   
   To test this hypothesis, I wrote the attached patch. pgbench doesn't
   seem to see any performance impact (expected, since pgbench uses
   really tiny queries that touch a single page). Using pgbench's data
   with a scale of 1000, I tried some other queries that were more taxing
   of index-only scans. This was done on my personal computer, with a
   really lame I/O subsystem (compared to database servers), and with
   9.2.1 rather than git, but I think it should be significant anyway. I
   will try to verify on RAID-ed disks, but I'm in short supply of test
   systems at the moment.
   
   Pgbench's biggest index (on pgbench_accounts.aid) is not
   unsurprisingly quite sequential, since it has been just created. So, I
   tested both forward and backward index scans, to get an idea of how
   the patch impacts on sequential and non-sequential workloads. I
   haven't been able to test truly random ones yet - I'm trying to load
   up a dump from a production database that's both big and messy to
   test.
   
   A few things worth noting, is that the patch avoids doing prefetch on
   single-page index access, and only when block numbers aren't
   sequentially increasing (only when scanning the index nonsequentially
   will prefetch be attempted), since I noticed the fadvise call in those
   cases was being counterproductive.
   
   So, here we go:
   
   The base query I used, is:
   
   explain analyze select aid, count(*) from pgbench_accounts where aid
   between 10000000 and 200000000 group by aid order by aid;
   
   For backward scans, just order by aid desc.
   
   The full command used is
   sudo bash -c 'echo 3 > /proc/sys/vm/drop_caches' ; pg_ctl start -l
   ${PGLOG} ; sleep 5 ; ( sleep 10 ; echo 'set effective_io_concurrency
   to 0;' ; echo 'explain analyze select aid, count(*) from
   pgbench_accounts where aid between 10000000 and 200000000 group by aid
   order by aid;' ) | psql -h localhost -p 5433 pgbench ; sleep 5 ;
   pg_ctl stop
   server starting
   
   The server is started and stopped every time to make sure the shared
   cache is empty, and sleeps are there to avoid backlash I/O from
   dropping caches to influence the benchmark.
   
   Results:
   
   With effective_io_concurrency set to 0 (patch disabled):
   
   Forward:
   
             QUERY PLAN
   ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
    GroupAggregate  (cost=0.00..4149039.04 rows=90257289 width=4) (actual
   time=47.552..31113.353 rows=90000001 loops=1)
      ->  Index Only Scan using pgbench_accounts_pkey on pgbench_accounts
    (cost=0.00..2795179.71 rows=90257289 width=4) (actual
   time=47.542..13197.982 rows=90000001 loops=1)
            Index Cond: ((aid >= 10000000) AND (aid <= 200000000))
            Heap Fetches: 0
    Total runtime: 33648.500 ms
   I/O thoughtput averages 60MB/s (clearly sequential)
   I/O utilization averages around 30%
   
   Backward:
   
                  QUERY PLAN
   --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
    GroupAggregate  (cost=0.00..4149039.04 rows=90257289 width=4) (actual
   time=10.279..159704.590 rows=90000001 loops=1)
      ->  Index Only Scan Backward using pgbench_accounts_pkey on
   pgbench_accounts  (cost=0.00..2795179.71 rows=90257289 width=4)
   (actual time=10.266..132853.382 rows=90000001 loops=1)
            Index Cond: ((aid >= 10000000) AND (aid <= 200000000))
            Heap Fetches: 0
    Total runtime: 163202.869 ms
   I/O thoughput averages 11MB/s (clearly not fully random, but neither sequential)
   I/O utilization averages 68%
   
   
   With effective_io_concurrency set to 1 (patch enabled):
   
   Forward:
   
             QUERY PLAN
   ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
    GroupAggregate  (cost=0.00..4149039.04 rows=90257289 width=4) (actual
   time=47.582..30474.222 rows=90000001 loops=1)
      ->  Index Only Scan using pgbench_accounts_pkey on pgbench_accounts
    (cost=0.00..2795179.71 rows=90257289 width=4) (actual
   time=47.571..12208.340 rows=90000001 loops=1)
            Index Cond: ((aid >= 10000000) AND (aid <= 200000000))
            Heap Fetches: 0
    Total runtime: 32875.695 ms
   I/O thoughput still averages 60MB/s (tiny performance imrpovement is
   probably just variation, although in the multiple tests I've made
   there is a systematic bias towards lower times, probably the effect of
   prefetch on the few cases where the index jumps nonsequentially)
   I/O utilization remains around 35%
   
   Backward:
   
                  QUERY PLAN
   --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
    GroupAggregate  (cost=0.00..4149039.04 rows=90257289 width=4) (actual
   time=28.190..157708.405 rows=90000001 loops=1)
      ->  Index Only Scan Backward using pgbench_accounts_pkey on
   pgbench_accounts  (cost=0.00..2795179.71 rows=90257289 width=4)
   (actual time=28.178..135282.317 rows=90000001 loops=1)
            Index Cond: ((aid >= 10000000) AND (aid <= 200000000))
            Heap Fetches: 0
    Total runtime: 160735.539 ms
   I/O thoughput averages 12MB/s (a small increase), and the 3-second
   difference seems related to it (it's consistent).
   I/O utilization averages 88% (important increase)
   
   This last result makes me think deeper prefetching could be
   potentially beneficial (it would result in read merges), but it's
   rather hard to implement without a skiplist of leaf pages. Maybe the
   backward-sequential pattern could be detected. I'll have to tinker
   with that.
   
   With a hot OS cache, there's no discernible difference in timings.
   
   For heap-including scans forward (using sum(abalance) instead of
   count(*)), the times are 418522.583ms with, and 425497.436ms without
   (still very small, still consistent improvement).
   For heap-including scans backward, the times are 1764391.372ms with
   (with an I/O of 8.4MB/s at 95% utilization), and 1794715.164ms wihtout
   (7.8MB/s at 92% utilization). So, not whopping, but better.
   
   However small the improvement (5% on backward scans), since I see no
   ill effect, I thought I'd post the patch. Besides, I'm convinced
   first, with more chaotic indexes, the improvement should be noticeably
   bigger, and second, with more complex queries, the parallelization may
   be too. Especially with queries involving more than one index scan.
   This I believe since, if I attach an strace to the backend process,
   the improvement with prefetch jumps to 30% on backward scans, probably
   due to the increased computation window between reads.
   

2. Re: [PATCH] Prefetch index pages for B-Tree index scans

   Claudio Freire <klaussfreire@gmail.com> — 2012-10-18T22:42:55Z

   On Thu, Oct 18, 2012 at 5:30 PM, Claudio Freire <klaussfreire@gmail.com> wrote:
   > Backward:
   >
   >                QUERY PLAN
   > --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   >  GroupAggregate  (cost=0.00..4149039.04 rows=90257289 width=4) (actual
   > time=28.190..157708.405 rows=90000001 loops=1)
   >    ->  Index Only Scan Backward using pgbench_accounts_pkey on
   > pgbench_accounts  (cost=0.00..2795179.71 rows=90257289 width=4)
   > (actual time=28.178..135282.317 rows=90000001 loops=1)
   >          Index Cond: ((aid >= 10000000) AND (aid <= 200000000))
   >          Heap Fetches: 0
   >  Total runtime: 160735.539 ms
   > I/O thoughput averages 12MB/s (a small increase), and the 3-second
   > difference seems related to it (it's consistent).
   > I/O utilization averages 88% (important increase)
   >
   > This last result makes me think deeper prefetching could be
   > potentially beneficial (it would result in read merges), but it's
   > rather hard to implement without a skiplist of leaf pages. Maybe the
   > backward-sequential pattern could be detected. I'll have to tinker
   > with that.
   
   Fun. That didn't take long.
   
   With the attached anti-sequential scan patch, and effective_io_concurrency=8:
   
   
                 QUERY PLAN
   -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
    GroupAggregate  (cost=0.00..4149039.04 rows=90257289 width=4) (actual
   time=26.964..84299.789 rows=90000001 loops=1)
      ->  Index Only Scan Backward using pgbench_accounts_pkey on
   pgbench_accounts  (cost=0.00..2795179.71 rows=90257289 width=4)
   (actual time=26.955..62761.774 rows=90000001 loops=1)
            Index Cond: ((aid >= 10000000) AND (aid <= 200000000))
            Heap Fetches: 0
    Total runtime: 87170.355 ms
   I/O thoughput 22MB/s (twice as fast)
   I/O utilization 95% (I was expecting 100% but... hey... good enough)
   
   With e_i_c=24, it gets to 100% utilization and 30MB/s (that's 3 times
   faster). So, I'd like to know what you think, but maybe for
   back-sequential scans, prefetch should be set to a multiple (ie: x24)
   of e_i_c, in order to exploit read request merges.
   

3. Re: [PATCH] Prefetch index pages for B-Tree index scans

   Claudio Freire <klaussfreire@gmail.com> — 2012-10-22T19:47:37Z

   On Thu, Oct 18, 2012 at 7:42 PM, Claudio Freire <klaussfreire@gmail.com> wrote:
   > Fun. That didn't take long.
   >
   > With the attached anti-sequential scan patch, and effective_io_concurrency=8:
   >
   >
   >               QUERY PLAN
   > -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   >  GroupAggregate  (cost=0.00..4149039.04 rows=90257289 width=4) (actual
   > time=26.964..84299.789 rows=90000001 loops=1)
   >    ->  Index Only Scan Backward using pgbench_accounts_pkey on
   > pgbench_accounts  (cost=0.00..2795179.71 rows=90257289 width=4)
   > (actual time=26.955..62761.774 rows=90000001 loops=1)
   >          Index Cond: ((aid >= 10000000) AND (aid <= 200000000))
   >          Heap Fetches: 0
   >  Total runtime: 87170.355 ms
   > I/O thoughput 22MB/s (twice as fast)
   > I/O utilization 95% (I was expecting 100% but... hey... good enough)
   >
   > With e_i_c=24, it gets to 100% utilization and 30MB/s (that's 3 times
   > faster). So, I'd like to know what you think, but maybe for
   > back-sequential scans, prefetch should be set to a multiple (ie: x24)
   > of e_i_c, in order to exploit read request merges.
   
   
   Earlier patch had a regression for heap-including scans backwards with
   RAID, so I made the back-sequential optimization index-only-only and
   now I can find no regression. Make check runs fine, btw.
   
   I hope I'm not talking to myself.