7

How can I GROUP BY one column, while sorting only by another.

I'm trying to do the following:

SELECT dbId,retreivalTime 
    FROM FileItems 
    WHERE sourceSite='something' 
    GROUP BY seriesName 
    ORDER BY retreivalTime DESC 
    LIMIT 100 
    OFFSET 0;

I want to select the last /n/ items from FileItems, in descending order, with the rows filtered by DISTINCT values of seriesName. The above query errors out ERROR: column "fileitems.dbid" must appear in the GROUP BY clause or be used in an aggregate function. I need the dbid value in order to then take the output of this query, and JOIN it on the source table to get the rest of the columns I wasn.

Note this is basically the gestalt of the below question, with a lot of the extraneous details removed for clarity.


Original question

I have a system I'm migrating from sqlite3 to PostgreSQL, because I've largely outgrown sqlite:

    SELECT
            d.dbId,
            d.dlState,
            d.sourceSite,
        [snip a bunch of rows]
            d.note

    FROM FileItems AS d
        JOIN
            ( SELECT dbId
                FROM FileItems
                WHERE sourceSite='{something}'
                GROUP BY seriesName
                ORDER BY MAX(retreivalTime) DESC
                LIMIT 100
                OFFSET 0
            ) AS di
            ON  di.dbId = d.dbId
    ORDER BY d.retreivalTime DESC;

Basically, I want to select the last n DISTINCT items in the database, where the distinct constraint is on one column, and the sorting order is on a different column.

Unfortunately, the above query, while it works fine in sqlite, errors out in PostgreSQL with the error psycopg2.ProgrammingError: column "fileitems.dbid" must appear in the GROUP BY clause or be used in an aggregate function.

Unfortunately, while adding dbId to the GROUP BY clause fixes the issue (e.g. GROUP BY seriesName,dbId), it means the distinct filtering on the query results no longer work, since dbid is the database primary key, and as such all values are distinct.

From reading the Postgres documentation, there is SELECT DISTINCT ON ({nnn}), but that requires that the returned results be sorted by {nnn}.

Therefore, to do what I'd want via SELECT DISTINCT ON, I'd have to query for all DISTINCT {nnn} and their MAX(retreivalTime), sort again by retreivalTime rather then {nnn}, then take the largest 100 and query using those against the table to get the rest of the rows, which I'd like to avoid, as the database has ~175K rows and ~14K distinct values in the seriesName column, I only want the latest 100, and this query is somewhat performance critical (I need query times < 1/2 second).

My naive assumption here is basically the DB needs to just iterate over each row in descending order of retreivalTime, and simply stop once it's seen LIMIT items, so a full table query is non-ideal, but I don't pretend to really understand how the database system optimizes internally, and I may be approaching this completely wrong.

FWIW, I do occasionally use different OFFSET values, but long query times for cases where offset > ~500 is completely acceptable. Basically, OFFSET is a crappy paging mechanism that lets me get away without needing to dedicate scrolling cursors to each connection, and I'll probably revisit it at some point.


Ref - Question I asked a month ago that lead to this query.


Ok, more notes:

    SELECT
            d.dbId,
            d.dlState,
            d.sourceSite,
        [snip a bunch of rows]
            d.note

    FROM FileItems AS d
        JOIN
            ( SELECT seriesName, MAX(retreivalTime) AS max_retreivalTime
                FROM FileItems
                WHERE sourceSite='{something}'
                GROUP BY seriesName
                ORDER BY max_retreivalTime DESC
                LIMIT %s
                OFFSET %s
            ) AS di
            ON  di.seriesName = d.seriesName AND di.max_retreivalTime = d.retreivalTime
    ORDER BY d.retreivalTime DESC;

