Oracle Scratchpad

January 23, 2014

Optimisation

Filed under: Execution plans,Oracle,Performance — Jonathan Lewis @ 6:05 pm BST Jan 23,2014

Here’s a recent request from the OTN database forum – how do you make this query go faster (tkprof output supplied):

 select a.rowid
   from  a, b
   where A.MARK IS NULL
     and a.cntry_code = b.cntry_code and b.dir_code='XX' and b.numb_type='XXX'
     and upper(Trim(replace(replace(replace(replace(replace(replace(replace(a.co_name,'*'),'&'),'-'),'/'),')'),'('),' '))) like
         upper(Trim(substr(replace(replace(replace(replace(replace(replace(replace(b.e_name,'*'),'&'),'-'),'/'),')'),'('),' '),1,25)))||'%';


call     count       cpu    elapsed       disk      query    current        rows
------- ------  -------- ---------- ---------- ---------- ----------  ----------
Parse        1      0.01       0.01          0          0          0           0
Execute      2      0.00       0.00          0          0          0           0
Fetch        3   3025.53    3260.11       8367       7950          0          31
------- ------  -------- ---------- ---------- ---------- ----------  ----------
total        6   3025.54    3260.13       8367       7950          0          31

Misses in library cache during parse: 1
Optimizer goal: CHOOSE
Parsing user id: 74

Rows     Row Source Operation
-------  ---------------------------------------------------
     31  HASH JOIN
 302790   INDEX FAST FULL SCAN OBJ#(39024) (object id 39024)   -- B 500,000 in the table
  55798   TABLE ACCESS FULL OBJ#(78942)                        -- A 175,000 in the table

-- and from some "explain plan" tool
SELECT STATEMENT  CHOOSE Cost: 333  Bytes: 52,355,940  Cardinality: 608,790
3 HASH JOIN  Cost: 333  Bytes: 52,355,940  Cardinality: 608,790
  1 INDEX FAST FULL SCAN UNIQUE B_PK Cost: 4  Bytes: 503,022  Cardinality: 12,898
    2 TABLE ACCESS FULL A Cost: 215  Bytes: 3,150,034  Cardinality: 67,022

One thing you might note from the spartan tkprof output – this is an old version of Oracle (9.2.0.1 to be exact).

The first thing to do is note that most of the time is spent on the CPU – and maybe that multiply cascading replace() has something to do with it. ┬áNow replace() and translate() are things I use so rarely that I usually get them wrong first time, but I think the predicate could be replaced by:

upper(translate(a.co_name, 'x*&-/)( ', 'x')) like upper(substr(translate(b.e_name, 'x*&-/)( ', 'x'),1,25))||'%'

Beyond making the code slightly less eye-boggling, though, I don’t think this is going to help much. Consider the information we have about the sizes of the rowsources involved.

If we can trust the tkprof row counts as being the complete output from the first execution of the statement (there seem to have been 2 in the trace file) – we selected 300,000 rows from one table and 56,000 rows from the other and then joined them with a hash join. A hash join requires equality predicates, and the only join predicate in the query that could be used is the one “a.cntry_code = b.cntry_code”.

Now, if cntry_code is short for “country code” we have a scaling problem: there are only about 600 countries in the world, so on average each row in the A table (56,000 rows acquired) is going to find roughly 500 rows in the B table (300,000 rows divided across 600 countries). So at run time the hash join will generate a rowsource of at least 56,000 * 500 = 28 Million rows; then Oracle is going to do that complicated bit of textual manipulation on two columns, compare them, and find that ultimately only 31 rows match !

So how can we do less work ?

If we’re lucky we can make the hash join much more efficient by thinking about what that nasty textual predicate means. We compare to see if one string looks like it’s starting with the first 25 characters of the other string – but if it does then the two strings have to be identical on the first 25 characters, and a hash join works with equality. So let’s just add in a new predicate to see what effect it has:

upper(substr(translate(a.co_name, 'x*&-/)( ', 'x'),1,25)) = upper(substr(translate(b.e_name, 'x*&-/)( ', 'x'),1,25))

