Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Optimizing the SORT MERGE join of a MERGE statement

Consider the problem of applying changes to an aggregate table. Row that exist must be updated while new rows must be inserted. My approach was as follows:

  • Insert all changes in a temporary table (100K at a time)
  • MERGE the temporary table into the main table (eventually reaching 100s of millions rows)

The SQL (with a SORT MERGE hint) looks as follows (nothing fancy):

merge /*+ USE_MERGE(t s) */ 
into F_SCREEN_INSTANCE t
using F_SCREEN_INSTANCE_BUF s 
    on (s.DAY_ID = t.DAY_ID and s.PARTIAL_ID = t.PARTIAL_ID)
when matched then update set 
    t.ACTIVE_TIME_SUM = t.ACTIVE_TIME_SUM + s.ACTIVE_TIME_SUM,
    t.IDLE_TIME_SUM = t.IDLE_TIME_SUM + s.IDLE_TIME_SUM
when not matched then insert values (
    s.DAY_ID, s.PARTIAL_ID, s.ID, s.AGENT_USER_ID, s.COMPUTER_ID, s.RAW_APPLICATION_ID, s.APP_USER_ID, s.APPLICATION_ID, s.USER_ID, s.RAW_MODULE_ID, s.MODULE_ID, s.START_TIME, s.RAW_SCREEN_NAME, s.SCREEN_ID, s.SCREEN_TYPE, s.ACTIVE_TIME_SUM, s.IDLE_TIME_SUM)

The F_SCREEN_INSTANCE table has (DAY_ID, PARTIAL_ID) as a primary key and also is IOT (index organized table). This makes it an ideal candidate for a merge join: the rows are physically sorted by the lookup key.

So far so good. I've started a benchmark and the initial times looked good, 10s for one merge. But after about an hour, the merges were taking about 4 min with heavy tempdb usage (4GB per merge). The query plan below shows that F_SCREEN_INSTANCE is re-sorted before the merge, even though the table is ideally sorted already. And of course, as the table grows even more tempdb will be needed and the whole approach falls apart.

Sort Merge Join

OK, so why re-sort the table? It turns to be a limitation of the merge join implementation: the second table is always sorted.

If an index exists, then the database can avoid sorting the first data set. However, the database always sorts the second data set, regardless of indexes.

O...K, so then can I make the main table to be first and the buffer to be second? Nope, that's not possible either. No matter how I list the tables in the USE_MERGE hint, the source table is always first.

Finally, here is my question: Have I missed anything? Is it possible to make this SORT MERGE approach work?

Here are some more details addressing questions you might ask:

  • What Oracle version? 12c.
  • Have you tried HASH JOIN? Yes, it's bad, as expected. The main table needs to be scanned in order to build the hash table. It can't scale as F_SCREEN_INSTANCE grows.
  • Have you tried LOOP JOIN? Yes, it's also bad. Considering the size of the buffer table, 100K lookups into F_SCREEN_INSTANCE take unreasonably long. Merges took about 3 min very quickly.
  • All in all, the MERGE JOIN is conceptually the best access strategy, but the Oracle implementation seems to be severely crippled by re-sorting the target table.
like image 274
Bogdan Calmac Avatar asked Feb 28 '14 23:02

Bogdan Calmac


People also ask

Is Merge Join faster than hash join?

Merge join is used when projections of the joined tables are sorted on the join columns. Merge joins are faster and uses less memory than hash joins.

What is sort-merge join in Oracle?

In a SORT-MERGE join, Oracle sorts the first row source by its join columns, sorts the second row source by its join columns, and then merges the sorted row sources together. As matches are found, they are put into the result set.

What is the difference between merge and Merge Join in SSIS?

While Merge transformation is used to combine rows (such as UNION operation), SSIS Merge Join transformation is used to combine columns between different rows (such as SQL Joins).


1 Answers

Sort merge outer joins will always put the outer-joined table second regardless of the hints. Adding an extra inner-join allows control of the join order, and then ROWID can be used to join again to the large table. Hopefully two good joins will work better than one bad join.

Assumptions

This answer assumes that the sort merge join is the fastest join, and that the manual is correct that the second data set is always sorted. It would be difficult to test these assumptions without significantly more information about the data.

Sample Schema

Here are some similar tables, with fake statistics to make the optimizer think they have 500M rows and 100K rows.

create table F_SCREEN_INSTANCE(DAY_ID number, PARTIAL_ID number, ID number, AGENT_USER_ID number,COMPUTER_ID number, RAW_APPLICATION_ID number, APP_USER_ID number, APPLICATION_ID number, USER_ID number, RAW_MODULE_ID number,MODULE_ID number, START_TIME date, RAW_SCREEN_NAME varchar2(100), SCREEN_ID number, SCREEN_TYPE number, ACTIVE_TIME_SUM number, IDLE_TIME_SUM number,
    constraint f_screen_instance_pk primary key (day_id, partial_id)
) organization index;

