Oracle Scratchpad

March 12, 2020

dense_rank

Filed under: Execution plans,Oracle,Performance,sorting,subqueries — Jonathan Lewis @ 6:42 pm GMT Mar 12,2020

I’ve just been prompted to complete and publish a draft I started a few years ago. It’s (ultimately) about a feature that appeared in 9i but doesn’t seem to show up very often at client sites or as a common solution to performance problems on the various Oracle forums – but maybe that’s not surprising given how slowly analytic functions have been taken up.

I want to work towards the feature by starting with a requirement, then examine several solutions. To supply a touch of realism I’ll create an orders table, which holds a customer id and an order date (including time), ,and then ask for a report of the most recent order for each customer. Here’s some starting data:

rem
rem     Script:         order_sample.sql
rem     Author:         Jonathan Lewis
rem     Dated:          June 2006
rem     Purpose:        
rem
rem     Last tested 
rem             19.3.0.0
rem             12.2.0.1
rem             12.1.0.0        Costs are consistent
rem             11.2.0.4        Costs become consistent by 11.2.0.3
rem             11.1.0.7
rem             10.2.0.3
rem              9.2.0.8
rem

create table orders
as
with generator as (
        select
                rownum id 
        from dual 
        connect by 
                level <= 1e4 -- > comment to avoid wordpress format issue
)
select
        rownum                                                                  id,
        mod(rownum-1,200)                                                       customer,
        sysdate - 20 + dbms_random.value(0,20)                                  date_ordered,
        rpad('x' || to_char(trunc(dbms_random.value(0,1000)),'FM009'),100)      padding
from
        generator       v1,
        generator       v2
where
        rownum <= 1e4 -- > comment to avoid wordpress format issue
;

alter table orders modify customer not null;
alter table orders modify date_ordered not null;
alter table orders add constraint ord_pk primary key(id);

create index ord_cus on orders(customer);
-- create unique index ord_cus_date on orders(customer, date_ordered);

begin
        dbms_stats.gather_table_stats(
                ownname          => user,
                tabname          =>'orders',
                method_opt       => 'for all columns size 1',
                cascade          => true
        );
end;
/

I’ve got 200 customers, at 50 orders per customer dating back over the last 20 days. There’s a primary key on the table and (as it stands) an obvious “foreign key index” on the customer column, though I’ve allowed for changing this to a more useful (customer, date_ordered) combination which I’ve decided could be declared as unique.

With this data, how do I report “the most recent order for each customer”? The first question to ask in response to this request is: “do you literally mean ‘THE’ most recent; what if the customer has placed two or more orders on the same day or, in my initial case, at the same time?” There’s a special case to think about the moment you start to turn the natural language request into a formal language specification.

In this case I’m going to run with the “customer-only” index and allow for the fact that two or more orders could be placed at the same time by the same customer, and report both (all) of them if any such simultaneously placed orders appear.

Strategy number 1:

Start with a list showing the most recent order date for each customer and then report all orders that we can identify using that list of (customer, date_ordered). To do that I’ll start with a simple aggregate query and use the result it produced in an “IN” subquery:


prompt  =========================
prompt  Use IN subquery for max()
prompt  =========================

select  
        /*+ qb_name(main) */
        ord1.* 
from
        orders  ord1
where
        (ord1.customer, ord1.date_ordered) in (
                select  /*+ qb_name(subq) */
                        ord2.customer, max(ord2.date_ordered)
                from
                        orders  ord2
                group by 
                        ord2.customer
        )
order by
        ord1.customer
;

select * from table(dbms_xplan.display_cursor(null,null,'cost allstats last'));

Plan hash value: 1500776991

------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation             | Name     | Starts | E-Rows | Cost (%CPU)| A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |          |      1 |        |    54 (100)|    200 |00:00:00.01 |     344 |       |       |          |
|   1 |  SORT ORDER BY        |          |      1 |      1 |    54  (15)|    200 |00:00:00.01 |     344 |   115K|   115K|  102K (0)|
|*  2 |   HASH JOIN RIGHT SEMI|          |      1 |      1 |    53  (14)|    200 |00:00:00.01 |     344 |  1695K|  1695K| 1568K (0)|
|   3 |    VIEW               | VW_NSO_1 |      1 |    200 |    28  (18)|    200 |00:00:00.01 |     172 |       |       |          |
|   4 |     HASH GROUP BY     |          |      1 |    200 |    28  (18)|    200 |00:00:00.01 |     172 |  1484K|  1484K| 1421K (0)|
|   5 |      TABLE ACCESS FULL| ORDERS   |      1 |  10000 |    24   (5)|  10000 |00:00:00.01 |     172 |       |       |          |
|   6 |    TABLE ACCESS FULL  | ORDERS   |      1 |  10000 |    24   (5)|  10000 |00:00:00.01 |     172 |       |       |          |
------------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("ORD1"."CUSTOMER"="CUSTOMER" AND "ORD1"."DATE_ORDERED"="MAX(ORD2.DATE_ORDERED)")

