Horton

Re: [HACKERS] path toward faster partition pruning

Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp>

View thread View on postgr.es
From: Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp>
To: david.rowley@2ndquadrant.com
Cc: Langote_Amit_f8@lab.ntt.co.jp, sulamul@gmail.com, robertmhaas@gmail.com, dilipbalaut@gmail.com, rajkumar.raghuwanshi@enterprisedb.com, memissemerson@gmail.com, pgsql-hackers@postgresql.org
Date: 2017-11-16T02:54:23Z
Lists: pgsql-hackers 
Thanks for the interesting test, David.

At Tue, 14 Nov 2017 17:00:12 +1300, David Rowley <david.rowley@2ndquadrant.com> wrote in <CAKJS1f-1Lc_b=Y1iicPQzvUgSn1keHSgmRqLuOGq_VR6M==zbw@mail.gmail.com>
> On 13 November 2017 at 22:46, Amit Langote
> <Langote_Amit_f8@lab.ntt.co.jp> wrote:
> > On 2017/11/10 12:30, Kyotaro HORIGUCHI wrote:
> >> Without some aggressive optimization, the loop takes most of the
> >> time to check-and-jump for nothing especially with many
> >> partitions and somewhat unintuitive.
> >>
> >> The following uses a bit tricky bitmap operation but
> >> is straightforward as a whole.
> >>
> >> =====
> >> /* fill the bits upper from BITNUM(lower) (0-based) of the first word */
> >> a->workds[wordnum++] += ~(bitmapword)((1 << BITNUM(lower)) - 1);

'+='.. ^^;

> >> /* fill up intermediate words */
> >> while (wordnum < uwordnum)
> >>    a->words[wordnum++] = ~(bitmapword) 0;
> >>
> >> /* fill up to BITNUM(upper) bit (0-based) of the last word */
> >> a->workds[wordnum++] |=
> >>      (~(bitmapword) 0) >> (BITS_PER_BITMAPWORD - (BITNUM(upper) - 1));
> >> =====
> >
> > Considering also the David's comment downthread, I will try to incorporate
> > this into bms_add_range().
> 
> I've attached an implementation of the patch using this method.
> 
> I've also attached bitset.c which runs each through their paces. I'd
> have expected Kyotaro's method to be faster, but gcc 7.2 with -O2
> generates very slightly slower code. I didn't really check why. clang
> seems to do a better job with it.
..
> $ gcc -O2 bitset.c -o bitset && ./bitset
> bms_add_range in 0.694254 (6.94254 ns per loop)
> bms_add_range2 in 0.726643 (7.26643 ns per loop)
..
> $ gcc --version
> gcc (Ubuntu 7.2.0-8ubuntu3) 7.2.0
> Copyright (C) 2017 Free Software Foundation, Inc.
> This is free software; see the source for copying conditions.  There is NO
> warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Hmm bms_add_range doesn't seem getting so aggressive optimization
but I had a similar result.

Looking the output of gcc -S, I found that bms_add_range() is
embedded in main(). (gcc 7.1.0) It's not surprizing after finding
that but.. Anyway I added __attribute((noinline)) to the two
functions and got the following result.

> bms_add_range in 1.24 (12.4 ns per loop)
> bms_add_range2 in 0.8 (8 ns per loop)

It seems reasonable.

> $ clang -O2 bitset.c -o bitset && ./bitset
> bms_add_range in 0.866554 (8.66554 ns per loop)
> bms_add_range2 in 0.467138 (4.67138 ns per loop)
..
> $ clang --version
> clang version 4.0.1-6 (tags/RELEASE_401/final)
> Target: x86_64-pc-linux-gnu
> Thread model: posix
> InstalledDir: /usr/bin
> 
> Probably just go with Kyotaro's idea (v2). I don't think this is worth
> debating, I just wanted to show it's not that clear-cut.

I agree that it's not so clear-cut.

regard,

-- 
Kyotaro Horiguchi
NTT Open Source Software Center

Commits

  1. Fix assorted partition pruning bugs

  2. Make gen_partprune_steps static

  3. Remove useless 'default' clause

  4. Reorganize partitioning code

  5. Use custom hash opclass for hash partition pruning

  6. Blindly attempt to fix sepgsql tests broken due to 9fdb675fc5.

  7. Attempt to fix endianess issues in new hash partition test.

  8. Faster partition pruning

  9. For partitionwise join, match on partcollation, not parttypcoll.

  10. Revise API for partition bound search functions.

  11. Revise API for partition_rbound_cmp/partition_rbound_datum_cmp.

  12. Fix possible crash in partition-wise join.

  13. Refactor code for partition bound searching

  14. New C function: bms_add_range

  15. Add extensive tests for partition pruning.

  16. Add null test to partition constraint for default range partitions.

  17. Remove BufFile's isTemp flag.

  18. Make OWNER TO subcommand mention consistent

  19. Fix index matching for operators with mixed collatable/noncollatable inputs.