Re: query for top 10 sql?

From: Mark Richard <mrichard_at_transurban.com.au>
Date: Fri, 12 Mar 2004 08:29:48 +1100
Message-ID: <OFAF42C4A0.4A0CB144-ONCA256E54.0075B388@transurban.com.au>

Interesting - I have never seen "SORT (ORDER BY STOPKEY)" - Was this introduced in Oracle 9i?

I have been thinking about this problem. My best guess (sorry, it's only a guess) is that the algorithm can become something along the lines of:

Read next record
If record is one of top ten records so far insert it into list
Else, throw record away since it won't be required so far
Loop

Therefore, every record must be inspected but there is no need to build a tree containing all results if the record isn't a candidate for the result set. I can see a saving in building the sorted list, and I can see a definite memory saving, but the cost of reading and comparing every record still exists.

Having said that, kudos to Oracle for realising this optimisation - Does anyone know when it was introduced?

Regards,

Mark.

                                                                                                                                       
                      Mladen Gogala                                                                                                    
                      <mladen_at_wangtradin        To:       oracle-l_at_freelists.org                                                       
                      g.com>                    cc:                                                                                    
                      Sent by:                  Subject:  Re: query for top 10 sql?                                                    
                      oracle-l-bounce_at_fr                                                                                               
                      eelists.org                                                                                                      
                                                                                                                                       
                                                                                                                                       
                      12/03/2004 05:53                                                                                                 
                      Please respond to                                                                                                
                      oracle-l

To prove my statement of one sort to sort them all, in the land of queries where the counting stops, I did the following thing:

SQL> set autotrace on explain
SQL> select ticker from
  2 (
  3 select ticker,tso from spxmember
  4 order by tso)
  5 where rownum<=10;

TICKER

RKY
RKY
RKY
PGL
PGL
PGL
CMI
CMI
CMI
GAS 10 rows selected.

Execution Plan

0 SELECT STATEMENT Optimizer=CHOOSE (Cost=5 Card=10 Bytes=70) 1 0 COUNT (STOPKEY)

   2    1     VIEW (Cost=5 Card=1000 Bytes=7000)
   3    2       SORT (ORDER BY STOPKEY) (Cost=5 Card=1000 Bytes=16000)
   4    3         TABLE ACCESS (FULL) OF 'SPXMEMBER' (Cost=4 Card=1000
           Bytes=16000)

SQL> select count(*) from spxmember;

COUNT(*)

1500

Execution Plan

0 SELECT STATEMENT Optimizer=CHOOSE (Cost=2 Card=1) 1 0 SORT (AGGREGATE)

   2    1     INDEX (FULL SCAN) OF 'SPXMEMBER_PK' (UNIQUE) (Cost=4 Car
          d=1000)

In the meantime, V$SYSSTAT was counting sorted rows:

Before the execution:

SQL> select name,value from v$sysstat where name like 'sort%rows%';

NAME                                                                  VALUE
---------------------------------------------------------------- ----------
sorts (rows)                                                       40967148

and
b) after the execution.

SQL> /

NAME                                                                  VALUE
---------------------------------------------------------------- ----------
sorts (rows)                                                       40968667

SQL> select 40968667-40967148 from dual;

40968667-40967148

1519

I was the only user of the database, nobody else was sorting anything. As the SPXMEMBER table
has 1500 rows, I conclude that all rows were sorted, just as I predicted that they'll have to
be. I would still like to read Tom's explanation of how to sort only 10 rows and leave the
other 1490 alone. I'm sure that the explanation is logical and, probably, misunderstood.

On 03/11/2004 10:39:05 AM, Igor Neyman wrote:
> Obviously in this case (second out of 3) it doesn't make any difference.
> But, if asked for top 10 out of 1000:
> - Without optimization: all 1000 would have been sorted;
> - With optimization: find top 10 and stop, no need to sort the rest 990.

> Igor Neyman, OCP DBA
> ineyman_at_perceptron.com

>
>
>

> -----Original Message-----
> From: oracle-l-bounce_at_freelists.org
> [mailto:oracle-l-bounce_at_freelists.org] On Behalf Of Mladen Gogala
> Sent: Thursday, March 11, 2004 9:16 AM
> To: oracle-l_at_freelists.org
> Subject: Re: query for top 10 sql?

