# Comparing client lists with Cross Joins

I've written a query to compare the clients in our database with the people in a list that I've received. It needs to check if anyone from the list is one of our clients. I've created a temporary table which has been filled with the names and the query below makes a cross-join with the two tables. That query works very slowly (two very large tables), so I was wondering if there's any way to speed this up. Would it be faster to just join everything in the database and compare strings in code (java or something similar)?

(The second list was just names, so I can't use any indexed columns in our database.)

select C.NUMCLI, C.NAAM, T.FULLNAME, (UTL_MATCH.EDIT_DISTANCE_SIMILARITY(NAAM, FULLNAME))
as DIFF from (select LASTNAME ||' '|| FIRSTNAME ||' '|| MIDDLENAME  as FULLNAME from
TMP_CONTROL) T, (select NUMCLI, NOMCLI ||' '|| PRNCLI as NAAM from CLIENT
where CODLAN = 3 and STAANN <> 'D') C
where (UTL_MATCH.EDIT_DISTANCE_SIMILARITY(NAAM, FULLNAME)) >= 60


NOTE: A large portion of people on the list may have their name written in a slightly different manner, which is why I'm using the EDIT_DISTANCE SIMILARITY >= 60. The goal is just to filter out the large differences, so I can easily compare the smaller ones.

## Update

This is the explain-plan for the query:

SQL> SET LINESIZE 130
SQL> SET PAGESIZE 0
SQL> SELECT *
2 FROM TABLE(DBMS_XPLAN.DISPLAY);
Plan hash value: 1462516232

---------------------------------------------------------------------------------
| Id  | Operation          | Name       | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |            |    74M|  3041M|  2197K  (3)| 07:19:29 |
|   1 |  NESTED LOOPS      |            |    74M|  3041M|  2197K  (3)| 07:19:29 |
|*  2 |   TABLE ACCESS FULL| CLIENT     | 71843 |  2174K|  2386   (2)| 00:00:29 |
|*  3 |   TABLE ACCESS FULL| TMP_CONTROL|  1033 | 12396 |    31   (4)| 00:00:01 |
---------------------------------------------------------------------------------


## Predicate Information (identified by operation id):

2 - filter("STAANN"<>'D' AND TO_NUMBER("CODLAN")=3)
3 - filter("UTL_MATCH"."EDIT_DISTANCE_SIMILARITY"("NOMCLI"||'
'||"PRNCLI","LASTNAME"||' '||"FIRSTNAME"||' '||"MIDDLENAME")>=60)


17 rows selected.

• Rolled back the change you made in Rev 3. (Please don't edit questions in a way that invalidates answers.) – 200_success Mar 11 '14 at 22:27

Notes:

1. ... have you done an explain-plan to figure out which option it has taken? I suggested this in the first answer... have you done it?
2. If the explain plan shows that the code is producing a temp-table for the name-concat of the TMP_CONTROL data, and that it does a nested-loop scan of the CLIENT -> temp-table to calculate the Edit Distance - then there is nothing you can do that will be faster.
3. If you really, really can't create the tables manually, then it is likely that the best result you will be able to achieve will be to externalize the data and process it outside the database.

But, this is hard work, and, to match the DB performance, you will need a decent machine (lots of memory), and be willing to process the data in parallel, etc.

You suggested this before, using Java.

The basic algorithm I would use in Java (Java7) is as follows:

• Create a JDBC session to the database.
• Select the string-concatenation of the names from the TMP_CONTROL table.
• save these values in to an ArrayList<String> (or, if you do not have enough memory, to a file on disk - one name per line)
• Create an ExecutorService with about as many threads as you have 'logical' CPUs (Executors.newFixed...).
• Set up an ExecutorCompletionService to handle results...
• Select the ID and the string-concatenation of the names from the CLIENT table. Save each record in to a new CLient class. This Client class will look something like:
    public class Client implements Callable<Client> {
private final int id;
private final String fullname;
private final Map<String, Integer> matches = new HashMap<>();

// constructor

// getters for ID and fullname

public void addMatch(String naam, int score) {
matches.put(naam, score);
}

public Client call() {
// Loop over each of the TMP names we stored earlier...
for (String othername : tempnames) {
// calculate the EditDistance from our name.
// if it is > 60, do:
if (editdistance > threshold) {
}
}
return this;
}
}


That's about how I would do it in Java.....

• If I'm reading my explain plan correctly, it's using a nested loop C->T (added it to my main post). Since I'm running this on a production server, I have to make sure the query uses minimal resources (also, there's software that uses our database that is very sensitive to changes on the DB - I'm not allowed to add extra indexes to the db, etc...) – Andreas Mar 13 '14 at 9:03
• @Andreas Alright, it is not using any temp space, which means it has to re-calculate the name-concatenation of the TMP_CONTACT 74K times more than it should. You TMP_CONTACT table is much smaller than I expected.... you should alter the table, add a FULLNAME column, and pre-compute the concatenation.... really. 74M rows is not that large either.... are your statistics up to date? Why don't you join the CodeReview Chat room... the 2nd Monitor – rolfl Mar 13 '14 at 13:30
• that's because I limited the resultset for the tmp_control subquery for tests. that table normally contains 20.100 rows (not that much compared to the 170.000 rows from my client table, but when you cross join both). I did a few optimizations in my queries and they seem to be a bit faster already (by removing subqueries and adding stuff to the main query) – Andreas Mar 13 '14 at 13:39
• Solved on 2nd Monitor: Exported the data in a different DB where I could get full control. – Andreas Mar 13 '14 at 14:04

Fundamentally, at some point, you have to do a cross-join to calculate your results. Performance will be a problem... but there are things that can be done.

First though, why the ugly SQL? Formatting SQL to make it readable is not hard to do:

select C.NUMCLI,
C.NAAM,
T.FULLNAME,
(UTL_MATCH.EDIT_DISTANCE_SIMILARITY(NAAM, FULLNAME)) as DIFF
from (
select LASTNAME ||' '|| FIRSTNAME ||' '|| MIDDLENAME  as FULLNAME
from TMP_CONTROL
) T,
(
select NUMCLI,
NOMCLI ||' '|| PRNCLI as NAAM
from CLIENT
where CODLAN = 3
and STAANN <> 'D'
) C
where (UTL_MATCH.EDIT_DISTANCE_SIMILARITY(NAAM, FULLNAME)) >= 60


We can see a few things in here.....

• Your source data contains a middle-name but your main table does not. Are you sure you want to be joining them this way? Will it create the correct results?

Now, about those performance improving options....

Let's assume that the best way to solve this problem is to do a cross-product of the two tables. Compare each value in table a with all values in table b. Oracle ha a few options for doing this. I will list them in what I consider to be a worst-to-best order:

• true cross-product - It can do a true Cartesian product of the data - build an in-memory join of each value in the temp table joined to each value in the primary table, and then scan the results once, calculating the edit distance, and then discarding those results which are < 60. It can either calculate the string concatenation of the names before or after the Cartesian product, either option will be (very) slow.
• nested-loop T->C - It can loop through each temp table value, and for each of them, it can do the name-concatenation, and then it will need to join to the primary table (with the conditions), do the name-concatenation, and discard bad edit-distances.
• nested-loop C->T - It can loop through each value in the primary table, check the conditions, and for each successful value, it can do the String-concatenation, it can scan all values in the temp table, compute the name-concatenation, and then calculate the edit distance, and discard the bad results.
• nested-loop C'->T' or T'->C' - It can produce a temporary, or in-memory version of the pre-filtered C table and name-concatenated T and C tables, and then do a nested-loop of these two in-memory tables, discarding bad edit distances.

Your SQL is written to suggest you want it to do the last option, create two in-memory data sets, each of them pre-computed to contain just the name-concatenated values, and then you only perform the cross-product on these tables.... but, just because you wrote the SQL that way does not mean that Oracle will do the process that way....

... have you done an explain-plan to figure out which option it has taken?

My guess is that it has chosen nested-loop T->C, with a second possibility of nested-loop C->T. The reasons?

1. the temp table probably does not have statistics up to date, and is not indexed at all
2. the primary table probably has some indexes on CODLAN and/or STAAN
3. when Oracle optimizes the query, it will likely decide the temp-space required to store all the name-concatenated values will require too much memory, or even physical IO

Now, we want/need Oracle to choose the most efficient cross-join mechanism... and we do not want it calculating the name-concatenation on the fly because it will need to repeat that many times for at least one side of the cross-product.

The solution is to force Oracle's plan to do what we want, and the way to do that is to pre-compute the data needed for the cross-product.

Your temp table should already have the pre-computed name-concatenated values... why are you having to do the name-concatenation as part of the query? Call this column FULLNAME

Then, create a second table as:

create table TMP_CLIENTNAME (
NUMCLI INTEGER NOT NULL,
NAAM NVARCHAR(255) NOT NULL)
)

insert into TMP_CLIENTNAME
select NUMCLI,
NOMCLI ||' '|| PRNCLI as NAAM
from CLIENT
where CODLAN = 3
and STAANN <> 'D'


select C.NUMCLI,
C.NAAM,
T.FULLNAME,
(UTL_MATCH.EDIT_DISTANCE_SIMILARITY(NAAM, FULLNAME)) as DIFF
from TMP_CONTROL T,
TMP_CLIENTNAME C
where (UTL_MATCH.EDIT_DISTANCE_SIMILARITY(NAAM, FULLNAME)) >= 60


This query forces Oracle not to do any calculations other than the edit-distance in the join. This will make a difference....

The down-side is that you need additional storage for the data.

Once you have your data in this format you can consider some other options.... (which will likely affect the results of the edit-distance calculations)

• index the first letter of each name, and only calculate the edit distances where the first letters are the same.
• only calculate the edit distance when the length of the two names are less than say 5 characters different.
• .....
• 1) A number of clients have a middlename added to their firstname, and not all people on the list have a middlename. 2) We're normally not allowed to make temporary tables (I had to get permission to add a table to the DB), so I'd rather not add more. 3) Would it be better if I loaded the data in another program? (just combine the data in oracle, then do the similarity search in java/C++/...) ? – Andreas Mar 11 '14 at 14:14
• Somewhat related to your last question : blog.jooq.org/2014/03/10/… – Josay Mar 11 '14 at 22:39
• @Andreas you can probably create temporary tables... and populate/use those – rolfl Mar 11 '14 at 22:51
• @Josay not using hibernate (just jdbc), so no. – Andreas Mar 12 '14 at 8:17
• @rolfl Not allowed to create temporary tables & given the size of the resulting table, it's probably not a good idea (I need to run the query on our production DB). (Would be a good idea in other circumstances, so +1 for that) – Andreas Mar 12 '14 at 8:19