How can I generate a row_number without using a window function?

Question

In PostgreSQL, how do you generate a row number:

• WITHOUT a Window Function (like row_number())
• WITHOUT a Temp Table
• Only using a single SELECT

Here is some sample data to play with,

CREATE TEMP TABLE foo AS 
SELECT * FROM ( VALUES
  ('wgates', 'Gates', 'William' ),
  ('wgrant', 'Grant', 'Wallace' ),
  ('jjones', 'Jones', 'John' ),
  ('psmith', 'Smith', 'Paul' )
) AS t(name_id, last_name, first_name);

The desired output would be:

 row_number │ name_id │ last_name │ first_name 
────────────┼─────────┼───────────┼────────────
          1 │ wgates  │ Gates     │ William
          2 │ wgrant  │ Grant     │ Wallace
          3 │ jjones  │ Jones     │ John
          4 │ psmith  │ Smith     │ Paul

Some of these methods can get tricky. Please explain your answers. I can also imagine two categories of answers that work:

• data with a UNIQUE or PRIMARY KEY (we can still use name_id here)
• nothing UNIQUE at all.

All features are on the table for the most recent version of PostgreSQL.

Ultimately, I need a unique key on a table that has no ID so I can update it against a cross-join of itself. I am also asking out of simple curiosity.

Answer 1

identify a good technical PK for duplicate removal

Now that is a completely different question then finding a workaround for row_number().

In Postgres you can use ctid for that. No need for window functions or slow and non-scalable workarounds.

---

To answer the direct question:

This can be done without window functions, but this is going to be horribly slow:

select name_id, last_name, first_name, 
       (select count(*)
        from the_table t2
        where t2.name_id <= t1.name_id) as row_number
from the_table t1
order by name_id;

The above is identical to:

select name_id, last_name, first_name, 
       row_number() over (order by name_id) as row_number
from the_table
order by name_id;

But the solution with a window function will be a lot faster. If you don't need any ordering, then use

select name_id, last_name, first_name, 
       row_number() over () as row_number
from the_table
order by name_id;

You won't get a "stable" row number that way, but it will be unique.

Another possible alternative is to create a sequence, then use nextval() in the select statement.

Answer 2

If it is performance you are worried about, use row_number without order by to avoid sorting.

row_number() over ()

Answer 3

UNIQUE Column Required

One approach I found (in SIMULATING ROW NUMBER IN POSTGRESQL PRE 8.4 by Leo Hsu and Regina Obe), is called the "The all in one WTF". It's been slightly adapted, but it's amazing.

SELECT row_number, name_id, last_name, first_name
FROM people
CROSS JOIN (
  SELECT array_agg(name_id ORDER BY last_name, first_name) AS id FROM people
) AS oldids
CROSS JOIN generate_series(1, (SELECT count(*) FROM people))
  AS gs(row_number)
WHERE id[row_number] = people.name_id;

So let's go down the rabbit hole:

1. Create an ARRAY[] of any specific column, generating no additional rows.

   SELECT *
   FROM people
   CROSS JOIN (
     SELECT array_agg(name_id ORDER BY last_name, first_name) AS id
     FROM people
   ) AS oldids;
   

    name_id │ last_name │ first_name │              id               
   ─────────┼───────────┼────────────┼───────────────────────────────
    jjones  │ Jones     │ John       │ {wgates,wgrant,jjones,psmith}
    psmith  │ Smith     │ Paul       │ {wgates,wgrant,jjones,psmith}
    wgates  │ Gates     │ William    │ {wgates,wgrant,jjones,psmith}
    wgrant  │ Grant     │ Wallace    │ {wgates,wgrant,jjones,psmith}
   

