Re: PG 10 release notes

On 2017-04-25 10:10:07 -0400, Bruce Momjian wrote:
> On Mon, Apr 24, 2017 at 08:52:05PM -0700, Andres Freund wrote:
> > On 2017-04-24 23:45:06 -0400, Tom Lane wrote:
> > Oh, I completely agree with accumulating related changes, and that
> > code-level details aren't useful. I think we skipped them entirely
> > here. And I just listed my own changes because I could find them
> > quickly, but they're not alone, e.g:
> > 090010f2ec9b1f9ac1124dc628b89586f911b641 - Improve performance of find_tabstat_entry()/get_tabstat_entry()
> > which makes it realistic to have sessions touching many relations, which
> > previously was O(#relations^2), and which caused repeated complaints
> > over the years, and allows for different usecases.
>
> Looking at this commit it appears to improve pg_stat statistics handling.
> I don't see how that improves performance except to improve statistics
> aggregation, which happens in the statistics process.

Previously when creating a new relation, we had to walk a list of all
open relations (i.e. O(N) work for each relation), now it's O(1) for
each relation. And that happens in the backends, not in the statistics
collector. It's pretty easy to see the effect. Write a plpgsql
function that creates, say, 100k tables. Run it in 9.6 and v10.

CREATE OR REPLACE FUNCTION create_tables(p_ntables int) RETURNS void LANGUAGE plpgsql AS $$DECLARE i int;BEGIN FOR i IN 1 .. p_ntables LOOP EXECUTE 'CREATE TABLE tbl_'||i::text||'();';END LOOP;END;$$

Measuring the time for the SELECT in
BEGIN;SELECT create_tables(10000);ROLLBACK;

Recreating the server inbetween each run I get:

version #nrels time
9.6 10 7ms
9.6 100 23ms
9.6 1000 159ms
9.6 10000 1465ms
9.6 100000 32367ms
9.6 200000 144026ms

at this point, you can see, we've squarely left O(N) country, and
entered the vast O(N^2) waste.

10 10 9ms
10 100 22ms
10 1000 162ms
10 10000 1497ms
10 100000 17260ms
10 200000 39275ms

Here we roughly stay in O(N).

(there's some other suboptimal behaviour in smgrclose(); but that's for
another day)

- Andres