Обсуждение: big joins not converging

On Mar 10, 2011, at 1:25 PM, Dan Ancona wrote:

> Hi postgressers -
>
> As part of my work with voter file data, I pretty regularly have to join one large-ish (over 500k rows) table to
another.Sometimes this is via a text field (countyname) + integer (voter id). I've noticed sometimes this converges and
sometimesit doesn't, seemingly regardless of how I index things. So I'm looking for general thoughts on the joining of
largetables, but also running into a specific issue with the following slightly different query: 
>
> This one is between two tables that are a 754k row list of voters and a 445k row list of property owners. (I'm trying
tofind records where the owner name matches the voter name at the same address.) I have btree single column indices
builton all the relevant fields, and multicolumn indices built across all the columns I'm matching. The full schemas of
bothtables are below. The machine is an older-ish (3 years ago) dual-core pentium w/ 4GB RAM running FreeBSD, more
detailsbelow. 
>
> This is the query I've come up with so far:
>
> explain analyze
> update vanalameda set ownerflag = 'exact'
>   from aralameda where
>   vanalameda.streetno ~~ aralameda.streetnum and
>   vanalameda.streetname ~~ aralameda.streetname and
>   vanalameda.lastname ~~ aralameda.ownername and
>   vanalameda.firstname ~~ aralameda.ownername;
>
> If I include the analyze, this didn't complete after running overnight. If I drop the analyze and just explain, I get
this:
>
> "Nested Loop  (cost=46690.74..15384448712.74 rows=204 width=204)"
> "  Join Filter: (((vanalameda.streetno)::text ~~ (aralameda.streetnum)::text) AND ((vanalameda.streetname)::text ~~
(aralameda.streetname)::text)AND ((vanalameda.lastname)::text ~~ (aralameda.ownername)::text) AND
((vanalameda.firstname)::text~~ (aralameda.ownername)::text))" 
> "  ->  Seq Scan on vanalameda  (cost=0.00..26597.80 rows=734780 width=204)"
> "  ->  Materialize  (cost=46690.74..58735.87 rows=444613 width=113)"
> "        ->  Seq Scan on aralameda  (cost=0.00..38647.13 rows=444613 width=113)"
>
> One general question: does the width of the tables (i.e. the numbers of columns not being joined and the size of
thosefields) matter? The tables do have a lot of extra columns that I could slice out. 
>

Is there any reason you're using '~~' to compare values, rather than '='?

If you're intentionally using LIKE-style comparisons then there are some other things you can do, but I don't think you
meanto do that, for streeno and streetname anyway. 

Switching to an equality comparison should let your query use an index, most usefully one on (streetname, streetnum)
probably.

I'm not sure what you're intending by comparing ownername to both firstname and lastname. I don't think that'll do
anythinguseful, and doubt it'll ever match. Are you expecting firstname and lastname to be substrings of ownername? If
so,you might need to use wildcards with the like. 

(Also, performance and smart use of indexes tends to get better in newer versions of postgresql. You might want to
upgradeto 9.0.3 too.) 

Cheers,
  Steve

Steve Atkins <steve <at> blighty.com> writes:

>
>
> On Mar 10, 2011, at 1:25 PM, Dan Ancona wrote:
>
> > Hi postgressers -
> >
> > As part of my work with voter file data, I pretty regularly have to join one
large-ish (over 500k rows) table
> to another. Sometimes this is via a text field (countyname) + integer (voter
id). I've noticed sometimes
> this converges and sometimes it doesn't, seemingly regardless of how I index
things.

By "converge" you mean "finish running" -- "converge" has a lot of other
overtones for us amateur math types.

Note that I think you are doing "record linkage" which is a stepchild academic
of its own these days.  It might bear some research.  THere is also a CDC
matching program for text files freely downloadalbe to windows (ack), if you
hunt for it.

For now, my first thought is that you should try a few different matches, maybe
via PL/PGSQL functions, cascading the non-hits to the next step in the process
while shrinking your tables. upcase and delete all spaces, etc. First use
equality on all columns, which should be able to use indices, and separate those
records.  Then try equality on a few columns.  Then try some super fuzzy regexes
on a few columns.  Etc.

You will also have to give some thought to scoring a match, with perfection a
one, but, say, name and birthday the same with all else different a .75, etc.

Also, soundex(), levenshtein, and other fuzzy string tools are your friend.  I
want to write a version of SAS's COMPGED for Postgres, but I haven't got round
to it yet.

On Mar 10, 2011, at 3:48 PM, fork wrote:
[much thoughtfulness]

> Steve Atkins <steve <at> blighty.com> writes:
> [also much thoughtfulness]

Steve and fork -- thank you, this is super helpful. I meant to tweak
that exact search before sending this around, sorry if that was
confusing. That was meant to be a place holder for [some set of
matches that works]. And yes, "not converging" was incorrect, I did
mean "not finishing." But together from your answers it sounds pretty
clear that there's no particularly obvious easy solution that I'm
missing; this really is kind of tricky. This is a choice between
developing some in-house capacity for this and sending people to
various vendors so we'll probably lean on the vendors for now, at
least while we work on it. I've gotten my head partway around PL/PGSQL
functions, I may give that another try.

And you're right fork, Record Linkage is in fact an entire academic
discipline! I had no idea, this is fascinating and helpful:

http://en.wikipedia.org/wiki/Record_linkage

Thanks so much!

Dan

Dan Ancona <da <at> vizbang.com> writes:

>  his is a choice between
> developing some in-house capacity for this and sending people to
> various vendors so we'll probably lean on the vendors for now, at
> least while we work on it.

I would try to do the record matching in house and see how far you get, even if
you are talking to vendors concurrently.  You might get lucky, and you will
learn a lot about your data and how much to expect and pay for vendor solutions.

I would: Try building multi column indices on both tables for what you think are
the same rows, and match deterministically (if you have a key like social
security, then do this again on full names).  Examine your data to see what
hits, what misses, what hits multiple.  If you know there is a "good" and an
"iffy" table, you can use a left outer, otherwise you need a full outer.   Then
put all your leftovers from each into new tables, and try again with something
fuzzy.

If you build the indices and use "=" and it is still slow, ask again here --
that shouldn't happen.

> And you're right fork, Record Linkage is in fact an entire academic
> discipline!

Indeed.  Look for "blocking" and "editing" with your data first, I think.

I find this problem pretty interesting, so I would love to hear your results.  I
am right now matching building permits to assessor parcels....  I wish I was
using PG ...