Could someone explain bizarre behavior executing millions of UPDATES?

Question

Could someone explain this behavior to me? I ran the following query on Postgres 9.3 running natively on OS X. I was trying to simulate some behavior where the index size could grow much larger than the table size, and instead found something even more bizarre.

CREATE TABLE test(id int);
CREATE INDEX test_idx ON test(id);

CREATE FUNCTION test_index(batch_size integer, total_batches integer) RETURNS void AS $$
DECLARE
  current_id integer := 1;
BEGIN
FOR i IN 1..total_batches LOOP
  INSERT INTO test VALUES (current_id);
  FOR j IN 1..batch_size LOOP
    UPDATE test SET id = current_id + 1 WHERE id = current_id;
    current_id := current_id + 1;
  END LOOP;
END LOOP;
END;
$$ LANGUAGE plpgsql;

SELECT test_index(500, 10000);

I let this run for about an hour on my local machine, before I started getting disk issue warnings from OS X. I noticed that Postgres was sucking up about 10MB/s from my local disk, and that the Postgres database was consuming a grand total of 30GB from my machine. I ended up cancelling the query. Regardless, Postgres did not return the disk space to me and I queried the database for usage statistics with the following result:

test=# SELECT nspname || '.' || relname AS "relation",
    pg_size_pretty(pg_relation_size(C.oid)) AS "size"
  FROM pg_class C
  LEFT JOIN pg_namespace N ON (N.oid = C.relnamespace)
  WHERE nspname NOT IN ('pg_catalog', 'information_schema')
  ORDER BY pg_relation_size(C.oid) DESC
  LIMIT 20;

           relation            |    size
-------------------------------+------------
 public.test                   | 17 GB
 public.test_idx               | 14 GB

However, selecting from the table yielded no results.

test=# select * from test limit 1;
 id
----
(0 rows)

Running 10000 batches of 500 is 5,000,000 rows, which should yield a pretty small table/index size (on the scale of MB). I suspect that Postgres is creating a new version of the table/index for each INSERT/UPDATE that's happening with function, but this seems strange. The entire function is run transactionally, and the table was empty to start.

Any thoughts on why I'm seeing this behavior?

Specifically, the two questions I have are: why has this space not yet been reclaimed by the database and the second is why did the database require this much space in the first place? 30GB seems like a lot even when accounting for MVCC

Answer 1

Short version

Your algorithm looks O(n*m) on first glance, but effectively grows O(n * m^2), because all rows have the same ID. Instead of 5M rows, you are getting >1.25G rows

Long version

Your function is inside an implicit transaction. That's why you see no data after cancelling your query, and also why it needs to maintain distinct versions of the updated/inserted tuples for both loops.

Additionally, I suspect you have a bug in your logic or underestimating the number of updates made.

First iteration of the outer loop - current_id starts at 1, inserts 1 row, then the inner loop performs an update 10000 times for the same row, finalizing with the only row showing an ID of 10001, and current_id with a value of 10001. 10001 versions of the row are still kept, as the transaction is not finished.

Second iteration of the outer loop - as current_id is 10001, a new row is inserted with ID 10001. Now you have 2 rows with the same "ID", and 10003 versions in total of both rows (10002 of the first one, 1 of the second one). Then the inner loop updates 10000 times BOTH rows, creating 20000 new versions, getting to 30003 tuples so far...

Third iteration of the outer loop: current ID is 20001, a new row is inserted with ID 20001. You have 3 rows, all with same "ID" 20001, 30006 row/tuples versions so far. Then you perform 10000 updates of 3 rows, creating 30000 new versions, now 60006...

...

(If your space had allowed) - 500th iteration of the outer loop, creates 5M updates of 500 rows, just in this iteration

As you see, instead of your expected 5M updates, you got 1000 + 2000 + 3000 + ... + 4990000 + 5000000 updates (plus change), which would be 10000 * (1+2+3+...+499+500), over 1.25G updates. And of course a row is not just the size of your int, it needs some additional structure, so your table and index gets over ten gigabytes size.

Related Q & A:

• set isolation level for postgresql stored procedures
• Making sense of Postgres row sizes

Answer 2

PostgreSQL only returns disk space after VACUUM FULL, not after a DELETE or ROLLBACK (as a result of cancellation)

The standard form of VACUUM removes dead row versions in tables and indexes and marks the space available for future reuse. However, it will not return the space to the operating system, except in the special case where one or more pages at the end of a table become entirely free and an exclusive table lock can be easily obtained. In contrast, VACUUM FULL actively compacts tables by writing a complete new version of the table file with no dead space. This minimizes the size of the table, but can take a long time. It also requires extra disk space for the new copy of the table, until the operation completes.

As a side note your whole function seems questionable. I'm not sure what you're trying to test, but if you want to create data, you can use generate_series

INSERT INTO test
SELECT x FROM generate_series(1, batch_size*total_batches) AS t(x);

Answer 3

The actual numbers after analyzing the function are much bigger because all the rows of the table get the same value which is updated multiple times in each iteration.

When we run it with parameters n and m:

SELECT test_index(n, m);

there are m row inserts and n * (m^2 + m) / 2 updates. So, for n = 500 and m = 10000, Postgres will need to insert only 10K rows but perform ~25G (25 billion) tuple updates.

Considering that a row in Postgres has some 24 bytes overhead, a table with just a single int column will need 28 bytes per row plus the page overhead. So, for the operation to finish, we'd need about 700GB plus the space for the index (which would be a few hundred GB as well).

---

Testing

To test the theory, we created another table test_test with a single row.

CREATE TABLE test_test (i int not null) ;
INSERT INTO test_test (i) VALUES (0);

Then we add a trigger on test so every update will increase the counter by 1. (Code omitted). Then we we run the function, with smaller values, n = 50 and m = 100.

Our theory predicts:

• 100 row inserts,
• 250K tuple updates (252500 = 50*100*101/2)
• at least 7MB for the table on disk
• (+ space for the index)

Test 1 (original test table, with index)

    SELECT test_index(50, 100) ;

After completion, we check table contents:

x=# SELECT COUNT(*) FROM test ;
 count 
-------
   100
(1 row)

x=# SELECT i FROM test_test ;
   i    
--------
 252500
(1 row)

And disk usage (query under Index size/usage statistics in Index Maintenance):

tablename | indexname | num_rows | table_size | index_size | unique | number_of_scans | tuples_read 
----------+-----------+----------+------------+------------+--------+-----------------+-------------
test      | test_idx  |      100 | 8944 kB    | 5440 kB    | N      |           10001 |      505003
test_test |           |        1 | 8944 kB    |            | N      |                 |            

The test table has used almost 9MB for the table and 5MB for the index. Note that the test_test table has used another 9MB! That's expected as it also went through 250K updates (our second trigger updated the single row of test_test for each update of a row in test.)

Note also the number of scan on table test (10K) and the tuples reads (500K).

Test 2 (test table without index)

Exactly the same as above, except that the table has no index.

tablename | indexname | num_rows | table_size | index_size | unique | number_of_scans | tuples_read 
----------+-----------+----------+------------+------------+--------+-----------------+-------------
 test        |        |      100 | 8944 kB    |            | N      |                 |            
 test_test   |        |        1 | 8944 kB    |            | N      |                 |            

We get the same size for disk usage of the table and of course no disk usage for indexes. The number of scans on table test is zero though and the tuples reads as well.

Test 3 (with lower fillfactor)

Tried with fillfactor 50 and the lowest possible, 10. No improvement at all. Disk usage was almost identical to the previous tests (which used the default fillfactor, 100 percent)