Faster 'select distinct thing_id,thing_name from table1' in oracle

Question

I have this query:

select distinct id,name from table1

For a given ID, the name will always be the same. Both fields are indexed. There's no separate table that maps the id to the name. The table is very large (10 of millions of rows), so the query could take some time.

This query is very fast, since it's indexed:

select distinct name from table1

Likewise for this query:

select distinct id from table1

Assuming I can't get the database structure changed (a very safe assumption) what's a better way to structure the first query for performance?

Edit to add a sanitized desc of the table:

Name                           Null     Type
------------------------------ -------- ----------------------------
KEY                            NOT NULL NUMBER
COL1                           NOT NULL NUMBER
COL2                           NOT NULL VARCHAR2(4000 CHAR)
COL3                           VARCHAR2(1000 CHAR)
COL4                           VARCHAR2(4000 CHAR)
COL5                           VARCHAR2(60 CHAR)
COL6                           VARCHAR2(150 CHAR)
COL7                           VARCHAR2(50 CHAR)
COL8                           VARCHAR2(3 CHAR)
COL9                           VARCHAR2(3 CHAR)
COLA                           VARCHAR2(50 CHAR)
COLB                           NOT NULL DATE
COLC                           NOT NULL DATE
COLD                           NOT NULL VARCHAR2(1 CHAR)
COLE                           NOT NULL NUMBER
COLF                           NOT NULL NUMBER
COLG                           VARCHAR2(600 CHAR)
ID                             NUMBER
NAME                           VARCHAR2(50 CHAR)
COLH                           VARCHAR2(3 CHAR)

20 rows selected

Answer 1

[LATEST EDIT]

My ORIGINAL ANSWER regarding creating the appropriate index on (name,id) to replace the index on (name) is below. (That wasn't an answer to the original question, which disallowed any database changes.)

Here are statements that I have not yet tested. There's probably some obvious reason these won't work. I'd never actually suggest writing statements like this (at the risk of being drummed thoroughly for such ridiculous suggestion.)

If these queries even return result sets, the ressult set will only resemble the result set from the OP query, almost by accident, taking advantage of a quirky guarantee about the data that Don has provided us. This statement is NOT equivalent to the original SQL, these statements are designed for the special case as described by Don.

 select m1.id
      , m2.name
   from (select min(t1.rowid) as min_rowid
              , t1.id
           from table1 t1
          where t1.id is not null
          group by t1.id
        ) m1
      , (select min(t2.rowid) as min_rowid
             , t2.name from table1 t2
         where t2.name is not null
         group by t2.name
        ) m2
  where m1.min_rowid = m2.min_rowid
  order
     by m1.id

Let's unpack that:

• m1 is an inline view that gets us a list of distinct id values.
• m2 is an inline view that gets us a list of distinct name values.
• materialize the views m1 and m2
• match the ROWID from m1 and m2 to match id with name

Someone else suggested the idea of an index merge. I had previously dismissed that idea, an optimizer plan to match 10s of millions of rowids without eliminating any of them.

With sufficiently low cardinality for id and name, and with the right optimizer plan:

 select m1.id
      , ( select m2.name
            from table1 m2
           where m2.id = m1.id
             and rownum = 1
        ) as name
   from (select t1.id
           from table1 t1
          where t1.id is not null
          group by t1.id
        ) m1
  order
     by m1.id

Let's unpack that

• m1 is an inline view that gets us a list of distinct id values.
• materialize the view m1
• for each row in m1, query table1 to get the name value from a single row (stopkey)

IMPORTANT NOTE

These statements are FUNDAMENTALLY different that the OP query. They are designed to return a DIFFERENT result set than the OP query. The happen to return the desired result set because of a quirky guarantee about the data. Don has told us that a name is determined by id. (Is the converse true? Is id determined by name? Do we have a STATED GUARANTEE, not necessarily enforced by the database, but a guarantee that we can take advantage of?) For any ID value, every row with that ID value will have the same NAME value. (And we are also guaranteed the converse is true, that for any NAME value, every row with that NAME value will have the same ID value?)

If so, maybe we can make use of that information. If ID and NAME appear in distinct pairs, we only need to find one particular row. The "pair" is going to have a matching ROWID, which conveniently happens to be available from each of the existing indexes. What if we get the minimum ROWID for each ID, and get the minimum ROWID for each NAME. Couldn't we then match the ID to the NAME based on the ROWID that contains the pair? I think it might work, given a low enough cardinality. (That is, if we're dealing with only hundreds of ROWIDs rather than 10s of millions.)

[/LATEST EDIT]

[EDIT]

The question is now updated with information concerning the table, it shows that the ID column and the NAME column both allow for NULL values. If Don can live without any NULLs returned in the result set, then adding the IS NOT NULL predicate on both of those columns may enable an index to be used. (NOTE: in an Oracle (B-Tree) index, NULL values do NOT appear in the index.)

