Re: [PERFORM] Releasing memory during External sorting?
On Fri, 2005-09-23 at 12:48 -0400, Ron Peacetree wrote: I have some indications from private tests that very high memory settings may actually hinder performance of the sorts, though I cannot explain that and wonder whether it is the performance tests themselves that have issues. Hmmm. Are you talking about amounts so high that you are throwing the OS into paging and swapping thrash behavior? If not, then the above is weird. Thanks for your thoughts. I'll retest, on the assumption that there is a benefit, but there's something wrong with my earlier tests. Best Regards, Simon Riggs ---(end of broadcast)--- TIP 1: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] [PERFORM] Releasing memory during External sorting?
From: Dann Corbit [EMAIL PROTECTED] Sent: Sep 23, 2005 5:38 PM Subject: RE: [HACKERS] [PERFORM] Releasing memory during External sorting? _C Unleashed_ also explains how to use a callback function to perform arbitrary radix sorts (you simply need a method that returns the [bucketsize] most significant bits for a given data type, for the length of the key). So you can sort fairly arbitrary data in linear time (of course if the key is long then O(n*log(n)) will be better anyway.) But in any case, if we are talking about external sorting, then disk time will be so totally dominant that the choice of algorithm is practically irrelevant. Horsefeathers. Jim Gray's sorting contest site: http://research.microsoft.com/barc/SortBenchmark/ proves that the choice of algorithm can have a profound affect on performance. After all, the amount of IO done is the most important of the things that you should be optimizing for in choosing an external sorting algorithm. Clearly, if we know or can assume the range of the data in question the theoretical minimum amount of IO is one pass through all of the data (otherwise, we are back in O(lg(n!)) land ). Equally clearly, for HD's that one pass should involve as few seeks as possible. In fact, such a principle can be applied to _all_ forms of IO: HD, RAM, and CPU cache. The absolute best that any sort can possibly do is to make one pass through the data and deduce the proper ordering of the data during that one pass. It's usually also important that our algorithm be Stable, preferably Wholly Stable. Let's call such a sort Optimal External Sort (OES). Just how much faster would it be than current practice? The short answer is the difference between how long it currently takes to sort a file vs how long it would take to cat the contents of the same file to a RAM buffer (_without_ displaying it). IOW, there's SIGNIFICANT room for improvement over current standard practice in terms of sorting performance, particularly external sorting performance. Since sorting is a fundamental operation in many parts of a DBMS, this is a Big Deal. This discussion has gotten my creative juices flowing. I'll post some Straw Man algorithm sketches after I've done some more thought. Ron -Original Message- From: Dann Corbit [EMAIL PROTECTED] Sent: Friday, September 23, 2005 2:21 PM Subject: Re: [HACKERS] [PERFORM] Releasing memory during ... For the subfiles, load the top element of each subfile into a priority queue. Extract the min element and write it to disk. If the next value is the same, then the queue does not need to be adjusted. If the next value in the subfile changes, then adjust it. Then, when the lowest element in the priority queue changes, adjust the queue. Keep doing that until the queue is empty. You can create all the subfiles in one pass over the data. You can read all the subfiles, merge them, and write them out in a second pass (no matter how many of them there are). The Gotcha with Priority Queues is that their performance depends entirely on implementation. In naive implementations either Enqueue() or Dequeue() takes O(n) time, which reduces sorting time to O(n^2). The best implementations I know of need O(lglgn) time for those operations, allowing sorting to be done in O(nlglgn) time. Unfortunately, there's a lot of data manipulation going on in the process and two IO passes are required to sort any given file. Priority Queues do not appear to be very IO friendly. I know of no sorting performance benchmark contest winner based on Priority Queues. Replacement selection is not a good idea any more, since obvious better ideas should take over. Longer runs are of no value if you do not have to do multiple merge passes. Judging from the literature and the contest winners, Replacement Selection is still a viable and important technique. Besides Priority Queues, what obvious better ideas have you heard of? I have explained this general technique in the book C Unleashed, chapter 13. Sample code is available on the book's home page. URL please? ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
[PERFORM] Releasing memory during External sorting?
I have concerns about whether we are overallocating memory for use in external sorts. (All code relating to this is in tuplesort.c) When we begin a sort we allocate (work_mem | maintenance_work_mem) and attempt to do the sort in memory. If the sort set is too big to fit in memory we then write to disk and begin an external sort. The same memory allocation is used for both types of sort, AFAICS. The external sort algorithm benefits from some memory but not much. Knuth says that the amount of memory required is very low, with a value typically less than 1 kB. I/O overheads mean that there is benefit from having longer sequential writes, so the optimum is much larger than that. I've not seen any data that indicates that a setting higher than 16 MB adds any value at all to a large external sort. I have some indications from private tests that very high memory settings may actually hinder performance of the sorts, though I cannot explain that and wonder whether it is the performance tests themselves that have issues. Does anyone have any clear data that shows the value of large settings of work_mem when the data to be sorted is much larger than memory? (I am well aware of the value of setting work_mem higher for smaller sorts, so any performance data needs to reflect only very large sorts). If not, I would propose that when we move from qsort to tapesort mode we free the larger work_mem setting (if one exists) and allocate only a lower, though still optimal setting for the tapesort. That way the memory can be freed for use by other users or the OS while the tapesort proceeds (which is usually quite a while...). Feedback, please. Best Regards, Simon Riggs ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [PERFORM] Releasing memory during External sorting?
Ron Peacetree [EMAIL PROTECTED] writes: 2= No optimal external sorting algorithm should use more than 2 passes. 3= Optimal external sorting algorithms should use 1 pass if at all possible. A comparison-based sort must use at least N log N operations, so it would appear to me that if you haven't got approximately log N passes then your algorithm doesn't work. regards, tom lane ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [PERFORM] Releasing memory during External sorting?
operations != passes. If you were clever, you could probably write a modified bubble-sort algorithm that only made 2 passes. A pass is a disk scan, operations are then performed (hopefully in memory) on what you read from the disk. So there's no theoretical log N lower-bound on the number of disk passes. Not that I have anything else useful to add to this discussion, just a tidbit I remembered from my CS classes back in college :) -- Mark On Fri, 2005-09-23 at 13:17 -0400, Tom Lane wrote: Ron Peacetree [EMAIL PROTECTED] writes: 2= No optimal external sorting algorithm should use more than 2 passes. 3= Optimal external sorting algorithms should use 1 pass if at all possible. A comparison-based sort must use at least N log N operations, so it would appear to me that if you haven't got approximately log N passes then your algorithm doesn't work. regards, tom lane ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [PERFORM] Releasing memory during External sorting?
Mark Lewis [EMAIL PROTECTED] writes: operations != passes. If you were clever, you could probably write a modified bubble-sort algorithm that only made 2 passes. A pass is a disk scan, operations are then performed (hopefully in memory) on what you read from the disk. So there's no theoretical log N lower-bound on the number of disk passes. Given infinite memory that might be true, but I don't think I believe it for limited memory. If you have room for K tuples in memory then it's impossible to perform more than K*N useful comparisons per pass (ie, as each tuple comes off the disk you can compare it to all the ones currently in memory; anything more is certainly redundant work). So if K logN it's clearly not gonna work. It's possible that you could design an algorithm that works in a fixed number of passes if you are allowed to assume you can hold O(log N) tuples in memory --- and in practice that would probably work fine, if the constant factor implied by the O() isn't too big. But it's not really solving the general external-sort problem. regards, tom lane ---(end of broadcast)--- TIP 2: Don't 'kill -9' the postmaster
Re: [PERFORM] Releasing memory during External sorting?
Yep. Also, bear in mind that the lg(n!)= ~ nlgn - n lower bound on the number of comparisions: a= says nothing about the amount of data movement used. b= only holds for generic comparison based sorting algorithms. As Knuth says (vol 3, p180), Distribution Counting sorts without ever comparing elements to each other at all, and so does Radix Sort. Similar comments can be found in many algorithms texts. Any time we know that the range of the data to be sorted is substantially restricted compared to the number of items to be sorted, we can sort in less than O(lg(n!)) time. DB fields tend to take on few values and are therefore substantially restricted. Given the proper resources and algorithms, O(n) sorts are very plausible when sorting DB records. All of the fastest external sorts of the last decade or so take advantage of this. Check out that URL I posted. Ron -Original Message- From: Mark Lewis [EMAIL PROTECTED] Sent: Sep 23, 2005 1:43 PM To: Tom Lane [EMAIL PROTECTED] Subject: Re: [PERFORM] Releasing memory during External sorting? operations != passes. If you were clever, you could probably write a modified bubble-sort algorithm that only made 2 passes. A pass is a disk scan, operations are then performed (hopefully in memory) on what you read from the disk. So there's no theoretical log N lower-bound on the number of disk passes. Not that I have anything else useful to add to this discussion, just a tidbit I remembered from my CS classes back in college :) -- Mark On Fri, 2005-09-23 at 13:17 -0400, Tom Lane wrote: Ron Peacetree [EMAIL PROTECTED] writes: 2= No optimal external sorting algorithm should use more than 2 passes. 3= Optimal external sorting algorithms should use 1 pass if at all possible. A comparison-based sort must use at least N log N operations, so it would appear to me that if you haven't got approximately log N passes then your algorithm doesn't work. regards, tom lane ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [PERFORM] Releasing memory during External sorting?
From: Tom Lane [EMAIL PROTECTED] Sent: Sep 23, 2005 2:15 PM Subject: Re: [PERFORM] Releasing memory during External sorting? Mark Lewis [EMAIL PROTECTED] writes: operations != passes. If you were clever, you could probably write a modified bubble-sort algorithm that only made 2 passes. A pass is a disk scan, operations are then performed (hopefully in memory) on what you read from the disk. So there's no theoretical log N lower-bound on the number of disk passes. Given infinite memory that might be true, but I don't think I believe it for limited memory. If you have room for K tuples in memory then it's impossible to perform more than K*N useful comparisons per pass (ie, as each tuple comes off the disk you can compare it to all the ones currently in memory; anything more is certainly redundant work). So if K logN it's clearly not gonna work. Actually, it's far better than that. I recall a paper I saw in one of the algorithms journals 15+ years ago that proved that if you knew the range of the data, regardless of what that range was, and had n^2 space, you could sort n items in O(n) time. Turns out that with very modest constraints on the range of the data and substantially less extra space (about the same as you'd need for Replacement Selection + External Merge Sort), you can _still_ sort in O(n) time. It's possible that you could design an algorithm that works in a fixed number of passes if you are allowed to assume you can hold O(log N) tuples in memory --- and in practice that would probably work fine, if the constant factor implied by the O() isn't too big. But it's not really solving the general external-sort problem. If you know nothing about the data to be sorted and must guard against the worst possible edge cases, AKA the classic definition of the general external sorting problem, then one can't do better than some variant of Replacement Selection + Unbalanced Multiway Merge. OTOH, ITRW things are _not_ like that. We know the range of the data in our DB fields or we can safely assume it to be relatively constrained. This allows us access to much better external sorting algorithms. For example Postman Sort (the 2005 winner of the PennySort benchmark) is basically an IO optimized version of an external Radix Sort. Ron ---(end of broadcast)--- TIP 2: Don't 'kill -9' the postmaster
Re: [PERFORM] Releasing memory during External sorting?
From: Simon Riggs [EMAIL PROTECTED] Sent: Sep 23, 2005 5:37 AM Subject: [PERFORM] Releasing memory during External sorting? I have concerns about whether we are overallocating memory for use in external sorts. (All code relating to this is in tuplesort.c) A decent external sorting algorithm, say a Merge Sort + Radix (or Distribution Counting) hybrid with appropriate optimizations for small sub- files, should become more effective / efficient the more RAM you give it. The external sort algorithm benefits from some memory but not much. That's probably an artifact of the psql external sorting code and _not_ due to some fundamental external sorting issue. Knuth says that the amount of memory required is very low, with a value typically less than 1 kB. Required means the external sort can operate on that little memory. How Much memory is required for optimal performance is another matter. I/O overheads mean that there is benefit from having longer sequential writes, so the optimum is much larger than that. I've not seen any data that indicates that a setting higher than 16 MB adds any value at all to a large external sort. It should. A first pass upper bound would be the amount of RAM needed for Replacement Selection to create a run (ie sort) of the whole file. That should be ~ the amount of RAM to hold 1/2 the file in a Replacement Selection pass. At the simplest, for any file over 32MB the optimum should be more than 16MB. I have some indications from private tests that very high memory settings may actually hinder performance of the sorts, though I cannot explain that and wonder whether it is the performance tests themselves that have issues. Hmmm. Are you talking about amounts so high that you are throwing the OS into paging and swapping thrash behavior? If not, then the above is weird. Does anyone have any clear data that shows the value of large settings of work_mem when the data to be sorted is much larger than memory? (I am well aware of the value of setting work_mem higher for smaller sorts, so any performance data needs to reflect only very large sorts). This is not PostgreSQL specific, but it does prove the point that the performance of external sorts benefits greatly from large amounts of RAM being available: http://research.microsoft.com/barc/SortBenchmark/ Looking at the particulars of the algorithms listed there should shed a lot of light on what a good external sorting algorithm looks like: 1= HD IO matters the most. 1a= Seeking behavior is the largest factor in poor performance. 2= No optimal external sorting algorithm should use more than 2 passes. 3= Optimal external sorting algorithms should use 1 pass if at all possible. 4= Use as much RAM as possible, and use it as efficiently as possible. 5= The amount of RAM needed to hide the latency of a HD subsytem goes up as the _square_ of the difference between the bandwidth of the HD subsystem and memory. 6= Be cache friendly. 7= For large numbers of records whose sorting key is substantially smaller than the record itself, use a pointer + compressed key representation and write the data to HD in sorted order (Replace HD seeks with RAM seeks. Minimize RAM seeks). 8= Since your performance will be constrained by HD IO first and RAM IO second, up to a point it is worth it to spend more CPU cycles to save on IO. Given the large and growing gap between CPU IO, RAM IO, and HD IO, these issues are becoming more important for _internal_ sorts as well. Feedback, please. Best Regards, Simon Riggs Hope this is useful, Ron ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
