From: Tom Lane <tgl@sss.pgh.pa.us>
To: Jonah H. Harris <jonah.harris@gmail.com>
Cc: Rauan Maemirov <rauan1987@gmail.com>
Cc: pgsql-performance@postgresql.org
Subject: Re: Re: Re: Re: Query Optimization with Kruskal’s Algorithm
Date: Sat, 10 May 2008 20:30:39 -0400
Message-ID: <9051.1210465839@sss.pgh.pa.us> (raw)
In-Reply-To: <36e682920805101417l3ece50b9g8feeceda7de7e5d@mail.gmail.com>
References: <461a87490805070928h14226615hb87bf2574e26f330@mail.gmail.com>
<88daf38c0805071309k3ce86c22l74a42a29739a1c28@mail.gmail.com>
<b685fbf7-0845-4ea2-9c7e-0cf8e57ba785@m36g2000hse.googlegroups.com>
<36e682920805101327q18013c73v36bb58c7963a006d@mail.gmail.com>
<6948.1210453942@sss.pgh.pa.us>
<36e682920805101417l3ece50b9g8feeceda7de7e5d@mail.gmail.com>
"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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: tgl@sss.pgh.pa.us, jonah.harris@gmail.com, rauan1987@gmail.com
Subject: Re: Re: Re: Re: Query Optimization with Kruskal’s Algorithm
In-Reply-To: <9051.1210465839@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
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