Skip site navigation (1) Skip section navigation (2)

pgsql: Fix efficiency problems in tuplestore_trim().

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: pgsql-committers(at)postgresql(dot)org
Subject: pgsql: Fix efficiency problems in tuplestore_trim().
Date: 2010-12-10 16:36:40
Message-ID: (view raw, whole thread or download thread mbox)
Lists: pgsql-committers
Fix efficiency problems in tuplestore_trim().

The original coding in tuplestore_trim() was only meant to work efficiently
in cases where each trim call deleted most of the tuples in the store.
Which, in fact, was the pattern of the original usage with a Material node
supporting mark/restore operations underneath a MergeJoin.  However,
WindowAgg now uses tuplestores and it has considerably less friendly
trimming behavior.  In particular it can attempt to trim one tuple at a
time off a large tuplestore.  tuplestore_trim() had O(N^2) runtime in this
situation because of repeatedly shifting its tuple pointer array.  Fix by
avoiding shifting the array until a reasonably large number of tuples have
been deleted.  This can waste some pointer space, but we do still reclaim
the tuples themselves, so the percentage wastage should be pretty small.

Per Jie Li's report of slow percent_rank() evaluation.  cume_dist() and
ntile() would certainly be affected as well, along with any other window
function that has a moving frame start and requires reading substantially
ahead of the current row.

Back-patch to 8.4, where window functions were introduced.  There's no
need to tweak it before that.



Modified Files
src/backend/utils/sort/tuplestore.c |   52 ++++++++++++++++++++++++-----------
1 files changed, 36 insertions(+), 16 deletions(-)

pgsql-committers by date

Next:From: Tom LaneDate: 2010-12-10 19:21:04
Subject: Re: pgsql: Reduce spurious Hot Standby conflicts from never-visible records
Previous:From: Simon RiggsDate: 2010-12-10 07:00:42
Subject: pgsql: Reduce spurious Hot Standby conflicts from never-visiblerecords

Privacy Policy | About PostgreSQL
Copyright © 1996-2018 The PostgreSQL Global Development Group