Works correctly for the query as described, but if I remove the GROUP BY clause, it fails (it's optional in my application).

psycopg2.ProgrammingError: column "FileItems.seriesname" must appear in the GROUP BY clause or be used in an aggregate function

I think I'm fundamentally not understanding how subqueries work in PostgreSQL. Where am I going wrong? I was under the impression that a subquery is basically just a inline function, where the results are just fed into the main query.

8

Consistent rows

The important question which does not seem to be on your radar yet:
From each set of rows for the same seriesName, do you want the columns of one row, or just any values from multiple rows (which may or may not go together)?

Your answer does the latter, you combine the maximum dbid with the maximum retreivaltime, which may come from a different row.

To get consistent rows, use DISTINCT ON and wrap it in a subquery to order the result differently:

SELECT * FROM (
   SELECT DISTINCT ON (seriesName)
          dbid, seriesName, retreivaltime
   FROM   FileItems
   WHERE  sourceSite = 'mk' 
   ORDER  BY seriesName, retreivaltime DESC NULLS LAST  -- latest retreivaltime
   ) sub
ORDER BY retreivaltime DESC NULLS LAST
LIMIT  100;

Details for DISTINCT ON:

Aside: should probably be retrievalTime, or better yet: retrieval_time. Unquoted mixed case identifiers are a common source of confusion in Postgres.

Better Performance with rCTE

Since we are dealing with a big table here, we'd need a query that can use an index, which is not the case for the above query (except for WHERE sourceSite = 'mk')

On closer inspection, your problem seems to be a special case of a loose index scan. Postgres does not support loose index scans natively, but it can be emulated with a recursive CTE. There is a code example for the simple case in the Postgres Wiki.

Related answer on SO with more advanced solutions, explanation, fiddle:

Your case is more complex, though. But I think I found a variant to make it work for you. Building on this index (without WHERE sourceSite = 'mk')

CREATE INDEX mi_special_full_idx ON MangaItems
(retreivaltime DESC NULLS LAST, seriesName DESC NULLS LAST, dbid)

Or (with WHERE sourceSite = 'mk')

CREATE INDEX mi_special_granulated_idx ON MangaItems
(sourceSite, retreivaltime DESC NULLS LAST, seriesName DESC NULLS LAST, dbid)

The first index can be used for both queries, but is not fully efficient with the additional WHERE condition. The second index is of very limited use for the first query. Since you have both variants of the query consider creating both indexes.

I added dbid at the end to allow Index Only scans.

This query with a recursive CTE makes use of the index. I tested with Postgres 9.3 and it works for me: no sequential scan, all index-only scans:

WITH RECURSIVE cte AS (
   (
   SELECT dbid, seriesName, retreivaltime, 1 AS rn, ARRAY[seriesName] AS arr
   FROM   MangaItems
   WHERE  sourceSite = 'mk'
   ORDER  BY retreivaltime DESC NULLS LAST, seriesName DESC NULLS LAST
   LIMIT  1
   )
   UNION ALL
   SELECT i.dbid, i.seriesName, i.retreivaltime, c.rn + 1, c.arr || i.seriesName
   FROM   cte c
   ,      LATERAL (
      SELECT dbid, seriesName, retreivaltime
      FROM   MangaItems
      WHERE (retreivaltime, seriesName) < (c.retreivaltime, c.seriesName)
      AND    sourceSite = 'mk'  -- repeat condition!
      AND    seriesName <> ALL(c.arr)
      ORDER  BY retreivaltime DESC NULLS LAST, seriesName DESC NULLS LAST
      LIMIT  1
      ) i
   WHERE  c.rn < 101
   )
SELECT dbid
FROM   cte
ORDER  BY rn;

You need to include seriesName in ORDER BY, since retreivaltime is not unique. "Almost" unique is still not unique.

Explain

  • The non-recursive query starts with the latest row.

  • The recursive query adds the next-latest row with a seriesName that's not in the list, yet etc., until we have 100 rows.

  • Essential parts are the JOIN condition (b.retreivaltime, b.seriesName) < (c.retreivaltime, c.seriesName) and the ORDER BY clause ORDER BY retreivaltime DESC NULLS LAST, seriesName DESC NULLS LAST. Both match the sort order of the index, which allows for the magic to happen.

  • Collecting seriesName in an array to rule out duplicates. The cost for b.seriesName <> ALL(c.foo_arr) grows progressively with the number of rows, but for just 100 rows it is still cheap.

  • Just returning dbid as clarified in the comments.

Alternative with partial indexes:

We have been dealing with similar problems before. Here is a highly optimized complete solution based on partial indexes and a looping function:

Probably the fastest way (except for a materialized view) if done right. But more complex.

Materialized View

Since you do not have a lot of write operations and they are not performance-critical as stated in the comments (should be in the question), save the top n pre-computed rows in a materialized view and refresh it after relevant changes to the underlying table. Base your performance-critical queries on the materialized view instead.

  • Could just be a "thin" mv of the latest 1000 dbid or so. In the query, join to the original table. For instance, if content is sometimes updated, but the top n rows can remain unchanged.

  • Or a "fat" mv with whole rows to return. Faster, yet. Needs to be refreshed more often, obviously.

Details in the manual here and here.

4

Ok, I've read the docs more, and now I understand the issue at least a bit better.

Basically, what's going on is there are multiple possible values for dbid as a result of the GROUP BY seriesName aggregation. With SQLite and MySQL, apparently the DB engine just choses one at random (which is absolutely fine in my application).

However, PostgreSQL is much more conservative, so rather then chose a random value, it throws an error.

A simple way to make this query work is to apply an aggregation function to the relevant value:

SELECT MAX(dbid) AS mdbid, seriesName, MAX(retreivaltime) AS mrt
    FROM MangaItems 
    WHERE sourceSite='mk' 
    GROUP BY seriesName
    ORDER BY mrt DESC 
    LIMIT 100 
    OFFSET 0;

This makes the query output fully qualified, and the query now works.

1

Well, I actually wound up using some procedural logic outside of the database to accomplish what I wanted to do.

Basically, 99% of the time, I want the last 100 200 results. The query planner does not seem to optimize for this, and if the value of OFFSET is large, my procedural filter will be much slower.

Anyways, I used a named cursor to iterate over the rows in the database manually, retreiving the rows in groups of a few hundred. I then filter them for distinctness in my application code, and close the cursor immediately after I have accumulated the number of distinct results I wanted.

The mako code (basically python). Lots of debug statements remaining.

<%def name="fetchMangaItems(flags='', limit=100, offset=0, distinct=False, tableKey=None, seriesName=None)">
    <%
        if distinct and seriesName:
            raise ValueError("Cannot filter for distinct on a single series!")

        if flags:
            raise ValueError("TODO: Implement flag filtering!")

        whereStr, queryAdditionalArgs = buildWhereQuery(tableKey, None, seriesName=seriesName)
        params = tuple(queryAdditionalArgs)


        anonCur = sqlCon.cursor()
        anonCur.execute("BEGIN;")

        cur = sqlCon.cursor(name='test-cursor-1')
        cur.arraysize = 250
        query = '''

            SELECT
                    dbId,
                    dlState,
                    sourceSite,
                    sourceUrl,
                    retreivalTime,
                    sourceId,
                    seriesName,
                    fileName,
                    originName,
                    downloadPath,
                    flags,
                    tags,
                    note

            FROM MangaItems
            {query}
            ORDER BY retreivalTime DESC;'''.format(query=whereStr)

        start = time.time()
        print("time", start)
        print("Query = ", query)
        print("params = ", params)
        print("tableKey = ", tableKey)

        ret = cur.execute(query, params)
        print("Cursor ret = ", ret)
        # for item in cur:
        #   print("Row", item)

        seenItems = []
        rowsBuf = cur.fetchmany()

        rowsRead = 0

        while len(seenItems) < offset:
            if not rowsBuf:
                rowsBuf = cur.fetchmany()
            row = rowsBuf.pop(0)
            rowsRead += 1
            if row[6] not in seenItems or not distinct:
                seenItems.append(row[6])

        retRows = []

        while len(seenItems) < offset+limit:
            if not rowsBuf:
                rowsBuf = cur.fetchmany()
            row = rowsBuf.pop(0)
            rowsRead += 1
            if row[6] not in seenItems or not distinct:
                retRows.append(row)
                seenItems.append(row[6])

        cur.close()
        anonCur.execute("COMMIT;")

        print("duration", time.time()-start)
        print("Rows used", rowsRead)
        print("Query complete!")

        return retRows
    %>

</%def>

This currently retrieves the latest 100 200 distinct series items in 115 ~80 milliseconds (lower time is when using a local connection, rather then a TCP socket), while processing approximately 1500 rows.

Come comments:

  • Rows are read in chunks of 250.
  • buildWhereQuery is my own dynamic query builder. Yes, this is a horrible idea. Yes, I know about SQLalchemy et al. I wrote my own because A. this is a personal project that I don't expect to ever use outside of my home LAN, and B. It's a great way to learn SQL.
  • I may consider switching between the two query mechanisms as dependent on the value of offset. It looks like when offset > 1000 and I'm filtering for distinct items, this approach starts to exceed the time required for procedures like the ones in @ErwinBrandstetter's answer.
  • @ErwinBrandstetter's answer is still a much better general solution. This is only better in one very specific case.
  • I had to use two cursors, for some odd reason. You can't create a named cursor unless you're in a transaction, but you can't start a transaction without a cursor (note - this is with autocommit mode off). I have to instantiate a anonymous cursor, issue some SQL (just a BEGIN, here), create my named cursor, use it, close it, and finally commit with the anonymous cursor.
  • This could probably be done entirely in PL/pgSQL, and the result would probably be even faster, but I know python much better.

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.