Horton

Re: POC: converting Lists into arrays

David Rowley <david.rowley@2ndquadrant.com>

View thread View on postgr.es
From: David Rowley <david.rowley@2ndquadrant.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Jesper Pedersen <jesper.pedersen@redhat.com>, Andres Freund <andres@anarazel.de>, Robert Haas <robertmhaas@gmail.com>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2019-07-22T01:15:06Z
Lists: pgsql-hackers 
On Mon, 22 Jul 2019 at 02:45, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> One small question is whether it loses if most of the subplans
> are present in the bitmap.  I imagine that would be close enough
> to break-even, but it might be worth trying to test to be sure.
> (I'd think about breaking out just the loops in question and
> testing them stand-alone, or else putting in an outer loop to
> repeat them, since as you say the surrounding work probably
> dominates.)

My 2nd test was for when all subplans were present in the bitmap. It
did show a very slight slowdown for the case were all subplans were
present in the bitmapset. However, yeah, it seems like a good idea to
try it a million times to help show the true cost.

I did:

int x = 0;

/* Patched version */
for (j = 0; j < 1000000; j++)
{
    i = -1;
    while ((i = bms_next_member(validsubplans, i)) >= 0)
    {
        Plan    *initNode = (Plan *) list_nth(node->appendplans, i);
        x++;
    }
}

/* Master version */
for (j = 0; j < 1000000; j++)
{
    ListCell *lc;
    i = 0;
    foreach(lc, node->appendplans)
    {
        Plan    *initNode;
        if (bms_is_member(i, validsubplans))
       {
            initNode = (Plan *)lfirst(lc);
            x++;
        }
    }
}

elog(DEBUG1, "%d", x); /* stop the compiler optimizing away the loops */

I separately commented out each one of the outer loops away before
performing the test again.

plan_cache_mode = force_generic_plan

-- Test 1 (one matching subplan) --

prepare q1(int) as select * from ht where a = $1;
execute q1(1);

Master version:

Time: 14441.332 ms (00:14.441)
Time: 13829.744 ms (00:13.830)
Time: 13753.943 ms (00:13.754)

Patched version:

Time: 41.250 ms
Time: 40.976 ms
Time: 40.853 ms

-- Test 2 (all matching subplans (8192 of them)) --

prepare q2 as select * from ht;
execute q2;

Master version:

Time: 14825.304 ms (00:14.825)
Time: 14701.601 ms (00:14.702)
Time: 14650.969 ms (00:14.651)

Patched version:

Time: 44551.811 ms (00:44.552)
Time: 44357.915 ms (00:44.358)
Time: 43454.958 ms (00:43.455)

So the bms_next_member() loop is slower when the bitmapset is fully
populated with all subplans, but way faster when there's just 1
member.  In realiy, the ExecInitNode() call drowns most of it out.
Plus a plan with more subnodes is going take longer to execute and
then shutdown the plan after too.

-- 
 David Rowley                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

Commits

  1. Remove EState.es_range_table_array.

  2. Rationalize use of list_concat + list_copy combinations.

  3. Cosmetic improvements in setup of planner's per-RTE arrays.

  4. Make better use of the new List implementation in a couple of places

  5. Fix sepgsql test results for commit d97b714a2.

  6. Avoid using lcons and list_delete_first where it's easy to do so.

  7. Remove lappend_cell...() family of List functions.

  8. Clean up some ad-hoc code for sorting and de-duplicating Lists.

  9. Redesign the API for list sorting (list_qsort becomes list_sort).

  10. Remove dead code.

  11. Represent Lists as expansible arrays, not chains of cons-cells.

  12. Standardize some more loops that chase down parallel lists.

  13. Reimplement the linked list data structure used throughout the backend.