Oracle Scratchpad

April 15, 2015

Cartesian join

Filed under: Oracle,Performance,Tuning — Jonathan Lewis @ 6:40 pm GMT Apr 15,2015

Some time ago I pulled off the apocryphal “from 2 hours to 10 seconds” trick for a client using a technique that is conceptually very simple but, like my example from last week, falls outside the pattern of generic SQL. The problem (with some camouflage) is as follows: we have a data set with 8 “type” attributes which are all mandatory columns. We have a “types” table with the same 8 columns together with two more columns that are used to translate a combination of attributes into a specific category and “level of relevance”. The “type” columns in the types table are, however, allowed to be null although each row must have at least one column that is not null – i.e. there is no row where every “type” column is null.

The task is to match each row in the big data set with all “sufficiently similar” rows in the types table and then pick the most appropriate of the matches – i.e. the match with the largest “level of relevance”. The data table had 500,000 rows in it, the types table has 900 rows. Here’s a very small data set representing the problem client data (cut down from 8 type columns to just 4 type columns):


create table big_table(
	id		number(10,0)	primary key,
	v1		varchar2(30),
	att1		number(6,0),
	att2		number(6,0),
	att3		number(6,0),
	att4		number(6,0),
	padding		varchar2(4000)
);

create table types(
	att1		number(6,0),
	att2		number(6,0),
	att3		number(6,0),
	att4		number(6,0),
	category	varchar2(12)	not null,
	relevance	number(4,0)	not null
);

insert into big_table values(1, 'asdfllkj', 1, 1, 2, 1, rpad('x',4000));
insert into big_table values(2, 'rirweute', 1, 3, 1, 4, rpad('x',4000));

insert into types values(   1, null, null, null, 'XX',  10);
insert into types values(   1, null, null,    1, 'YY',  20);
insert into types values(   1, null,    1, null, 'ZZ',  20);

commit;

A row from the types table is similar to a source row if it matches on all the non-null columns. So if we look at the first row in big_table, it matches the first row in types because att1 = 1 and all the other attN columns are null; it matches the second row because att1 = 1 and att4 = 1 and the other attN columns are null, but it doesn’t match the third row because types.att3 = 1 and big_table.att3 = 2.

Similarly, if we look at the second row in big_table, it matches the first row in types, doesn’t match the second row because types.att4 = 1 and big_table.att4 = 4, but does match the third row. Here’s how we can express the matching requirement in SQL:


select
	bt.id, bt.v1,
	ty.category,
	ty.relevance
from
	big_table	bt,
	types		ty
where
	nvl(ty.att1(+), bt.att1) = bt.att1
and	nvl(ty.att2(+), bt.att2) = bt.att2
and	nvl(ty.att3(+), bt.att3) = bt.att3
and	nvl(ty.att4(+), bt.att4) = bt.att4
;

You’ll realise, of course, that essentially we have to do a Cartesian merge join between the two tables. Since there’s no guaranteed matching column that we could use to join the two tables we have to look at every row in types for every row in big_table … and we have 500,000 rows in big_table and 900 in types, leading to an intermediate workload of 450,000,000 rows (with, in the client case, 8 checks for each of those rows). Runtime for the client was about 2 hours, at 100% CPU.

When you have to do a Cartesian merge join there doesn’t seem to be much scope for reducing the workload, however I didn’t actually know what the data really looked like so I ran a couple of queries to analyse it . The first was a simple “select count (distinct)” query to see how many different combinations of the 8 attributes existed in the client’s data set. It turned out to be slightly less than 400.

Problem solved – get a list of the distinct combinations, join that to the types table to translate to categories, then join the intermediate result set back to the original table. This, of course, is just applying two principles that I’ve discussed before: (a) be selective about using a table twice to reduce the workload, (b) aggregate early if you can reduce the scale of the problem.

Here’s my solution:


with main_data as (
	select
		/*+ materialize */
		id, v1, att1, att2, att3, att4
	from
		big_table
),
distinct_data as (
	select
		/*+ materialize */
		distinct att1, att2, att3, att4
	from	main_data
)
select
	md.id, md.v1, ty.category, ty.relevance
from
	distinct_data	dd,
	types		ty,
	main_data	md
