PostgreSQL/PostGIS: Query seems inordinately time-consuming

Question

I'm doing what I would consider a pretty straightforward query on two tables that aren't huge (~626k records in one; ~47k records in the other).

Both tables have GIST indices on their spatial columns (a.g1 and b.g1 in the query below): these are the columns being used for the conditional part of the query.

The spatial columns are WKB MultiPolygons: they have been checked using ST_IsValid(), and are all lovely and clean.

The offending query looks like this:

# Query 1 (elapsed time: 90 minutes without completing)
CREATE TABLE se_add_mz AS 
SELECT b.zone_code, 
       b.g1 AS zone_geom,
       a.* 
  FROM se_add_tmp AS a    /* this is the 600k record table */
  JOIN plan_zone AS b     /* this is the 47k record table */
    ON (ST_Overlaps(b.g1, a.g1));

The logic of the query is as follows: each se_add_tmp.g1 is known to have a portion of its area in more than one plan_zone.g1.

The aim is to find all the plan_zone.g1 that each se_add_tmp.g1 touches. Eventually the proportion of se_add_tmp.g1 area in each zone will be calculated, but I decided against trying to do that inside this query on the basis that the thing was already taking too damn long. That can happen intra-table (and hence be more faster) once this query finishes.

The se_add_tmp.g1 are known to be multi-zone because the se_add.g1 that are ST_Within() a plan_zone.g1 have already been identified in a query that only took 14 minutes (which still seems a long time):

# Query 2 (elapsed time: 13 min 55 sec; matches 2827611/3455218 rows)
CREATE TABLE se_add_z AS 
SELECT b.zone_code
       a.*,
  FROM se_add AS a,     /* this table has 3.45 million records */
       plan_zone AS b   /* this one has 47k again/still */
 WHERE ST_Contains(b.g1, a.g1);

That query looks an awful lot like the one above, but was working with a 3.45 million-row table (se_add_tmp is the unmatched data from se_add).

I first tried Query 1 with no JOIN ... ON, using WHERE as per Query 2: that ran for upwards of an hour without producing results.

I have VACUUM (FULL+ANALYZE)ed, ANALYZEd, and REINDEXed both tables (nothing remotely interesting was found).

And now - finally - my question: is there some 'trap for young players' that I have fallen into here?

SPEC:

PostgreSQL 9.3.5 64-bit; PostGIS 2.1.3 r12457 on localhost under Win7 Ultimate. Machine has 16GB RAM, quad i7-4770 @3.4GHz, and a 500GB SSD (PostgreSQL data is on an internal 2TB HDD).

My machine is not under any perceptible load when the query is happening: the postgres process hovers at 5-9% of CPU and 15MB RAM, tops... I would be happy to hand it 8GB if it would just get the job done.

SPEC-related question: I have a CUDA-capable card (nVidia Titan X with 12GB RAM of its own - oh hell yeah). I've read that PGStrom can 'smartly' figure out how to push calc load to the GPU. Has anybody here had a crack at that sort of thing? I can't be bothered installing PostgreSQL 9.5dev if it's not going to give a tangible boost.

I ask mainly because I've CUDA-fied some Python stuff (big aerial-image analyses and some number crunching) with mind-boggling results. I would be happy to chuck the whole of postgresql and the related data at the GPU and let it whizz around there until it finishes, if that were possible.