Postgres Array Overhead – What is the Impact?

Note: this will only work if you make data.id a PRIMARY KEY

SELECT
    data.id
FROM 
    data, 
    LATERAL (SELECT DISTINCT unnest(values)) no_duplicates
GROUP BY 
    data.id 
HAVING
    array_length(values, 1) > COUNT(no_duplicates)

Here's an SQL Fiddle.

This works by converting your array into a recordset/table (which I've called "no_duplicates") using unnest(), and removing duplicates using DISTINCT:

LATERAL (SELECT DISTINCT unnest(values)) no_duplicates

Then I GROUP BY the original data table's ID, and compare the length of the new, filtered recordset with the old, unfiltered table. If the original, unfiltered array is bigger, then we removed duplicates so we should select that row:

array_length(values, 1) > COUNT(no_duplicates)

Unsurprisingly, the manual is right. But there is more to it.

For one, size on disk (in any table, even when not actually stored on disk) can be different from size in memory. On disk, the overhead for short varchar values up to 126 bytes is reduced to a 1 byte as stated in the manual. But the overhead in memory is always 4 bytes (once individual values are extracted).

The same is true for text, varchar, varchar(n) or char(n) - except that char(n) is blank-padded to n characters and you normally don't want to use it. Its effective size can still vary in multi-byte encodings because n denotes a maximum of characters, not bytes:

strings up to n characters (not bytes) in length.

All of them use varlena internally.
"char" (with double-quotes) is a different creature and always occupies a single byte.
Untyped string literals ('foo') have a single byte overhead. Not to be confused with typed values!

Test with pg_column_size().

CREATE TEMP TABLE t (id int, v_small varchar, v_big varchar);
INSERT INTO t VALUES (1, 'foo', '12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890');

SELECT pg_column_size(id)        AS id
     , pg_column_size(v_small)   AS v_small
     , pg_column_size(v_big)     AS v_big
     , pg_column_size(t)         AS t
FROM   t
UNION ALL  -- 2nd row measuring values in RAM
SELECT pg_column_size(1)
     , pg_column_size('foo'::varchar)
     , pg_column_size('12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890'::varchar)
     , pg_column_size(ROW(1, 'foo'::varchar, '12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890'::varchar));

 id | v_small | v_big |  t
----+---------+-------+-----
  4 |       4 |   144 | 176
  4 |       7 |   144 | 176

As you can see:

• The 3-byte string 'foo' occupies 4 bytes on disk and 7 bytes in RAM (so 1 byte vs. 4 bytes of overhead).
• The 140-byte string '123...' occupies 144 bytes both on disk and in RAM (so always 4 bytes of overhead).
• Storage of integer has no overhead (but it has alignment requirements that can impose padding).
• The row has an additional overhead of 24 bytes for the tuple header (plus an additional 4 bytes per tuple for the item identifier in the page header).
• And last but not least: The overhead of the small varchar is still just 1 byte while it has not been extracted from the row - as can be seen from the row size. (That's why it's sometimes a bit faster to select whole rows.)

Related:

• Would index lookup be noticeably faster with char vs varchar when all values are 36 chars
• Detailed optimal column order with large text and bytea
• Measure the size of a PostgreSQL table row
• Configuring PostgreSQL for read performance