Re: [HACKERS] Randomisation for ensuring nlogn complexity in quicksort

2013-07-02 Thread Claudio Freire
On Tue, Jul 2, 2013 at 12:36 PM, Peter Geoghegan wrote: > On Tue, Jul 2, 2013 at 5:04 AM, Atri Sharma wrote: >>> I think if you'll try it you'll find that we perform quite well on >>> data sets of this kind - and if you read the code you'll see why. >> >> Right, let me read the code again from th

Re: [HACKERS] Randomisation for ensuring nlogn complexity in quicksort

2013-07-02 Thread Peter Geoghegan
On Tue, Jul 2, 2013 at 5:04 AM, Atri Sharma wrote: >> I think if you'll try it you'll find that we perform quite well on >> data sets of this kind - and if you read the code you'll see why. > > Right, let me read the code again from that viewpoint. In my opinion, it would be worthwhile reading th

Re: [HACKERS] Randomisation for ensuring nlogn complexity in quicksort

2013-07-02 Thread Atri Sharma
On Tue, Jul 2, 2013 at 5:20 PM, Robert Haas wrote: > On Tue, Jul 2, 2013 at 12:33 AM, Atri Sharma wrote: >>> If you want to get a useful response to your emails, consider >>> including a statement of what you think the problem is and why you >>> think your proposed changes will help. Consider of

Re: [HACKERS] Randomisation for ensuring nlogn complexity in quicksort

2013-07-02 Thread Robert Haas
On Tue, Jul 2, 2013 at 12:33 AM, Atri Sharma wrote: >> If you want to get a useful response to your emails, consider >> including a statement of what you think the problem is and why you >> think your proposed changes will help. Consider offering a test case >> that performs badly and an analysis

Re: [HACKERS] Randomisation for ensuring nlogn complexity in quicksort

2013-07-01 Thread Atri Sharma
On Tue, Jul 2, 2013 at 1:02 AM, Robert Haas wrote: > On Sun, Jun 30, 2013 at 8:30 AM, Atri Sharma wrote: >> I have been reading the recent discussion and was researching a bit, and I >> think that we should really go with the idea of randomising the input >> data(if it is not completely presort

Re: [HACKERS] Randomisation for ensuring nlogn complexity in quicksort

2013-07-01 Thread Robert Haas
On Mon, Jul 1, 2013 at 4:31 PM, Claudio Freire wrote: > What? > > A median of medians algorithm will guarantee floor(N/2) elements on > the smaller. That's the definition of median. > > Note that I'm referring to picking the actual median of all tuples, > not just a sample. That's slow, but it gua

Re: [HACKERS] Randomisation for ensuring nlogn complexity in quicksort

2013-07-01 Thread Peter Geoghegan
On Mon, Jul 1, 2013 at 12:32 PM, Robert Haas wrote: >> I have been reading the recent discussion and was researching a bit, and I >> think that we should really go with the idea of randomising the input >> data(if it is not completely presorted), to ensure that we do not get >> quadratic comple

Re: [HACKERS] Randomisation for ensuring nlogn complexity in quicksort

2013-07-01 Thread Claudio Freire
On Mon, Jul 1, 2013 at 5:12 PM, Robert Haas wrote: > On Mon, Jul 1, 2013 at 3:54 PM, Claudio Freire wrote: >> On Mon, Jul 1, 2013 at 4:32 PM, Robert Haas wrote: This shouldn't be too complex, and should give us a fixed nlogn complexity even for wild data sets, without affecting existi

Re: [HACKERS] Randomisation for ensuring nlogn complexity in quicksort

2013-07-01 Thread Robert Haas
On Mon, Jul 1, 2013 at 3:54 PM, Claudio Freire wrote: > On Mon, Jul 1, 2013 at 4:32 PM, Robert Haas wrote: >>> This shouldn't be too complex, and should give us a fixed nlogn complexity >>> even for wild data sets, without affecting existing normal data sets that >>> are present in every day tr

Re: [HACKERS] Randomisation for ensuring nlogn complexity in quicksort

2013-07-01 Thread Claudio Freire
On Mon, Jul 1, 2013 at 4:32 PM, Robert Haas wrote: >> This shouldn't be too complex, and should give us a fixed nlogn complexity >> even for wild data sets, without affecting existing normal data sets that >> are present in every day transactions. I even believe that those data sets >> will als

Re: [HACKERS] Randomisation for ensuring nlogn complexity in quicksort

2013-07-01 Thread Robert Haas
On Sun, Jun 30, 2013 at 8:30 AM, Atri Sharma wrote: > I have been reading the recent discussion and was researching a bit, and I > think that we should really go with the idea of randomising the input data(if > it is not completely presorted), to ensure that we do not get quadratic > complexity

Re: [HACKERS] Randomisation for ensuring nlogn complexity in quicksort

2013-07-01 Thread Atri Sharma
On Mon, Jul 1, 2013 at 10:02 PM, David Fetter wrote: > On Mon, Jul 01, 2013 at 04:42:04AM -0700, jasmine wrote: >> My PostgresSQL (9.2) is crashing after certain load tests. Currently, >> postgressql is crashing when simulatenously 800 to 1000 threads are run on a >> 10 million records schema. Not

Re: [HACKERS] Randomisation for ensuring nlogn complexity in quicksort

2013-07-01 Thread David Fetter
On Mon, Jul 01, 2013 at 04:42:04AM -0700, jasmine wrote: > My PostgresSQL (9.2) is crashing after certain load tests. Currently, > postgressql is crashing when simulatenously 800 to 1000 threads are run on a > 10 million records schema. Not sure, if we have to tweak some more > parameters of postgr

Re: [HACKERS] Randomisation for ensuring nlogn complexity in quicksort

2013-07-01 Thread jasmine
My PostgresSQL (9.2) is crashing after certain load tests. Currently, postgressql is crashing when simulatenously 800 to 1000 threads are run on a 10 million records schema. Not sure, if we have to tweak some more parameters of postgres. - jasmine -- View this message in context: http://po