Efficient way to perform approximated search

oracleoracle-11g-r2performance

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.

Best 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

Related Solutions

Why does the query cost change so much and how to prevent it

Most likely your tables have up-to-date statistics but sometimes the optimizer is baffled because it oversimplifies the cardinality estimation.

This seems to be a good candidate for dynamic sampling. In its default value (2 in 10g and 11g), dynamic sampling will only be used if one of the table has no statistics. In your case you would need to change its value to be able to let the optimizer collect statistics to build a better plan.

I suggest you use the DYNAMIC_SAMPLING hint that will let you modify the optimizer behaviour for a single query. I tested with a subquery and you need to use one of the following syntax:

the full hint directly on the top of the query, this will sample all tables, which will definitely work but may take too much time.
```
SELECT /*+ DYNAMIC_SAMPLING (10) */ FROM ...
```

the full hint on the subquery:

SELECT
  ... a lot of stuff ...
WHERE
  ... lots of complex clauses ...
  AND my_id in ( select /*+ DYNAMIC_SAMPLING (10) */ my_id 
                   from small_table 
                  where .. something simple ..)

the hint with a query block name:

SELECT /*+ DYNAMIC_SAMPLING (@my_block 10) */
  ... a lot of stuff ...
WHERE
  ... lots of complex clauses ...
  AND my_id in ( select /*+ QB_NAME(my_block) */ my_id 
                   from small_table 
                  where .. something simple ..)

The second and third option should produce the same result: sampling only on one table.

PostgreSQL – Slow MAX and MIN Query in View

Bound to query

If you can only change the view, not the query: this is 100 % equivalent using a correlated subquery instead of the LEFT JOIN:

CREATE VIEW the_view_new AS
SELECT a.id, a.name
    , (SELECT age_group FROM table_b WHERE id = a.id) AS age_group
FROM   table_a a;

Your query as is just reads top and bottom row from the index now, IOW blazingly fast. This is a workaround, gets more complicated with more columns and may exhibit weak spots with other queries.

Better query

Your query:

SELECT MIN("id") AS "min_id",MAX("id") AS "max_id" FROM "the_view" LIMIT 1;

Only needs table_a. In the view, table_b is joined with a LEFT JOIN. Obviously, the query planner does realize that table_b is not needed for the result of min() and max() after a LEFT JOIN (contrary to what I assumed at first). The query plan does not mention table_b.
It can also only return a single row, so LIMIT 1 is only complicating matters for the query planner further, to no effect. (Seems not to be the tipping point here.)
The obfuscation confuses the planner enough to read the whole 100 million rows from the index (rows=106434752), while it would only need to look up first and last row. That's a whole lot of pointless work.

This is simpler, cleaner and faster, while returning the same:

SELECT MIN(id) AS min_id, MAX(id) AS max_id FROM table_a;

As you can see in the EXPLAIN ANALYZE output of this SQL Fiddle with 100k rows in table_a:

Simple query

(actual time=0.010..0.010 rows=1 loops=1)

Your query:

(actual time=0.012..400.498 rows=100000 loops=1)

This looks like a weakness of the query planner in any case. We should repeat the test with pg 9.4 and possibly file a bug report ...

Bound to use the view

If you are bound to use the view (as commented), there is a workaround to convince the query planner (id must be NOT NULL - true in your case since PK):

SELECT (SELECT id AS min_id FROM the_view ORDER BY id ASC  LIMIT 1) AS min_id
     , (SELECT id AS max_id FROM the_view ORDER BY id DESC LIMIT 1) AS max_id;

Check the query plans in the fiddle: two times rows=1.

Aside: I suggest you take a look at the chapter Identifiers and Key Words in the manual.