Re: A worst case for qsort - Mailing list pgsql-hackers

From Fabien COELHO
Subject Re: A worst case for qsort
Date
Msg-id alpine.DEB.2.10.1408060838090.24380@sto
Whole thread Raw
In response to A worst case for qsort  (Peter Geoghegan <pg@heroku.com>)
Responses Re: A worst case for qsort
List pgsql-hackers
> 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.

That is an interesting point.

Indeed, a database in general often stores user-supplied data, which may 
happen to be sorted for presentation purpose in an interface. Same thing 
occured with hashtable algorithms and was/is a way to do DOS attacks on 
web applications. I'm not sure whether the qsort version discussed here 
would apply on user-supplied data, though. If so, adding some randomness 
in the decision process would suffice to counter the adversarial input 
argument you raised.

-- 
Fabien.



pgsql-hackers by date:

Previous
From: Fujii Masao
Date:
Subject: Re: missing PG_RETURN_UINT16
Next
From: Peter Geoghegan
Date:
Subject: Re: A worst case for qsort