PostGIS: create new polygons in between existing?

So my colleague came up with this solution. It works great for small areas, but I'd like to find a solution for millions of shapes across an entire country. I can see the ST_UNION here causing a blockage in this respect. The ST_BUFFER is just to close out thin slithers.

SELECT ST_DIFFERENCE(foo.geom, bar.geom)
FROM (SELECT ST_CONVEXHULL(ST_COLLECT(shape::geometry)) as geom FROM schema.polytable) as foo, 
(SELECT ST_BUFFER(ST_UNION(shape),0.5) as geom FROM schema.polytable) as bar

result:

If anyone has suggestions for larger tables, I'm all ears.

---

UPDATE: I have found a solution for the entire country whereby I execute a similar process to that above, but using a gridded version of the country and iterating through each grid using ST_Intersect.

(optional) Before we start we may want to make a grid that does not extend beyond the country outline. So we'll take the entire 25x25km square grid table and a simple outline polygon of the country, then create a new table using SELECT (ST_DUMP(ST_INTERSECTION(a.geom,b.geom))).geom as geom to produce:

standard grid or country outline defined grid, we can then use:

SELECT ST_SUBDIVIDE(ST_DIFFERENCE(a.geom, b.geom)) as geom
FROM 
(SELECT ST_BUFFER(ST_UNION(b.geom),0.5) as geom
 FROM schema.polytable b, schema.gridtable a 
 WHERE ST_INTERSECTS(b.geom,a.geom) AND a.grid_id = [use id number as a iteration variable here]) as b, schema.gridtable a 
WHERE a.grid_id = [use the same id number as a iteration variable here];

So slightly different from the previous SQL statement. There's no need for ST_CONVEXHULL this time as we're using a square grid to contain the output. Also again we use ST_BUFFER 0.5 to remove any thin inter-polygon slithers from the output. For better rendering and performance of the output, we use ST_SUBDIVIDE to divide up the resulting, and potentially huge, multipart polygon.

I need to put this in a python pipeline using the psycopg2 library, then I'll post the results on here. Testing on one grid (out of 500) takes 30secs. So could be 4 hours to run in total.