Thread: pgsql: Improve performance of our private version of qsort.
pgsql: Improve performance of our private version of qsort.
From
tgl@postgresql.org (Tom Lane)
Date:
Log Message: ----------- Improve performance of our private version of qsort. Per recent testing, the logic it contained to switch to insertion sort for near-sorted input was in fact a big loss, because it could fairly easily be fooled into applying insertion sort to large subfiles that weren't all that well ordered. Remove that, and instead add a simple check for already-perfectly-sorted input, as per suggestion from Dann Corbit. This adds at worst O(N*lgN) overhead, and usually far less, while sometimes allowing a subfile sort to finish in O(N) time. Preliminary testing says this is an improvement over the basic Bentley & McIlroy code for many nonrandom inputs, and it costs almost nothing when the input is random. Tags: ---- REL8_1_STABLE Modified Files: -------------- pgsql/src/port: qsort.c (r1.8 -> r1.8.2.1) (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/port/qsort.c.diff?r1=1.8&r2=1.8.2.1)