pgsql: Avoid O(N^2) behavior when enlarging SPI tuple table in spi_prin

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: pgsql-committers(at)postgresql(dot)org
Subject: pgsql: Avoid O(N^2) behavior when enlarging SPI tuple table in spi_prin
Date: 2015-08-22 00:33:15
Message-ID: E1ZSwkF-0000d3-9S@gemulon.postgresql.org
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-committers

Avoid O(N^2) behavior when enlarging SPI tuple table in spi_printtup().

For no obvious reason, spi_printtup() was coded to enlarge the tuple
pointer table by just 256 slots at a time, rather than doubling the size at
each reallocation, as is our usual habit. For very large SPI results, this
makes for O(N^2) time spent in repalloc(), which of course soon comes to
dominate the runtime. Use the standard doubling approach instead.

This is a longstanding performance bug, so back-patch to all active
branches.

Neil Conway

Branch
------
REL9_5_STABLE

Details
-------
http://git.postgresql.org/pg/commitdiff/68a14ca74be03ab189b83c2bbf0b68c5d1daba44

Modified Files
--------------
src/backend/executor/spi.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)

Browse pgsql-committers by date

  From Date Subject
Next Message Heikki Linnakangas 2015-08-22 13:26:00 pgsql: Add hint to run "pgbench -i", if test tables don't exist.
Previous Message Tom Lane 2015-08-22 00:17:24 pgsql: Detect mismatched CONTINUE and EXIT statements at plpgsql compil