3 ms·

Sort improvements in PostgreSQL since 1997 [pdf]

36 points by postila 11y ago

Ono-Sendai 11y ago
why not radix sort? (or some variant of it)
- Alexss 11y ago
  It's mentioned, albeit in the second-last line of the whole presentation, as a possible reaction to GPU-based sorting in the future.
  - Ono-Sendai 11y ago
    Ok. Because you can radix sort on CPU and it's a lot faster than e.g. quicksort in my experience.
    - zkzkz 11y ago
      Postgres has an extensible type system so Radix sort isn't really suitable, it really needs a comparison sort. For SSE/MMX/AVX/etc or GPU sorts it would have to use integer or floating point surrogate keys. It would probably be the same abbreviated keys mentioned in the last few slides. That could be a radix sort but generally I think bitonic sort is preferred.
      - Jweb_Guru 11y ago
        > Postgres has an extensible type system so Radix sort isn't really suitable, it really needs a comparison sort. That's not quite true. It supports string tries, for example (using SP-GIST). Such operations just have to be built for specific types. I think it would be more accurate to say that (AFAICT) Postgres doesn't currently have any way to extend the optimizer with custom plans (though it's been a very popular feature suggestion).
        anarazel 11y ago
        > I think it would be more accurate to say that (AFAICT) Postgres doesn't currently have any way to extend the optimizer with custom plans (though it's been a very popular feature suggestion). There's http://www.postgresql.org/docs/devel/static/custom-scan.html http://www.postgresql.org/docs/devel/static/custom-scan.html
wolf550e 11y ago
Using SIMD instructions (MMX/SSE/AVX) ○ Most operators limited to floats but recently more general purpose (integer) vector operations have been supported ○ Registers keep increasing in size -- the next generation of CPUs will have 512 byte registers which may be sufficient Nobody uses MMX these days, SSE and AVX are not mostly limited to floating point, and AVX-512 is 512 bits, not bytes.
- zkzkz 11y ago
  Good point. Will correct the "byte" error. Thanks.

36 points by postila 11y ago

Ono-Sendai 11y ago

why not radix sort? (or some variant of it)

Alexss 11y ago
It's mentioned, albeit in the second-last line of the whole presentation, as a possible reaction to GPU-based sorting in the future.
- Ono-Sendai 11y ago
  Ok. Because you can radix sort on CPU and it's a lot faster than e.g. quicksort in my experience.
  - zkzkz 11y ago
    Postgres has an extensible type system so Radix sort isn't really suitable, it really needs a comparison sort. For SSE/MMX/AVX/etc or GPU sorts it would have to use integer or floating point surrogate keys. It would probably be the same abbreviated keys mentioned in the last few slides. That could be a radix sort but generally I think bitonic sort is preferred.
    - Jweb_Guru 11y ago
      > Postgres has an extensible type system so Radix sort isn't really suitable, it really needs a comparison sort. That's not quite true. It supports string tries, for example (using SP-GIST). Such operations just have to be built for specific types. I think it would be more accurate to say that (AFAICT) Postgres doesn't currently have any way to extend the optimizer with custom plans (though it's been a very popular feature suggestion).
      - anarazel 11y ago
        > I think it would be more accurate to say that (AFAICT) Postgres doesn't currently have any way to extend the optimizer with custom plans (though it's been a very popular feature suggestion). There's http://www.postgresql.org/docs/devel/static/custom-scan.html http://www.postgresql.org/docs/devel/static/custom-scan.html

wolf550e 11y ago

Using SIMD instructions (MMX/SSE/AVX) ○ Most operators limited to floats but recently more general purpose (integer) vector operations have been supported ○ Registers keep increasing in size -- the next generation of CPUs will have 512 byte registers which may be sufficient Nobody uses MMX these days, SSE and AVX are not mostly limited to floating point, and AVX-512 is 512 bits, not bytes.

zkzkz 11y ago
Good point. Will correct the "byte" error. Thanks.