I’ve made the suggestion on the forum – now I’m waiting to see if it has a beneficial effect (or whether I’ve made a silly mistake in my logic or guesswork)

13 Comments »

  1. Hi Jonathan,

    it’s not the same because of the (most likely unintended) possibility that the 2nd string contained “_”, “%” and “\” before.
    But in that case it will remove a bug :)

    Regarding the rest, please see this example:
    a.co_name = 12345678901234567890123456
    b.e_name = 12345678901234567890123456xxxx
    => match before and match after

    a.co_name = 1234567890123456789012345
    b.e_name = 12345
    => match before, no match after

    Best regards,
    Salek Talangi

    Comment by Salek Talangi — January 23, 2014 @ 7:14 pm BST Jan 23,2014 | Reply

    • Salek,

      Thanks for that – you’re right of course.

      I’m going to look a little embarrassed about the wild-card error, but very embarrassed about the “short strings” error – I simply didn’t consider the possibility that the strings could be shorter than 25 characters.

      I’m now struggling to think of any way in which we could still introduce an equality that would reduce the explosion of data at the join.

      Comment by Jonathan Lewis — January 23, 2014 @ 8:07 pm BST Jan 23,2014 | Reply

      • Hi Jonathan,

        How about a hash function around the purifying function? To be perfectly safe, it would have to be completed by the purifying function alone to avoid hash collisions, but it would allow equality.

        Best regards, Stew

        Comment by stewashton — January 24, 2014 @ 8:15 am BST Jan 24,2014 | Reply

        • Hmm, don’t see anything like a hash function in the 9.2 documentation. Oh well…

          Comment by stewashton — January 24, 2014 @ 8:29 am BST Jan 24,2014

        • Please ignore my suggestion about the hash function: it too ignores the problem of differing lengths less than 25.

          Comment by stewashton — January 24, 2014 @ 9:26 am BST Jan 24,2014

      • Stew,

        I see you spotted your own error before I got to your comment – so you did better than me on this one :)
        Just for the record, there is a legal hash function in 9i (and even in 8i – can’t remember if it’s there in 7) which is dbms_utility.get_hash_value()

        Comment by Jonathan Lewis — January 24, 2014 @ 12:26 pm BST Jan 24,2014 | Reply

  2. Jonathan,

    what’s about 2 function based indexes?
    the function can be “upper(substr(translate(COLUMN, ‘x*&-/)( ‘, ‘x’),1,25))” (or whatever it is in detail) –
    a initial join can be on instr(function(b.e_name),function(a.co_name)) – I’m not sure if this gives the correct results, but we can use it as a kind of “manual bloom filter” so the indexes are used.
    just an idea to elaborate?

    Martin

    Comment by Martin Berger (berx) — January 23, 2014 @ 9:53 pm BST Jan 23,2014 | Reply

    • Martin,

      An index on a(cntry_code, upper(translate(a.co_name, ‘x*&-/)( ‘, ‘x’))) is probably the damage-limiting option with a nested loop join from B to A (given the direction effectively forced by the LIKE operator). Possibly go a little further and create indexes that allow the whole thing to be an index-only join driven in the the order of (cntry_cde, upper(substr(translate(b.e_name, ‘x*&-/)( ‘, ‘x’),1,25))).

      The drawback is the 300,000 index probes it entails to find 30 rows, and given the point Salek made about wild cards in mid-string, some of those probes could be very big range scans – depending on the data though (particularly the position of any wildcards) it could be a lot less CPU than the hash join explosion from a cntry_cde join.

      The OP pointed out that Oracle wasn’t using the existing FBI(s) – which doesn’t sound too surprising given the cost and cardinality figures involved – but it would be worth hinting them into play.

      Comment by Jonathan Lewis — January 23, 2014 @ 10:58 pm BST Jan 23,2014 | Reply

  3. Does it look like the db is using the larger rowsource as the build?

    Comment by Andy — January 24, 2014 @ 9:49 am BST Jan 24,2014 | Reply

    • Andy,

      A good question – I’ve added an execution plan to the posting to answer it.

      The optimizer “thinks” it’s using the smaller source, but the tkprof shows it’s the larger source (not just by rows but, if we use the execution plan “bytes/cardinality” as an estimate of row, also by total volume).

      The costing on the plan for the fast full scan is suspiciously small – a cost of 4 to do a fast full scan, when the PK contains all the columns in the query for a table with several hundred thousand rows. This might be an indication that the stats are bad, on the other hand it’s 9.2.0.1 and I wouldn’t be surprised if it turned out to be an error in the costing of fast full scans.

      The “disk” statistic from tkprof is higher than the “query” statistic – which suggests the first rowsource has spilled to disc, so there may be some benefit in (a) increasing the PGA, or (b) switching the order of the row sources. However, almost all the time is CPU so the benefit of avoiding the spill will be relatively small. THe other effect of switch the sources is the way the data explosion takes place:

      Large row source first => 500 rows per hash bucket, 100 rows from the second source for each city code used follow its chain
      Small row source first => 100 rows per hash bucket, 500 rows from the second source for each city code used to follow its chain

      Net effect, 500,000 steps taken along hash chains for each city code – it might be interesting to see if there was any significant difference in the choice of strategy.

      Comment by Jonathan Lewis — January 24, 2014 @ 10:27 am BST Jan 24,2014 | Reply

      • Jonathan, I think you are right. The order of the rowsouce is not damaging. I did a simple test by duplicating the long string of ‘replace’, and then another test with the whole string after ‘LIKE’ to just a simple b.v1 || ‘%’, and the timing is dramatically different in the FETCH part ( I also did the same test with wrong statistics of the tables to simulate wrong join order, and the timing difference hardly matters):

        select count(*) from bigtab a, smalltab b where
        a.c1 = b.c1
        and
        upper(Trim(replace(replace(replace(replace(replace(replace(replace(a.v1,’*’),’&’),’-’),’/’),’)’),’(‘),’ ‘))) like
        upper(Trim(substr(replace(replace(replace(replace(replace(replace(replace(b.v1,’*’),’&’),’-’),’/’),’)’),’(‘),’ ‘),1,25)))||’%’

        call count cpu elapsed disk query current rows
        ——- —— ——– ———- ———- ———- ———- ———-
        Parse 1 0.00 0.00 0 0 0 0
        Execute 1 0.00 0.00 0 0 0 0
        Fetch 1 2.35 2.37 0 76 0 1
        ——- —— ——– ———- ———- ———- ———- ———-
        total 3 2.35 2.37 0 76 0 1

        select count(*) from bigtab a, smalltab b where
        a.c1 = b.c1
        and
        upper(Trim(replace(replace(replace(replace(replace(replace(replace(a.v1,’*’),’&’),’-’),’/’),’)’),’(‘),’ ‘))) like
        b.v1 || ‘%’

        call count cpu elapsed disk query current rows
        ——- —— ——– ———- ———- ———- ———- ———-
        Parse 1 0.00 0.00 0 0 0 0
        Execute 1 0.00 0.00 0 0 0 0
        Fetch 1 1.12 1.13 0 76 0 1
        ——- —— ——– ———- ———- ———- ———- ———-
        total 3 1.12 1.13 0 76 0 1

        Comment by Andy — January 24, 2014 @ 6:09 pm BST Jan 24,2014 | Reply

        • Test performed on 12C.

          Comment by Andy — January 24, 2014 @ 6:32 pm BST Jan 24,2014

        • An observation:

          1) the pattern for replace are the same for both e_name and co_name,
          2) e_name looks like a subset of co_name by design ( ie, e_name varchar2(100 byte) and co_name varchar2(150))

          Based on these, I wonder if the nature of the data already ‘support’ a direct pattern match without any need for all those text replacement and a substr operation.

          ie, a direct comparison can be made by co_name like e_name || ‘%’

          Only the OP would know I guess :)

          Comment by Andy — January 24, 2014 @ 6:53 pm BST Jan 24,2014


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

The Rubric Theme Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 3,507 other followers