create table F_SCREEN_INSTANCE_BUF(DAY_ID number, PARTIAL_ID number, ID number, AGENT_USER_ID number,COMPUTER_ID number, RAW_APPLICATION_ID number, APP_USER_ID number,APPLICATION_ID number, USER_ID number, RAW_MODULE_ID number, MODULE_ID number, START_TIME date, RAW_SCREEN_NAME varchar2(100), SCREEN_ID number, SCREEN_TYPE number, ACTIVE_TIME_SUM number, IDLE_TIME_SUM number,
    constraint f_screen_instance_buf_pk primary key (day_id, partial_id)
);

begin
    dbms_stats.set_table_stats(user, 'F_SCREEN_INSTANCE', numrows => 500000000);
    dbms_stats.set_table_stats(user, 'F_SCREEN_INSTANCE_BUF', numrows => 100000);
end;
/

The Problem

The desired join and join order can be achieved with the LEADING hint when an inner join is used. The smaller table, F_SCREEN_INSTANCE_BUF, is the second table.

explain plan for
select /*+ use_merge(t s) leading(t s) */ *
from f_screen_instance_buf s
join f_screen_instance t
    on (s.DAY_ID = t.DAY_ID and s.PARTIAL_ID = t.PARTIAL_ID);

select * from table(dbms_xplan.display(format => '-predicate'));

Plan hash value: 563239985

-----------------------------------------------------------------------------------------------------
| Id  | Operation           | Name                  | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |                       |   100K|    19M|       |  6898  (66)| 00:00:01 |
|   1 |  MERGE JOIN         |                       |   100K|    19M|       |  6898  (66)| 00:00:01 |
|   2 |   INDEX FULL SCAN   | F_SCREEN_INSTANCE_PK  |   500M|    46G|       |  4504 (100)| 00:00:01 |
|   3 |   SORT JOIN         |                       |   100K|  9765K|    26M|  2393   (1)| 00:00:01 |
|   4 |    TABLE ACCESS FULL| F_SCREEN_INSTANCE_BUF |   100K|  9765K|       |    34   (6)| 00:00:01 |
-----------------------------------------------------------------------------------------------------

The LEADING hint does not work when changing to a left join.

explain plan for
select /*+ use_merge(t s) leading(t s) */ *
from f_screen_instance_buf s
left join f_screen_instance t
    on (s.DAY_ID = t.DAY_ID and s.PARTIAL_ID = t.PARTIAL_ID);

select * from table(dbms_xplan.display(format => '-predicate'));

Plan hash value: 1472690071

-----------------------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name                     | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                          |   100K|    19M|       |    16M  (1)| 00:10:34 |
|   1 |  MERGE JOIN OUTER            |                          |   100K|    19M|       |    16M  (1)| 00:10:34 |
|   2 |   TABLE ACCESS BY INDEX ROWID| F_SCREEN_INSTANCE_BUF    |   100K|  9765K|       |   826   (0)| 00:00:01 |
|   3 |    INDEX FULL SCAN           | F_SCREEN_INSTANCE_BUF_PK |   100K|       |       |    26   (0)| 00:00:01 |
|   4 |   SORT JOIN                  |                          |   500M|    46G|   131G|    16M  (1)| 00:10:34 |
|   5 |    INDEX FAST FULL SCAN      | F_SCREEN_INSTANCE_PK     |   500M|    46G|       |  2703 (100)| 00:00:01 |
-----------------------------------------------------------------------------------------------------------------

This limitation is not documented as far as I can tell. I tried using the +outline setting of DBMS_XPLAN to see the full set of hints and then changed them around. But nothing I did could make the join order change for the LEFT JOIN version. Perhaps someone else can get this to work.

select * from table(dbms_xplan.display(format => '-predicate +outline'));

... 
Outline Data
-------------

  /*+
      BEGIN_OUTLINE_DATA
      USE_MERGE(@"SEL$0E991E55" "T"@"SEL$1")
      LEADING(@"SEL$0E991E55" "S"@"SEL$1" "T"@"SEL$1")
      INDEX_FFS(@"SEL$0E991E55" "T"@"SEL$1" ("F_SCREEN_INSTANCE"."DAY_ID" "F_SCREEN_INSTANCE"."PARTIAL_ID"))
      INDEX(@"SEL$0E991E55" "S"@"SEL$1" ("F_SCREEN_INSTANCE_BUF"."DAY_ID" 
              "F_SCREEN_INSTANCE_BUF"."PARTIAL_ID"))
      OUTLINE(@"SEL$9EC647DD")
      OUTLINE(@"SEL$2")
      MERGE(@"SEL$9EC647DD")
      OUTLINE_LEAF(@"SEL$0E991E55")
      ALL_ROWS
      DB_VERSION('12.1.0.1')
      OPTIMIZER_FEATURES_ENABLE('12.1.0.1')
      IGNORE_OPTIM_EMBEDDED_HINTS
      END_OUTLINE_DATA
  */

