Different performance of two simple queries

Hi all.
Two queries return same result. The first one always takes about 7ms,
the second 1.5ms.

Query 1:
-------------------------
select
c2c.position, c2c.category, c.*
from categories_companies c2c
join companies c on c2c.company = c.id
where c2c.category ~ 'otdelka_i_remont.*'::lquery
order by c2c.position, c.id
limit 20 offset 1760;
-------------------------

Query 2:
-------------------------
with cte as (
select c2c.position, c2c.company, c2c.category
from categories_companies c2c
where c2c.category ~ 'otdelka_i_remont.*'::lquery
order by c2c.position, c2c.company, c2c.category
limit 20 offset 1760
)
select c2c.position, c2c.category, c.*
from cte c2c
join companies c on c2c.company = c.id;
-------------------------

Indexes:
- categories_companies.category (c2c.category) is of type ltree, indexed
by both gist and btree
- categories_companies (c2c) have composite PK of company and category
- companies.id (c.id) is PK, no explicit indexes created

Questions:
1. Is this is normal, or I done something incorrectly?
2. What can I do to make first query perform as fast as the second one?

What I tried:
Removing order by clause (though I do need that ordering) does not helps.
Putting "category ~ 'otdelka_i_remont.*'" to ON block of JOIN clause
does not make difference.

Same queries with explain:
Query 1:
-------------------------
select
c2c.position, c2c.category, c.*
from categories_companies c2c
join companies c on c2c.company = c.id
where c2c.category ~ 'otdelka_i_remont.*'::lquery
order by c2c.position, c.id
limit 20 offset 1760;
-------------------------
Limit (cost=155.54..155.54 rows=1 width=526) (actual time=6.544..6.545
rows=20 loops=1)
-> Sort (cost=155.50..155.54 rows=14 width=526) (actual
time=6.347..6.466 rows=1780 loops=1)
Sort Key: c2c."position", c.id
Sort Method: quicksort Memory: 1683kB
-> Nested Loop (cost=4.67..155.24 rows=14 width=526) (actual
time=0.016..4.259 rows=1940 loops=1)
-> Bitmap Heap Scan on categories_companies c2c
(cost=4.38..46.83 rows=14 width=45) (actual time=0.014..0.374 rows=1940
loops=1)
Recheck Cond: (category ~ 'otdelka_i_remont.*'::lquery)
Heap Blocks: exact=49
-> Bitmap Index Scan on
query_by_subtree_tilde_ltree_gist (cost=0.00..4.38 rows=14 width=0)
(actual time=0.014..0.014 rows=1940 loops=1)
Index Cond: (category ~
'otdelka_i_remont.*'::lquery)
-> Index Scan using companies_pkey on companies c
(cost=0.29..7.73 rows=1 width=485) (actual time=0.001..0.002 rows=1
loops=1940)
Index Cond: (id = c2c.company)
Planning time: 0.231 ms
Execution time: 7.089 ms

Query 2:
-------------------------
with cte as (
select c2c.position, c2c.company, c2c.category
from categories_companies c2c
where c2c.category ~ 'otdelka_i_remont.*'::lquery
order by c2c.position, c2c.company, c2c.category
limit 20 offset 1760
)
select c2c.position, c2c.category, c.*
from cte c2c
join companies c on c2c.company = c.id;
-------------------------
Nested Loop (cost=47.41..55.46 rows=1 width=519) (actual
time=1.559..1.607 rows=20 loops=1)
CTE cte
-> Limit (cost=47.13..47.13 rows=1 width=45) (actual
time=1.542..1.544 rows=20 loops=1)
-> Sort (cost=47.09..47.13 rows=14 width=45) (actual
time=1.364..1.452 rows=1780 loops=1)
Sort Key: c2c_1."position", c2c_1.company, c2c_1.category
Sort Method: quicksort Memory: 291kB
-> Bitmap Heap Scan on categories_companies c2c_1
(cost=4.38..46.83 rows=14 width=45) (actual time=0.350..0.687 rows=1940
loops=1)
Recheck Cond: (category ~
'otdelka_i_remont.*'::lquery)
Heap Blocks: exact=49
-> Bitmap Index Scan on
query_by_subtree_tilde_ltree_gist (cost=0.00..4.38 rows=14 width=0)
(actual time=0.339..0.339 rows=1940 loops=1)
Index Cond: (category ~
'otdelka_i_remont.*'::lquery)
-> CTE Scan on cte c2c (cost=0.00..0.02 rows=1 width=38) (actual
time=1.545..1.552 rows=20 loops=1)
-> Index Scan using companies_pkey on companies c (cost=0.29..8.30
rows=1 width=485) (actual time=0.002..0.002 rows=1 loops=20)
Index Cond: (id = c2c.company)
Planning time: 0.154 ms
Execution time: 1.651 ms