DROP TABLE IF EXISTS test_table;
CREATE table test_table(low_cardinality integer, medium_cardinality integer, high_cardinality integer, very_high_cardinality integer);
INSERT into test_table select (random()* 10 )::integer, (random()* 100 )::integer, (random()* 10000 )::integer, (random()* 1000000 )::integer from generate_series( 1 , 10000000 );
create index test_table_low_cardinality_key on test_table(low_cardinality);
create index test_table_medium_cardinality_key on test_table(medium_cardinality);
create index test_table_high_cardinality_key on test_table(high_cardinality);
create index test_table_very_high_cardinality_key on test_table(very_high_cardinality);
analyze test_table;

select count(distinct low_cardinality) from test_table;
 count
-------
     11 
Time:  25656 , 434  ms

select count(distinct medium_cardinality) from test_table;
 count
-------
    101 
Time:  30456 , 120  ms

select count(distinct high_cardinality) from test_table;
 count
-------
  10001 
Time:  32730 , 315  ms

select count(distinct very_high_cardinality) from test_table;
 count
--------
  999961 
Time:  34082 , 421  ms

WITH RECURSIVE collector(field) AS (
      SELECT min(low_cardinality) FROM test_table
      UNION ALL
      SELECT * FROM (
          SELECT (SELECT test_table.low_cardinality FROM test_table WHERE test_table.low_cardinality>collector.field ORDER BY test_table.low_cardinality LIMIT  1 ) as field
          FROM collector
          ORDER BY collector.field DESC LIMIT  1 
      ) _  WHERE field IS NOT NULL
)
SELECT count(*) FROM collector;
 count
-------
     11 
Time:  1 , 100  ms
Итого в  30000  раз быстрее :)

WITH RECURSIVE collector(field) AS (
      SELECT min(medium_cardinality) FROM test_table
      UNION ALL
      SELECT * FROM (
          SELECT (SELECT test_table.medium_cardinality FROM test_table WHERE test_table.medium_cardinality>collector.field ORDER BY test_table.medium_cardinality LIMIT  1 ) as field
          FROM collector
          ORDER BY collector.field DESC LIMIT  1 
      ) _  WHERE field IS NOT NULL
)
SELECT count(*) FROM collector;
 count
-------
    101 
Time:  4 , 734  ms
Итого почти в  8000  раз быстрее.


WITH RECURSIVE collector(field) AS (
      SELECT min(high_cardinality) FROM test_table
      UNION ALL
      SELECT * FROM (
          SELECT (SELECT test_table.high_cardinality FROM test_table WHERE test_table.high_cardinality>collector.field ORDER BY test_table.high_cardinality LIMIT  1 ) as field
          FROM collector
          ORDER BY collector.field DESC LIMIT  1 
      ) _  WHERE field IS NOT NULL
)
SELECT count(*) FROM collector;
 count
-------
  10001 
Time:  335 , 375  ms
Итого в  100  раз быстрее


WITH RECURSIVE collector(field) AS (
      SELECT min(very_high_cardinality) FROM test_table
      UNION ALL
      SELECT * FROM (
          SELECT (SELECT test_table.very_high_cardinality FROM test_table WHERE test_table.very_high_cardinality>collector.field ORDER BY test_table.very_high_cardinality LIMIT  1 ) as field
          FROM collector
          ORDER BY collector.field DESC LIMIT  1 
      ) _  WHERE field IS NOT NULL
)
SELECT count(*) FROM collector;
 count
--------
  999961 
Time:  32106 , 819  ms
Итого баш на баш.

WITH RECURSIVE
xx(x) AS
(
  select ( select test_table from test_table order by a,b,c limit 1 )
  union all
  select ( select test_table from test_table where (a,b,c) > ((x).a, (x).b, (x).c) order by a,b,c limit 1 ) from xx where x is not null
)  
select (x).* from xx where x is not null

 -- нам не нужен "остановочный" нул

