Thread: Re: [PATCHES] putting CHECK_FOR_INTERRUPTS in qsort_comparetup()
"Charles Duffy" <charles.duffy@gmail.com> writes:
> [ CHECK_FOR_INTERRUPTS inside qsort comparison routine ]
It occurs to me that there's a nonzero risk of problems here, because if
the interrupt occurs qsort() will lose control. I'm wondering whether
there are any implementations of qsort() that allocate memory and then
release it before returning. If so, interrupting the sort would lead to
memory leaked permanently (till backend exit anyway).
We might have to just tolerate this, but if it occurs on a lot of
platforms I'd have second thoughts about applying the patch. Anyone
familiar with the internals of glibc's qsort, in particular?
regards, tom lane
Tom Lane wrote: > We might have to just tolerate this, but if it occurs on a lot of > platforms I'd have second thoughts about applying the patch. Anyone > familiar with the internals of glibc's qsort, in particular? Doesn't look like it's allocating any nonlocal memory: http://sourceware.org/cgi-bin/cvsweb.cgi/libc/stdlib/qsort.c?rev=1.12&content-type=text/x-cvsweb-markup&cvsroot=glibc -- Peter Eisentraut http://developer.postgresql.org/~petere/
Peter Eisentraut <peter_e@gmx.net> writes: > Tom Lane wrote: >> We might have to just tolerate this, but if it occurs on a lot of >> platforms I'd have second thoughts about applying the patch. Anyone >> familiar with the internals of glibc's qsort, in particular? > Doesn't look like it's allocating any nonlocal memory: > http://sourceware.org/cgi-bin/cvsweb.cgi/libc/stdlib/qsort.c?rev=1.12&content-type=text/x-cvsweb-markup&cvsroot=glibc But this file defines _quicksort() not qsort(). I was under the impression that the latter is actually a mergesort in glibc ... regards, tom lane
Tom Lane wrote: > > Doesn't look like it's allocating any nonlocal memory: > > > > http://sourceware.org/cgi-bin/cvsweb.cgi/libc/stdlib/qsort.c?rev=1. > >12&content-type=text/x-cvsweb-markup&cvsroot=glibc > > But this file defines _quicksort() not qsort(). I was under the > impression that the latter is actually a mergesort in glibc ... The merge sort is here: http://sourceware.org/cgi-bin/cvsweb.cgi/libc/stdlib/msort.c?rev=1.21&content-type=text/x-cvsweb-markup&cvsroot=glibc It uses alloca, so we're good here. -- Peter Eisentraut http://developer.postgresql.org/~petere/
Peter Eisentraut <peter_e@gmx.net> writes: > The merge sort is here: > http://sourceware.org/cgi-bin/cvsweb.cgi/libc/stdlib/msort.c?rev=1.21&content-type=text/x-cvsweb-markup&cvsroot=glibc > It uses alloca, so we're good here. Uh ... but it also uses malloc, and potentially a honkin' big malloc at that (up to a quarter of physical RAM). So I'm worried again. Anyway, Qingqing's question still needs to be answered: how can a sort of under 30k items take so long? regards, tom lane
On 7/15/06, Tom Lane <tgl@sss.pgh.pa.us> wrote: > Anyway, Qingqing's question still needs to be answered: how can a sort > of under 30k items take so long? > It happens because (as previously suggested by Tom) the dataset for the 'short' (~10k rows, .3 sec) sort has no rows whose leftmost fields evaluate to 'equal' when passed to the qsort compare function. The 'long' sort, (~30k rows, 78 sec) has plenty of rows whose first 6 columns all evaluate as 'equal' when the rows are compared. For the 'long' data, the compare moves on rightward until it encounters 'flato', which is a TEXT column with an average length of 7.5k characters (with some rows up to 400k). The first 6 columns are mostly INTEGER, so compares on them are relatively inexpensive. All the expensive compares on 'flato' account for the disproportionate difference in sort times, relative to the number of rows in each set. As for the potential for memory leaks - thinking about it. Thanks, Charles Duffy. > Peter Eisentraut <peter_e@gmx.net> writes: > > The merge sort is here: > > > http://sourceware.org/cgi-bin/cvsweb.cgi/libc/stdlib/msort.c?rev=1.21&content-type=text/x-cvsweb-markup&cvsroot=glibc > > > It uses alloca, so we're good here. > > Uh ... but it also uses malloc, and potentially a honkin' big malloc at > that (up to a quarter of physical RAM). So I'm worried again. > > Anyway, Qingqing's question still needs to be answered: how can a sort > of under 30k items take so long? > > regards, tom lane >
Attachment
"Charles Duffy" <charles.duffy@gmail.com> writes:
> ... For the 'long' data, the compare moves on rightward until it
> encounters 'flato', which is a TEXT column with an average length of
> 7.5k characters (with some rows up to 400k). The first 6 columns are
> mostly INTEGER, so compares on them are relatively inexpensive. All
> the expensive compares on 'flato' account for the disproportionate
> difference in sort times, relative to the number of rows in each set.
Yeah, and it's not just that it's text either. At those sizes, all
the values will be toasted, which means each compare is paying the
price of fetching multiple rows from the toast table. And decompressing
them too, no doubt. These costs are most likely swamping the actual
strcoll() (not that that's not bad enough compared to int4cmp).
We could probably tweak the sorting code to forcibly detoast sort keys
before beginning the sort, but I'm not entirely convinced that would be
a win: reading and writing enormous sort keys won't be cheap either.
Meanwhile, for a cheap solution: do you really need to sort on flato
at all? Maybe sorting on substr(flato,1,100) would be good enough?
regards, tom lane
Are we done with the sort interrupt issue mentioned in the subject line, and the issue outlined below? --------------------------------------------------------------------------- Tom Lane wrote: > "Charles Duffy" <charles.duffy@gmail.com> writes: > > ... For the 'long' data, the compare moves on rightward until it > > encounters 'flato', which is a TEXT column with an average length of > > 7.5k characters (with some rows up to 400k). The first 6 columns are > > mostly INTEGER, so compares on them are relatively inexpensive. All > > the expensive compares on 'flato' account for the disproportionate > > difference in sort times, relative to the number of rows in each set. > > Yeah, and it's not just that it's text either. At those sizes, all > the values will be toasted, which means each compare is paying the > price of fetching multiple rows from the toast table. And decompressing > them too, no doubt. These costs are most likely swamping the actual > strcoll() (not that that's not bad enough compared to int4cmp). > > We could probably tweak the sorting code to forcibly detoast sort keys > before beginning the sort, but I'm not entirely convinced that would be > a win: reading and writing enormous sort keys won't be cheap either. > > Meanwhile, for a cheap solution: do you really need to sort on flato > at all? Maybe sorting on substr(flato,1,100) would be good enough? > > regards, tom lane > > ---------------------------(end of broadcast)--------------------------- > TIP 3: Have you checked our extensive FAQ? > > http://www.postgresql.org/docs/faq -- Bruce Momjian bruce@momjian.us EnterpriseDB http://www.enterprisedb.com + If your life is a hard drive, Christ can be your backup. +
Bruce Momjian <bruce@momjian.us> writes:
> Are we done with the sort interrupt issue mentioned in the subject line,
> and the issue outlined below?
I'm inclined not to apply the proposed patch (adding
CHECK_FOR_INTERRUPTS) because of the risk of memory leakage inside
qsort. OTOH you could argue that there's an unfixable risk of memory
leakage there anyway, because it's always possible that the invoked
datatype comparison routine exits with elog(ERROR) for some reason,
or even contains a CHECK_FOR_INTERRUPTS call itself. Comments?
As for the question of whether we should try to detoast sort keys before
sorting, I'd suggest adding that to TODO. Investigating whether this
would be a good idea will take more time than we have for 8.2, so it's
gonna have to wait for a future cycle.
regards, tom lane
Tom Lane wrote:
> Bruce Momjian <bruce@momjian.us> writes:
> > Are we done with the sort interrupt issue mentioned in the subject line,
> > and the issue outlined below?
>
> I'm inclined not to apply the proposed patch (adding
> CHECK_FOR_INTERRUPTS) because of the risk of memory leakage inside
> qsort. OTOH you could argue that there's an unfixable risk of memory
> leakage there anyway, because it's always possible that the invoked
> datatype comparison routine exits with elog(ERROR) for some reason,
> or even contains a CHECK_FOR_INTERRUPTS call itself. Comments?
OK, we do check somewhere during sorting, I assume. I can't imagine a
single qsort() call taking all that long because we do them in batches
anyway.
> As for the question of whether we should try to detoast sort keys before
> sorting, I'd suggest adding that to TODO. Investigating whether this
> would be a good idea will take more time than we have for 8.2, so it's
> gonna have to wait for a future cycle.
Added to TODO:
* Consider detoasting keys before sorting
--
Bruce Momjian bruce@momjian.us
EnterpriseDB http://www.enterprisedb.com
+ If your life is a hard drive, Christ can be your backup. +