Re: [HACKERS] Which qsort is used
-Original Message-
From: Tom Lane [mailto:[EMAIL PROTECTED]
Sent: Thursday, December 15, 2005 6:24 PM
To: Dann Corbit
Cc: Qingqing Zhou; Greg Stark; Jim C. Nasby; Luke Lonergan; Neil
Conway;
Bruce Momjian; pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Which qsort is used
Dann Corbit [EMAIL PROTECTED] writes:
Radix sort can also be made completely generic by using a callback
function.
The function gives back n-bits at a time, from the most significant
bits
to the least significant.
That's mighty handwavy --- it assumes that the datatype permits a
simple
breakdown into small pieces that can be sorted lexicographically.
It's not so hard. For fixed length character strings, the mapping is
just the character. For integers the mapping is obvious [msb to lsb or
lsb to msb of the integer, depending on whether you are doing msd or lsd
radix sort]. For intel floating point, the transformation is:
#include assert.h
#include inteltyp.h
uint32
float2key(float f)
{
uint32 sign,
mant,
mask;
assert(sizeof(float) == sizeof(uint32));
mant = *(uint32 *) f; /* Load float as array of bits */
sign = mant SB_MASK32;/* Isolate the leading sign bit */
mant ^= SB_MASK32; /* Invert the sign bit, making + - */
mask = sign - (sign 31); /* Either 0 or 0x7fff */
mant ^= mask; /* Invert exp and mant if negative */
return mant;
}
uint64
double2key(double d)
{
uint64 sign,
mant,
mask;
assert(sizeof(double) == sizeof(uint64));
mant = *(uint64 *) d; /* Load float as array of bits */
sign = mant SB_MASK64;/* Isolate the leading sign bit */
mant ^= SB_MASK64; /* Invert the sign bit, making + - */
mask = sign - (sign 63); /* Either 0 or 0x7fff */
mant ^= mask; /* Invert exp and mant if negative */
return mant;
}
Where the contents of inteltyp.h are as follows:
/*
** Typdefs for Intel formats.
** See keyxfrm.c for usage.
*/
typedef unsigned long uint32;
#define SB_MASK32 0x8000UL
#ifdef _MSC_VER
typedef unsigned __int64 uint64;
typedef __int64 sint64;
#define SB_MASK64 0x8000ui64
#else
typedef unsigned long long uint64;
typedef long long sint64;
#define SB_MASK64 0x8000ULL
#endif
extern uint32 float2key(float f);
uint64 double2key(double d);
===
After the above transformation, you just use the same buckets as for
integers.
In general, the creation of the mapping function is no more difficult
than the creation of a comparison function.
Seems
to me that's a much stronger requirement than assuming that you can
tell
which of two whole values is smaller. What's worse, it needs to be
the
same number of pieces for every value, which makes it hard to deal
with
variable-length data.
No. The number of pieces is irrelevant. And you can use MSD radix sort
for variable length data.
So, for char string, and a radix of 256, you just return the first
char,
then the second char, etc. to get the classical radix sort.
Uh, no, you'd need to work right-to-left, after having padded all the
strings to the same length somehow.
Unless you use MSD radix sort (which is usually better anyway).
regards, tom lane
---(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] Which qsort is used
Here's some results for a 2.5Ghz G5 and a 933Mhz G4 http://www.jefftrout.com/sort/ -- Jeff Trout [EMAIL PROTECTED] http://www.jefftrout.com/ http://www.stuarthamm.net/ ---(end of broadcast)--- TIP 2: Don't 'kill -9' the postmaster
[HACKERS] I am back online
The my email address is now working. If you sent an email on Monday _and_ received a rejection email yesterday, please resend the email, otherwise all email has been received. -- Bruce Momjian| http://candle.pha.pa.us pgman@candle.pha.pa.us | (610) 359-1001 + If your life is a hard drive, | 13 Roberts Road + Christ can be your backup.| Newtown Square, Pennsylvania 19073 ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
[HACKERS] Web archive issue?
This archive: http://archives.postgresql.org/pgsql-patches/2005-12/index.php was last updated on wednesday, whereas the others: http://archives.postgresql.org/pgsql-bugs/2005-12/index.php http://archives.postgresql.org/pgsql-interfaces/2005-12/index.php http://archives.postgresql.org/pgsql-hackers/2005-12/index.php have all been updated today. Does it need some magic pixie dust to start working again? :) BTW, the mailing lists seem to be blazingly fast recently, very nice. Have a nice day, -- Martijn van Oosterhout kleptog@svana.org http://svana.org/kleptog/ Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a tool for doing 5% of the work and then sitting around waiting for someone else to do the other 95% so you can sue them. pgpnkmYxxWdsb.pgp Description: PGP signature
Re: [HACKERS] Web archive issue?
On Fri, 16 Dec 2005, Martijn van Oosterhout wrote: This archive: http://archives.postgresql.org/pgsql-patches/2005-12/index.php http://svr5.postgresql.org/pgsql-patches/2005-12/index.php is the build server for the archives, and is up to date ... so I'm going to guess that the front-end server hasn't had a chance to sync up yet ... Marc G. Fournier Hub.Org Networking Services (http://www.hub.org) Email: [EMAIL PROTECTED] Yahoo!: yscrappy ICQ: 7615664 ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] Improving planning of outer joins
On Wed, 2005-12-14 at 21:27 -0500, Tom Lane wrote: I've spent some time looking into how we can improve our planning of outer joins. Sounds good. I'm not sure whether we'd need any additional planner knobs to control this. I think that the existing join_collapse_limit GUC variable should continue to exist, but its effect on left/right joins will be the same as for inner joins. If anyone wants to force join order for outer joins more than for inner joins, we'd need some other control setting, but I don't currently see why that would be very useful. Agreed. No additional GUCs required. Does this seem like a reasonable agenda Yup - tis good. Best Regards, Simon Riggs ---(end of broadcast)--- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] Improving planning of outer joins
On Thu, 2005-12-15 at 09:25 -0500, Tom Lane wrote: I did find some papers that talked about ways to push joins up and down past aggregations and GROUP BY, but that's a problem for another day. Yes, they seem like a good thing to get round to... the papers seem to present them as fairly clear transformations. I'd be interested if you get the chance to look at that. Best Regards, Simon Riggs ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] Web archive issue?
On Fri, Dec 16, 2005 at 03:19:58PM -0400, Marc G. Fournier wrote: On Fri, 16 Dec 2005, Martijn van Oosterhout wrote: This archive: http://archives.postgresql.org/pgsql-patches/2005-12/index.php http://svr5.postgresql.org/pgsql-patches/2005-12/index.php is the build server for the archives, and is up to date ... so I'm going to guess that the front-end server hasn't had a chance to sync up yet ... Sorry for the noise. Looks like the pages don't get updated if there was no traffic which means that as long as no emails cross the list, the page will keep displaying the old date. It seems logical and will teach me for jumping to conclusions... Have a nice day, -- Martijn van Oosterhout kleptog@svana.org http://svana.org/kleptog/ Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a tool for doing 5% of the work and then sitting around waiting for someone else to do the other 95% so you can sue them. pgptr3VY3b7MU.pgp Description: PGP signature
Re: [HACKERS] Improving planning of outer joins
Tom Lane wrote: I've spent some time looking into how we can improve our planning of outer joins. The current planner code slavishly follows the syntactic join order, which can lead to quite bad plans. The reason it does this is that in some cases altering the join order of outer joins can change the results. However, there are many cases where the results would not be changed, and we really need to start taking advantage of those cases. I wonder if the code is already able to transform right joins to left joins, like (A rightjoin B on (Pab)) = (B leftjoin A on (Pab)) I haven't looked at the code but I vaguely remember it is possible with some strings attached, like not being able to use not-mergejoinable conditions or something. I imagine it shows up as a leftjoin node with some flag set. How does this affect this optimization? Does this hold: (A rightjoin B on (Pab)) innerjoin C on (Pbc) = (B leftjoin A on (Pab)) innerjoin C on (Pbc) = (B innerjoin C on (Pbc)) leftjoin A on (Pab) ? -- Alvaro Herrerahttp://www.CommandPrompt.com/ The PostgreSQL Company - Command Prompt, Inc. ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] Improving planning of outer joins
Alvaro Herrera [EMAIL PROTECTED] writes: I wonder if the code is already able to transform right joins to left joins, like (A rightjoin B on (Pab)) = (B leftjoin A on (Pab)) Yeah, we already know that part. It's a freebie --- I didn't even bother mentioning rightjoin in my post, since it's equivalent to leftjoin after swapping the inputs. regards, tom lane ---(end of broadcast)--- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] Improving planning of outer joins
Tom Lane wrote: Alvaro Herrera [EMAIL PROTECTED] writes: I wonder if the code is already able to transform right joins to left joins, like (A rightjoin B on (Pab)) = (B leftjoin A on (Pab)) Yeah, we already know that part. It's a freebie --- I didn't even bother mentioning rightjoin in my post, since it's equivalent to leftjoin after swapping the inputs. Why the thing about the mergejoinable conditions then? Is that even true? -- Alvaro Herrerahttp://www.CommandPrompt.com/ PostgreSQL Replication, Consulting, Custom Development, 24x7 support ---(end of broadcast)--- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] Improving planning of outer joins
Alvaro Herrera [EMAIL PROTECTED] writes: Why the thing about the mergejoinable conditions then? Is that even true? There are some things that work off mergejoinable conditions, but the equivalence of right and left join isn't one of them ... regards, tom lane ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] Web archive issue?
On Fri, Dec 16, 2005 at 08:54:37PM +0100, Martijn van Oosterhout wrote: On Fri, Dec 16, 2005 at 03:19:58PM -0400, Marc G. Fournier wrote: On Fri, 16 Dec 2005, Martijn van Oosterhout wrote: This archive: http://archives.postgresql.org/pgsql-patches/2005-12/index.php http://svr5.postgresql.org/pgsql-patches/2005-12/index.php is the build server for the archives, and is up to date ... so I'm going to guess that the front-end server hasn't had a chance to sync up yet ... Sorry for the noise. Looks like the pages don't get updated if there was no traffic which means that as long as no emails cross the list, the page will keep displaying the old date. It seems logical and will teach me for jumping to conclusions... Actually, it would be much better IMHO if the last updated date was changed even if there was no traffic. Otherwise there's no way to know if the updates are actually working. -- Jim C. Nasby, Sr. Engineering Consultant [EMAIL PROTECTED] Pervasive Software http://pervasive.comwork: 512-231-6117 vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461 ---(end of broadcast)--- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] Self-modifying code
Tom Lane wrote: Alvaro Herrera [EMAIL PROTECTED] writes: I just read an article on LWN.net about the usage of self-modifying code for selecting the optimum code for a given operation at run time. That went out with hula hoops, I think. For sure the security implications of making your code segment writable mean that the bar for is it worth it is a WHOLE lot higher than it might possibly make TAS a bit faster. Actually I was thinking in the issue with defining different sets of TAS for SMP versus non-SMP. There was discussion that suggested handing off two set of binaries, one for each configuration. So it's not just it might possibly but rather a possible answer to that problem, which was not mentioned as minor and for which a solution was not found AFAIR. However it's not something that I'll personally code, so I'll let somebody else argue about it if they really care about the issue. I just felt the need to mention it. -- Alvaro Herrerahttp://www.CommandPrompt.com/ PostgreSQL Replication, Consulting, Custom Development, 24x7 support ---(end of broadcast)--- TIP 6: explain analyze is your friend
[HACKERS] second begin transaction emits a warning
Hi, recently someone show us this code in the spanish list... BEGIN WORK; INSERT INTO mitabla VALUES (1); BEGIN TRANSACTION; INSERT INTO mitabla VALUES (2); INSERT INTO mitabla VALUES (3); COMMIT TRANSACTION; INSERT INTO mitabla VALUES (4); ROLLBACK WORK; this is clearly bad you can't use a begin transaction inside a transaction... but the user was expecting other results and because he receives no error (actually was a warning but he is sending the commands via an external application)... he was expecting an empty table but instead he gets this: mitabla 1 2 3 (3 rows) so, why BeginTransactionBlock emits just a warning and not an error? this is not the same as in the case of the one who was closing and already closed cursor? -- regards, Jaime Casanova (DBA: DataBase Aniquilator ;) ---(end of broadcast)--- TIP 6: explain analyze is your friend
[HACKERS] reducing bloat in pg_statistic
I'm looking at a postgresql 7.3 database that has gotten rather bloated
in pg_statistic:
VACUUM verbose pg_statistic;
INFO: --Relation pg_catalog.pg_statistic--
INFO: Index pg_statistic_relid_att_index: Pages 4420; Tuples 1590:
Deleted 3789.
CPU 0.33s/0.03u sec elapsed 0.96 sec.
INFO: Removed 3789 tuples in 203 pages.
CPU 0.01s/0.03u sec elapsed 0.06 sec.
INFO: Pages 80345: Changed 7, Empty 0; Tup 1580: Vac 3789, Keep 25,
UnUsed 1566169.
Total CPU 7.12s/0.58u sec elapsed 150.03 sec.
INFO: --Relation pg_toast.pg_toast_16408--
INFO: Pages 16: Changed 0, Empty 0; Tup 4: Vac 0, Keep 0, UnUsed 75.
Total CPU 0.00s/0.00u sec elapsed 0.11 sec.
VACUUM
I am trying to figure out a way to shrink this down to something more
reasonable, with the caveat of not restarting the database server.
Vacuum Full doesnt work because it blocks all the queries on the system,
basically running the machine out of connections after a minute or so.
I also cannot truncate, reindex, or cluster the table as it is a system
table. I even tried some evil hackery like trying to rename the table
and create a new copy in a transaction all with no luck.
One person suggested that I delete all the rows and then vacuum full it,
but as far as i can tell this would still block the planner from
accessing it while the vacuum full took place, so I'd be out of
connections.
So I guess the first question is does anyone see any alternative scheme
for trimming this table down to size?
The secondary question is, if I can schedule a restart, is there a way
to get it shrunken with one restart? I was thinking that doing
stats_reset_on_server_start = true might work, can anyone confirm that?
TIA,
Robert Treat
--
Build A Brighter Lamp :: Linux Apache {middleware} PostgreSQL
---(end of broadcast)---
TIP 2: Don't 'kill -9' the postmaster
Re: [HACKERS] second begin transaction emits a warning
Jaime Casanova [EMAIL PROTECTED] writes: recently someone show us this code in the spanish list... BEGIN WORK; INSERT INTO mitabla VALUES (1); BEGIN TRANSACTION; INSERT INTO mitabla VALUES (2); INSERT INTO mitabla VALUES (3); COMMIT TRANSACTION; INSERT INTO mitabla VALUES (4); ROLLBACK WORK; he was expecting an empty table but instead he gets this: so, why BeginTransactionBlock emits just a warning and not an error? I can't get real excited about this case. If the second BEGIN had errored out, he'd *still* not get an empty table: the COMMIT would end the aborted transaction, then the last INSERT would succeed, then the ROLLBACK would complain about no transaction in progress. Maybe there's an argument for turning the warning into an error, but this example doesn't provide it. regards, tom lane ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [HACKERS] second begin transaction emits a warning
On Fri, 2005-12-16 at 17:36, Jaime Casanova wrote:
Hi,
recently someone show us this code in the spanish list...
BEGIN WORK;
INSERT INTO mitabla VALUES (1);
BEGIN TRANSACTION;
INSERT INTO mitabla VALUES (2);
INSERT INTO mitabla VALUES (3);
COMMIT TRANSACTION;
INSERT INTO mitabla VALUES (4);
ROLLBACK WORK;
this is clearly bad you can't use a begin transaction inside a
transaction... but the user was expecting other results and because he
receives no error (actually was a warning but he is sending the
commands via an external application)...
he was expecting an empty table but instead he gets this:
mitabla
1
2
3
(3 rows)
I'm not entirely sure that it's relevant, but he should have actually
recieved all 4 rows in his query, since the commit transaction would
have committed the first three inserts, and the 4th insert should have
gone in via auto-commit. So if he really got this result, his external
application is doing something extra here for him. Which might be the
point, emulating non-autocommit through an interface would be harder if
multiple begin's tossed an error. I'm sure other reasons have been
brought up as well.
so, why BeginTransactionBlock emits just a warning and not an error?
this is not the same as in the case of the one who was closing and
already closed cursor?
I might argue that closing a closed cursor should only emit a warning
and not an error... but perhaps someone else will jump in here.
Robert Treat
--
Build A Brighter Lamp :: Linux Apache {middleware} PostgreSQL
---(end of broadcast)---
TIP 2: Don't 'kill -9' the postmaster
Re: [HACKERS] reducing bloat in pg_statistic
Robert Treat [EMAIL PROTECTED] writes: I'm looking at a postgresql 7.3 database that has gotten rather bloated in pg_statistic: I am trying to figure out a way to shrink this down to something more reasonable, with the caveat of not restarting the database server. You haven't got too many options in 7.3, but it might work reasonably well to do delete from pg_statistic; vacuum full pg_statistic; re-analyze to repopulate vacuum full with no records should take well under a minute. It won't shrink the index, but it'll fix the table bloat which seems the worst part. The main gotcha here is that any queries started before you can finish the re-analyze will not have the benefit of statistics; in the worst case they might choose bad enough plans that you'll wish you had not done it. regards, tom lane ---(end of broadcast)--- TIP 2: Don't 'kill -9' the postmaster
Re: [HACKERS] Re: Which qsort is used
Luke Lonergan wrote: Tom, On 12/12/05 2:47 PM, Tom Lane [EMAIL PROTECTED] wrote: As those results suggest, there can be huge differences in sort performance depending on whether the input is random, nearly sorted, nearly reverse sorted, possesses many equal keys, etc. It would be very dangerous to say implementation A is better than implementation B without having tested all those scenarios. Yes. The Linux glibc qsort is proven terrible in the general case by these examples though. Bruce's point on that thread was that we shouldn't be replacing the OS routine in the general case. On the other hand, there is the precedent of replacing Solaris' routine with the NetBSD version. At this point, I think we have done enough testing on enough platforms to just use port/qsort on all platforms in 8.2. It seems whenever someone tries to improve the BSD qsort, they make it worse. Were the BSD programmers geniuses and we are all idiots now, or what? -- Bruce Momjian| http://candle.pha.pa.us pgman@candle.pha.pa.us | (610) 359-1001 + If your life is a hard drive, | 13 Roberts Road + Christ can be your backup.| Newtown Square, Pennsylvania 19073 ---(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] Re: Which qsort is used
On Fri, 16 Dec 2005, Bruce Momjian wrote: At this point, I think we have done enough testing on enough platforms to just use port/qsort on all platforms in 8.2. It seems whenever someone tries to improve the BSD qsort, they make it worse. Not necessariliy true. Dann Corbit sent me an implementation a while ago (you can see it on the same site). BSD qsort is improved, though not that much, by two methods. Since Dann write the program from scratch, so I am not sure if we are afford to take the efforts for the improvement. Regards, Qingqing ---(end of broadcast)--- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] Re: Which qsort is used
-Original Message- From: [EMAIL PROTECTED] [mailto:pgsql-hackers- [EMAIL PROTECTED] On Behalf Of Qingqing Zhou Sent: Friday, December 16, 2005 5:14 PM To: Bruce Momjian Cc: Luke Lonergan; Tom Lane; Neil Conway; pgsql-hackers@postgresql.org Subject: Re: [HACKERS] Re: Which qsort is used On Fri, 16 Dec 2005, Bruce Momjian wrote: At this point, I think we have done enough testing on enough platforms to just use port/qsort on all platforms in 8.2. It seems whenever someone tries to improve the BSD qsort, they make it worse. Not necessariliy true. Dann Corbit sent me an implementation a while ago (you can see it on the same site). BSD qsort is improved, though not that much, by two methods. Since Dann write the program from scratch, so I am not sure if we are afford to take the efforts for the improvement. Both of them are modified versions of Bentley's sort algorithm. I just added the in-order check to both of them, and the reversed partition check for the second method (in the case of the subfiles because insertion sort is allergic to reversed partitions). At any rate, neither is much of an improvement on Bentley's version. For the rare cases of completely ordered or completely reversed, it will be a monumental improvement. But that is a pretty rare case. If I could use C++, I could do much better. It is very difficult for me to write an ADT in C instead of in C++. ---(end of broadcast)--- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] number of loaded/unloaded COPY rows
Volkan YAZICI wrote: I prepared a patch for Have COPY return the number of rows loaded/unloaded? TODO. (Sorry for disturbing list with such a simple topic, but per warning from Bruce Momjian, I send my proposal to -hackers first.) I used the appending related information to commandTag method which is used for INSERT/UPDATE/DELETE/FETCH commands too. Furthermore, I edited libpq to make PQcmdTuples() interpret affected rows from cmdStatus value for COPY command. (Changes don't cause any compatibility problems for API and seems like work with triggers too.) One of the problems related with the used concept is trying to encapsulate processed number of rows within an uint32 variable. This causes an internal limit for counting COPY when we think it can process billions of rows. I couldn't find a solution for this. (Maybe, two uint32 can be used to store row count.) But other processed row counters (like INSERT/UPDATE) uses uint32 too. What's your suggestions and comments? Good question. The libpq interface returns the count as a character string using PQcmdTuples(), meaning libpq doesn't have any size limitation. The problem is only the counter you are using, and I think an int64 is the proper solution. If int64 isn't really 64-bits, the code should still work though. In fact we have this TODO, which is related: * Change LIMIT/OFFSET and FETCH/MOVE to use int8 This requires the same type of change. I have added this TODO: * Allow the count returned by SELECT, etc to be to represent as an int64 to allow a higher range of values This requires a change to es_processed, I think. -- Bruce Momjian| http://candle.pha.pa.us pgman@candle.pha.pa.us | (610) 359-1001 + If your life is a hard drive, | 13 Roberts Road + Christ can be your backup.| Newtown Square, Pennsylvania 19073 ---(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: [HACKERS] Which qsort is used
Luke Lonergan wrote: Qingqing, On 12/15/05 6:33 PM, Qingqing Zhou [EMAIL PROTECTED] wrote: Thanks for Greg let me take a second look at qsortB.c - there is paste-and-copy error there, so when it perform recursive sort, it calls glibc's qsort ... Really sorry, and feel a little bit gun-shy now ... After I re-tested it, now BSD qsort is the obvious winner in most situations. :-D Can you post the new results like the last post? - Luke Here is a result from a dual 0.8G x86 running Freebsd 6.0-RELEASE: http://homepages.paradise.net.nz/markir/download/sort-fbsd.out (after patching the bug with qsortB calling qsort). Clearly in this case, there is no glibc version, hence I've relabeled the 1st case as native qsort. Cheers Mark ---(end of broadcast)--- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] Automatic function replanning
Good idea, TODO updated: * Flush cached query plans when the dependent objects change or when the cardinality of parameters changes dramatically --- Jim C. Nasby wrote: On Tue, Dec 13, 2005 at 04:49:10PM -0500, Neil Conway wrote: On Tue, 2005-12-13 at 22:32 +0100, Joachim Wieland wrote: there's a topic that comes up from time to time on the lists, the problem that pgsql functions get planned only once and thereafter the same query plan is used until server shutdown or explicit recreation of the function. The problem really has nothing to do with functions, per se: whenever a plan is created and then stored for future use, the assumptions made by that plan may be invalidated by the time the plan is executed. This applies to PREPARE, pl/pgsql functions, perhaps the plan caching done by the RI triggers, and so forth. I also think that invalidating cached plans on a periodic basis is the wrong approach -- we can use sinval to invalidate plans as soon as a dependent database object changes and not before. This thread contains some ideas on how to do this: http://archives.postgresql.org/pgsql-hackers/2005-03/msg00426.php I got somewhat sidetracked by the complexities of the central plan caching module that Tom would like to see, but I'm still hoping to take a look at this for 8.2. As for predicate-driven plan changes (ie: query is planned the first time with a predicate that has high cardinality, but there are also low cardinality values that will be queried on), it would make more sense to track the amount of work (probably tuples fetched) normally required to execute a prepared statement. Any time that prepared statement is executed with a set of predicates that substantially changes the amount of work required it should be remembered and considered for re-planning the next time the query is executed with those predicates. -- Jim C. Nasby, Sr. Engineering Consultant [EMAIL PROTECTED] Pervasive Software http://pervasive.comwork: 512-231-6117 vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461 ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org -- Bruce Momjian| http://candle.pha.pa.us pgman@candle.pha.pa.us | (610) 359-1001 + If your life is a hard drive, | 13 Roberts Road + Christ can be your backup.| Newtown Square, Pennsylvania 19073 ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] Re: Which qsort is used
Dann Corbit [EMAIL PROTECTED] writes: Both of them are modified versions of Bentley's sort algorithm. Jon Bentley of Bell Labs? Small world ... he was my thesis adviser for awhile when he was at CMU. He's a good algorithms man, for sure. I just added the in-order check to both of them, and the reversed partition check for the second method (in the case of the subfiles because insertion sort is allergic to reversed partitions). I've still got a problem with these checks; I think they are a net waste of cycles on average. They would only be a win if you expected a nontrivial percentage of perfectly-in-order or perfectly-reverse-order inputs. What I think is much more probable in the Postgres environment is almost-but-not-quite-ordered inputs --- eg, a table that was perfectly ordered by key when filled, but some of the tuples have since been moved by UPDATEs. This is the worst possible case for the in-order checks, because they can then grovel over large percentages of the file before failing ... and when they fail, those cycles are entirely wasted; you have not advanced the state of the sort at all. For the usual case of randomly ordered input, of course it doesn't matter much at all because the in-order checks will fail after examining not too many items. But to argue that the checks are worth making, you have to assume that perfectly-ordered inputs are more common than almost-ordered inputs, and I think that is exactly the wrong assumption for the Postgres environment. I sure haven't seen any evidence that it's a good assumption. regards, tom lane ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [HACKERS] Re: Which qsort is used
-Original Message- From: Tom Lane [mailto:[EMAIL PROTECTED] Sent: Friday, December 16, 2005 9:03 PM To: Dann Corbit Cc: Qingqing Zhou; Bruce Momjian; Luke Lonergan; Neil Conway; pgsql- [EMAIL PROTECTED] Subject: Re: [HACKERS] Re: Which qsort is used Dann Corbit [EMAIL PROTECTED] writes: Both of them are modified versions of Bentley's sort algorithm. Jon Bentley of Bell Labs? Small world ... he was my thesis adviser for awhile when he was at CMU. He's a good algorithms man, for sure. I just added the in-order check to both of them, and the reversed partition check for the second method (in the case of the subfiles because insertion sort is allergic to reversed partitions). I've still got a problem with these checks; I think they are a net waste of cycles on average. They would only be a win if you expected a nontrivial percentage of perfectly-in-order or perfectly-reverse-order inputs. What I think is much more probable in the Postgres environment is almost-but-not-quite-ordered inputs --- eg, a table that was perfectly ordered by key when filled, but some of the tuples have since been moved by UPDATEs. This is the worst possible case for the in-order checks, because they can then grovel over large percentages of the file before failing ... and when they fail, those cycles are entirely wasted; you have not advanced the state of the sort at all. For the usual case of randomly ordered input, of course it doesn't matter much at all because the in-order checks will fail after examining not too many items. But to argue that the checks are worth making, you have to assume that perfectly-ordered inputs are more common than almost-ordered inputs, and I think that is exactly the wrong assumption for the Postgres environment. I sure haven't seen any evidence that it's a good assumption. The benchmarks say that they (order checks) are a good idea on average for ordered data, random data, and partly ordered data. It does not require perfectly ordered data for the checks to be useful. On mostly ordered data, it is likely that some partitions are perfectly ordered. If you trace the algorithms in a debugger you will be surprised at how often the partitions are ordered, even with random sets as input. ---(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] Re: Which qsort is used
On Sat, 17 Dec 2005, Dann Corbit wrote: The benchmarks say that they (order checks) are a good idea on average for ordered data, random data, and partly ordered data. I interpret that in linux, 500 seems a divide for qsortpdq. Before that number, it wins, after that, bsd wins more. On SunOS, qsortpdq takes the lead till the last second -- I suspect this is due to the rand() function: Linux - #define RAND_MAX2147483647 SunOS - #define RAND_MAX32767 So in SunOS, the data actually not that scattered - so more favourate for sorted() or reversed() check? Regards, Qingqing ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] Re: Which qsort is used
-Original Message- From: Qingqing Zhou [mailto:[EMAIL PROTECTED] Sent: Friday, December 16, 2005 10:13 PM To: Dann Corbit Cc: Tom Lane; Bruce Momjian; Luke Lonergan; Neil Conway; pgsql- [EMAIL PROTECTED] Subject: RE: [HACKERS] Re: Which qsort is used On Sat, 17 Dec 2005, Dann Corbit wrote: The benchmarks say that they (order checks) are a good idea on average for ordered data, random data, and partly ordered data. I interpret that in linux, 500 seems a divide for qsortpdq. Before that number, it wins, after that, bsd wins more. On SunOS, qsortpdq takes the lead till the last second -- I suspect this is due to the rand() function: Linux - #define RAND_MAX2147483647 SunOS - #define RAND_MAX32767 So in SunOS, the data actually not that scattered - so more favourate for sorted() or reversed() check? There is a lot of variability from system to system even for the same tests. I see different results depending on whether I use GCC or Intel or MS compilers. ---(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] Re: Which qsort is used
Dann Corbit [EMAIL PROTECTED] writes: I've still got a problem with these checks; I think they are a net waste of cycles on average. The benchmarks say that they (order checks) are a good idea on average for ordered data, random data, and partly ordered data. There are lies, damn lies, and benchmarks ;-) The problem with citing a benchmark for this discussion is that a benchmark can't tell you anything about real-world probabilities; it only tells you about the probabilities occuring in the benchmark case. You need to make the case that the benchmark reflects the real world, which you didn't. If you trace the algorithms in a debugger you will be surprised at how often the partitions are ordered, even with random sets as input. Well, I do agree that checking for orderedness on small partitions would succeed more often than on larger partitions or the whole file --- but the code-as-given checks all the way down. Moreover, the argument given for spending these cycles is that insertion sort sucks on reverse-order input ... where sucks means that it spends O(N^2) time. But it spends O(N^2) in the average case, too. regards, tom lane ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] Re: Which qsort is used
-Original Message- From: Tom Lane [mailto:[EMAIL PROTECTED] Sent: Friday, December 16, 2005 10:41 PM To: Dann Corbit Cc: Qingqing Zhou; Bruce Momjian; Luke Lonergan; Neil Conway; pgsql- [EMAIL PROTECTED] Subject: Re: [HACKERS] Re: Which qsort is used Dann Corbit [EMAIL PROTECTED] writes: I've still got a problem with these checks; I think they are a net waste of cycles on average. The benchmarks say that they (order checks) are a good idea on average for ordered data, random data, and partly ordered data. There are lies, damn lies, and benchmarks ;-) The problem with citing a benchmark for this discussion is that a benchmark can't tell you anything about real-world probabilities; it only tells you about the probabilities occuring in the benchmark case. You need to make the case that the benchmark reflects the real world, which you didn't. If you trace the algorithms in a debugger you will be surprised at how often the partitions are ordered, even with random sets as input. Well, I do agree that checking for orderedness on small partitions would succeed more often than on larger partitions or the whole file --- but the code-as-given checks all the way down. Moreover, the argument given for spending these cycles is that insertion sort sucks on reverse-order input ... where sucks means that it spends O(N^2) time. But it spends O(N^2) in the average case, too. I agree that in general these checks are not important and they complicate what is a simple and elegant algorithm. The cases where the checks are important (highly ordered data sets) are rare and so the value added is minimal. I am actually quite impressed with the excellence of Bentley's sort out of the box. It's definitely the best library implementation of a sort I have seen. ---(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