mboguk=# create table test_table(a integer not null, b integer not null, c integer not null);
CREATE TABLE
mboguk=# insert into test_table select random()*10::integer, random()*10::integer, random()*10::integer from generate_series(1,1000000);
INSERT 0 1000000
mboguk=# create index test_index on test_table(a,b,c);
CREATE INDEX
mboguk=# vacuum ANALYZE test_table;
VACUUM
mboguk=# explain analyze WITH RECURSIVE
xx(x) AS
(
  select ( select test_table from test_table order by a,b,c limit 1 )
  union all
  select ( select test_table from test_table where (a,b,c) > ((x).a, (x).b, (x).c) order by a,b,c limit 1 ) from xx where x is not null
)
select (x).* from xx where x is not null
;
                                                                           QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------
 CTE Scan on xx  (cost=14.33..16.35 rows=100 width=32) (actual time=0.120..174.800 rows=1331 loops=1)
   Filter: (x IS NOT NULL)
   Rows Removed by Filter: 1
   CTE xx
     ->  Recursive Union  (cost=0.05..14.33 rows=101 width=32) (actual time=0.101..155.561 rows=1332 loops=1)
           ->  Result  (cost=0.05..0.06 rows=1 width=0) (actual time=0.090..0.096 rows=1 loops=1)
                 InitPlan 1 (returns $1)
                   ->  Limit  (cost=0.00..0.05 rows=1 width=48) (actual time=0.061..0.067 rows=1 loops=1)
                         ->  Index Scan using test_index on test_table  (cost=0.00..51947.31 rows=1000000 width=48) (actual time=0.044..0.044 rows=1 loops=1)
           ->  WorkTable Scan on xx  (cost=0.00..1.22 rows=10 width=32) (actual time=0.089..0.096 rows=1 loops=1332)
                 Filter: (x IS NOT NULL)
                 Rows Removed by Filter: 0
                 SubPlan 2
                   ->  Limit  (cost=0.00..0.10 rows=1 width=48) (actual time=0.058..0.064 rows=1 loops=1331)
                         ->  Index Scan using test_index on test_table  (cost=0.00..32488.84 rows=333333 width=48) (actual time=0.041..0.041 rows=1 loops=1331)
                               Index Cond: (ROW(a, b, c) > ROW((xx.x).a, (xx.x).b, (xx.x).c))
 Total runtime: 182.060 ms

vs

mboguk=# explain analyze select distinct * from test_table;
                                                          QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
 HashAggregate  (cost=22906.00..22919.31 rows=1331 width=12) (actual time=11512.108..11520.078 rows=1331 loops=1)
   ->  Seq Scan on test_table  (cost=0.00..15406.00 rows=1000000 width=12) (actual time=0.027..6173.637 rows=1000000 loops=1)
 Total runtime: 11525.688 ms

WITH RECURSIVE
xx(x) AS
(
  select ( select hstore(ARRAY['a',a::text,'b',b::text,'c',c::text]) from test_table order by a,b,c limit 1 )
  union all
  select ( select hstore(ARRAY['a',a::text,'b',b::text,'c',c::text]) from test_table where (a,b,c) > ((x->'a')::integer, (x->'b')::integer, (x->'c')::integer) order by a,b,c limit 1 ) from xx where x is not null
)  
select (x->'a')::integer, (x->'b')::integer, (x->'c')::integer from xx where x is not null

mboguk=# explain analyze WITH RECURSIVE
xx(x) AS
(
  select ( select hstore(ARRAY['a',a::text,'b',b::text,'c',c::text]) from test_table order by a,b,c limit 1 )
  union all
  select ( select hstore(ARRAY['a',a::text,'b',b::text,'c',c::text]) from test_table where (a,b,c) > ((x->'a')::integer, (x->'b')::integer, (x->'c')::integer) order by a,b,c limit 1 ) from xx where x is not null
)
select (x->'a')::integer, (x->'b')::integer, (x->'c')::integer from xx where x is not null
;
                                                                             QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
 CTE Scan on xx  (cost=11.87..16.14 rows=100 width=32) (actual time=0.204..163.935 rows=1331 loops=1)
   Filter: (x IS NOT NULL)
   Rows Removed by Filter: 1
   CTE xx
     ->  Recursive Union  (cost=0.05..11.87 rows=101 width=32) (actual time=0.164..143.777 rows=1332 loops=1)
           ->  Result  (cost=0.05..0.06 rows=1 width=0) (actual time=0.143..0.154 rows=1 loops=1)
                 InitPlan 1 (returns $1)
                   ->  Limit  (cost=0.00..0.05 rows=1 width=12) (actual time=0.096..0.107 rows=1 loops=1)
                         ->  Index Only Scan using test_index on test_table  (cost=0.00..47912.40 rows=1000000 width=12) (actual time=0.074..0.074 rows=1 loops=1)
                               Heap Fetches: 0
           ->  WorkTable Scan on xx  (cost=0.00..0.98 rows=10 width=32) (actual time=0.083..0.089 rows=1 loops=1332)
                 Filter: (x IS NOT NULL)
                 Rows Removed by Filter: 0
                 SubPlan 2
                   ->  Limit  (cost=0.03..0.08 rows=1 width=12) (actual time=0.057..0.063 rows=1 loops=1331)
                         ->  Index Only Scan using test_index on test_table  (cost=0.03..16807.09 rows=333333 width=12) (actual time=0.041..0.041 rows=1 loops=1331)
                               Index Cond: (ROW(a, b, c) > ROW(((xx.x -> 'a'::text))::integer, ((xx.x -> 'b'::text))::integer, ((xx.x -> 'c'::text))::integer))
                               Heap Fetches: 0
 Total runtime: 170.443 ms