Thread: Internal operations when the planner makes a hash join.
Hello:
I'm an ignorant in what refers to performance analysis of PostgreSQL.
I've a doubt about how the PostgreSQL planner makes a hash join. I've
tried to "dig" into the archive of this mailing list but I haven't found
what I'm looking for. So I'm explaining my doubt with an example to see
if anyone can help me.
Let's suppose that I've 2 tables, one of students and the other one of
parents in a many-to-one relation. I want to do something like this:
SELECT s.complete_name, f.complete_name
FROM students AS s
JOIN fathers AS f ON f.id_father = s.id_father;
Using the ANALYZE command, I've checked that the planner firstly scans
and extracts the required information from "fathers", builds a temporary
hash table from it, then scans "students", and finally joins the
information from this table and the temporary one employing the relation
"f.id_father = s.id_father".
My doubt is about this last step. When the planner checks the temporary
table looking for the parent of a student:
A) Does it run through the temporary father's table one time per
student? This means that if there are 500 students, it's doing 500 loops
on the temporary table.
B) Or does it try to internally group students with the same father ID
to avoid doing "absurd" loops on the temporary one?
That's all. Thank you very much for your kindness :) .
negora <negora@negora.com> wrote: > I've a doubt about how the PostgreSQL planner makes a hash join. > Let's suppose that I've 2 tables, one of students and the other > one of parents in a many-to-one relation. I want to do something > like this: > > SELECT s.complete_name, f.complete_name > FROM students AS s > JOIN fathers AS f ON f.id_father = s.id_father; > > Using the ANALYZE command, I've checked that the planner firstly > scans and extracts the required information from "fathers", builds > a temporary hash table from it, then scans "students", and finally > joins the information from this table and the temporary one > employing the relation "f.id_father = s.id_father". This sort of plan is sometimes used when the optimizer expects the hash table to fit into RAM, based on statistics and your work_mem setting. If it does fit, that's one sequential scan of the father table's heap, and a hashed lookup into RAM to find the father to match each student. For the sort of query you're showing, that's typically a very good plan. -Kevin
<font face="Verdana">First of all, thank you for your fast answer, Kevin :) .<br /><br /> However I still wonder if on
thesearch into the hashed table (stored in the RAM, as you're pointing out), it checks for fathers as many times as
studentsare selected, or if the engine uses some kind of intelligent heuristic to avoid searching for the same father
morethan once.<br /><br /> For example:<br /><br /> students<br /> ----------------------------------------<br />
id_student| name | id_father<br /> ----------------------------------------<br /> 1 | James | 1<br /> 2 | Laura | 2<br
/>3 | Anthony | 1<br /><br /><br /> fathers (hashed table into RAM)<br /></font><font
face="Verdana">----------------------------------------<br/></font><font face="Verdana">id_father</font><font
face="Verdana">| name<br /> ----------------------------------------<br /> 1 | John<br /> 2 | Michael<br /><br /><br />
Accordingto how I understood the process, the engine would get the name from the student with ID 1 and would look for
thename of the father with ID 1 in the hashed table. It'd do exactly the same with the student #2 and father #2. But my
bigdoubt is about the 3rd one (Anthony). Would the engine "know" that it already had retrieved the father's name for
thestudent 1 and would avoid searching for it into the hashed table (using some kind of internal mechanism which allows
to"re-utilize" the name)? Or would it search into the hashed table again?<br /><br /> Thanks a lot for your patience :)
.<br/><br /></font><br /> Kevin Grittner wrote: <blockquote cite="mid:4B83A03E020000250002F4FD@gw.wicourts.gov"
type="cite"><prewrap="">negora <a class="moz-txt-link-rfc2396E"
href="mailto:negora@negora.com"><negora@negora.com></a>wrote: </pre><blockquote type="cite"><pre wrap="">I've a
doubtabout how the PostgreSQL planner makes a hash join. </pre></blockquote><pre wrap=""> </pre><blockquote
type="cite"><prewrap="">Let's suppose that I've 2 tables, one of students and the other
one of parents in a many-to-one relation. I want to do something
like this:
SELECT s.complete_name, f.complete_name FROM students AS s JOIN fathers AS f ON f.id_father =
s.id_father;
Using the ANALYZE command, I've checked that the planner firstly
scans and extracts the required information from "fathers", builds
a temporary hash table from it, then scans "students", and finally
joins the information from this table and the temporary one
employing the relation "f.id_father = s.id_father". </pre></blockquote><pre wrap="">
This sort of plan is sometimes used when the optimizer expects the
hash table to fit into RAM, based on statistics and your work_mem
setting. If it does fit, that's one sequential scan of the father
table's heap, and a hashed lookup into RAM to find the father to
match each student. For the sort of query you're showing, that's
typically a very good plan.
-Kevin
</pre></blockquote>
negora wrote: > According to how I understood the process, the engine would get the > name from the student with ID 1 and would look for the name of the > father with ID 1 in the hashed table. It'd do exactly the same with the > student #2 and father #2. But my big doubt is about the 3rd one > (Anthony). Would the engine "know" that it already had retrieved the > father's name for the student 1 and would avoid searching for it into > the hashed table (using some kind of internal mechanism which allows to > "re-utilize" the name)? Or would it search into the hashed table again?<br> The hash table is searched again. But that's fast, because it's a hash table. -- Alvaro Herrera http://www.CommandPrompt.com/ The PostgreSQL Company - Command Prompt, Inc.
On Feb 23, 2010, at 8:53 AM, Alvaro Herrera wrote: > negora wrote: > >> According to how I understood the process, the engine would get the >> name from the student with ID 1 and would look for the name of the >> father with ID 1 in the hashed table. It'd do exactly the same with the >> student #2 and father #2. But my big doubt is about the 3rd one >> (Anthony). Would the engine "know" that it already had retrieved the >> father's name for the student 1 and would avoid searching for it into >> the hashed table (using some kind of internal mechanism which allows to >> "re-utilize" the name)? Or would it search into the hashed table again?<br> > > The hash table is searched again. But that's fast, because it's a hash > table. > To answer the question another way, "remembering" that it has already seen father A once and tracking that would use a hashtable to remember that fact. The hash table created by the first scan IS the "remember you have seen this father" data structure, optimized for fast lookup. So before even looking at the first student, the hash table is built so that it is fast to find out if a father hasbeen seen before, and if so where that father's data is located. Looking this data up is often referred to as a "probe"and not a "scan" because it takes just as long to do if the hash table has 100 entries or 10000 entries. The drawbackis that the whole thing has to fit in RAM. > -- > Alvaro Herrera http://www.CommandPrompt.com/ > The PostgreSQL Company - Command Prompt, Inc. > > -- > Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) > To make changes to your subscription: > http://www.postgresql.org/mailpref/pgsql-performance
Thank you for explaining me the internal behaviour of the PostgreSQL engine. I'll try to look for more information about that hash tables. It sounds really really interesting. Your information was very useful. The origin of my doubt resides in the fact that I need to do a joint between 3 HUGE tables (millions of registries) and do certain operations with the retrieved information. I was deciding whether to use one SELECT with 3 JOINs, as I've been doing since the beginning, or build a PL/PgSQL function based on 3 nested "FOR ... IN SELECT ... LOOP" structures which tried to minimize the subsequent table searches storing intermediate useful data in arrays (curiously, these would act as the hash tables which you mention, but in a very very rudimentary way). In a case like this one (possibly unable to fit in RAM), Is also JOIN the best solution? Since I've to retrieve such a big amount of columns and crossed registries I had started to think that using 1 SELECT with 3 JOINs would increase the number of table searches a LOT and also "duplicate" the information too much. I mean "duplicate" as in this case, where the Factor 1 appears millions of times for every Element: Element 1 | Sub-factor 1 | Factor 1 Element 2 | Subf-actor 1 | Factor 1 ... Element 12639747465586 | Sub-factor 1 | Factor 1 Element 1 | Sub-factor 2 | Factor 1 I hope not to robber you much time but... What do you think about it? Is it better either 1 SELECT with 3 JOINs or build nested "FOR ... IN SELECT ... LOOP" structures? Could it be one of that cases in which I've to choose between either higher speed but higher memory consume (3 JOINs) or lower speed but less memory expense (3 FORs)? Thanks again and apologizes for extending this topic too much. Scott Carey wrote: > On Feb 23, 2010, at 8:53 AM, Alvaro Herrera wrote: > > >> negora wrote: >> >> >>> According to how I understood the process, the engine would get the >>> name from the student with ID 1 and would look for the name of the >>> father with ID 1 in the hashed table. It'd do exactly the same with the >>> student #2 and father #2. But my big doubt is about the 3rd one >>> (Anthony). Would the engine "know" that it already had retrieved the >>> father's name for the student 1 and would avoid searching for it into >>> the hashed table (using some kind of internal mechanism which allows to >>> "re-utilize" the name)? Or would it search into the hashed table again?<br> >>> >> The hash table is searched again. But that's fast, because it's a hash >> table. >> >> > > To answer the question another way, "remembering" that it has already seen father A once and tracking that would use ahash table to remember that fact. > > The hash table created by the first scan IS the "remember you have seen this father" data structure, optimized for fastlookup. So before even looking at the first student, the hash table is built so that it is fast to find out if a fatherhas been seen before, and if so where that father's data is located. Looking this data up is often referred to asa "probe" and not a "scan" because it takes just as long to do if the hash table has 100 entries or 10000 entries. Thedrawback is that the whole thing has to fit in RAM. > > > >> -- >> Alvaro Herrera http://www.CommandPrompt.com/ >> The PostgreSQL Company - Command Prompt, Inc. >> >> -- >> Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) >> To make changes to your subscription: >> http://www.postgresql.org/mailpref/pgsql-performance >> > > >
negora <negora@negora.com> wrote: > The origin of my doubt resides in the fact that I need to do a > joint between 3 HUGE tables (millions of registries) and do > certain operations with the retrieved information. I was deciding > whether to use one SELECT with 3 JOINs, as I've been doing since > the beginning, or build a PL/PgSQL function based on 3 nested "FOR > ... IN SELECT ... LOOP" structures which tried to minimize the > subsequent table searches storing intermediate useful data in > arrays It's almost always faster (and less error prone) to write one SELECT statement declaring what you want than to try to do better by navigating individual rows procedurally. I would *strongly* recommend you write it with the JOINs and then post here if you have any concerns about the performance. In general, try to *declare* what you want, and let the PostgreSQL planner sort out the best way to navigate the tables to produce what you want. If you hit some particular weakness in the planner, you many need to coerce it, but certainly you should not *start* with that. -Kevin
<font face="Verdana">Hello Kevin. I'm going to take and apply your advices, certainly. No more "crazy" PL/PgSQLs then. Iwas worried because of the possibility that repetition of fields caused some kind of memory saturation. But I guess thatPostgreSQL takes care of that fact properly. I even might return the entire result to my external Java application (Iwas using a similar approach on it too). I just hope that the speed of that single SQL compensates the transfer of sucha big mass of data between PostgreSQL and Java in terms of delay. Thanks ;) .<br /><br /><br /></font><br /> Kevin Grittnerwrote: <blockquote cite="mid:4B83F811020000250002F579@gw.wicourts.gov" type="cite"><pre wrap="">negora <a class="moz-txt-link-rfc2396E"href="mailto:negora@negora.com"><negora@negora.com></a> wrote: </pre><blockquote type="cite"><prewrap="">The origin of my doubt resides in the fact that I need to do a joint between 3 HUGE tables (millions of registries) and do certain operations with the retrieved information. I was deciding whether to use one SELECT with 3 JOINs, as I've been doing since the beginning, or build a PL/PgSQL function based on 3 nested "FOR ... IN SELECT ... LOOP" structures which tried to minimize the subsequent table searches storing intermediate useful data in arrays </pre></blockquote><pre wrap=""> It's almost always faster (and less error prone) to write one SELECT statement declaring what you want than to try to do better by navigating individual rows procedurally. I would *strongly* recommend you write it with the JOINs and then post here if you have any concerns about the performance. In general, try to *declare* what you want, and let the PostgreSQL planner sort out the best way to navigate the tables to produce what you want. If you hit some particular weakness in the planner, you many need to coerce it, but certainly you should not *start* with that. -Kevin </pre></blockquote>
>negora <negora@negora.com> wrote: > I even might return the entire result to my external Java > application You are probably going to want to configure it to use a cursor, at least if the result set is large (i.e., too big to cache the entire result set in memory before you read the first row). Read this over carefully: http://jdbc.postgresql.org/documentation/84/query.html#query-with-cursor You don't have to use a Java cursor or do anything procedurally there, but a PostgreSQL cursor is the only way to stream the data to the application on demand (ResultSet.next), rather than pushing it all there during the Statement.execute(). -Kevin
> -----Original Message----- > From: negora [mailto:negora@negora.com] > Sent: Tuesday, February 23, 2010 4:33 PM > To: Scott Carey > Cc: Alvaro Herrera; pgsql-performance@postgresql.org > Subject: Re: Internal operations when the planner makes a hash join. > > Thank you for explaining me the internal behaviour of the > PostgreSQL engine. I'll try to look for more information > about that hash tables. It sounds really really interesting. > Your information was very useful. > > The origin of my doubt resides in the fact that I need to do > a joint between 3 HUGE tables (millions of registries) and do > certain operations with the retrieved information. I was > deciding whether to use one SELECT with 3 JOINs, as I've been > doing since the beginning, or build a PL/PgSQL function based > on 3 nested "FOR ... IN SELECT ... LOOP" > structures which tried to minimize the subsequent table > searches storing intermediate useful data in arrays > (curiously, these would act as the hash tables which you > mention, but in a very very rudimentary way). In a case like > this one (possibly unable to fit in RAM), Is also JOIN the > best solution? > > Since I've to retrieve such a big amount of columns and > crossed registries I had started to think that using 1 SELECT > with 3 JOINs would increase the number of table searches a > LOT and also "duplicate" the information too much. I mean > "duplicate" as in this case, where the Factor 1 appears > millions of times for every Element: > > Element 1 | Sub-factor 1 | Factor 1 > Element 2 | Subf-actor 1 | Factor 1 > ... > Element 12639747465586 | Sub-factor 1 | Factor 1 Element 1 | > Sub-factor 2 | Factor 1 > > I hope not to robber you much time but... What do you think > about it? Is it better either 1 SELECT with 3 JOINs or build > nested "FOR ... IN SELECT ... LOOP" structures? Could it be > one of that cases in which I've to choose between either > higher speed but higher memory consume (3 > JOINs) or lower speed but less memory expense (3 FORs)? > > Thanks again and apologizes for extending this topic too much. > > > Scott Carey wrote: > > On Feb 23, 2010, at 8:53 AM, Alvaro Herrera wrote: > > > > > >> negora wrote: > >> > >> > >>> According to how I understood the process, the engine > would get the > >>> name from the student with ID 1 and would look for the > name of the > >>> father with ID 1 in the hashed table. It'd do exactly the > same with > >>> the student #2 and father #2. But my big doubt is about > the 3rd one > >>> (Anthony). Would the engine "know" that it already had > retrieved the > >>> father's name for the student 1 and would avoid searching for it > >>> into the hashed table (using some kind of internal > mechanism which > >>> allows to "re-utilize" the name)? Or would it search into > the hashed > >>> table again?<br> > >>> > >> The hash table is searched again. But that's fast, because it's a > >> hash table. > >> > >> > > > > To answer the question another way, "remembering" that it > has already seen father A once and tracking that would use a > hash table to remember that fact. > > > > The hash table created by the first scan IS the "remember > you have seen this father" data structure, optimized for fast > lookup. So before even looking at the first student, the > hash table is built so that it is fast to find out if a > father has been seen before, and if so where that father's > data is located. Looking this data up is often referred to > as a "probe" and not a "scan" because it takes just as long > to do if the hash table has 100 entries or 10000 entries. > The drawback is that the whole thing has to fit in RAM. > > > > > > > >> -- > >> Alvaro Herrera > http://www.CommandPrompt.com/ > >> The PostgreSQL Company - Command Prompt, Inc. > >> > >> -- > >> Sent via pgsql-performance mailing list > >> (pgsql-performance@postgresql.org) > >> To make changes to your subscription: > >> http://www.postgresql.org/mailpref/pgsql-performance > >> > > > > > > > So, you are trying to do "nested loop" in PL/PgSQL. Why not let optimizer decide between "nested loop" and "hash join" based on your memory settings and statistics collected for objects involved? I'm pretty sure, it'll be faster than PL/PgSQL 3 nested loops. Igor Neyman