Why does a SELECT (JOIN on regex) gets 30x slower with +1 row (query plan stays the same)? Lack of memory?
Thanks for the full example.  With that and a little help from "perf" and "gdb", I traced the problem down to this:

src/backend/utils/adt/regexp.c:#define MAX_CACHED_RES   32


Once you are trying to hold 33 regexps in working memory and accessing them in a predictable cycle, each one pushes out of the cache the one that will be needed next, and so every regexp is recompiled every time it is needed.  This recompilation is slow.

I don't know why 32 was chosen for that value, but clearly the cache can't be made unlimited in size.  Maybe it would be nice of this were user-settable rather than compiled in.

With this knowledge, it is easy to tweak the query to change the order of the join execution so that one regexp is tested to completion before moving on to the next one:

SELECT t2.id, t1.id FROM sample t1
right JOIN (select * from regex_set limit 33) t2 ON t1.data ~* t2.regex


However, if there are regexp in t2 which match no rows in t1, then this query will start returning null-extended results for those rows, which is a change in behavior from your existing query.  And if you try to add a simple WHERE clause to filter out those extra rows, then the planner will see through your trick and go back to using the slow join order.  You could try to use a non-transparent equivalent to filter them out:

SELECT t2.id, t1.id FROM sample t1
right JOIN (select * from regex_set limit 33) t2 ON t1.data ~* t2.regex 
where coalesce(t1.id,-5) != -5


(assuming real t1.id are always positive)

But perhaps the best solution to this problem is to build a speciality index which supports regexp queries:

create extension pg_trgm ;
create index on sample using gin (data gin_trgm_ops);


The prospect of using that index will inherently require the faster join order to be used, and the actual use of the index will make the query faster as well.