1

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 Apr 11 '18 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 Apr 12 '18 at 0:31
1

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;
$$;

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.