where
	nvl(ty.att1(+), dd.att1) = dd.att1
and	nvl(ty.att2(+), dd.att2) = dd.att2
and	nvl(ty.att3(+), dd.att3) = dd.att3
and	nvl(ty.att4(+), dd.att4) = dd.att4
and	md.att1 = dd.att1
and	md.att2 = dd.att2
and	md.att3 = dd.att3
and	md.att4 = dd.att4
;

And here’s the execution plan.


---------------------------------------------------------------------------------------------------------
| Id  | Operation                  | Name                       | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT           |                            |    12 |  2484 |    11  (10)| 00:00:01 |
|   1 |  TEMP TABLE TRANSFORMATION |                            |       |       |            |          |
|   2 |   LOAD AS SELECT           | SYS_TEMP_0FD9D6619_8FE93F1 |       |       |            |          |
|   3 |    TABLE ACCESS FULL       | BIG_TABLE                  |     2 |   164 |     2   (0)| 00:00:01 |
|   4 |   LOAD AS SELECT           | SYS_TEMP_0FD9D661A_8FE93F1 |       |       |            |          |
|   5 |    HASH UNIQUE             |                            |     2 |   104 |     3  (34)| 00:00:01 |
|   6 |     VIEW                   |                            |     2 |   104 |     2   (0)| 00:00:01 |
|   7 |      TABLE ACCESS FULL     | SYS_TEMP_0FD9D6619_8FE93F1 |     2 |   164 |     2   (0)| 00:00:01 |
|*  8 |   HASH JOIN                |                            |    12 |  2484 |     6   (0)| 00:00:01 |
|   9 |    NESTED LOOPS OUTER      |                            |     6 |   750 |     4   (0)| 00:00:01 |
|  10 |     VIEW                   |                            |     2 |   104 |     2   (0)| 00:00:01 |
|  11 |      TABLE ACCESS FULL     | SYS_TEMP_0FD9D661A_8FE93F1 |     2 |   104 |     2   (0)| 00:00:01 |
|* 12 |     TABLE ACCESS FULL      | TYPES                      |     3 |   219 |     1   (0)| 00:00:01 |
|  13 |    VIEW                    |                            |     2 |   164 |     2   (0)| 00:00:01 |
|  14 |     TABLE ACCESS FULL      | SYS_TEMP_0FD9D6619_8FE93F1 |     2 |   164 |     2   (0)| 00:00:01 |
---------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   8 - access("MD"."ATT1"="DD"."ATT1" AND "MD"."ATT2"="DD"."ATT2" AND
              "MD"."ATT3"="DD"."ATT3" AND "MD"."ATT4"="DD"."ATT4")
  12 - filter("DD"."ATT1"=NVL("TY"."ATT1"(+),"DD"."ATT1") AND
              "DD"."ATT2"=NVL("TY"."ATT2"(+),"DD"."ATT2") AND
              "DD"."ATT3"=NVL("TY"."ATT3"(+),"DD"."ATT3") AND
              "DD"."ATT4"=NVL("TY"."ATT4"(+),"DD"."ATT4"))

Critically I’ve taken a Cartesian join that had a source of 500,000 and a target of 900 possible matches, and reduced it to a join between the 400 distinct combinations and the 900 possible matches. Clearly we can expect this to to take something like one twelve-hundredth (400/500,000) of the work of the original join – bringing 7,200 seconds down to roughly 6 seconds. Once this step is complete we have an intermediate result set which is the 4 non-null type columns combined with the matching category and relevance columns – and can use this in a simple and efficient hash join with the original data set.

Logic dictated that the old and new results would be the same – but we did run the two hour query to check that the results matched.

Footnote: I was a little surprised that the optimizer produced a nested loops outer join rather than a Cartesian merge in the plan above – but that’s probably an arterfact of the very small data sizes in my test.There’s presumably little point in transferring the data into the PGA when the volume is so small.

Footnote 2: I haven’t included the extra steps in the SQL to eliminate the reduce the intermediate result to just “the most relevant” – but that’s just an inline view with an analytic function. (The original code actually selected the data with an order by clause and used a client-side filter to eliminate the excess!).

