Oracle Scratchpad

November 6, 2006

Filter Subqueries

Filed under: Hints,Oracle,Performance,Troubleshooting,Tuning — Jonathan Lewis @ 11:33 pm BST Nov 6,2006

Here’s a little demonstration of a feature that can cause random fluctuations in performance because of an unlucky data item. It starts with an emp table holding 20.000 employees spread across six departments, and then moves one employee to a new (carefully chosen) department. You will have to run this in version 9i or later, as it makes use of subquery factoring to generate the emp table.

create table emp(
	dept_no		not null,
	sal,
	emp_no		not null,
	padding,
	constraint e_pk primary key(emp_no)
)
as
with generator as (
	select	--+ materialize
		rownum 		id
	from	all_objects
	where	rownum )
select
	mod(rownum,6),
	rownum,
	rownum,
	rpad('x',60)
from
	generator	v1,
	generator	v2
where
	rownum  user,
		tabname		 => 'EMP',
		estimate_percent => null,
		block_sample 	 => true,
		method_opt 	 => 'for all columns size 1',
		degree		 => null,
		granularity	 => 'default',
		cascade		 => true
	);
end;
/

select
	count(*)
from	(
	select	/*+ no_merge */
		outer.*
	from	emp outer
	where	outer.sal >
		(
			select	/*+ no_unnest */
				avg(inner.sal)
		 	from	emp inner
			where	inner.dept_no = outer.dept_no
		)
	)
;

The query is a little strange as it uses the /*+ no_unnest */ hint to stop the optimizer from unnesting the subquery. Unnesting would normally happen in simple cases like this one, but more complex queries aren’t alway able to undergo the unnest transformation. The query also has a /*+ no_merge */ hint so that it can execute and instantiate the main body of the query, then only output a count. You should find that the query takes a fraction of a second to run – possibly less than one hundredth if you are able to hold the emp table cached in memory – returning the value 9,998.

Now execute the following update, and run the query again:

update emp
	set dept_no = 432
where
	dept_no = 1
and	rownum = 1
;

Running at 1.6GHz, my laptop takes about 21 seconds of flat out CPU time to complete the query with just this one row-change, so be prepared for a bit of a wait. This change in performance is what happens when a particular run-time optimisation known as scalar subquery caching fails (and this correlated subquery is just one example of the more general class of scalar subquery).

When the query ran quickly, Oracle managed to cache the average salaries for the six departments as it ran through the first six rows in the tablescan. But these values were stored in a hash table keyed by the department number.

When I changed the first occurrence of department 1 to 432, Oracle got to the row with department 432 before it got to a row with department 1, and stored the average salary for department 432 in the hash table location that would otherwise have been used by department 1.

Unfortunately, the caching algorithm does not allow for hash collisions of this type, so the next 3,333 times Oracle needed the average salary for department 1 it discovered that it wasn’t cached, and ran the subquery again, .. and again, .. and again …

If you do find that you have a particular query that is subject to this problem you may have to write it to avoid the filter subquery (and you may find that a simple /*+ unnest */ hint will be enough to pre-empt the issue).

Here is a counter-intuitive mechanism that will be highly cost-effective in some cases – I replace the first occurrence of the emp table with a non-mergeable inline view that sorts the emp table by department number **:

select
	count(*)
from	(
	select	/*+ no_merge */
		outer.*
	from	(
		select
			/*+
				no_merge
				qb_name(ordering)
				no_eliminate_oby(@ordering)
			*/
			*
		from	emp
		order by
			dept_no
		)	outer
	where	outer.sal >
		(
			select	/*+ no_unnest */
				avg(inner.sal)
		 	from 	emp inner
			where	inner.dept_no = outer.dept_no
		)
	)
/

On my laptop, using this sorting strategy, my response time dropped back to 0.02 seconds. This works because the code now acquires the department numbers in order, and Oracle doesn’t even do a lookup to the hash table if the current row uses the same input as the previous row.

** It has occurred to me that in 10gR2 you may need to include a qb_name() hint and a no_eliminate_oby hint in the inline view to stop the optimizer from eliminating what it sees as a redundant order by. (See the end of this article for an example of the necessary hints). But I don’t have a 10.2 database to hand to check this at the moment – so I’ll have to test that some time in the next couple of days. (Relevant 10g hint introduced in ordering sub-query after receiving note from Jeff Moss – see comments below).

