Return to Question

Final solution:

I have decomposed the json to key-value and stored it as table "recordId, key, value, stamp". And I created a btree index on these - and the result is returned universally in few millis. I do not think there is any good universal solution for json without statistics.

Correct answer goes to Evan, as this is probably the best what can be done in jsonb structure.

Edit 5 Only compound gin(stamp, metadata_json) index present:

explain analyze select * from metadata where metadata_json @> '{"someBool": true}
         AND stamp >= '01-01-2016' ORDER BY stamp DESC LIMIT 100;
Limit  (cost=14132.36..14132.61 rows=100 width=381) (actual time=308836.991..308837.052 rows=100 loops=1)
  ->  Sort  (cost=14132.36..14141.36 rows=3600 width=381) (actual time=308836.988..308837.018 rows=100 loops=1)
        Sort Key: stamp DESC
        Sort Method: top-N heapsort  Memory: 109kB
        ->  Bitmap Heap Scan on metadata  (cost=124.90..13994.77 rows=3600 width=381) (actual time=3160.418..308183.328 rows=1437024 loops=1)
              Recheck Cond: ((stamp >= '2016-01-01 00:00:00'::timestamp without time zone) AND (metadata_json @> '{"someBool": true}'::jsonb))
              Heap Blocks: exact=882439
              ->  Bitmap Index Scan on metadata_stamp_metadata_json_idx  (cost=0.00..124.00 rows=3600 width=0) (actual time=2883.484..2883.484 rows=1437024 loops=1)
                    Index Cond: ((stamp >= '2016-01-01 00:00:00'::timestamp without time zone) AND (metadata_json @> '{"someBool": true}'::jsonb))
Planning time: 0.233 ms
Execution time: 308857.051 ms