2. Create a Cartesian product with a generate_series(1..last_row). In order to get the last row, we do a subselect with count().

    SELECT *
    FROM people
    CROSS JOIN (
      SELECT array_agg(name_id ORDER BY last_name, first_name) AS id FROM people
    ) AS oldids
    CROSS JOIN generate_series(1, (SELECT count(*) FROM people))
      AS gs(row_number);
   

     name_id │ last_name │ first_name │              id               │ row_number 
    ─────────┼───────────┼────────────┼───────────────────────────────┼────────────
     jjones  │ Jones     │ John       │ {wgates,wgrant,jjones,psmith} │          1
     psmith  │ Smith     │ Paul       │ {wgates,wgrant,jjones,psmith} │          1
     wgates  │ Gates     │ William    │ {wgates,wgrant,jjones,psmith} │          1
     wgrant  │ Grant     │ Wallace    │ {wgates,wgrant,jjones,psmith} │          1
     jjones  │ Jones     │ John       │ {wgates,wgrant,jjones,psmith} │          2
     psmith  │ Smith     │ Paul       │ {wgates,wgrant,jjones,psmith} │          2
     wgates  │ Gates     │ William    │ {wgates,wgrant,jjones,psmith} │          2
     wgrant  │ Grant     │ Wallace    │ {wgates,wgrant,jjones,psmith} │          2
     jjones  │ Jones     │ John       │ {wgates,wgrant,jjones,psmith} │          3
     psmith  │ Smith     │ Paul       │ {wgates,wgrant,jjones,psmith} │          3
     wgates  │ Gates     │ William    │ {wgates,wgrant,jjones,psmith} │          3
     wgrant  │ Grant     │ Wallace    │ {wgates,wgrant,jjones,psmith} │          3
     jjones  │ Jones     │ John       │ {wgates,wgrant,jjones,psmith} │          4
     psmith  │ Smith     │ Paul       │ {wgates,wgrant,jjones,psmith} │          4
     wgates  │ Gates     │ William    │ {wgates,wgrant,jjones,psmith} │          4
     wgrant  │ Grant     │ Wallace    │ {wgates,wgrant,jjones,psmith} │          4
   

3. Now comes the magic, we use the row number as index into the array we created. Because the array is a function of: (a) The UNIQUE column and (b) the order in the set, we can reduce the cartesian product, and preserve the row_number. All we do is add the clause WHERE id[row_number] = people.name_id;

Answer 4

No UNIQUE column required, but a unique ordering must be possible

This method requires no single unique column but it requires a unique order. This is effectively the window version of rank() and not row_number(); however, rank() is row_number() if you can get a unique ordering. I based this approach on SIMULATING ROW NUMBER IN POSTGRESQL PRE 8.4 by Leo Hsu and Regina Obe, it's listed as the "cross-platform method."

SELECT (
  SELECT COUNT(*) FROM people
  WHERE 
  (COALESCE(people.last_name,'') || COALESCE(people.first_name,'')) <= 
  (COALESCE(oldtable.last_name,'') || COALESCE(oldtable.first_name,''))
) AS row_number,
  oldtable.*
FROM people AS oldtable
ORDER BY oldtable.last_name, oldtable.first_name;

In the comments of that page, we can find a slightly simplified version made pg-specific with

SELECT (
  SELECT COUNT(*) FROM people
  WHERE 
  ROW(people.last_name, people.first_name) <= 
  ROW(oldtable.last_name,first_name)
) AS row_number,
  oldtable.*
FROM people AS oldtable
ORDER BY oldtable.last_name, oldtable.first_name;

There really is no elegant way to break this down... We have a

SELECT oldtable.*
FROM people AS oldtable
ORDER BY oldtable.last_name, oldtable.first_name;

Now we're going to do a correlated subquery in the SELECT that compares how many rows are <= the current row.

• In the first example, we do the comparison with the database-agnostic method of concatenating columns to create something that should likely makes unique.
• In the second example, we do the comparison with the PostgreSQL specific ROW() constructor

It's not an easy query to break down, but we can construct a simpler table.

CREATE TABLE foobar AS
SELECT x FROM generate_series(1,10)
  AS t(x) ORDER BY random();

SELECT
  x,
  (SELECT count(*) FROM foobar AS f2 WHERE f2.x <= f1.x)
FROM foobar AS f1
ORDER BY x;

In this example we again

1. take an unordered set that provides for a unique ordering
2. order the set
3. compare it with itself to see how many rows are <= the current row.

Here would be the output of the above simplified example. We're only simplifying by providing a single column with a unique order (rather than composite-ordering, and bypassing the protection against nulls). As another aside, if rows are unique by a left-to-right ordering of the columns, we can compare ROW(people.*) <= ROW(oldtable.*)

 x  | count 
----+-------
  1 |     1
  2 |     2
  3 |     3
  4 |     4
  5 |     5
  6 |     6
  7 |     7
  8 |     8
  9 |     9
 10 |    10