I’ve included the qb_name() hint in both query blocks here – it’s always a good idea as it gives you a little extra edge in interpreting the execution plan when the queries get more complicated.

The first thing you’ll notice about the resulting execution plan is that the optimizer has “unnested” the subquery to create an inline view (which it has named VW_NSO_1) and then used a simple join to get the final result. That’s an interesting observation, and it’s something that will often happen with an “IN” subquery – and that brings us to strategy 2.

Strategy number 2:

Some people will take as gospel the claim that the optimizer “cannot handle subqueries efficiently” and will prefer to write their own inline views (possibly using the “WITH subquery” a.k.a. “Common Table Expression (CTE)” mechanism). There will be occasions, even in the latest versions of Oracle, where you may need to do this but there will also be occasions where the optimizer hasn’t done it because it would produce the wrong results – and I have seen a couple of accidents go into production code where this variant has been written incorrectly.


prompt  ==============================
prompt  Introduce max() as inline view
prompt  ==============================

select  
        /*+ qb_name(main) */
        ord1.* 
from
        (
                select  /*+ qb_name(in_line) */
                        ord2.customer, max(ord2.date_ordered) date_ordered
                from
                        orders  ord2
                group by 
                        ord2.customer
        )       ordv,
        orders  ord1
where
        ord1.customer     = ordv.customer
and     ord1.date_ordered = ordv.date_ordered
order by
        ord1.customer
;

select * from table(dbms_xplan.display_cursor(null,null,'cost allstats last'));

Plan hash value: 2750501889

----------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation             | Name   | Starts | E-Rows | Cost (%CPU)| A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
----------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |        |      1 |        |    54 (100)|    200 |00:00:00.01 |     344 |       |       |          |
|   1 |  SORT ORDER BY        |        |      1 |    200 |    54  (15)|    200 |00:00:00.01 |     344 |   115K|   115K|  102K (0)|
|*  2 |   HASH JOIN           |        |      1 |    200 |    53  (14)|    200 |00:00:00.01 |     344 |  1695K|  1695K| 1531K (0)|
|   3 |    VIEW               |        |      1 |    200 |    28  (18)|    200 |00:00:00.01 |     172 |       |       |          |
|   4 |     HASH GROUP BY     |        |      1 |    200 |    28  (18)|    200 |00:00:00.01 |     172 |  1484K|  1484K| 1413K (0)|
|   5 |      TABLE ACCESS FULL| ORDERS |      1 |  10000 |    24   (5)|  10000 |00:00:00.01 |     172 |       |       |          |
|   6 |    TABLE ACCESS FULL  | ORDERS |      1 |  10000 |    24   (5)|  10000 |00:00:00.01 |     172 |       |       |          |
----------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("ORD1"."CUSTOMER"="ORDV"."CUSTOMER" AND "ORD1"."DATE_ORDERED"="ORDV"."DATE_ORDERED")

You’ll notice, of course, the remarkable similarity between the previous plan and this one – the only significant difference being that the optimimzer used a “plain” hash join here rather than the “hash join right semi” that appeared in the previous plan. The “right semi” is an indication that the optimizer has first transformed your “IN” subquery to an equivalent “EXISTS” (“=ANY”) subquery. Don’t be misled by the “right”, by the way, this isn’t indicating any sort of outer join it’s just trying to let you know which table is the one where Oracle should stop its probe after finding the first row. It is, however, unfortunate that it gets a little awkward trying to sort out left from right when Oracle can do a “swap join inputs” on you.

It would have been nice if the VIEW operatio1n had reported the name of my inline view (to correspond to the generated VW_NSO_1 viewname from the previous plan) – but you if you included the ‘alias’ formatting option in the call to display_cursor() it would have reported the alias ordv@main at operation 3.

Strategy Number 3:

We might have decided to check every row in the table to see if the date in that row was the most recent date for the customer in that row, which we could do by running a correlated subquery to do the check for every row in the table.

prompt  ========================================
prompt  Orders with correlated EQUALITY subquery
prompt  ========================================

select  
        /*+ qb_name(main) */
        ord1.* 
from
        orders  ord1
where
        ord1.date_ordered = (
                select  /*+ qb_name(subq) */
                        max(ord2.date_ordered)
                from
                        orders  ord2
                where
                        ord2.customer = ord1.customer
        )
order by
        ord1.customer
;

select * from table(dbms_xplan.display_cursor(null,null,'cost allstats last'));


Plan hash value: 1152467146