[/EDIT]

ORIGINAL ANSWER:

create an appropriate index

create index table1_ix3 on table_1 (name,id) ... ;

Okay, that's not the answer to the question you asked, but it's the right answer to fixing the performance problem. (You specified no changes to the database, but in this case, changing the database is the right answer.)

Note that if you have an index defined on (name,id), then you (very likely) don't need an index on (name), sine the optimizer will consider the leading name column in the other index.

(UPDATE: as someone more astute than I pointed out, I hadn't even considered the possibility that the existing indexes were bitmap indexes and not B-tree indexes...)

---

Re-evaluate your need for the result set... do you need to return id, or would returning name be sufficient.

select distinct name from table1 order by name;

For a particular name, you could submit a second query to get the associated id, if and when you needed it...

select id from table1 where name = :b1 and rownum = 1;

---

If you you really need the specified result set, you can try some alternatives to see if the performance is any better. I don't hold out much hope for any of these:

select /*+ FIRST_ROWS */ DISTINCT id, name from table1 order by id;

or

select /*+ FIRST_ROWS */ id, name from table1 group by id, name order by name;

or

select /*+ INDEX(table1) */ id, min(name) from table1 group by id order by id;

UPDATE: as others have astutely pointed out, with this approach we're testing and comparing performance of alternative queries, which is a sort of hit or miss approach. (I don't agree that it's random, but I would agree that it's hit or miss.)

