6.4 allows to use ORDER BY with a column that does not appear 
in a target list. This is great. However, following result seems
strange to me. Sometimes DISTINCT does not remove duplication.
Is this normal behavior?

create table dtest (i text, j date, k int);
CREATE
insert into dtest values ('a', '1998/12/1', 1);
INSERT 215243 1
insert into dtest values ('a', '1998/12/2', 2);
INSERT 215244 1
insert into dtest values ('a', '1998/12/3', 3);
INSERT 215245 1
select * from dtest;
i|         j|k
-+----------+-
a|12-01-1998|1
a|12-02-1998|2
a|12-03-1998|3
(3 rows)

select distinct i from dtest;
i
-
a
(1 row)

select distinct i from dtest order by j;
i
-
a
a
a
(3 rows)

select distinct i from dtest order by k;
i
-
a
a
a
(3 rows)

--
Tatsuo Ishii
t-ishii@sra.co.jp


Sun, 8 Nov 1998 08:51:22 +0900
t-ishii@sra.co.jp (Tatsuo Ishii)
distinct + order by
t-ishii@sra.co.jp (Tatsuo Ishii) writes:
> 6.4 allows to use ORDER BY with a column that does not appear 
> in a target list. This is great. However, following result seems
> strange to me. Sometimes DISTINCT does not remove duplication.
> Is this normal behavior?

I think there's something funny going on, but it's not clear that
this kind of query is sensible anyway.

It's easy to see what's happening.  DISTINCT relies on sorting by the
"distinct" column first, so that a pass of a uniq(1)-like duplicate
detector can get rid of the duplicates:

tree=> explain select distinct i from t;
NOTICE:  QUERY PLAN:

Unique  (cost=545.65 size=0 width=0)
  ->  Sort  (cost=545.65 size=0 width=0)
        ->  Seq Scan on t  (cost=545.65 size=11262 width=4)

EXPLAIN

Now, if we add an ORDER BY:

tree=> explain select distinct i from t order by j;
NOTICE:  QUERY PLAN:

Unique  (cost=545.65 size=0 width=0)
  ->  Sort  (cost=545.65 size=0 width=0)
        ->  Seq Scan on t  (cost=545.65 size=11262 width=12)

EXPLAIN

Oops.  The sort is evidently being done on the order-by column,
thus there's no guarantee that the duplicate i values will be
brought together.

Still, I'd expect the Unique pass to get rid of duplicates that did
manage to be adjacent.  Your example shows that that's not happening.
So Unique has some unexpected dependency on how the prior sort pass
is done.  (Maybe it assumes that the sort pass is on *exactly* the
columns that were requested to be distinct, and re-uses the sort's
comparison results somehow?)

It seems clear that the query tree builder and the Unique executor
have different assumptions about how this is supposed to work.  That
probably will yield bugs, so it needs to be looked at.

But I'm not convinced that the example you give is a sensible query
at all.  If you have done a SELECT DISTINCT on column A, what does it
mean to specify that the results are sorted by column B?  A single row
of the result might represent many table rows with different values of
column B --- how should the system know which of those B values to use
for sorting the result?

My guess is that if you look into the SQL standard, this combination
is forbidden.  Thus the *real* bug is that Postgres isn't rejecting it.

I'd still recommend that someone take a close look at how this example
is behaving now, because even if it should be kicked out as a user
error, there might be related legal cases that are also having trouble.

If we did want to make this example behave in a rational way, then
probably the right implementation is something like

	* sort by i,j
	* distinct-filter on i only, being careful to keep first row
		in each set of duplicates
	* sort by j

This would ensure that the final sort by j uses, for each distinct i,
the lowest of the j-values associated with that i.  This is a totally
arbitrary decision, but at least it will give reproducible results.

			regards, tom lane

Sun, 08 Nov 1998 11:16:37 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: [HACKERS] distinct + order by 
I said:
> If we did want to make this example behave in a rational way, then
> probably the right implementation is something like
> 	* sort by i,j
> 	* distinct-filter on i only, being careful to keep first row
> 		in each set of duplicates
> 	* sort by j
> This would ensure that the final sort by j uses, for each distinct i,
> the lowest of the j-values associated with that i.  This is a totally
> arbitrary decision, but at least it will give reproducible results.

Some closer probing with "explain verbose" shows that
"SELECT DISTINCT i FROM dtest ORDER BY j" is actually transformed
into this:

Unique on i,j  (cost=1.10 size=0 width=0)
  ->  Sort by i,j  (cost=1.10 size=0 width=0)
        ->  Seq Scan on dtest selecting i,j  (cost=1.10 size=3 width=16)

This explains why you get the apparently duplicate i values --- they're
not duplicate when both i and j are considered.

It looks to me like someone tried to make the query tree builder deal
with this case in the way I suggest above, but didn't finish the job.
The "Unique" pass is being done on the wrong targets, and there's no
final sort.

			regards, tom lane

Sun, 08 Nov 1998 12:06:59 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: [HACKERS] distinct + order by 
> I said:
> > If we did want to make this example behave in a rational way, then
> > probably the right implementation is something like
> > 	* sort by i,j
> > 	* distinct-filter on i only, being careful to keep first row
> > 		in each set of duplicates
> > 	* sort by j
> > This would ensure that the final sort by j uses, for each distinct i,
> > the lowest of the j-values associated with that i.  This is a totally
> > arbitrary decision, but at least it will give reproducible results.
> 
> Some closer probing with "explain verbose" shows that
> "SELECT DISTINCT i FROM dtest ORDER BY j" is actually transformed
> into this:
> 
> Unique on i,j  (cost=1.10 size=0 width=0)
>   ->  Sort by i,j  (cost=1.10 size=0 width=0)
>         ->  Seq Scan on dtest selecting i,j  (cost=1.10 size=3 width=16)
> 
> This explains why you get the apparently duplicate i values --- they're
> not duplicate when both i and j are considered.
> 
> It looks to me like someone tried to make the query tree builder deal
> with this case in the way I suggest above, but didn't finish the job.
> The "Unique" pass is being done on the wrong targets, and there's no
> final sort.

I have added this to TODO:

	* SELECT DISTINCT i FROM dtest ORDER BY j generates strange output


-- 
  Bruce Momjian                        |  http://www.op.net/~candle
  maillist@candle.pha.pa.us            |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Sat, 12 Dec 1998 15:33:13 -0500 (EST)
Bruce Momjian <maillist@candle.pha.pa.us>
Re: [HACKERS] distinct + order by