-----------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation             | Name    | Starts | E-Rows | Cost (%CPU)| A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
-----------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |         |      1 |        |    54 (100)|    200 |00:00:00.01 |     344 |       |       |          |
|   1 |  SORT ORDER BY        |         |      1 |    200 |    54  (15)|    200 |00:00:00.01 |     344 |   115K|   115K|  102K (0)|
|*  2 |   HASH JOIN           |         |      1 |    200 |    53  (14)|    200 |00:00:00.01 |     344 |  1695K|  1695K| 1622K (0)|
|   3 |    VIEW               | VW_SQ_1 |      1 |    200 |    28  (18)|    200 |00:00:00.01 |     172 |       |       |          |
|   4 |     HASH GROUP BY     |         |      1 |    200 |    28  (18)|    200 |00:00:00.01 |     172 |  1484K|  1484K| 1435K (0)|
|   5 |      TABLE ACCESS FULL| ORDERS  |      1 |  10000 |    24   (5)|  10000 |00:00:00.01 |     172 |       |       |          |
|   6 |    TABLE ACCESS FULL  | ORDERS  |      1 |  10000 |    24   (5)|  10000 |00:00:00.01 |     172 |       |       |          |
-----------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("ORD1"."DATE_ORDERED"="MAX(ORD2.DATE_ORDERED)" AND "ITEM_1"="ORD1"."CUSTOMER")

Yet again we end up with the same execution plan (barring the “right semi” issue) but with a different generated name for the unnested subquery. This is an interesting facet of Oracle (and SQL in general) – completely different ways of stating a requirement can end up doing the same work in the same way.

An important corrollary to this observation is that the first thing you should do when you start writing an SQL statement is to write it in a way that clearly expresses the requirement and is easy for others to comprehend. Don’t (at the first stage) try to do anything clever because (a) you may do it wrong and (b) the optimizer might have taken your clear, simple, code and done the clever bit behind the scenes for you.

However, we may have to move on to doing something new (-ish) and exciting.

Strategy number 4:

An “obvious” defect in the three plans so far is that we have to visit the orders table twice. Is there a way we can avoid doing this? The answer is yes. Oracle 8.1.6 gave us the analytic functions:


prompt  =======================
prompt  Analytic max() function
prompt  =======================

column padding noprint
column date_ordered noprint

select
        /*+ qb_name(main) */
        ordv.* 
from    (
        select  /*+ qb_name(inline) */
                customer, id, date_ordered, padding,
                max(date_ordered) over (
                        partition by customer
                ) max_date
        from    orders  ord2
        )       ordv
where
        ordv.date_ordered = ordv.max_date
order by
        ordv.customer
;

select * from table(dbms_xplan.display_cursor(null,null,'cost outline allstats last'));

Plan hash value: 813391662

--------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation           | Name   | Starts | E-Rows | Cost (%CPU)| A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
--------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |        |      1 |        |   262 (100)|    200 |00:00:00.01 |     172 |       |       |          |
|*  1 |  VIEW               |        |      1 |  10000 |   262   (3)|    200 |00:00:00.01 |     172 |       |       |          |
|   2 |   WINDOW SORT       |        |      1 |  10000 |   262   (3)|  10000 |00:00:00.01 |     172 |  1612K|   624K| 1432K (0)|
|   3 |    TABLE ACCESS FULL| ORDERS |      1 |  10000 |    24   (5)|  10000 |00:00:00.01 |     172 |       |       |          |
--------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter("ORDV"."DATE_ORDERED"="ORDV"."MAX_DATE")

By adding the analytic max() function I can acquire the necessary “raw” data once and post-process it to find the max(date_ordered) for each customer before discarding all the rows where the row’s date doesn’t match the maximum date. The expression “max(date_ordered) over (partition by customer)” is like a virtual column that tells Oracle to partition the data by customer and find the maximum date within customer. Imagine copying the original data into a spreadsheet, sorting it by customer, then using one of the spreadsheet functions to add an extra column that derives it’s value by looking at the rows that have the same customer as the current row and you’ve got an exact replica of what Oracle is doing here.

So we’ve managed to produce the same result with a single tablescan of orders instead of the two tablescans we saw in every other plan. But there’s a drawback – to be able to partition by customer Oracle has had to fetch every row and column we’re interested in and sort the data before deriving values for the new column: the cost of this plan (262) is much higher than the cost of the plan (54) we got from the previous three queries.

In this case the variation in actual run-time for the two different plans was undetectable – and insignificant compared to the time spent getting the result set to the terminal and displaying. In general, though, you need to consider the trade off between the sorting that goes into the use of analytic functions and the “double visit” work of using subqueries.

Strategy number 5:

There is (at least) one more possibility that I’ve used in the past when the data structure has allowed it to produce the right answers; and it’s the one that is the ultimate target of this blog. Consider the following SQL:


select
        customer, 
        max(id)                 keep (dense_rank last order by date_ordered) as max_id,
        max(date_ordered)       keep (dense_rank last order by date_ordered) as max_date,