> Second out of 3? How do you sort them?

> On 03/11/2004 08:58:44 AM, Igor Neyman wrote:
> > T.Kyte explains this optimization very well in his (second) book.
> >
> > Sorting stops as soon as top-N (where N specified by ROWNUM) elements
> of
> > "sorted" array are filled.
> >
> > Igor Neyman, OCP DBA
> > ineyman_at_perceptron.com
> >
> >
> >
> > -----Original Message-----
> > From: oracle-l-bounce_at_freelists.org
> > [mailto:oracle-l-bounce_at_freelists.org] On Behalf Of Tim Gorman
> > Sent: Wednesday, March 10, 2004 11:04 PM
> > To: oracle-l_at_freelists.org
> > Subject: Re: query for top 10 sql?
> >
> > A slight correction, below...
> >
> > on 3/10/04 7:07 PM, Mark Richard at mrichard_at_transurban.com.au wrote:
> >
> > >
> > > Originally I thought the same but then noticed it was "query for" &
> > "top
> > > ten sql" - which I interpreted as a query about SQL (similar to the
> > > Statspack type results).
> > >
> > > As far as the SQL Server "TOP" equivalent - I have not seen such a
> > graceful
> > > solution in Oracle. One approach I have seen includes using an
> ORDER
> > BY in
> > > a subquery and applying "where rownum <= 10" in the outer query - if
> > the
> > > inner query returns a large result set then a big sort is required.
> >
> > Oracle has an optimization on this operation that halts the sort after
> > the
> > first N rows (where "N" is the number specified in "rownum <= N") are
> > retrieved from the inner query.
> >
> > The following test case may help illustrate:
> >
> > SQL> select count(*)
> > 2 from dba_objects;
> >
> > COUNT(*)
> > ----------
> > 4905
> > SQL>
> > SQL> select count(distinct object_type)
> > 2 from (select object_id, object_type, object_name
> > 3 from dba_objects
> > 4 order by 1, 2, 3)
> > 5 where rownum <= 1000;
> >
> > COUNT(DISTINCTOBJECT_TYPE)
> > --------------------------
> > 10
> > SQL>
> > SQL> select s.value - &&V_VALUE sort_rows, s.value
> > 2 from v$mystat s, v$statname n
> > 3 where s.statistic# = n.statistic# and n.name = 'sorts
> (rows)';
> >
> > SORT_ROWS
> > ----------
> > 6185
> > SQL>
> > SQL> select count(distinct object_type)
> > 2 from (select object_id, object_type, object_name
> > 3 from dba_objects
> > 4 order by 1, 2, 3)
> > 5 where rownum <= 100;
> >
> > COUNT(DISTINCTOBJECT_TYPE)
> > --------------------------
> > 3
> > SQL>
> > SQL> select s.value - &&V_VALUE sort_rows, s.value
> > 2 from v$mystat s, v$statname n
> > 3 where s.statistic# = n.statistic# and n.name = 'sorts
> (rows)';
> >
> > SORT_ROWS
> > ----------
> > 5285
> > SQL>
> > SQL> select count(distinct object_type)
> > 2 from (select object_id, object_type, object_name
> > 3 from dba_objects
> > 4 order by 1, 2, 3)
> > 5 where rownum <= 10;
> >
> > COUNT(DISTINCTOBJECT_TYPE)
> > --------------------------
> > 3
> > SQL>
> > SQL> select s.value - &&V_VALUE sort_rows, s.value
> > 2 from v$mystat s, v$statname n
> > 3 where s.statistic# = n.statistic# and n.name = 'sorts
> (rows)';
> >
> > SORT_ROWS
> > ----------
> > 5195
> >
> > Notice that when the query returned 1,000 rows, the total number of
> rows
> > sorted by the operation was 6,185. When the number of rows returned
> by
> > the
> > query was reduced by 900 to 100, then the total number of rows sorted
> > reduced correspondingly by 900 to 5,285. When the number of rows
> > returned
> > by the query was further reduced by 90 to 10, then the total number of
> > rows
> > sorted also reduced by 90 to 5,195.
> >
> > Mind you, I didn't see the number of logical I/Os change for any
> > operation,
> > so the initial scan of the inner query certainly did not change (which
> > is to
> > be expected).
> >
> > But the secondary operation of sorting appears to have been reduced.
> A
> > small optimization in this small test case, but if this was a huge
> sort
> > in
> > which significant I/O is performed from disk in the temporary
> > tablespace,
> > then perhaps this optimization would show more pronounced
> improvement...
> >
> > Well, you can't expect "top N" (or "bottom N") operations without a
> full
> > scan of the problem-set as well at least one sort operation on the
> > results.
> > So, the optimization isn't as trivial as it might seem.
> >
> >
> > > second approach might be to use an analytical function like RANK()
> or
> > > ROW_NUM() - but again a large sort is often required. A third
> > approach
> > > relies on using index ordering (with a hint typically for force
> index
> > > traversal) and "where rownum <= 10" applied on the original query -
> > this
> > > depends on a suitable index being available and is quite risky (for
> > > example, if the index is dropped the query won't fail but will
> return
> > a
> > > very incorrect result without warning).
> >
> > ----------------------------------------------------------------
> > Please see the official ORACLE-L FAQ: http://www.orafaq.com
> > ----------------------------------------------------------------
> > To unsubscribe send email to: oracle-l-request_at_freelists.org
> > put 'unsubscribe' in the subject line.
> > --
> > Archives are at http://www.freelists.org/archives/oracle-l/
> > FAQ is at http://www.freelists.org/help/fom-serve/cache/1.html
> > -----------------------------------------------------------------
> >
> >
> > ----------------------------------------------------------------
> > Please see the official ORACLE-L FAQ: http://www.orafaq.com
> > ----------------------------------------------------------------
> > To unsubscribe send email to: oracle-l-request_at_freelists.org
> > put 'unsubscribe' in the subject line.
> > --
> > Archives are at http://www.freelists.org/archives/oracle-l/
> > FAQ is at http://www.freelists.org/help/fom-serve/cache/1.html
> > -----------------------------------------------------------------
> >
> ----------------------------------------------------------------
> Please see the official ORACLE-L FAQ: http://www.orafaq.com
> ----------------------------------------------------------------
> To unsubscribe send email to: oracle-l-request_at_freelists.org
> put 'unsubscribe' in the subject line.
> --
> Archives are at http://www.freelists.org/archives/oracle-l/
> FAQ is at http://www.freelists.org/help/fom-serve/cache/1.html
> -----------------------------------------------------------------

