From e0c91a7ff015fab0ccbb0f75b6819f29ae00295e Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Sun, 13 Apr 2014 13:59:17 -0400 Subject: 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. --- src/include/utils/tuplestore.h | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'src/include') diff --git a/src/include/utils/tuplestore.h b/src/include/utils/tuplestore.h index 1e22feecee8..16eca871cd1 100644 --- a/src/include/utils/tuplestore.h +++ b/src/include/utils/tuplestore.h @@ -72,8 +72,12 @@ extern bool tuplestore_in_memory(Tuplestorestate *state); extern bool tuplestore_gettupleslot(Tuplestorestate *state, bool forward, bool copy, TupleTableSlot *slot); + extern bool tuplestore_advance(Tuplestorestate *state, bool forward); +extern bool tuplestore_skiptuples(Tuplestorestate *state, + int64 ntuples, bool forward); + extern bool tuplestore_ateof(Tuplestorestate *state); extern void tuplestore_rescan(Tuplestorestate *state); -- cgit v1.2.3