21 Comments »

  1. FYI

    I tested it on 10.2.0.2.0 on XP and it does need both the qb_name and no_eliminate_oby hints before it will execute the SORT ORDER BY and make the query run quickly.

    Took about 10s to run the slow version on my 3GHz PC.

    Comment by Jeff Moss — November 7, 2006 @ 12:41 pm BST Nov 7,2006 | Reply

  2. This is almost certainly a crazy idea, but I wonder if it’s possible to draw up a table that cross-references numbers on which hash collisions would occur when building a hash table? Presumably if dept_no 432 was actually 433 then it wouldn’t collide with dept_no 1. A cross reference table might allow one to avoid the problem of collisions entirely, although it would be a fiddly task and probably prone to change with a new Oracle release.

    Well maybe the hash function that the CBO uses depends on the number of expected values though, or something like that.

    Come to think of it, do you know what the hash function is, Jonathan?

    Comment by David Aldridge — November 7, 2006 @ 3:53 pm BST Nov 7,2006 | Reply

  3. Jeff, Thanks for running the test – I’m home now, and have added the necessary hint back in to the relevant query.

    David, There are some notes about this in my book, chapter 9. In particular, the number of entries in the hash table seems to be fixed in 8i and 9i to 256 entries; but in 10g it is a fixed size in bytes (default 64K but controlled by a hidden parameter) which happens to equate to 1024 entries for numbers but only 16 for unconstrained character columns. As a conjecture, it may be the same hash algorithm used by the thing that defines hash partitions, which may be exposed in dbms_utility.get_hash_value – but I haven’t checked that, or even worked out how to use that for numbers yet.

    Comment by Jonathan Lewis — November 7, 2006 @ 9:03 pm BST Nov 7,2006 | Reply

  4. Thanks Jonathan, I’ll consult the book as well then.

    Do you know if dbms_utility.get_hash_value is officially stable across major releases now? I recall that it used to be documented that it could change, but the more recent docs don’t seem to mention that.

    Comment by David Aldridge — November 7, 2006 @ 11:59 pm BST Nov 7,2006 | Reply

  5. I checked back to “Practical Oracle 8i” where I made some comments about this function, and I don’t have any warnings about stability there, nor in the note I published in June 1999 for 8.1.5.
    I have no more information about the internal activities and decisions of Oracle Corp. than you do, so I can only guess about stability; and it seems likely that it will be stable because it appears to be the function used for calculating hash partition numbers from strings.

    Comment by Jonathan Lewis — November 8, 2006 @ 9:16 am BST Nov 8,2006 | Reply

  6. [...] you think back to my notes on filter subqueries, you will realise that the change in join order could easily affect the number of times a filter [...]

    Pingback by Ordering « Oracle Scratchpad — March 5, 2007 @ 1:37 pm BST Mar 5,2007 | Reply

  7. [...] be reported, if it isn’t then Oracle will (in principle – but check my comments about  filter subqueries) run the subquery as the second [...]

    Pingback by Subquery with OR « Oracle Scratchpad — March 5, 2007 @ 5:54 pm BST Mar 5,2007 | Reply

  8. [...] If you want a real-life example of code that could “randomly” produce massive numbers of buffer visits and distort your BCHR in a “real” system, you need look no further than this old article of mine. [...]

    Pingback by Hit ratios (2) « Oracle Scratchpad — September 5, 2007 @ 8:33 pm BST Sep 5,2007 | Reply

  9. Jonathan, this article is wonderful but I cant´t understand the following. When the average salary for the department 432 is stored in the hash table, it will use the entry used by the department 1. This will produce collisions. But … when the query is executed again, doesn´t should it reallocate the average salary for the department 1 in its old location?. Please correct me if I´m wrong. Is it perhaps due to the hash value of the query that is in the Library Cache yet so information about merory structures used (the hash table) is retained and it is not recalculated?.

    Thank you Jonathan.

    Comment by Richard — October 25, 2007 @ 2:57 pm BST Oct 25,2007 | Reply

  10. [...] most important hint in this example is probably the no_eliminate_oby hint, which I have described in the past. Without this hint you may find that the optimizer decides that the order by adds no value to the [...]

    Pingback by Manual Optimisation « Oracle Scratchpad — May 2, 2008 @ 12:09 pm BST May 2,2008 | Reply

  11. [...] I’ve used the /*+ no_merge */ hint in the SQL, with an inline view that contains the select and “order by” so that I can force Oracle to sort the data but only output a single row. Then I’ve used the /*+ no_eliminate_oby() */ hint to make sure that the optimizer doesn’t eliminate the (apparently) redundant “order by” clause in the in-line view (a trick that it learnt to do in 10gR2 – see the notes towards the end of this article). [...]

    Pingback by SAS Bug « Oracle Scratchpad — November 25, 2008 @ 11:32 pm BST Nov 25,2008 | Reply

  12. Respected Sir,

    update emp
    set dept_no = 432
    where
    dept_no = 1
    and rownum = 1

    In your above example with respect to filter you updated the first row of dept_no=1 with 432.

    Also you said a statement as below

    Oracle got to the row with department 432 before it got to a row with department 1, and stored the average salary for department 432 in the hash table location that would otherwise have been used by department 1

    I have one confusion that who would it possible during sql execution that the row with deptno=432 appear first among other row with same department (i.e. dept_no =1)

    could you please flash more light on this?

    Also who could oracle hash dept_no=432 on the location where dept_no=1 would supppose to be store?

    Thanks

    Sir

    Comment by Henish — August 4, 2009 @ 8:10 pm BST Aug 4,2009 | Reply

    • Henish,
      If I’ve understood your questions, you want to know (a) why Oracle got to the row with the department set to 432 before it got to a row with department set to 1; and (b) why 432 and 1 has to the same location.

      a) Although you should not rely on any specific ordering of data (or action) when using SQL, there are simple cases where the actual mechanics cannot change. I defined a table with no indexes in a tablespace using freelist management, so I could make some reasonable assumptions about the way in the which the data would be inserted and queried. In effect I was relying on my knowledge of the current internal mechanics used by Oracle – this is not something I would do for a production system.

      b) The principle of hashing is that you have an infinite number of different values that you need to store as evenly as possible in a finite number of locations. Consequently you will find cases where two different input numbers hash to the same output value. I justed experimented until I found a suitable second number.

      Comment by Jonathan Lewis — August 6, 2009 @ 5:33 pm BST Aug 6,2009 | Reply

  13. Hello Sir,

    It would be great if you would please flash more light on your below comment

    “I defined a table with no indexes in a tablespace using freelist management, so I could make some reasonable assumptions about the way in the which the data would be inserted and queried”

    Many Thanks

    Comment by Henish — August 7, 2009 @ 2:14 pm BST Aug 7,2009 | Reply

  14. Hi Jonathan,

    Can this type of collision happen to a character based columns not just numbers

    Comment by josh — October 19, 2009 @ 4:11 pm BST Oct 19,2009 | Reply

  15. [...] A small change in data can cause a huge  variation in the number of times a subquery runs [...]

    Pingback by No change « Oracle Scratchpad — November 12, 2009 @ 7:52 pm BST Nov 12,2009 | Reply

  16. Hi Jonathan,

    Many thanks for this amazing blog.

    How about using below query ? it seems then you avoid to run the subquery again and again as it does a join between emp and avg.

    select
            count(*)
            from    emp,
             (  select  dept_no,
                          avg(inner.sal) sal 
                   from    emp inner
                  group by dept_no
                ) avg
            where   emp.sal > avg.sal
               and   emp.dept_no = avg.dept_no
    

    Cheers,
    Victor

    Comment by Victor — September 2, 2010 @ 2:43 pm BST Sep 2,2010 | Reply

    • Victor,

      The transformation you’ve done to get your query is known as unnesting. In this specific case, to demonstrate a point, I blocked the automatic unnesting that the optimizer would have done; but there are some cases of filter subqueries which the optimizer won’t handle automatically that you could do this type of manual rewrite for.

      Comment by Jonathan Lewis — September 3, 2010 @ 11:35 am BST Sep 3,2010 | Reply

      • Thanks Jonathan for your reply. I see. I came to this post from “Join ordering” post where you talk about different strategies on similar kind of queries and now it makes more sense. There is something I can’t understand as you said “When I changed the first occurrence of department 1 to 432, Oracle got to the row with department 432 before it got to a row with department 1, and stored the average salary for department 432 in the hash table location that would otherwise have been used by department 1.”. Do you know about how the algorithm builds the hash table to go into this hash colission (as you called it)?
        Many thanks.

        Comment by Victor — September 3, 2010 @ 2:47 pm BST Sep 3,2010 | Reply

  17. [...] different products – which is unlikely in this case) we may find that our subquery benefits from “scalar subquery caching”, which means that under perfect conditions we will run the subquery just once per product sold in [...]

    Pingback by Indexes are Tables – All Things Oracle — December 16, 2011 @ 2:48 pm BST Dec 16,2011 | Reply

  18. [...] Note: although the plan in lines 3 – 7 could be executed once for each row returned by the plan in lines 9 – 11, the number of executions could (and in this case is) fewer than the worst case thanks to scalar subquery caching. [...]

    Pingback by Plan timing « Oracle Scratchpad — November 19, 2012 @ 9:59 pm BST Nov 19,2012 | 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

The Rubric Theme Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 3,453 other followers