>
>


> ----------------------------------------------------------------

> Please see the official ORACLE-L FAQ: http://www.orafaq.com
> ----------------------------------------------------------------
> To unsubscribe send email to: oracle-l-request_at_freelists.org
> put 'unsubscribe' in the subject line.
> --
> Archives are at http://www.freelists.org/archives/oracle-l/
> FAQ is at http://www.freelists.org/help/fom-serve/cache/1.html
> -----------------------------------------------------------------
>

Please see the official ORACLE-L FAQ: http://www.orafaq.com

To unsubscribe send email to: oracle-l-request_at_freelists.org put 'unsubscribe' in the subject line.

--
Archives are at http://www.freelists.org/archives/oracle-l/
FAQ is at http://www.freelists.org/help/fom-serve/cache/1.html
-----------------------------------------------------------------





<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<---->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Privileged/Confidential information may be contained in this message.
If you are not the addressee indicated in this message (or responsible for delivery of the message to such person), you may not copy or deliver this message to anyone.
In such a case, you should destroy this message and kindly notify the sender by reply e-mail or by telephone on (03) 9612-6999 or (61) 3 9612-6999.
Please advise immediately if you or your employer does not consent to Internet e-mail for messages of this kind.
Opinions, conclusions and other information in this message that do not relate to the official business of Transurban Infrastructure Developments Limited and CityLink Melbourne Limited shall be understood as neither given nor endorsed by them.
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<---->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

----------------------------------------------------------------
Please see the official ORACLE-L FAQ: http://www.orafaq.com
----------------------------------------------------------------
To unsubscribe send email to:  oracle-l-request_at_freelists.org
put 'unsubscribe' in the subject line.
--
Archives are at http://www.freelists.org/archives/oracle-l/
FAQ is at http://www.freelists.org/help/fom-serve/cache/1.html
-----------------------------------------------------------------

Received on Thu Mar 11 2004 - 17:15:49 CST