pgsql: Improve some O(N^2) behavior in window function evaluation.

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: pgsql-committers(at)postgresql(dot)org
Subject: pgsql: Improve some O(N^2) behavior in window function evaluation.
Date: 2014-04-13 17:59:27
Message-ID: E1WZOgh-0008PT-Qa@gemulon.postgresql.org
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-committers

Improve some O(N^2) behavior in window function evaluation.

Repositioning the tuplestore seek pointer in window_gettupleslot() turns
out to be a very significant expense when the window frame is sizable and
the frame end can move. To fix, introduce a tuplestore function for
skipping an arbitrary number of tuples in one call, parallel to the one we
introduced for tuplesort objects in commit 8d65da1f. This reduces the cost
of window_gettupleslot() to O(1) if the tuplestore has not spilled to disk.
As in the previous commit, I didn't try to do any real optimization of
tuplestore_skiptuples for the case where the tuplestore has spilled to
disk. There is probably no practical way to get the cost to less than O(N)
anyway, but perhaps someone can think of something later.

Also fix PersistHoldablePortal() to make use of this API now that we have
it.

Based on a suggestion by Dean Rasheed, though this turns out not to look
much like his patch.

Branch
------
master

Details
-------
http://git.postgresql.org/pg/commitdiff/e0c91a7ff015fab0ccbb0f75b6819f29ae00295e

Modified Files
--------------
src/backend/commands/portalcmds.c | 27 +++++--------
src/backend/executor/nodeWindowAgg.c | 57 +++++++++++++++++++-------
src/backend/utils/sort/tuplestore.c | 73 +++++++++++++++++++++++++++++++++-
src/include/utils/tuplestore.h | 4 ++
4 files changed, 129 insertions(+), 32 deletions(-)

Browse pgsql-committers by date

  From Date Subject
Next Message Greg Stark 2014-04-13 20:24:55 Re: pgsql: Add ANALYZE into regression tests
Previous Message Tom Lane 2014-04-13 15:00:19 pgsql: Suppress compiler warning in new contrib/pg_trgm code.