--      max(padding)            keep (dense_rank last order by date_ordered) as max_padding
        trim(
                max(padding)    keep (dense_rank last order by date_ordered)
        )       as max_padding
from
        orders
group by
        customer
;

(The trim() function on the padding column doesn’t change the fundamental behaviour of this query, it’s just there to avoid line-wrapping on my output.)

I’ve written a query that does an aggregate on customer, so “customer, max() group by customer”, but it’s a variant of the analytic max() function based on “keep(dense_rank last order by …)” rather then the more familiar “over(partition by … order by …)” form.

Because of the group by customer, the max() function is applied per customer (i.e. behaving like over(partition by customer)), and we’re not actually looking for the maximum value of the referenced column, we’re first ordering by the date_ordered (within customer) applying the dense_rank mechanism, keeping only the rows that have the highest (last) dense_rank, and then taking the maximum of that subset of the data.

Here’s an example applying the combination of mechanisms to a tiny data set:

Raw data
=========
   N1           V1
-----           ---
   93           'C'
   54           'Q',
   43           'A'
   13           'X'
   93           'G'
   54           'W',

Ordered by N1 and dense_rank() appended
========================================
   N1           V1              dr()
-----           ---             ----
   13           'X'             1
   43           'A'             2
   54           'W',            3
   54           'Q',            3
   93           'G'             4
   93           'C'             4

Keep(dense rank last)
=====================
   N1           V1              dr()
-----           ---             ----
   93           'G'             4
   93           'C'             4


max(v1) keep(dense rank last order by n1)
V1
---
'G'

In this tiny example we had cases where there were multiple rows for some of the rankings, but if we go back to our orders table and guarantee (by adding a unique constraint) that a customer will never have more than one row for any one value of date_ordered, then the expression max(id) keep (dense_rank last order by date_ordered) for any one customer will be the id of the row that has the maximum order date for that customer and, similarly, max(date_ordered) keep(…), and max(padding) keep (,,,) will also be the values from that same row.

Given the (absolutely critical) uniqueness constraint, we can get the data for the most recent for the customer using this dense_rank() strategy.

The question, of course, is why would we do something that may not be entirely intuitive and looks as if it could make Oracle do a lot of extra work to get the result. Here’s the answer – which is just the execution plan for the query on my orders table – with the unique constraint added:


-------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation          | Name   | Starts | E-Rows | Cost (%CPU)| A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
-------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |        |      1 |        |    28 (100)|    200 |00:00:00.01 |     172 |       |       |          |
|   1 |  SORT GROUP BY     |        |      1 |    200 |    28  (18)|    200 |00:00:00.01 |     172 |   142K|   142K|  126K (0)|
|   2 |   TABLE ACCESS FULL| ORDERS |      1 |  10000 |    24   (5)|  10000 |00:00:00.01 |     172 |       |       |          |
-------------------------------------------------------------------------------------------------------------------------------

The path uses a basic SORT GROUP BY, that “sorts” only 200 rows (A-rows) using only 126KB of memory. Compare that with the plan for the analytic max() over() in strategy 4 that takes 1.6MB of memory and sorts 10,000 rows and you’ll appreciate that the keep(dense_rank last) mechanism is doing something much more efficient. For cases where the drop from “num_rows” to “num_distinct” for the aggregating column(s) the benefit of using the somewhat non-intuitive dense_rank() approach may make a significant difference to memory, CPU, and even (if it avoids a spill to disk) I/O.

Footnotes

There are two major variations on how you can use the dense_rank() function, as well as this form in which dense_rank appears in the KEEP LAST (and FIRST) mechanism.

Remember the absolutely critical point that the “keep dense_rank last” strategy is only correct if there is a suitable unique constraint on the data set viz: unique on ({group by column(s)},{order by column(s)}).

There is another major option for getting the same “most recent” rows, which is to use the match_recognize() functionality, but I think I probably wrote this draft before the mechanism even existed – so it’s left as an exercise to the reader to work it out.  A key reason why I’m not going to do it myself is that (like the analytic over() in strategy 4) it will require all 10,000 rows to be sorted, and is therefore likely to be less efficient than strategy 5.

Finally – I thought I’d written a note explaining why a “sort group by” can use far less memory and CPU then a basic “sort order by”, but if I have it wasn’t on this blog.  I do have a note on how the mechanism to handle “rownum <= N” with a preceding “order by” minimises its use of memory, and that note should give you some idea of what the “sort group by” is doing to minimise memory usage. I’ll try to write a little note on the aggregate mechanism some time over the next few days.

 

 

