# Efficiently finding distinct values

I have a number of tables with the primary key (month, year, number) and differing cardinalities differ somewhat. For the tuple (month, year) the history doesn't go back very far, this will probably not grow beyond 50 in the very long term. For every (month, year) tuple there are not more than 2 million unique numbers. I want to know which combinations of month and years are available. I do this using this query:

`select month, year from table group by month, year`

This returns the correct result but does not seem to be very efficient. What is an efficient way to obtain this result (utilizing the unique index)?

The tuning advisor suggests to add an index on month-year for this query but this seems wasteful because a larger index is already available.

-
The index is not going to be useful for filtering because you need to scan all rows. There are marginal effects where the index might help - a FIS may beat an FTS, the pre-sort might make `distinct` cheaper but in 10g+ it probably won't. Can you give us an idea of cardinalities? how many rows per (month, year)? – Jack Douglas Jan 23 '12 at 9:29
Thanks, I added some more information to the question. – Bob Jansen Jan 23 '12 at 9:49

You may be able to use a variation of the following technique - which forces repeated 'MIN/MAX' range scans:

Assumptions

1. You can produce a list of all possible year/month combinations
2. `number` is not null (which it can't be as it is in the PK, but I mention it as there is a way of working around if nulls are permitted)

testbed:

``````create table foo(month, year, num, primary key(month, year, num)) as
with m as ( select extract(month from d) as month, extract(year from d) as year
from (select add_months(sysdate,1-level) as d from dual connect by level<50) )
select month, year, num
from m cross join
(select level as num from dual connect by level<100000 order by dbms_random.random());
``````

normal query:

``````select distinct month, year from foo;
--gets=11656
``````

min/max technique:

``````with m as ( select extract(month from d) as month, extract(year from d) as year
from (select add_months(sysdate,1-level) as d from dual connect by level<50) )
select month, year, decode(( select min(num)
from foo
where month=m.month and year=m.year )
,null, 'N', 'Y') as has_data_yn
from m;
--gets=294
``````

Some explanation in response to comments:

In each case (the testbed and the min/max query), the subquery factoring clause just generated a list of (year, month) tuples:

``````with m as ( select extract(month from d) as month, extract(year from d) as year
from (select add_months(sysdate,1-level) as d from dual connect by level<50) )
select * from m;
/*
MONTH                  YEAR
---------------------- ----------------------
1                      2012
12                     2011
11                     2011
10                     2011
...
...
*/
``````

Then the technique uses a subquery in the `select` clause to check if any rows are present for the (month, year) - this subquery necessarily must only produce at most 1 row:

``````select min(num)
from foo
where month=m.month and year=m.year;
``````

This is very quick because it makes use of the ordered nature of the PK - however it needs to be executed once for each month - if there are millions of rows for each month that makes sense, but not if there are few enough to fit in a small number of block.

-
Your solution is a bit over my head but I figured it out. Works like a charm! – Bob Jansen Jan 23 '12 at 12:28
Which bits were hard to decipher? I'll try and add some comments so it's more useful to others... – Jack Douglas Jan 23 '12 at 12:40
The statement is pretty long and I'm not familiar with all the idioms (my background is CRUD MySQL apps). I had to look up `with m as` and the decode function. With some Googling I managed OK. So you're answer is really fine, I just missed some basic knowledge. I do wonder why the database can't optimize the query by itself. I imagine a binary tree starting with month and then year. Checking which (month, year) tuples exist seems so easy. – Bob Jansen Jan 23 '12 at 18:03
I wonder that too :-) – Jack Douglas Jan 23 '12 at 18:11

Here is a solution using the same technique as the one from Jack Douglas (+1). It produces an identical number of consistent gets using his testbed, but whether it is easier to understand or not would be in the eye of the beholder.

``````SELECT extract(month from d) m, extract(year from d) y
FROM (SELECT add_months(sysdate,1-level) d FROM dual CONNECT BY level < 50)
WHERE EXISTS (
SELECT 1 FROM foo WHERE month=extract(month from d) AND year=extract(year from d)
);
``````

This option uses the select from dual to drive the query and the select from foo only to decide which dates to keep.

The same query could also be written as this:

``````SELECT * FROM (
FROM dual CONNECT BY level < 50)
WHERE EXISTS (
SELECT 1 FROM foo WHERE month=m AND year=y
);
``````
-
Much easier to understand, +1. Is there any danger of the CBO rewriting as a hash/merge semi-join? It never seems to do anything like that with a subquery in the `select`. – Jack Douglas Jan 24 '12 at 15:04
Thanks, +1. A nice alternative. – Bob Jansen Jan 24 '12 at 15:32
@Jack Good question, I don't know. – Leigh Riffel Jan 24 '12 at 15:33
In this case this solution has the added benefit that it's much more efficient if there is only a sorted index on (month, year, number) instead of a unique constraint. Of course YMMV. – Bob Jansen Jan 25 '12 at 21:17