Re: top N or rewriting MAX

Komix Hui wrote:
>
> Roger Wernersson wrote:
> >
> > Roger Wernersson wrote:
> > > otierney_at_freenet.edmonton.ab.ca wrote:
> > > > Does anyone know of good (ie FAST) ways of getting the top
> > > > N rows in a table?
> > > This is actually quite simple. This example assumes you have a table
> > > MY_TABLE with a numeric column VALUE. The SELECT statement will give you
> > > the two lowest values.
> >
> > You stupid! You are dead wrong! It is much simpler to create a view with
> > a GROUP BY clause and then use ROWNUM to get the lowest values, though
> > you might be in for some trouble if you want the highest ones.
> >
> > CREATE VIEW test_view AS
> > SELECT value
> > FROM test
> > GROUP BY value;
> >
> > SELECT value
> > FROM test
> > WHERE ROWNUM < 10;
>
> Before you say other people stupid, you should be sure your answer is
> correct.
>
> I do not think your answer will work.
>
> Try this:
>
> SELECT Column_1
> FROM Table_1 A
> WHERE 10 < (SELECT COUNT(*)
> FROM Table_1 B
> WHERE A.Column > B.Column);
>
> to select top 10 rows.
>
> If 'column_1' is not unique, you should adjust the statement with '>='
> and '<='.

Strictly speaking, your answer will not work either. It will return 9 rows, not 10. His answer _does_ work, sort of (you may want to try a suggested solution before rejecting it), except that it also will return only 9 rows, not 10, and it only works for ascending sequence values (where we need the bottom 10, not the top 10). It also has the disadvantage of ignoring 10th place "ties". The key is that GROUP BY _is_ allowed in a view, even though ORDER BY is not.

In any case, your solution, though elegant, is _extremely_ slow on large tables where the column in question is not indexed. In fact, given N rows in the table, this query will cause N^2 full table scans to get the result.

The following answer will return a fast result, relatively speaking, and has the advantage of working for ascending or descending searches, for alphabetic or numeric columns, with just a little bit of trickery. On my HP/UX box here, with a table containing 83,000 rows, this returned the desired result in 1 minute, 50 seconds. I cancelled your query after a half hour of waiting.

Assume the following table:

    CREATE TABLE my_table(

     my_key           VARCHAR2(10) NOT NULL,
     my_alpha_column  NUMBER       NOT NULL,
     my_number_column NUMBER       NOT NULL);

I'll start with the easiest type of query, which is a "bottom 10" query of either a numeric or text column:

    CREATE VIEW my_ascending_view AS

        SELECT     my_number_column
              FROM my_table
          GROUP BY my_number_column;

    SELECT * FROM my_table
     WHERE my_number_column <=
            (SELECT MAX(my_number_column) FROM my_ascending_view
              WHERE rownum <= 10);

A "top 10" query on a numeric field is slightly tricky. There are several different ways to use this technique, depending on personal preference. This is just one of them:

    CREATE VIEW my_descending_numeric_view AS

        SELECT     -my_number_column groupbykey,
                   my_number_column
              FROM my_table
          GROUP BY -my_number_column,
                   my_number_column;

    SELECT * FROM my_table
        WHERE my_number_column >=
               (SELECT MIN(my_number_column) FROM
my_descending_numeric_view
                 WHERE rownum <= 10)
        ORDER BY my_number_column DESC;

Lastly, text field top 10 lists may be constructed using this method and a bit more sleight-of-hand. For simplicity, this example deals with text fields that contain upper-case alphabetic, numeric, or blank characters only. It can easily be expanded to cover any printable character.

    CREATE VIEW my_descending_alpha_view AS

        SELECT     TRANSLATE(my_alpha_column,
                             ' 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ',
                             'ZYXWVUTSRQPONMLKJIHGFEDCBA9876543210 ')
groupbykey,
                   my_alpha_column
              FROM my_table
          GROUP BY TRANSLATE(my_alpha_column,
                             ' 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ',
                             'ZYXWVUTSRQPONMLKJIHGFEDCBA9876543210 '),
                   my_alpha_column;

    SELECT * FROM my_table
        WHERE my_alpha_column >=
            (SELECT MIN(my_alpha_column) FROM my_descending_alpha_view
                 WHERE rownum <= 10)
        ORDER BY my_alpha_column DESC;

I hope there are no typos here; I've transcribed it into a more generic version than the one I have ... if there's a typo here, point it out I'll be glad to fix it, but trust me, this method works. And it's fast.

-- 

========================================================================
John Verbil                          | e-mail: jverbil_at_uswest.com
U S WEST Information Technologies    | voice:  (303) 896-0916
Member of the Technical Staff        | fax:    (303) 896-7825
Technical Lead, Forecaster           | 1005 17th Street, Room 1340
                                     | Denver, Colorado  80202
========================================================================