Postgres: using existing index to support GROUP BY query on custom function

Question

I'm trying to optimize a query that looks like this:

SELECT f(a), sum(b) FROM table GROUP BY f(a) ORDER BY f(a) LIMIT 10

I have a b-tree index on column a, and f is a custom function where I know that if x > y, then f(x) >= f(y).

It seems like in a perfect world one ought to be able to execute this query using the index on column a to avoid reading more rows than necessary to calculate the first 10 groups, since an index scan on a will return all the rows in the first 10 groups before it starts returning rows not in the first 10 groups.

I know I could optimize this by creating an index on f(a), but I have multiple function fs so don't want to pay the overhead of doing that for each one.

Is there a way to re-write this query (or my function f, for that matter) so that it could use my existing index on column a to avoid reading the whole table?

How many distinct values of a are there compared to distinct values of f(a)? — jjanes
– jjanes, Commented Apr 11, 2018 at 13:52
@jjanes column a is continuous -- it's a bigint column. f(a) groups the numbers. So for instance, one example f is "round to the nearest 100" — josh
– josh, Commented Apr 12, 2018 at 0:31

filiprem · Accepted Answer · 2018-04-11 17:44:08Z

I'm not yet sure if this is doable in pure SQL (probably - yes), but here is the brute force solution using cursors. This is just a (working) draft, with some twiddling and dynamic SQL you could add more parameterers, like function name.

create or replace function top_f(_limit int)
returns table (f text, sum int)
language plpgsql
AS $$
declare
    _a text;
    _fa text;
    _asum int  := 0;
    _fasum int :=0;
    _cnt int   := 0;
    _cur cursor for SELECT a, sum(b) FROM t GROUP BY a ORDER BY a;
begin
    open _cur;
    LOOP
        fetch _cur into _a, _asum;
        if upper(_a) <> _fa then
            return query select _fa, _fasum;
            _fasum := 0;
            _cnt   := _cnt + 1;
        end if;
        exit when _cnt >= 10;
        _fasum := _fasum + _asum;
        _fa := upper(_a);
    END LOOP;
end;
$$;

And here is how it works. Please note run times which are the point here.

(filip@[local]:5432) filip=# SELECT a, sum(b) FROM t group by a order by a limit 12;
     a     | sum 
-----------+-----
 a         |  11
 A         |  11
 Aachen    |  11
 Aachens   |  11
 Aaliyah   |  11
 Aaliyahs  |  11
 aardvark  |  11
 aardvarks |  22
 Aaron     |  11
 Aarons    |  11
 aback     |  11
 abacus    |  11
(12 rows)

Time: 0.838 ms

(filip@[local]:5432) filip=# SELECT * from top_f(10);
     f     | sum 
-----------+-----
 A         |  22
 AACHEN    |  11
 AACHENS   |  11
 AALIYAH   |  11
 AALIYAHS  |  11
 AARDVARK  |  11
 AARDVARKS |  22
 AARON     |  11
 AARONS    |  11
 ABACK     |  11
(10 rows)

Time: 1.524 ms

(filip@[local]:5432) filip=# SELECT upper(a), sum(b) FROM t GROUP BY upper(a) ORDER BY upper(a) LIMIT 10;
   upper   | sum 
-----------+-----
 A         |  22
 AACHEN    |  11
 AACHENS   |  11
 AALIYAH   |  11
 AALIYAHS  |  11
 AARDVARK  |  11
 AARDVARKS |  22
 AARON     |  11
 AARONS    |  11
 ABACK     |  11
(10 rows)

Time: 2061.320 ms (00:02.061)

Update: here is the same with parametrized function name:

CREATE OR REPLACE FUNCTION top_f(_function name, _limit int)
RETURNS TABLE (f text, sum int)
LANGUAGE plpgsql
AS $$
DECLARE
    _a text;
    _fa text;
    _newfa text;
    _asum int  := 0;
    _fasum int :=0;
    _cnt int   := 0;
    _cur cursor for SELECT a, sum(b) FROM t GROUP BY a ORDER BY a;
BEGIN
    OPEN _cur;
    LOOP
        FETCH _cur INTO _a, _asum;
        EXECUTE 'SELECT ' || quote_ident(_function) || '($1)' INTO _newfa USING _a;
        IF _newfa < _fa then
            raise exception 'Function is not monotonic: f(%) = % < %', _a, _newfa, _fa;
        ELSIF _newfa > _fa then
            return query select _fa, _fasum;
            _fasum := 0;
            _cnt   := _cnt + 1;
            exit when _cnt >= _limit;
        END IF;
        _fasum := _fasum + _asum;
        _fa := _newfa;
    END LOOP;
END;
$$;

Stack Exchange Network

Postgres: using existing index to support GROUP BY query on custom function

1 Answer 1

Your Answer

Hot Network Questions

Postgres: using existing index to support GROUP BY query on custom function

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Related

Hot Network Questions