6 Comments »

  1. What you have not written Jonathan is that:

    select whatever from wherever where versionNumber = 1

    negates the necessity to rank on the date and then, however you disguise it, perform a top-1 (N) query.

    How do you get versionNumber = 1? Well when you insert a row into the orders table, the versionNumber (additional column) is 1. Prior to insertion however, a second piece of DML must be executed to “shuffle up” the existing versionNumber’s in the table. Something similar to:

    update wherever set versionNumber = versionNumber + 1 where customerId= :id

    would do the trick, either in application code, trigger, or whatever.

    A scalar versionNumber has the obvious advantage too that list partitioning on the orders table could then considered with the goal of improving performance further, and without being overly concerned about a recalcitrant CBO or unexpected changes to the execution plans between Oracle versions.

    Sadly however, as we all know, the luxury of refactoring and restructuring underlying data is rarely available to us.

    Lastly I really like this blog post Jonathan. Thank you for continuing to ever-present in your retirement.

    Mike

    Comment by /* Michael D O'Shea */ (@MichaelDOShea) — March 12, 2020 @ 7:11 pm GMT Mar 12,2020 | Reply

    • Mike,

      Thanks for the comment.

      Unfortunately I have to say that your suggestion sounds like a very bad idea. It’s 1turning one insert into multiple updates, if you want to use triggers you have the mess of working around “mutating table”, and if you try to do it from the front-end you have to worry about race conditions.

      If the query is important and has to be run frequently then it’s far better to write code that can be as efficient as possible and create indexes that support that code in the best possible way.

      If you’re going to make structural changes to support the requirement then the best option is probably to create an extra table outside the application to contain only “the most recent” row and use a “before row insert” trigger to maintain that table. Even then you’d have to think carefully about how to avoid deadlocking problems that the application might introduce through the way it’s written.

      Regards
      Jonathan Lewis

      Comment by Jonathan Lewis — March 14, 2020 @ 10:48 am GMT Mar 14,2020 | Reply

  2. Hi – A few notes and question about this.

    First, the trivial: in the last query using the LAST aggregate function, max_date can simply be max(date_ordered), you don’t need to use the LAST function for that particular column in the output.

    More seriously: The better analytic function solution uses ROW_NUMBER, or RANK or DENSE_RANK if non-unique (customer, ordered_date) – not analytic MAX. That is because with ROW_NUMBER the execution plan can use window sort PUSHED RANK; you alluded to that towards the end of the article, but I feel that that’s not enough.

    Then – for whatever reason, analytic functions that do “the same work” as the corresponding aggregate functions are (much) slower. Never mind the estimated cost – just run wall clock tests on your data, using your exact queries, and you will see the differences. I just did that, using 1 million rows in the input for better resolution. Perhaps I made mistakes in my tests; but here is what I found. The analytic MAX solution on my system takes about 45 seconds. The ROW_NUMBER solution takes about 3 seconds. The first solution in your article (scanning the base data twice) takes 0.25 seconds; surprisingly, the aggregate LAST function solution (the last one in your article here) takes longer, about 0.32 seconds. Still an order the magnitude faster than the best analytic function solutions.

    The fastest solution, written in three different ways in your article as Strategies 1, 2 and 3, is the “aggregate, then join” approach. Reading the table twice doesn’t seem like such a “defect” – much less an obvious one.

    In your table setup you commented out the creation of a unique index on (customer, date_ordered). That may make the “obviously defective” solution that much faster: use the index for the aggregate part; then use the index again to access full rows from the base table – just those that match what is returned by the aggregate subquery. This will be clear if there are only 200 customers for 1 million rows: the very fast aggregate subquery returns only 200 rows, so in the end we only need to access 200 rows in the base table. There is no such benefit with the analytic functions approach, is there? The runtime will read all 1 million rows from the base table, compute the analytic functions (either MAX or ROW_NUMBER) and proceed from there.

    Note that in this type of problem, I/O doesn’t seem to be the bottleneck; sorting does. In the “unique” case, the main benefit will come not from “only accessing 200 rows in the base table”, but from the aggregation existing already in the index. This particular point wasn’t discussed in your article; it’s why all the aggregate function solutions are faster in the “unique” case. Of course, by “unique” case I mean the constraint (or unique index) actually exists, not merely the empirical fact that the tuples are unique in the data.

    I guess my main two points are: (1) The analytic ROW_NUMBER or (DENSE_)RANK solution should be part of the discussion; and (2) wall clock comparisons should be added for a more complete analysis of the different strategies.

    Best regards, – mathguy

    Comment by mathguy — July 31, 2020 @ 11:03 pm BST Jul 31,2020 | Reply

    • Mathguy,

      Thanks for taking so much trouble with your comments.

      Taking the first point first – you’re right, of course, that I didn’t need the “keep (dense_rank last order by date_ordered) as max_date” and I don’t have any notes in my source script explaining why I haven’t used the simpler expression. This makes me think that the choice was based purely on consistency of presentation. I’ve added your variant to my copy of the script – the timing difference is negligible but it does seem to introduce a slight variation in (PGA) memory usage.

      max() vs. row_number() et. al.

      It would have been helpful if you had supplied an example of the code you were thinking of when you stated that row_number(), rank() or dense_rank() would have been a better analytic choice than max(). From your comment about “window sort pushed rank” I assume you were thinking of using row_number() roughly as follows – with plan and rowsoruce execution stats and (for the benefit of other readers) a couple of comments:

      
      select
              /*+ qb_name(main) */
              ordv.* 
      from    (
              select  /*+ qb_name(inline) */
                      customer, id, date_ordered, padding,
                      row_number() over (
                              partition by customer order by date_ordered desc
                      ) which_row
              from    orders  ord1
              )       ordv
      where
              which_row = 1
      order by
              customer
      ;
      
      -------------------------------------------------------------------------------------------------------------------------------------
      | Id  | Operation                | Name   | Starts | E-Rows | Cost (%CPU)| A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
      -------------------------------------------------------------------------------------------------------------------------------------
      |   0 | SELECT STATEMENT         |        |      1 |        |   263 (100)|    200 |00:00:00.04 |     186 |       |       |          |
      |*  1 |  VIEW                    |        |      1 |  10000 |   263   (3)|    200 |00:00:00.04 |     186 |       |       |          |
      |*  2 |   WINDOW SORT PUSHED RANK|        |      1 |  10000 |   263   (3)|    200 |00:00:00.04 |     186 |  1824K|   650K| 1621K (0)|
      |   3 |    TABLE ACCESS FULL     | ORDERS |      1 |  10000 |    25   (4)|  10000 |00:00:00.01 |     186 |       |       |          |
      -------------------------------------------------------------------------------------------------------------------------------------
      
      Predicate Information (identified by operation id):
      ---------------------------------------------------
      
         1 - filter("WHICH_ROW"=1)
         2 - filter(ROW_NUMBER() OVER ( PARTITION BY "CUSTOMER" ORDER BY INTERNAL FUNCTION("DATE_ORDERED") DESC )<=1)
      
      
      

      When compared with my use of max() the critical difference stands out fairly clearly

      --------------------------------------------------------------------------------------------------------------------------------
      | Id  | Operation           | Name   | Starts | E-Rows | Cost (%CPU)| A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
      --------------------------------------------------------------------------------------------------------------------------------
      |   0 | SELECT STATEMENT    |        |      1 |        |   262 (100)|    200 |00:00:00.01 |     172 |       |       |          |
      |*  1 |  VIEW               |        |      1 |  10000 |   262   (3)|    200 |00:00:00.01 |     172 |       |       |          |
      |   2 |   WINDOW SORT       |        |      1 |  10000 |   262   (3)|  10000 |00:00:00.01 |     172 |  1612K|   624K| 1432K (0)|
      |   3 |    TABLE ACCESS FULL| ORDERS |      1 |  10000 |    24   (5)|  10000 |00:00:00.01 |     172 |       |       |          |
      --------------------------------------------------------------------------------------------------------------------------------
       
      Predicate Information (identified by operation id):
      ---------------------------------------------------
         1 - filter("ORDV"."DATE_ORDERED"="ORDV"."MAX_DATE")
      
      

      The “pushed rank” means that the row_number() window sort doesn’t have to pass 10,000 rows to its parent – we can see the filter predicate at operation 2 which has pushed a preliminary check on row_number() to an earlier point in the execution; while the max() window sort passes 10,000 rows to its parent before any elimination can take place. (The contrary timing difference between these two plans is irrelevant – it’s quite possible that the test above was running on a different machine and different version of Oracle from the tests in the original blog note).

      Minimising traffic from child up to parent (and the general principle of early elimination) is a fundamental pattern for optimisation; so options for achieving a pushed rank are worth investigating. There is a potential downside, though, since pushed rank requires a “version 1” sort, which is less efficient than the “version 2” sort that would otherwise be used. Here, for example, is a set of stats from the “sort” trace (10032 and 10033) after scaling the data size up to nearly 1M rows (but keeping just 200 customers) in an environment where the sort spilled to disc:

      Using max()

      ---- Sort Statistics ------------------------------
      Initial runs                              2
      Intermediate runs                         1
      Number of merges                          1
      Input records                             999974
      Output records                            999974
      Disk blocks 1st pass                      15864
      Total disk blocks used                    16000
      Total number of comparisons performed     4974294
        Comparisons performed by in-memory sort 3979253
        Comparisons performed during merge      994976
        Comparisons while searching for key in-memory 65
      Number of seeks in final run              6016903
      Extents allocated                         125
      Uses version 2 sort
      Does not use asynchronous IO
      

      Using row_number()

      
      ---- Sort Statistics ------------------------------
      Initial runs                              16
      Number of merges                          1
      Input records                             999974
      Output records                            999974
      Disk blocks 1st pass                      112
      Total disk blocks used                    114
      Total number of comparisons performed     15662434
        Comparisons performed by in-memory sort 15636914
        Comparisons performed during merge      25520
      Number of seeks in final run              108468
      Temp segments allocated                   1
      Extents allocated                         1
      Uses version 1 sort
      Does not use asynchronous IO
      
      

      How one balances the huge difference (in one direction) between the number of comparisons and the huge difference (in the opposite direction) of seeks is anyone’s guess. But the upshot of the change between version 1 and vesion 2 sorting is that for difference circumstances I found that the variant with the pushed rank took a few seconds longer to complete than the variant that didn’t use the pushed rank.

      Scale up

      My demonstration involved 200 customers with 50 orders each; when you scaled up you didn’t say whether your 1M row test was 200 customers with 5,000 orders each or 20,000 customers with 50 orders each (or some variant in between the two extremes). Also, you didn’t supply any run time execution plans, so we had no indication of where your code spent its time. I have to admit to being particularly curious about the model that allowed the analytic max() example to take 45 seconds.

      As I mentioned in the previous section, in one of my tests comparing the row_number() with pushed rank with the max() approach the max() variant performed better than the row_number() variant. (The specific test involved increasing the available PGA memory to ensure that the entire sort operation could complete in memory – at which point the CPU and memory utilisation for the version 1 sort far outweighed the utilisation for the version 2 sort.)

      There is no absolute in terms of which code strategy to choose, too much is dependents on data patterns, caching effects, and the mechanical optimisations that are available to Oracle. For example, a scale up that involves a very small number of customers (such as the 200 I started with) with a large number of orders per customer may perform best as a filter subquery (which I haven’t mentioned at all) thanks to scalar subquery caching.

      Finally

      (1) The analytic ROW_NUMBER or (DENSE_)RANK solution should be part of the discussion

      The article was a brief outline of strategies, aiming to introduce the less well-known “dense rank keep first/last” mechanism that doesn’t seem to be very well known – it wasn’t intended as an intense examination of the costs and benefits of different analytic functions. Your comment about the “pushed rank” option was a help add-on though, (and the observation about the max(date_ordered) will probably answer the question that some readers may well be curious about but fail to ask.

      (2) wall clock comparisons should be added for a more complete analysis of the different strategies

      I’ve already done better than that. I’ve supplied the rowsource execution statistics showing what the time was spent on. Of course, with the tiny data set used to demonstrate the principles I can only remind you of the comment I made: In this case the variation in actual run-time for the two different plans was undetectable – and insignificant compared to the time spent getting the result set to the terminal and displaying

      You might note, by the way, that if I thought that visiting a table twice to satisfy a query should inevitably be regarded as a defect I wouldn’t have used the double-quotes to identify ‘the “obvious” defect’ nor would I have written: In general, though, you need to consider the trade off between the sorting that goes into the use of analytic functions and the “double visit” work of using subqueries (nor would I have written some articles several years ago explaining how sometimes you can improve performance significantly by rewriting your SQL to reference the same table twice.)

      Regards
      Jonathan Lewis

      Comment by Jonathan Lewis — August 3, 2020 @ 4:12 pm BST Aug 3,2020 | Reply

      • Hi, – Thank you so much for the thorough reply.

        Top-N query using ROW_NUMBER and such: yes, indeed, that is what I meant. I believe that is considered the standard way to use ranking analytic functions for top-N queries.

        My million-row test case: I had 200 customers with 5,000 orders each. I didn’t state it explicitly, and I should have; I did refer to “200 customers vs. 1 million rows” later, in a few places. To reproduce my scenario you may also need to know how much memory I had (if I am reading things correctly: 4.8 GB allocated to SGA, 2.7 GB to PGA) and perhaps other things too. I just re-ran the test for the MAX() analytic function approach (with 200 customers, 5,000 orders each) and I still get the same ~45 second execution time. I have to wonder: this can’t simply be caused by paging (most of) the 1 million rows to disk when they are passed from child process to parent, and then reading them again to apply the outer filter. After all, all solutions read all 1 million rows from disk once, and some solutions take less than 1 second. It’s, perhaps, more related to HOW those rows are passed between the processes, and/or how they are paged to disk. I can imagine that something that happens one row at a time, or only a few rows (say, 50 rows) at a time, might cause that kind of slow-down. But I am only speculating about things I know very little about.

        The comment about the ordering algorithm used with the PUSHED RANK filter deserves some discussion (not in this article – agreed.) If I understand correctly, Oracle for a long time used one of the stable ordering algorithms, and at some point they introduced an unstable (and faster and less resource-hungry, due to less overhead) ordering algorithm. For some reason, they chose to still use the old, stable version when ranking analytic functions are used in top-N queries – perhaps so that the output from old queries will remain the same in newer versions of the database (which use the newer ordering algorithm otherwise). By the way, that makes zero sense for RANK() and DENSE_RANK() – even if it does for ROW_NUMBER(), for example for the backward compatibility reason I just mentioned. But that is something for Oracle to consider – certainly out of scope for your article. I did check, though, and using RANK() in a top-N query does indeed still use “version 1” ordering.

        I thought a bit more also about what may make the aggregate solution using the FIRST/LAST function to be slower than the aggregate MAX solution, even though the latter reads the base data twice. It must be, I believe, the SORT GROUP BY. For some reason that I don’t understand, the FIRST/LAST function forces the optimizer to use SORT GROUP BY instead of HASH GROUP BY – even if hinted with use_hash_aggregation. One may point out that FIRST/LAST has a required ORDER BY clause and that justifies SORT GROUP BY, but that is a bad argument. The grouping is by one column; the ordering in the FIRST/LAST function is by a different column. The query engine should hash group by customer, and within each group order by something else however it pleases; one has nothing to do with the other. That may be enough to explain the observed timing difference. I assume all these speculations can be confirmed – or not – by looking at execution statistics.

        Curiosity got the best of me – I recreated the table with 20,000 customers, 50 orders each. The analytic MAX() approach still takes 45-46 seconds, but the ROW_NUMBER() approach, as expected, takes longer now, about 12 seconds on my system. Still significantly better than the analytic MAX() solution though. The time for the LAST aggregate function approach more than doubled, to 0.7 seconds. “Strategy 1” (read the base data twice, use aggregate MAX in subquery) is still fastest at 0.45 seconds, and still two orders of magnitude faster than the analytic MAX() approach.

        Best regards, – mathguy

        Comment by mathguy — August 5, 2020 @ 6:29 am BST Aug 5,2020 | Reply

  3. mathguy,

    Thanks for the detailed follow-up, and apologies for taking so long to reply to it.

    One of the plus points of blogging is that it can lead to interesting and important points showing up in the comments either extending the scope of the original or supplying warnings about oversights of special cases. The downside, of course, is that it’s possible to end up with a long and fragmented discusions as related points appear – and a desire to write a whole new blog note covering what might have started as a brief side comment. Given the number of posts you’ve made on the ODC forum that look more like blog articles I’d really like to see you start a blog on your Oracle investigations – some of the stuff you’re written is well worth referencing from time to time, but can be very hard to find from an internet search.

    Your comments here prompt all sorts of ideas of “things I might investigate”

    The available memory could make a big difference to the test times; counter-intuitively a large version 1 sort that completes in memory can take longer than the equivalent sort if you constrain it to the minimum amount of memory that will allow it to spill to disc as a “one-pass” sort. In part it’s the nature of the algorithm, in part it’s the need to allocate memory incrementally while following the code path Oracle has for monitoring PGA allocation to sessions. When demanding large PGA allocations in the past I’ve surprisingly large amounts of time lost in “acknowledge over PGA limit”.

    There are a few notes about the V1 sort in a note I wrote in 2009: https://jonathanlewis.wordpress.com/2009/10/01/_smm_isort_cap if you’re interested. I won’t guarantee that the details are 100% correct, though since they were deductions based on running a number of test cases. I remember reading a note somewhere on which algorithm the v2 sort used, but I can’t remember what it was at present.

    “One may point out that FIRST/LAST has a required ORDER BY clause and that justifies SORT GROUP BY, but that is a bad argument.”

    As an outsider looking in it’s hard for me to guess what goes on inside the development teams, but there seem to be two common patterns that leave me wondering why some pieces of code behave the way they do.

      One is the “code re-use” pattern:

    1. “I’ve got a new requirement but it’s so similar to an existing requirement that I’ll hijack the function calls and piggy-back on the existing code – it’s not the best way of doing it but it reduces the development time and testing time.”
    2. The other is “generic code” pattern – which might be visible in some of the analytic stuff:

    3. “I’ve to 20 different functions to deal with but I can manage to handle them all with the same basic code. If anyone (important) comes up with a serious complaint about efficiency I’ll code up special cases as required.”

    Sometimes, of course, anomalies like this “why did a hash group by change to a sort group by” can be answered as “maybe it’s a simple bug”. Maybe there’s some code which uses a flag to say “switch to sort group by” and it gets set when certain conditions are met – but with the passing of time cases have arisen where the conditions are met but the flag doesn’t need to be set.

    Regards
    Jonathan Lewis

    Comment by Jonathan Lewis — August 22, 2020 @ 4:01 pm BST Aug 22,2020 | Reply


RSS feed for comments on this post. TrackBack URI

Comments and related questions are welcome.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Powered by WordPress.com.