pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedRe: Re: Re: Query Optimization with Kruskal’s Algorithm
2+ messages / 2 participants
[nested] [flat]
* Re: Re: Re: Query Optimization with Kruskal’s Algorithm
@ 2008-05-10 21:17 Jonah H. Harris <jonah.harris@gmail.com>
0 siblings, 1 reply; 2+ messages in thread
From: Jonah H. Harris @ 2008-05-10 21:17 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Rauan Maemirov <rauan1987@gmail.com>; pgsql-performance
On Sat, May 10, 2008 at 5:12 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> "Jonah H. Harris" <jonah.harris@gmail.com> writes:
>> Repost to -hackers, you're more likely to get a response on this topic.
>
> Probably not, unless you cite a more readily available reference.
> (I dropped my IEEE membership maybe fifteen years ago ...)
Yeah, I don't have one either. Similarly, I couldn't find anything
applicable to the PG implementation except references to the paper.
Wikipedia has the algorithm itself
(http://en.wikipedia.org/wiki/Kruskal's_algorithm), but I was more
interested in the actual applicability to PG and any issues they ran
into.
--
Jonah H. Harris, Sr. Software Architect | phone: 732.331.1324
EnterpriseDB Corporation | fax: 732.331.1301
499 Thornall Street, 2nd Floor | jonah.harris@enterprisedb.com
Edison, NJ 08837 | http://www.enterprisedb.com/
^ permalink raw reply [nested|flat] 2+ messages in thread
* Re: Re: Re: Re: Query Optimization with Kruskal’s Algorithm
@ 2008-05-11 00:30 Tom Lane <tgl@sss.pgh.pa.us>
parent: Jonah H. Harris <jonah.harris@gmail.com>
0 siblings, 0 replies; 2+ messages in thread
From: Tom Lane @ 2008-05-11 00:30 UTC (permalink / raw)
To: Jonah H. Harris <jonah.harris@gmail.com>; +Cc: Rauan Maemirov <rauan1987@gmail.com>; pgsql-performance
"Jonah H. Harris" <jonah.harris@gmail.com> writes:
> Wikipedia has the algorithm itself
> (http://en.wikipedia.org/wiki/Kruskal's_algorithm), but I was more
> interested in the actual applicability to PG and any issues they ran
> into.
Hmm ... minimum spanning tree of a graph, eh? Right offhand I'd say
this is a pretty terrible model of the join order planning problem.
The difficulty with trying to represent join order as a weighted
graph is that it assumes the cost to join two relations (ie, the
weight on the arc between them) is independent of what else you have
joined first. Which is clearly utterly wrong for join planning.
Our GEQO optimizer has a similar issue --- it uses a search algorithm
that is designed to solve traveling-salesman, which is almost the same
thing as minimum spanning tree. The saving grace for GEQO is that its
TSP orientation is only driving a heuristic; when it considers a given
overall join order it is at least capable of computing the right cost.
It looks to me like Kruskal's algorithm is entirely dependent on the
assumption that minimizing the sum of some predetermined pairwise costs
gives the correct plan.
In short, I'm sure it's pretty fast compared to either of our current
join planning methods, but I'll bet a lot that it often picks a much
worse plan. Color me unexcited, unless they've found some novel way
of defining the graph representation that avoids this problem.
regards, tom lane
^ permalink raw reply [nested|flat] 2+ messages in thread
end of thread, other threads:[~2008-05-11 00:30 UTC | newest]
Thread overview: 2+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2008-05-10 21:17 Re: Re: Re: Query Optimization with Kruskal’s Algorithm Jonah H. Harris <jonah.harris@gmail.com>
2008-05-11 00:30 ` Tom Lane <tgl@sss.pgh.pa.us>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox