IMHO, while worst case performance is a very useful tool for analyzing
algorithms (particularly their worst case time complexity), a worst
case should be put in its practical context. For example, if we had
reason to be concerned about *adversarial* inputs, I think that there
is a good chance that our qsort() actually would be problematic to the
point of driving us to prefer some generally slower alternative.
ISTM that you raise two distinct questions wrt to PostgreSQL, which are,
is the worst case performance really an issue:
(1) in general
(2) wrt adversarial inputs
The answer could be (1) "mostly no" and (2) "maybe yes".
It suggests that where qsort is used, the administrator wary of (2) could
be allowed to use an alternate implementation, maybe some merge sort, say
by tweaking a configuration option in "postgresql.conf".
--
Fabien.
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