Footnote 3: The application was a multi-company application – and one of the other companies had not yet gone live on the system because they had a data set of 5 million rows to process and this query had never managed to run to completion in the available time window.  I’ll have to get back to the client some day and see if the larger data set also collapsed to a very small number of distinct combinations and how long the rewrite took with that data set.

 

7 Comments »

  1. It’s really good idea, perhaps I one question/query. Do we get benefited if we have any index on types (composite index probably with bitmap or binary or combined index with all types columns one column from big table). Just from optimizer perspective, how does it’s changes the plan.

    Comment by Pavan Kumar Kumar N — April 15, 2015 @ 7:18 pm GMT Apr 15,2015 | Reply

    • The benefit you could get from a suitable index depends entirely on the data patterns. In this example category and relevance were declared not null, so if we had an index (att1, att2, att3, att4, category, relevance) then it ought to be possible for the optimizer (depending on version) to find an execution path that did a nested loop with concatenation into the types table with an index-only access. I haven’t got this working with my dataset, but here’s an example moving in the right direction – using ANSI syntax, and 12.1.0.2:

      create index types_i1 on types(att1, att2, relevance);
      
      select
              bt.att1, bt.att2, bt.att3, bt.att4,
              bt.id, bt.v1,
              ty.category,
              ty.relevance
      from
              big_table       bt
      left join
              types           ty
      on
              (ty.att1 = bt.att1 or ty.att1 is null)
      and     (ty.att2 = bt.att2 or ty.att2 is null)
      and     (ty.att3 = bt.att3 or ty.att3 is null)
      and     (ty.att4 = bt.att4 or ty.att4 is null)
      ;
      
      
      Execution Plan
      ----------------------------------------------------------------------------------------------------------
      | Id  | Operation                              | Name            | Rows  | Bytes | Cost (%CPU)| Time     |
      ----------------------------------------------------------------------------------------------------------
      |   0 | SELECT STATEMENT                       |                 |     4 |   412 |    43   (0)| 00:00:01 |
      |   1 |  NESTED LOOPS OUTER                    |                 |     4 |   412 |    43   (0)| 00:00:01 |
      |   2 |   TABLE ACCESS FULL                    | BIG_TABLE       |     2 |   164 |    35   (0)| 00:00:01 |
      |   3 |   VIEW                                 | VW_LAT_3D36DCD2 |     2 |    42 |     4   (0)| 00:00:01 |
      |   4 |    CONCATENATION                       |                 |       |       |            |          |
      |*  5 |     TABLE ACCESS BY INDEX ROWID BATCHED| TYPES           |     1 |    73 |     2   (0)| 00:00:01 |
      |*  6 |      INDEX RANGE SCAN                  | TYPES_I1        |    41 |       |     1   (0)| 00:00:01 |
      |*  7 |     TABLE ACCESS BY INDEX ROWID BATCHED| TYPES           |     1 |    73 |     2   (0)| 00:00:01 |
      |*  8 |      INDEX RANGE SCAN                  | TYPES_I1        |   506 |       |     1   (0)| 00:00:01 |
      ----------------------------------------------------------------------------------------------------------
      
      Predicate Information (identified by operation id):
      ---------------------------------------------------
         5 - filter(("TY"."ATT2" IS NULL OR "TY"."ATT2"="BT"."ATT2") AND ("TY"."ATT3" IS NULL OR
                    "TY"."ATT3"="BT"."ATT3") AND ("TY"."ATT4" IS NULL OR "TY"."ATT4"="BT"."ATT4"))
         6 - access("TY"."ATT1"="BT"."ATT1")
         7 - filter(("TY"."ATT2" IS NULL OR "TY"."ATT2"="BT"."ATT2") AND ("TY"."ATT3" IS NULL OR
                    "TY"."ATT3"="BT"."ATT3") AND ("TY"."ATT4" IS NULL OR "TY"."ATT4"="BT"."ATT4"))
         8 - access("TY"."ATT1" IS NULL)
             filter(LNNVL("TY"."ATT1"="BT"."ATT1"))
      
      

      You’ll notice that the optimimzer isn’t doing quite what you might expect – although we get concatenation and manage to split the join into two index range scans (one where big_table.att1 is not null, the other where it is null) we don’t check att2 in the index, which is odd.

      This plan could be reasonably efficient, despite this anomaly, provided we can find one attN column that was “nearly unique” with a very small number of rows where it was null, so that any row in big_table had to check only a very small number of rows in types, rather than all 900 of them: that would be the column we would put in first place in the index. There would still be some benefit to applying the “select distinct” strategy – but if you’re lucky with the data and reduce the scale of the join by a factor of 100 because you can create the right index, the extra factor of 10 may not be worth making the code more subtle.

      Comment by Jonathan Lewis — April 16, 2015 @ 7:44 pm GMT Apr 16,2015 | Reply

      • Really appreciate for exploring further on this.
        It’s provided a bigger picture on indexes specially “TABLE ACCESS BY INDEX ROWID BATCHED”. Perhaps, after looking at the plan, if the rows from big_table are probed (when we have large number of rows) with child table, in above case where optimizer sub-divided/ split index in two batches. If we try to make push_pred from base table that is big_table, then instead of “NESTED LOOPS OUTER” , I though of “Hash Join” between two subset results from two batched indexe’s. So, that it may reduce the cost of fetch from “nested loop”.
        Not sure…whether do we have chance of push_predicate in this case. I was considering case with large set,with non-unique (just a example perspective).

        Comment by Pavan Kumar Kumar N — April 18, 2015 @ 10:10 am GMT Apr 18,2015 | Reply

        • If you know the data well enough (and if the data is constrained to follow the rule you think you know) then in theory you could join big_table to something like:

          (select * from types where att1 is not null
          union all
          select * from types where att1 is null and att2 is not null
          )

          This assumes that att2 is never null when when att1 is null – which isn’t an assumption built into my data set, of course, so the idea doesn’t apply; nevertheless if this constraint were present then the optimizer might well convert a join to this union all into a union all of the two joins to get the job done efficiently.

          Comment by Jonathan Lewis — April 18, 2015 @ 7:10 pm GMT Apr 18,2015

  2. I am very confused by the clauses of the form “nvl(ty.att1(+), bt.att1) = bt.att1”. What are they supposed to do and how do they do it? Consider:

    select * from (select 1 as a from dual) A, (select 2 as b from dual) B

    where A.a = B.b; — 1 != 2, so this returns 0 rows
    where A.a(+) = B.b; — outer join, so this returns 1 row
    where NVL(A.a(+), B.b) = B.b; — ?? outer join introduces a NULL, which NVL turns into a 2, and 2=2 so this returns 1 row ??
    where NVL(A.a(+), 3) = B.b; — ???? returns 1 row even though 3 != 2 ????

    Comment by Andrew Flowers — April 15, 2015 @ 10:22 pm GMT Apr 15,2015 | Reply

    • I’ll answer my own question, hopefully correctly.

      select * from (select 1 as a from dual) A, (select 2 as b from dual) B
      where NVL(A.a(+), B.b) = B.b;

      is equivalent to

      select * from (select 1 as a from dual) A, (select 2 as b from dual) B
      where NVL(A.a, B.b) = B.b
      union
      select * from (select 1 as a from dual) A, (select 2 as b from dual) B
      where A.a(+) = B.b;

      Intuitively that makes sense, but the sql parser in my brain still fails to accept the outer join operator (+) used in an expression other than a simple equivalence, even though the Oracle docs say it’s fine.

      Note that is it NOT equivalent to

      select * from (
      select * from (select 1 as a from dual) A, (select 2 as b from dual) B
      where A.a(+) = B.b
      )
      where NVL(a, b) = b;

      That might also have made sense, but it’s wrong. This returns a different result if A or B contains NULLs.

      Comment by Andrew Flowers — April 16, 2015 @ 5:23 pm GMT Apr 16,2015 | Reply

      • Andrew,

        I left the original predicate set in place (and emulated it in my example) even though I had to pause and spend a couple of minutes convincing myself that I understood what it was trying to do.

        Right or wrong, my view on the “columnX(+)” syntax is that we simply add an extra row that is completely null to the owning table, with the proviso that ANY predicate tested against this row (i.e. against any “columnX(+)” expression) will return true. No row from “the other” table is allowed to disappear.

        Comment by Jonathan Lewis — April 16, 2015 @ 7:54 pm GMT Apr 16,2015 | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.