Possible Solution

--#3: Join the large table to the smaller result set.  This uses the largest table twice,
--but the plan can use the ROWID for a very quick join.
explain plan for
merge into F_SCREEN_INSTANCE t
using
(
    --#2: Now get the missing rows with an outer join.  Since the _BUF table is
    --small I assume it does not make a big difference exactly how it it joind
    --to the 100K result set.
    --The hints NO_MERGE and NO_PUSH_PRED are required to keep the INNER_JOIN
    --inline view intact.
    select /*+ no_merge(inner_join) no_push_pred(inner_join) */ inner_join.*
    from f_screen_instance_buf s
    left join
    (
        --#1: Get 100K rows efficiently with an inner join.
        --Note that the ROWID is retrieved here.
        select /*+ use_merge(t s) leading(t s) */ s.*, s.rowid s_rowid
        from f_screen_instance_buf s
        join f_screen_instance t
            on (s.DAY_ID = t.DAY_ID and s.PARTIAL_ID = t.PARTIAL_ID)
    ) inner_join
        on (s.DAY_ID = inner_join.DAY_ID and s.PARTIAL_ID = inner_join.PARTIAL_ID)
) s
    on (s.s_rowid = t.rowid)
when matched then update set 
    t.ACTIVE_TIME_SUM = t.ACTIVE_TIME_SUM + s.ACTIVE_TIME_SUM,
    t.IDLE_TIME_SUM = t.IDLE_TIME_SUM + s.IDLE_TIME_SUM
when not matched then insert values (
    s.DAY_ID, s.PARTIAL_ID, s.ID, s.AGENT_USER_ID, s.COMPUTER_ID, s.RAW_APPLICATION_ID, s.APP_USER_ID, s.APPLICATION_ID, s.USER_ID, s.RAW_MODULE_ID, s.MODULE_ID, s.START_TIME, s.RAW_SCREEN_NAME, s.SCREEN_ID, s.SCREEN_TYPE, s.ACTIVE_TIME_SUM, s.IDLE_TIME_SUM);

It ain't pretty, but at least it generates a plan with the large table first in the sort merge join.

select * from table(dbms_xplan.display);

Plan hash value: 1086560566

-------------------------------------------------------------------------------------------------------------
| Id  | Operation                | Name                     | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------------------------
|   0 | MERGE STATEMENT          |                          |   500G|   173T|       |  5355K (43)| 00:03:30 |
|   1 |  MERGE                   | F_SCREEN_INSTANCE        |       |       |       |            |          |
|   2 |   VIEW                   |                          |       |       |       |            |          |
|*  3 |    HASH JOIN OUTER       |                          |   500G|   179T|    29M|  5355K (43)| 00:03:30 |
|*  4 |     HASH JOIN OUTER      |                          |   100K|    28M|  3712K|  8663  (53)| 00:00:01 |
|   5 |      INDEX FAST FULL SCAN| F_SCREEN_INSTANCE_BUF_PK |   100K|  2539K|       |     9   (0)| 00:00:01 |
|   6 |      VIEW                |                          |   100K|    25M|       |  6898  (66)| 00:00:01 |
|   7 |       MERGE JOIN         |                          |   100K|    12M|       |  6898  (66)| 00:00:01 |
|   8 |        INDEX FULL SCAN   | F_SCREEN_INSTANCE_PK     |   500M|    12G|       |  4504 (100)| 00:00:01 |
|*  9 |        SORT JOIN         |                          |   100K|  9765K|    26M|  2393   (1)| 00:00:01 |
|  10 |         TABLE ACCESS FULL| F_SCREEN_INSTANCE_BUF    |   100K|  9765K|       |    34   (6)| 00:00:01 |
|  11 |     INDEX FAST FULL SCAN | F_SCREEN_INSTANCE_PK     |   500M|    46G|       |  2703 (100)| 00:00:01 |
-------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   3 - access("INNER_JOIN"."S_ROWID"=("T".ROWID(+)))
   4 - access("S"."PARTIAL_ID"="INNER_JOIN"."PARTIAL_ID"(+) AND 
              "S"."DAY_ID"="INNER_JOIN"."DAY_ID"(+))
   9 - access("S"."DAY_ID"="T"."DAY_ID" AND "S"."PARTIAL_ID"="T"."PARTIAL_ID")
       filter("S"."PARTIAL_ID"="T"."PARTIAL_ID" AND "S"."DAY_ID"="T"."DAY_ID")
like image 197
Jon Heller Avatar answered Nov 15 '22 05:11

Jon Heller