Functionally dependent columns in SELECT DISTINCT

From: Willow Chargin <postgresql(at)wchargin(dot)com>
To: pgsql-general(at)postgresql(dot)org
Subject: Functionally dependent columns in SELECT DISTINCT
Date: 2024-09-13 05:20:10
Message-ID: CAALRJs5ne=gPYG=FdeY-G0p9QyjXHhPhAyAsJ_evdCwG3vuhug@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-general

Hello! Postgres lets us omit columns from a GROUP BY clause if they are
functionally dependent on a grouped key, which is a nice quality-of-life
feature. I'm wondering if a similar relaxation could be permitted for
the SELECT DISTINCT list?

I have a query where I want to find the most recent few items from a
table that match some complex condition, where the condition involves
joining other tables. Here's an example, with two approaches:

-- Store some data: an "item" has one or more "parts".
CREATE TABLE items(id int PRIMARY KEY, create_time timestamptz);
CREATE TABLE parts(part_id int PRIMARY KEY, item_id int);
INSERT INTO items(id, create_time)
SELECT i, now() - make_interval(secs => i)
FROM generate_series(1, 1000000) s(i);
INSERT INTO parts(item_id, part_id)
SELECT items.id, 2 * items.id + delta
FROM items, (VALUES(0), (1)) delta(delta);
CREATE INDEX ON items(create_time DESC);
CREATE INDEX ON parts(item_id);
ANALYZE items, parts;

-- Suppose we want to find the most recent few items with a part
-- whose part ID is threeven. Two approaches:

-- SELECT DISTINCT: fast, but superfluous column:
EXPLAIN ANALYZE
SELECT DISTINCT items.id, create_time
FROM items JOIN parts ON items.id = parts.item_id
WHERE part_id % 3 = 0
ORDER BY create_time DESC
LIMIT 5;
-- 4ms:
-- parallel index scan on items_create_time_idx
-- -> nested loop index scan parts_item_id_idx
-- -> incremental sort -> gather merge -> unique -> limit

-- GROUP BY: slow, but functional dependency recognized:
EXPLAIN ANALYZE
SELECT items.id
FROM items JOIN parts ON items.id = parts.item_id
WHERE part_id % 3 = 0
GROUP BY items.id
ORDER BY create_time DESC
LIMIT 5;
-- 400ms:
-- parallel seq scan on parts
-- -> parallel hash join on item_id via seq scan on items
-- -> sort -> group -> gather merge -> group -> sort -> limit

These timings are Postgres 14.5 on a Linux i7-1165G7. With Postgres 16.3
on an Apple M3 Pro, the shape is the same: the GROUP BY is about 300ms,
and the SELECT DISTINCT is way faster still, at 0.07ms. (It declines to
parallelize, which seems to help.)

I want to use the faster approach, and it works without issue so far.
But that extra column in the SELECT list is a bit inconvenient.

My questions are:

- Do I understand right that these kinds of queries are equivalent?

- If so, does the SQL standard permit Postgres to recognize functional
dependency in this case, so that users may omit the order column
column from the `SELECT DISTINCT` list? (I don't have a copy of the
standard to check myself.)

- Might future versions of Postgres allow this?

thanks!
~Willow

Responses

Browse pgsql-general by date

  From Date Subject
Next Message Tony Shelver 2024-09-13 05:20:24 Re: DDL issue
Previous Message Muhammad Usman Khan 2024-09-13 04:43:14 Re: DDL issue