> 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.