UPDATE: tom suggests the ALL_ROWS hint. I hadn't considered that, because I was really focused on getting a query plan using an INDEX. I suspect the OP query is doing a full table scan, and it's probably not the scan that's taking the time, it's the sort unique operation (<10g) or hash operation (10gR2+) that takes the time. (Absent timed statistics and event 10046 trace, I'm just guessing here.) But then again, maybe it is the scan, who knows, the high water mark on the table could be way out in a vast expanse of empty blocks.

It almost goes without saying that the statistics on the table should be up-to-date, and we should be using SQL*Plus AUTOTRACE, or at least EXPLAIN PLAN to look at the query plans.

But none of the suggested alternative queries really address the performance issue.

It's possible that hints will influence the optimizer to chooze a different plan, basically satisfying the ORDER BY from an index, but I'm not holding out much hope for that. (I don't think the FIRST_ROWS hint works with GROUP BY, the INDEX hint may.) I can see the potential for such an approach in a scenario where there's gobs of data blocks that are empty and sparsely populated, and ny accessing the data blocks via an index, it could actually be significantly fewer data blocks pulled into memory... but that scenario would be the exception rather than the norm.

---

UPDATE: As Rob van Wijk points out, making use of the Oracle trace facility is the most effective approach to identifying and resolving performance issues.

Without the output of an EXPLAIN PLAN or SQL*Plus AUTOTRACE output, I'm just guessing here.

I suspect the performance problem you have right now is that the table data blocks have to be referenced to get the specified result set.

There's no getting around it, the query can not be satisfied from just an index, since there isn't an index that contains both the NAME and ID columns, with either the ID or NAME column as the leading column. The other two "fast" OP queries can be satisfied from index without need reference the row (data blocks).

Even if the optimizer plan for the query was to use one of the indexes, it still has to retrieve the associated row from the data block, in order to get the value for the other column. And with no predicate (no WHERE clause), the optimizer is likely opting for a full table scan, and likely doing a sort operation (<10g). (Again, an EXPLAIN PLAN would show the optimizer plan, as would AUTOTRACE.)

I'm also assuming here (big assumption) that both columns are defined as NOT NULL.

You might also consider defining the table as an index organized table (IOT), especially if these are the only two columns in the table. (An IOT isn't a panacea, it comes with it's own set of performance issues.)

---

You can try re-writing the query (unless that's a database change that is also verboten) In our database environments, we consider a query to be as much a part of the database as the tables and indexes.)

Again, without a predicate, the optimizer will likely not use an index. There's a chance you could get the query plan to use one of the existing indexes to get the first rows returned quickly, by adding a hint, test a combination of:

select /*+ INDEX(table1) */ ...
select /*+ FIRST_ROWS */ ...
select /*+ ALL_ROWS */ ...

  distinct id, name from table1;
  distinct id, name from table1 order by id;
  distinct id, name from table1 order by name;
  id, name from table1 group by id, name order by id;
  id, min(name) from table1 group by id order by id;
  min(id), name from table1 group by name order by name;

With a hint, you may be able to influence the optimizer to use an index, and that may avoid the sort operation, but overall, it make take more time to return the entire result set.

(UPDATE: someone else pointed out that the optimizer might choose to merge two indexes based on ROWID. That's a possibility, but without a predicate to eliminate some rows, that's likely going to be a much more expensive approach (matching 10s of millions ROWIDs) from two indexes, especially when none of the rows are going to be excluded on the basis of the match.)

But all that theorizing doesn't amount to squat without some performance statistics.

---

Absent altering anything else in the database, the only other hope (I can think of) of you speeding up the query is to make sure the sort operation is tuned so that the (required) sort operation can be performed in memory, rather than on disk. But that's not really the right answer. The optimizer may not be doing a sort operation at all, it may be doing a hash operation (10gR2+) instead, in which case, that should be tuned. The sort operation is just a guess on my part, based on past experience with Oracle 7.3, 8, 8i, 9i.)

A serious DBA is going to have more issue with you futzing with the SORT_AREA_SIZE and/or HASH_AREA_SIZE parameters for your session(s) than he will in creating the correct indexes. (And those session parameters are "old school" for versions prior to 10g automatic memory management magic.)

Show your DBA the specification for the result set, let the DBA tune it.

Answer 2

If for a given id the same name is always returned, you can run the following:

SELECT  (
        SELECT  name
        FROM    table1
        WHERE   id = did
                AND rownum = 1
        )
FROM    (
        SELECT  DISTINCT id AS did
        FROM    table1
        WHERE   id IS NOT NULL
        )

Both queries will use the index on id.

If you still need the NULL values, run this:

SELECT  (
        SELECT  name
        FROM    table1
        WHERE   id = did
                AND rownum = 1
        )
FROM    (
        SELECT  DISTINCT id AS did
        FROM    table1
        WHERE   id IS NOT NULL
        )
UNION   ALL
SELECT  NULL, name
FROM    table1
WHERE   id IS NULL
        AND rownum = 1

This will be less efficient, since the second query doesn't use indexes, but it will stop on the first NULL it encounters: if it's close to the beginning of the tables, then you're lucky.

See the entry in my blog for performance details:

• Distinct pairs

Answer 3

This may perform better. It assumes that, as you said, the name is always the same for a given id.

WITH id_list AS (SELECT DISTINCT id FROM table1)
SELECT id_list.id, (SELECT name FROM table1 WHERE table1.id = id_list.id AND rownum = 1)
  FROM id_list;

Answer 4

Really try to work something out with the DBAs. Really. Attempt to communicate the benefits and ease their fears of degraded performance.

Got a development environment/database to test this stuff?

How timely must the data be?

How about a copy of the table already grouped by id and name with proper indexing? A batch job could be configured to refresh your new table once a night.

But if that doesn't work out...

How about exporting all of the id and name pairs to an alternate database where you can group and index to your benefit and leave the DBAs with all of their smug rigidness?

Answer 5

"The table is very large (10 of millions of rows)" If you can't change the database (add index etc). Then your query will have no choice but to read the entire table. So firstly, determine how long that takes (ie time the SELECT ID,NAME FROM TABLE1). You won't get it any quicker than that. The second step it has to do is the DISTINCT. In 10g+ that should use a HASH GROUP BY. Prior to that it is a SORT operation. The former is quicker. If your database is 9i, then you MAY get an improvement by copying the 10 million rows into a 10g database and doing it there. Alternatively, allocate gobs of memory (google ALTER SESSION SET SORT_AREA_SIZE). That may harm other processes on the database, but then your DBAs aren't giving you much option.

Answer 6

A query cannot be tuned by looking at it, or randomly suggesting some equivalent queries, regardless how well meant they are.

You, we or the optimizer needs to know statistics about your data. And then you can measure with tools like EXPLAIN PLAN or SQLTrace/tkprof or even the simple autotrace tool from SQLPlus.

Can you show us the output of this:

set serveroutput off
select /*+ gather_plan_statistics */ distinct id,name from table1;
select * from table(dbms_xplan.display_cursor(null,null,'allstats last'));

And how does your entire table1 look like? Please show a describe output.

Regards, Rob.

Answer 7

You could try something like

Select Distinct t1.id, t2.name
FROM (Select Distinct ID From Table) As T1
INNER JOIN table t2 on t1.id=t2.id

Select distinct t1.id, t2.name from table t1
inner Join table t2 on t1.id=t2.id

Not sure if this will work out slower or faster than the original as I'm not completely understanding how your table is set up. If each ID will always have the same name, and ID is unique, I don't really see the point of the distinct.

Answer 8

Is id unique? If so, you could drop DISTINCT from the query. If not - maybe it needs a new name? Yeah, I know, can't change the schema...

Answer 9

Why do you need to even have "name" in the clause if the name is always the same for a given id? (nm...you want the name you aren't just checking for existence)

SELECT name, id FROM table WHERE id in (SELECT DISTINCT id FROM table)?

Don't know if that helps...

Answer 10

Without wishing to indulge in the practice of throwing stuff at the wall until something sticks, try this:

select id, name from table1 group by id, name

I have vague memories of a GROUP BY being inexplicably quicker than a DISTINCT.

Answer 11

You could try this:

select id, max(name) from table1 group by id

This uses the index on id for sure, but you have to try if it performs fast.