# Efficient way to perform approximated search?

I have to perform a join between `table_a` and `table_b`, using three fields as key being one of them the date of the event, say, both tables have `id1`, `id2` and `evnt_time` for eache record.

As it happens though, the `evnt_time` can be displaced in a few seconds between these tables. Thus the join has to behave sort of `table_a.id1 = table_b.id1 and table_a.id2 = table_b.id2 and table_a.evnt_time ~ table_b.evnt_time`, where:

• `~` means approximately, given `+` or `-` seconds
• There must be a way to give `~` parameters of how precise should be. e.g.: `table_a.evnt_time ~(2) table_b.evnt_time` will join `table_a.evnt_time` with `table_b.evnt_time - 2s`, `table_b.evnt_time - 1s`, `table_b.evnt_time`, `table_b.evnt_time + 1s` and `table_b.evnt_time + 2s`.

To tackle the situation, there are a few possibilities I am experimenting, but my doubt is on which architecture should I use to perform a very efficient "approximated join" - these tables are partitioned, sub-partitioned and each sub part may contain billions of records... (although I have a reasonable amount of resources).

For once, I thought of storing the unique sencond of the event (i.e. second it happened since julian calendar) on both sides so the real join (give a "`~(2)`") could simply look like:

``````select *
from
table_a,
table_b
where
table_a.id1 = table_b.id1
and table_a.id2 = table_b.id2
and (table_a.evnt_sec = table_b.evnt_sec
or table_a.evnt_sec = table_b.evnt_sec + 1
or table_a.evnt_sec = table_b.evnt_sec + 2
or table_a.evnt_sec = table_b.evnt_sec - 1
or table_a.evnt_sec = table_b.evnt_sec - 2)
``````

But I am unsure of how efficiently would that perform with the indexes and scans..

This is just an example, I am not stuck to any sort of architecture. Also, I am using Oracle 11gR2.

• What's the cardinality of the evnt_sec column? How many evnt_sec per (id1,id2)? What indexes are already in place? Is such an approximate match likely to cause multiple rows returned because of its approximateness (not that it's a word :P )? (IE: Is the data per id1,id2 close together, as defined by evnt_sec?) – Philᵀᴹ Apr 25 '13 at 19:33
• I am working on a few test records at the moment so couldn't really tell, but as soon as I have a more real bulk of data, I'll make sure update this info. – filippo Apr 25 '13 at 19:41
• On what columns are the tables partitioned? – David Aldridge Apr 26 '13 at 6:54
• Floor the date to the nearest 5 seconds (or what ever jitter you want) and performe regular join. – haki Apr 26 '13 at 8:53
• @haki: no, that will not work. If the event time is 00:0:05 and 00:00:06 a join will happen because both times are truncated to 00:00:05. If the times are 00:00:04 and 00:00:05 than the first is truncated to 00:00:00 and no join will happen. This does not make sense because for both pairs the difference in time is the same, just 1 second. So in both situations a join should happen. – miracle173 Mar 23 '14 at 2:54

## 1 Answer

I think that what you need to use is a Nonequi join

``````select *
from
table_a,
table_b
where
table_a.id1 = table_b.id1
and table_a.id2 = table_b.id2
and table_a.evnt_sec BETWEEN table_b.evnt_sec -2 and table_b.evnt_sec +2
``````
• what about using the ANSI INNER JOIN syntax instead? – KookieMonster Apr 26 '13 at 15:38
• @KookieMonster ANSI INNER JOIN syntax is not very popular in the Oracle user community. Maybe because it is seldom used in examples in the Oracle manuals. – miracle173 Mar 23 '14 at 3:05