очередной велосипедист / PostgreSQL

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / PostgreSQL [игнор отключен] [закрыт для гостей] / очередной велосипедист

23 сообщений из 48, страница 2 из 2

все

очередной велосипедист

#38807063

?Ы

Гость

Шавлюк ЕвгенийMaxim Boguk,

А что даст запрос если в таблице будут 5 записей с ID = {1, 2, 2000000000, 2000000001, 2000000002}

P.S. попал в топик с Хабра

вот для такого "разделения по областям ключа" -- я и пытался накидать "на словах",

скорее всего много что наврал (где-то лишние коленца), но примерная канва "выбрасывания гигантских дырок" ( понятно, что основной выйгрыш должен идти от индекс скана, кторого в тесте нет) где-то такая:

Код: sql

DEALLOCATE ALL;
PREPARE FOO (int,int) AS

WITH RECURSIVE
table1 (id)  AS 
( SELECT -1E8::int + generate_series (-10000,1)
UNION ALL SELECT generate_series (1,10000)
UNION ALL SELECT 1E8::int + generate_series (1,10000)
)
,
r (res,mins,maxs ,RRange,cnt ,rnd) AS (
SELECT array[]::integer[] AS res, array[]::integer[]||min(id) AS mins, array[]::integer[]||max(id) AS maxs,max(id) - min(id) AS RRange, 0 AS cnt, NULL::int FROM table1
UNION ALL
SELECT 
	CASE WHEN (id IS NULL) THEN res ELSE res|| id END AS res
	,CASE WHEN (id IS NULL) and ((select MIN(ID) from table1 WHERE id>rnd) - (select max(ID) from table1 WHERE id<rnd))> $1
		THEN  ARRAY (SELECT unnest( RR.mins || (select MIN(ID) from table1 WHERE id>rnd) ) AS u ORDER BY u ) 
		ELSE RR.mins END AS mins
	,CASE WHEN (id IS NULL) and ((select MIN(ID) from table1 WHERE id>rnd) - (select max(ID) from table1 WHERE id<rnd))> $1
		THEN ARRAY (SELECT unnest(RR.maxs || (select max(ID) from table1 WHERE id<rnd) ) AS u ORDER BY u ) 
		ELSE RR.maxs END AS maxs
	--,(SELECT SUM (Lmax - Lmin) ::int FROM (SELECT unnest(r.mins) Lmin , unnest(r.maxs) Lmax )) FOO )
	,RR.RRange
	-CASE WHEN (id IS NULL) and ((select MIN(ID) from table1 WHERE id>rnd) - (select max(ID) from table1 WHERE id<rnd))> $1
		THEN (select MIN(ID) from table1 WHERE id>rnd)
		ELSE 0 END
	+CASE WHEN (id IS NULL) and ((select MIN(ID) from table1 WHERE id>rnd) - (select max(ID) from table1 WHERE id<rnd))> $1
		THEN (select max(ID) from table1 WHERE id<rnd)
		ELSE 0 END
	AS RRange
	,CASE WHEN (id IS NULL) THEN cnt ELSE cnt +1 END AS cnt
	--,cnt +1 
	,rnd
FROM 
(SELECT
 --/*
	((SELECT Lmin - LRange -0.5 FROM
		(SELECT Lmin , coalesce (lag(LRange)over(order by Lmin),0) as LRange FROM 
			(SELECT Lmin, sum(Lmax-Lmin)over (order by Lmin) ::int  as LRange FROM (SELECT unnest(R_FOO.mins) Lmin , unnest(R_FOO.maxs) Lmax) FOO order by Lmin)
		AS LF)		
	AS LFOO
	WHERE LRange <= rnd_dlt
	ORDER BY Lmin DESC LIMIT 1
	) +rnd_dlt)::int
--*/	rnd_dlt 

	AS rnd
			
	,res ,mins,maxs,RRange,cnt FROM
		(SELECT 
		--((SELECT SUM (Lmax - Lmin) ::int FROM (SELECT unnest(r.mins) Lmin , unnest(r.maxs) Lmax ) FOO)+1)
		((r.RRange +1)* random())::int		
		AS rnd_dlt
		,res ,mins,maxs,RRange,cnt FROM r) AS R_FOO
) AS RR
LEFT JOIN table1 ON id=rnd AND id <> all(res) 
WHERE 
	cnt<=$2
) 
--SELECT * from r;
--/*
SELECT unnest(res) FROM (
  SELECT res FROM r ORDER BY array_length(res,1) DESC NULLS LAST LIMIT 1
) AS t;
-- */

EXECUTE foo(1000,10);

...

Рейтинг:

0 / 0

15.11.2014, 15:20:22

| Ответить | Цитировать | Написать

очередной велосипедист

#38807077

?Ы

Гость

Misha Tyurin<>
это жесткий оффтоп, вот по этому поводу, в том числе, чтобы такого не было, я и предлагал вводить доп требования. можно найти по моему профилю, моим темам.
ну зочем же так шапковозгораццо ?
охолоните, что ли. тут вас больше одного, комсомольцев-то.
во всех пальцем не натыкаесся.

PS
там, на хабре, поцыент вообще например пишед:
авторПодвох обнаружился в самом "сердце" алгоритма — выборке записи из диапазона. Действительно, рекурсивный запрос пытается выбрать строчку, для которой выполнялось бы условие:

Код: plaintext

id > min + (max - min) * random()

Но в случае, когда random() возвращает "1", это условие трансформируется в:
...

и гордо лупцует себя пьяткой в хрудь

я, хоть помню, что много раз себя перепроверял , что рандом пж возвращает открытый интервал , но всё равно полез в RTFM -- смотртеь с какого конца открыто:

RTFM

Код: plaintext

random() 	dp 	random value in the range 0.0 <= x < 1.0 	random()

и т.д. тащемто. рукалицо и порченный стыд. вот что карма и прочие комсомольские склонности с людяма делают

...

Рейтинг:

0 / 0

15.11.2014, 16:02:10

| Ответить | Цитировать | Написать

очередной велосипедист

#38807082

?Ы

Гость

PS: кстати сообразил: чтобы принудить пж к индекс скану -- поцыенту потребовалось кастнуть левую сторону r int-у

Код: sql

t.id >= min + ((max - min) * random())::int AND

ну вот тут кривизна пж бесконечна, и таковой и будет ближайшие лет 200, как объясняет нам smagen

а дальше он попросту всё попутал -- полез на rendom() батоны крошить, когда причина -- в касте.

...

Рейтинг:

0 / 0

15.11.2014, 16:12:21

| Ответить | Цитировать | Написать

очередной велосипедист

#38807447

?Ы

Гость

PS . цена удаления дырок (т.е. усложнение алгоритма) получилась великовата. надо бы подсократить.

привожу скрипты теста

ddl

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.

CREATE TABLE testrand
(
  trid bigint NOT NULL,
  trbody text,
  CONSTRAINT testrand_pkey PRIMARY KEY (trid)
)
WITH (
  OIDS=FALSE
);
ALTER TABLE testrand
  OWNER TO postgres;
truncate testrand;

insert rnd with holes

Код: plsql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.

DO 
$dd$
DECLARE
	v_part bigint;
	i bigint;
	C_PART_max constant bigint:= 1E8::bigint;
	C_PART_cnt constant bigint:= 1E5::bigint;
	C_PART_wght constant NUMERIC := C_PART_CNT ::NUMERIC / C_PART_MAX::numeric;
BEGIN
	<<ploop>>
	FOR part IN -8..7 LOOP
		v_part :=part*1E13::bigint;
		
		INSERT INto testrand(trid)
		SELECT v_part + g FROM generate_series (1,C_PART_max) g
		WHERE random() < C_PART_wght;
		
		RAISE NOTICE ' part %' ,part;
		
	END LOOP ploop;
		
END;
$dd$

Bogyk

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.

WITH RECURSIVE
r AS (
    SELECT array[]::BIGINT[] AS res,min(trid) AS min, max(trid)-min(trid) AS range FROM testrand
  UNION ALL
    SELECT res||ARRAY(SELECT trid FROM testrand WHERE trid=(SELECT (-0.5 + min+(1+range)*random())::BIGINT) AND NOT trid=ANY(res)), min, range
    FROM r WHERE coalesce(array_length(res,1),0)<14
)
SELECT unnest(res) FROM (
  SELECT res FROM r ORDER BY array_length(res,1) DESC NULLS LAST LIMIT 1
) AS t;
-- очевидно, дождаться не всем удастся -- 10^13 -- это много

ORDER BY random()
на такой табличке быстрее всего

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.

SELECT trid FROM testrand 
ORDER BY random() LIMIT 14;
-------------------------
'Limit  (cost=65512.35..65512.38 rows=14 width=8) (actual time=356.541..356.542 rows=14 loops=1)'
'  ->  Sort  (cost=65512.35..69510.74 rows=1599357 width=8) (actual time=356.539..356.539 rows=14 loops=1)'
'        Sort Key: (random())'
'        Sort Method: top-N heapsort  Memory: 25kB'
'        ->  Seq Scan on testrand  (cost=0.00..27068.96 rows=1599357 width=8) (actual time=0.007..188.251 rows=1599357 loops=1)'
'Total runtime: 356.564 ms'

14random + 10^6row_number()
поиск по оконному порядку дороже ?

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.

WITH rndm (rnm) AS (
SELECT ((SELECT count(1) FROM testrand) /* 1599357*/ * random()) ::bigint FROM generate_series(1,14) s
)
SELECT trid FROM
(
SELECT trid , row_number() over() rnm FROM testrand 
) foo
WHERE rnm IN (SELECT rnm FROM rndm)
;
--------------------------
'Hash Join  (cost=27115.97..108163.24 rows=799678 width=8) (actual time=360.788..863.406 rows=14 loops=1)'
'  Hash Cond: ((row_number() OVER (?)) = rndm.rnm)'
'  CTE rndm'
'    ->  Function Scan on generate_series s  (cost=27068.97..27088.97 rows=1000 width=0) (actual time=205.375..205.380 rows=14 loops=1)'
'          InitPlan 1 (returns $0)'
'            ->  Aggregate  (cost=27068.96..27068.97 rows=1 width=0) (actual time=205.361..205.361 rows=1 loops=1)'
'                  ->  Seq Scan on testrand testrand_1  (cost=0.00..23070.57 rows=1599357 width=0) (actual time=0.003..103.550 rows=1599357 loops=1)'
'  ->  WindowAgg  (cost=0.00..43062.53 rows=1599357 width=8) (actual time=0.012..552.370 rows=1599357 loops=1)'
'        ->  Seq Scan on testrand  (cost=0.00..23070.57 rows=1599357 width=8) (actual time=0.005..162.487 rows=1599357 loops=1)'
'  ->  Hash  (cost=24.50..24.50 rows=200 width=8) (actual time=205.393..205.393 rows=14 loops=1)'
'        Buckets: 1024  Batches: 1  Memory Usage: 1kB'
'        ->  HashAggregate  (cost=22.50..24.50 rows=200 width=8) (actual time=205.388..205.391 rows=14 loops=1)'
'              ->  CTE Scan on rndm  (cost=0.00..20.00 rows=1000 width=8) (actual time=205.376..205.382 rows=14 loops=1)'
'Total runtime: 863.457 ms'

-- предподсчет count() удешевит на 0.1-0.2

removing BIG holes

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
210.
211.
212.
213.
214.
215.
216.
217.
218.
219.
220.
221.
222.
223.
224.
225.
226.
227.
228.
229.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
253.
254.
255.
256.
257.
258.
259.
260.
261.
262.
263.
264.
265.
266.
267.
268.
269.
270.
271.
272.
273.
274.
275.
276.
277.
278.
279.
280.
281.
282.
283.
284.
285.
286.
287.
288.
289.
290.
291.
292.
293.
294.
295.
296.
297.
298.
299.
300.
301.
302.
303.
304.
305.
306.
307.
308.
309.
310.
311.
312.
313.
314.
315.
316.
317.
318.
319.
320.
321.
322.
323.
324.
325.
326.
327.
328.
329.
330.
331.
332.
333.
334.
335.
336.
337.
338.
339.
340.
341.
342.
343.
344.
345.
346.
347.
348.
349.
350.
351.
352.
353.
354.
355.
356.
357.
358.
359.
360.
361.
362.
363.
364.
365.
366.
367.
368.
369.
370.
371.
372.
373.
374.
375.
376.
377.
378.
379.
380.
381.
382.
383.
384.
385.
386.
387.
388.
389.
390.
391.
392.
393.
394.

DEALLOCATE ALL;
PREPARE FOO (BIGINT,BIGINT) AS

WITH RECURSIVE
r (res,mins,maxs ,RRange,cnt ,rnd) AS (
SELECT array[]::BIGINT[] AS res, array[]::BIGINT[]||min(trid) AS mins, array[]::BIGINT[]||max(trid) AS maxs,max(trid) - min(trid) AS RRange, 0 AS cnt, NULL::BIGINT FROM testrand
UNION ALL
SELECT 
	CASE WHEN (trid IS NULL) THEN res ELSE res|| trid END AS res
	,CASE WHEN (trid IS NULL) and ((select MIN(trid) from testrand WHERE trid>rnd) - (select max(trid) from testrand WHERE trid<rnd))> $1
		THEN  ARRAY (SELECT unnest( RR.mins || (select MIN(trid) from testrand WHERE trid>rnd) ) AS u ORDER BY u ) 
		ELSE RR.mins END AS mins
	,CASE WHEN (trid IS NULL) and ((select MIN(trid) from testrand WHERE trid>rnd) - (select max(trid) from testrand WHERE trid<rnd))> $1
		THEN ARRAY (SELECT unnest(RR.maxs || (select max(trid) from testrand WHERE trid<rnd) ) AS u ORDER BY u ) 
		ELSE RR.maxs END AS maxs
	--,(SELECT SUM (Lmax - Lmin) ::BIGINT FROM (SELECT unnest(r.mins) Lmin , unnest(r.maxs) Lmax )) FOO )
	,RR.RRange
	-CASE WHEN (trid IS NULL) and ((select MIN(trid) from testrand WHERE trid>rnd) - (select max(trid) from testrand WHERE trid<rnd))> $1
		THEN (select MIN(trid) from testrand WHERE trid>rnd)
		ELSE 0 END
	+CASE WHEN (trid IS NULL) and ((select MIN(trid) from testrand WHERE trid>rnd) - (select max(trid) from testrand WHERE trid<rnd))> $1
		THEN (select max(trid) from testrand WHERE trid<rnd)
		ELSE 0 END
	AS RRange
	,CASE WHEN (trid IS NULL) THEN cnt ELSE cnt +1 END AS cnt
	--,cnt +1 
	,rnd
FROM 
(SELECT
 --/*
	((SELECT Lmin - LRange -0.5 FROM
		(SELECT Lmin , coalesce (lag(LRange)over(order by Lmin),0) as LRange FROM 
			(SELECT Lmin, sum(Lmax-Lmin)over (order by Lmin) ::BIGINT  as LRange FROM (SELECT unnest(R_FOO.mins) Lmin , unnest(R_FOO.maxs) Lmax) FOO order by Lmin)
		AS LF)		
	AS LFOO
	WHERE LRange < rnd_dlt
	ORDER BY Lmin DESC LIMIT 1
	) +rnd_dlt)::BIGINT
--*/	rnd_dlt 

	AS rnd
			
	,res ,mins,maxs,RRange,cnt FROM
		(SELECT 
		--((SELECT SUM (Lmax - Lmin) ::BIGINT FROM (SELECT unnest(r.mins) Lmin , unnest(r.maxs) Lmax ) FOO)+1)
		((r.RRange +1)* random())::BIGINT		
		AS rnd_dlt
		,res ,mins,maxs,RRange,cnt FROM r) AS R_FOO
) AS RR
LEFT JOIN testrand ON trid=rnd AND trid <> all(res) 
WHERE 
	cnt<$2
) 
--SELECT * from r;
--/*
SELECT unnest(res) FROM (
  SELECT res FROM r ORDER BY array_length(res,1) DESC NULLS LAST LIMIT 1
) AS t;
-- */

EXECUTE foo(50000,14);
---------------------------------------------------------------
'Subquery Scan on t  (cost=5401.38..5401.89 rows=100 width=32) (actual time=2753.755..2753.757 rows=14 loops=1)'
'  CTE r'
'    ->  Recursive Union  (cost=0.92..5400.53 rows=31 width=124) (actual time=0.030..2743.323 rows=6959 loops=1)'
'          ->  Result  (cost=0.92..0.94 rows=1 width=0) (actual time=0.029..0.030 rows=1 loops=1)'
'                InitPlan 1 (returns $1)'
'                  ->  Limit  (cost=0.43..0.46 rows=1 width=8) (actual time=0.013..0.013 rows=1 loops=1)'
'                        ->  Index Only Scan using testrand_pkey on testrand  (cost=0.43..52617.17 rows=1599357 width=8) (actual time=0.012..0.012 rows=1 loops=1)'
'                              Index Cond: (trid IS NOT NULL)'
'                              Heap Fetches: 1'
'                InitPlan 2 (returns $2)'
'                  ->  Limit  (cost=0.43..0.46 rows=1 width=8) (actual time=0.010..0.010 rows=1 loops=1)'
'                        ->  Index Only Scan Backward using testrand_pkey on testrand testrand_1  (cost=0.43..52617.17 rows=1599357 width=8) (actual time=0.009..0.009 rows=1 loops=1)'
'                              Index Cond: (trid IS NOT NULL)'
'                              Heap Fetches: 1'
'          ->  Nested Loop Left Join  (cost=11.68..539.90 rows=3 width=124) (actual time=0.393..0.393 rows=1 loops=6959)'
'                ->  WorkTable Scan on r r_1  (cost=0.00..0.26 rows=3 width=108) (actual time=0.001..0.001 rows=1 loops=6959)'
'                      Filter: (cnt < $2)'
'                      Rows Removed by Filter: 0'
'                ->  Index Only Scan using testrand_pkey on testrand testrand_14  (cost=11.68..19.71 rows=1 width=8) (actual time=0.003..0.003 rows=0 loops=6958)'
'                      Index Cond: (trid = (((SubPlan 42) + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint)'
'                      Filter: (trid <> ALL (r_1.res))'
'                      Heap Fetches: 14'
'                      SubPlan 42'
'                        ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.031..0.031 rows=1 loops=6958)'
'                              ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=6958)'
'                                    Sort Key: lfoo_13.lmin'
'                                    Sort Method: top-N heapsort  Memory: 25kB'
'                                    ->  Subquery Scan on lfoo_13  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.028 rows=9 loops=6958)'
'                                          Filter: (lfoo_13.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                          Rows Removed by Filter: 7'
'                                          ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=6958)'
'                                                ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.006..0.018 rows=16 loops=6958)'
'                                                      ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=6958)'
'                                                            Sort Key: (unnest(r_1.mins))'
'                                                            Sort Method: quicksort  Memory: 25kB'
'                                                            ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=6958)'
'                      SubPlan 42'
'                        ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.031..0.031 rows=1 loops=6958)'
'                              ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=6958)'
'                                    Sort Key: lfoo_13.lmin'
'                                    Sort Method: top-N heapsort  Memory: 25kB'
'                                    ->  Subquery Scan on lfoo_13  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.028 rows=9 loops=6958)'
'                                          Filter: (lfoo_13.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                          Rows Removed by Filter: 7'
'                                          ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=6958)'
'                                                ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.006..0.018 rows=16 loops=6958)'
'                                                      ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=6958)'
'                                                            Sort Key: (unnest(r_1.mins))'
'                                                            Sort Method: quicksort  Memory: 25kB'
'                                                            ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=6958)'
'                SubPlan 5'
'                  ->  Result  (cost=11.71..11.72 rows=1 width=0) (actual time=0.040..0.040 rows=1 loops=6944)'
'                        InitPlan 3 (returns $6)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.032..0.032 rows=1 loops=6944)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=6944)'
'                                      Sort Key: lfoo.lmin'
'                                      Sort Method: quicksort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.029 rows=9 loops=6944)'
'                                            Filter: (lfoo.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 7'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=6944)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.007..0.018 rows=16 loops=6944)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=6944)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=6944)'
'                        InitPlan 4 (returns $7)'
'                          ->  Limit  (cost=0.43..0.47 rows=1 width=8) (actual time=0.040..0.040 rows=1 loops=6944)'
'                                ->  Index Only Scan using testrand_pkey on testrand testrand_2  (cost=0.43..18876.81 rows=533119 width=8) (actual time=0.007..0.007 rows=1 loops=6944)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid > (($6 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 6944'
'                SubPlan 8'
'                  ->  Result  (cost=11.71..11.72 rows=1 width=0) (actual time=0.039..0.039 rows=1 loops=6944)'
'                        InitPlan 6 (returns $11)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.031..0.031 rows=1 loops=6944)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=6944)'
'                                      Sort Key: lfoo_1.lmin'
'                                      Sort Method: quicksort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_1  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.028 rows=9 loops=6944)'
'                                            Filter: (lfoo_1.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 7'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=6944)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.006..0.018 rows=16 loops=6944)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=6944)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=6944)'
'                        InitPlan 7 (returns $12)'
'                          ->  Limit  (cost=0.43..0.47 rows=1 width=8) (actual time=0.039..0.039 rows=1 loops=6944)'
'                                ->  Index Only Scan Backward using testrand_pkey on testrand testrand_3  (cost=0.43..18876.81 rows=533119 width=8) (actual time=0.006..0.006 rows=1 loops=6944)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid < (($11 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 6944'
'                SubPlan 12'
'                  ->  Sort  (cost=15.56..15.81 rows=100 width=0) (actual time=0.031..0.032 rows=9 loops=15)'
'                        Sort Key: (unnest((r_1.mins || $18)))'
'                        Sort Method: quicksort  Memory: 25kB'
'                        InitPlan 11 (returns $18)'
'                          ->  Result  (cost=11.71..11.72 rows=1 width=0) (actual time=0.027..0.027 rows=1 loops=15)'
'                                InitPlan 9 (returns $16)'
'                                  ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.018..0.018 rows=1 loops=15)'
'                                        ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.018..0.018 rows=1 loops=15)'
'                                              Sort Key: lfoo_2.lmin'
'                                              Sort Method: top-N heapsort  Memory: 25kB'
'                                              ->  Subquery Scan on lfoo_2  (cost=4.83..11.08 rows=33 width=16) (actual time=0.007..0.016 rows=4 loops=15)'
'                                                    Filter: (lfoo_2.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                    Rows Removed by Filter: 4'
'                                                    ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.006..0.014 rows=8 loops=15)'
'                                                          ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.005..0.011 rows=8 loops=15)'
'                                                                ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.004..0.004 rows=8 loops=15)'
'                                                                      Sort Key: (unnest(r_1.mins))'
'                                                                      Sort Method: quicksort  Memory: 25kB'
'                                                                      ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.002 rows=8 loops=15)'
'                                InitPlan 10 (returns $17)'
'                                  ->  Limit  (cost=0.43..0.47 rows=1 width=8) (actual time=0.026..0.026 rows=1 loops=15)'
'                                        ->  Index Only Scan using testrand_pkey on testrand testrand_4  (cost=0.43..18876.81 rows=533119 width=8) (actual time=0.007..0.007 rows=1 loops=15)'
'                                              Index Cond: ((trid IS NOT NULL) AND (trid > (($16 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                              Heap Fetches: 15'
'                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.028..0.029 rows=9 loops=15)'
'                SubPlan 15'
'                  ->  Result  (cost=11.71..11.72 rows=1 width=0) (actual time=0.039..0.040 rows=1 loops=6944)'
'                        InitPlan 13 (returns $22)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.031..0.032 rows=1 loops=6944)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=6944)'
'                                      Sort Key: lfoo_3.lmin'
'                                      Sort Method: quicksort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_3  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.029 rows=9 loops=6944)'
'                                            Filter: (lfoo_3.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 7'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=6944)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.007..0.018 rows=16 loops=6944)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=6944)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=6944)'
'                        InitPlan 14 (returns $23)'
'                          ->  Limit  (cost=0.43..0.47 rows=1 width=8) (actual time=0.039..0.039 rows=1 loops=6944)'
'                                ->  Index Only Scan using testrand_pkey on testrand testrand_5  (cost=0.43..18876.81 rows=533119 width=8) (actual time=0.006..0.006 rows=1 loops=6944)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid > (($22 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 6944'
'                SubPlan 18'
'                  ->  Result  (cost=11.71..11.72 rows=1 width=0) (actual time=0.039..0.039 rows=1 loops=6944)'
'                        InitPlan 16 (returns $27)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.032..0.032 rows=1 loops=6944)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=6944)'
'                                      Sort Key: lfoo_4.lmin'
'                                      Sort Method: quicksort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_4  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.029 rows=9 loops=6944)'
'                                            Filter: (lfoo_4.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 7'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=6944)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.007..0.018 rows=16 loops=6944)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=6944)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=6944)'
'                        InitPlan 17 (returns $28)'
'                          ->  Limit  (cost=0.43..0.47 rows=1 width=8) (actual time=0.039..0.039 rows=1 loops=6944)'
'                                ->  Index Only Scan Backward using testrand_pkey on testrand testrand_6  (cost=0.43..18876.81 rows=533119 width=8) (actual time=0.006..0.006 rows=1 loops=6944)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid < (($27 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 6944'
'                SubPlan 22'
'                  ->  Sort  (cost=15.56..15.81 rows=100 width=0) (actual time=0.030..0.030 rows=9 loops=15)'
'                        Sort Key: (unnest((r_1.maxs || $34)))'
'                        Sort Method: quicksort  Memory: 25kB'
'                        InitPlan 21 (returns $34)'
'                          ->  Result  (cost=11.71..11.72 rows=1 width=0) (actual time=0.025..0.025 rows=1 loops=15)'
'                                InitPlan 19 (returns $32)'
'                                  ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.018..0.018 rows=1 loops=15)'
'                                        ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.018..0.018 rows=1 loops=15)'
'                                              Sort Key: lfoo_5.lmin'
'                                              Sort Method: top-N heapsort  Memory: 25kB'
'                                              ->  Subquery Scan on lfoo_5  (cost=4.83..11.08 rows=33 width=16) (actual time=0.006..0.016 rows=4 loops=15)'
'                                                    Filter: (lfoo_5.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                    Rows Removed by Filter: 4'
'                                                    ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.006..0.014 rows=8 loops=15)'
'                                                          ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.005..0.011 rows=8 loops=15)'
'                                                                ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.004..0.004 rows=8 loops=15)'
'                                                                      Sort Key: (unnest(r_1.mins))'
'                                                                      Sort Method: quicksort  Memory: 25kB'
'                                                                      ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.002 rows=8 loops=15)'
'                                InitPlan 20 (returns $33)'
'                                  ->  Limit  (cost=0.43..0.47 rows=1 width=8) (actual time=0.024..0.024 rows=1 loops=15)'
'                                        ->  Index Only Scan Backward using testrand_pkey on testrand testrand_7  (cost=0.43..18876.81 rows=533119 width=8) (actual time=0.005..0.005 rows=1 loops=15)'
'                                              Index Cond: ((trid IS NOT NULL) AND (trid < (($32 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                              Heap Fetches: 15'
'                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.027..0.028 rows=9 loops=15)'
'                SubPlan 25'
'                  ->  Result  (cost=11.71..11.72 rows=1 width=0) (actual time=0.040..0.040 rows=1 loops=6944)'
'                        InitPlan 23 (returns $38)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.032..0.032 rows=1 loops=6944)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=6944)'
'                                      Sort Key: lfoo_6.lmin'
'                                      Sort Method: quicksort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_6  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.029 rows=9 loops=6944)'
'                                            Filter: (lfoo_6.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 7'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=6944)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.007..0.018 rows=16 loops=6944)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=6944)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=6944)'
'                        InitPlan 24 (returns $39)'
'                          ->  Limit  (cost=0.43..0.47 rows=1 width=8) (actual time=0.039..0.039 rows=1 loops=6944)'
'                                ->  Index Only Scan using testrand_pkey on testrand testrand_8  (cost=0.43..18876.81 rows=533119 width=8) (actual time=0.006..0.006 rows=1 loops=6944)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid > (($38 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 6944'
'                SubPlan 28'
'                  ->  Result  (cost=11.71..11.72 rows=1 width=0) (actual time=0.040..0.040 rows=1 loops=6944)'
'                        InitPlan 26 (returns $43)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.032..0.032 rows=1 loops=6944)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=6944)'
'                                      Sort Key: lfoo_7.lmin'
'                                      Sort Method: quicksort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_7  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.029 rows=9 loops=6944)'
'                                            Filter: (lfoo_7.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 7'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=6944)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.007..0.018 rows=16 loops=6944)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=6944)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=6944)'
'                        InitPlan 27 (returns $44)'
'                          ->  Limit  (cost=0.43..0.47 rows=1 width=8) (actual time=0.039..0.039 rows=1 loops=6944)'
'                                ->  Index Only Scan Backward using testrand_pkey on testrand testrand_9  (cost=0.43..18876.81 rows=533119 width=8) (actual time=0.006..0.006 rows=1 loops=6944)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid < (($43 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 6944'
'                SubPlan 31'
'                  ->  Result  (cost=11.71..11.72 rows=1 width=0) (actual time=0.027..0.027 rows=1 loops=15)'
'                        InitPlan 29 (returns $48)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.018..0.018 rows=1 loops=15)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.018..0.018 rows=1 loops=15)'
'                                      Sort Key: lfoo_8.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_8  (cost=4.83..11.08 rows=33 width=16) (actual time=0.006..0.016 rows=4 loops=15)'
'                                            Filter: (lfoo_8.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 4'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.006..0.014 rows=8 loops=15)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.005..0.010 rows=8 loops=15)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.003..0.004 rows=8 loops=15)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.002 rows=8 loops=15)'
'                        InitPlan 30 (returns $49)'
'                          ->  Limit  (cost=0.43..0.47 rows=1 width=8) (actual time=0.026..0.026 rows=1 loops=15)'
'                                ->  Index Only Scan using testrand_pkey on testrand testrand_10  (cost=0.43..18876.81 rows=533119 width=8) (actual time=0.007..0.007 rows=1 loops=15)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid > (($48 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 15'
'                SubPlan 34'
'                  ->  Result  (cost=11.71..11.72 rows=1 width=0) (actual time=0.039..0.039 rows=1 loops=6944)'
'                        InitPlan 32 (returns $53)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.031..0.031 rows=1 loops=6944)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=6944)'
'                                      Sort Key: lfoo_9.lmin'
'                                      Sort Method: quicksort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_9  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.028 rows=9 loops=6944)'
'                                            Filter: (lfoo_9.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 7'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=6944)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.006..0.018 rows=16 loops=6944)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=6944)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=6944)'
'                        InitPlan 33 (returns $54)'
'                          ->  Limit  (cost=0.43..0.47 rows=1 width=8) (actual time=0.039..0.039 rows=1 loops=6944)'
'                                ->  Index Only Scan using testrand_pkey on testrand testrand_11  (cost=0.43..18876.81 rows=533119 width=8) (actual time=0.006..0.006 rows=1 loops=6944)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid > (($53 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 6944'
'                SubPlan 37'
'                  ->  Result  (cost=11.71..11.72 rows=1 width=0) (actual time=0.039..0.040 rows=1 loops=6944)'
'                        InitPlan 35 (returns $58)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.032..0.032 rows=1 loops=6944)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=6944)'
'                                      Sort Key: lfoo_10.lmin'
'                                      Sort Method: quicksort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_10  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.029 rows=9 loops=6944)'
'                                            Filter: (lfoo_10.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 7'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=6944)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.007..0.018 rows=16 loops=6944)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=6944)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=6944)'
'                        InitPlan 36 (returns $59)'
'                          ->  Limit  (cost=0.43..0.47 rows=1 width=8) (actual time=0.039..0.039 rows=1 loops=6944)'
'                                ->  Index Only Scan Backward using testrand_pkey on testrand testrand_12  (cost=0.43..18876.81 rows=533119 width=8) (actual time=0.006..0.006 rows=1 loops=6944)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid < (($58 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 6944'
'                SubPlan 40'
'                  ->  Result  (cost=11.71..11.72 rows=1 width=0) (actual time=0.025..0.026 rows=1 loops=15)'
'                        InitPlan 38 (returns $63)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.018..0.018 rows=1 loops=15)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.018..0.018 rows=1 loops=15)'
'                                      Sort Key: lfoo_11.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_11  (cost=4.83..11.08 rows=33 width=16) (actual time=0.006..0.016 rows=4 loops=15)'
'                                            Filter: (lfoo_11.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 4'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.006..0.014 rows=8 loops=15)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.005..0.010 rows=8 loops=15)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.003..0.004 rows=8 loops=15)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.002 rows=8 loops=15)'
'                        InitPlan 39 (returns $64)'
'                          ->  Limit  (cost=0.43..0.47 rows=1 width=8) (actual time=0.025..0.025 rows=1 loops=15)'
'                                ->  Index Only Scan Backward using testrand_pkey on testrand testrand_13  (cost=0.43..18876.81 rows=533119 width=8) (actual time=0.005..0.005 rows=1 loops=15)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid < (($63 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 15'
'                SubPlan 41'
'                  ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.032..0.032 rows=1 loops=6958)'
'                        ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=6958)'
'                              Sort Key: lfoo_12.lmin'
'                              Sort Method: top-N heapsort  Memory: 25kB'
'                              ->  Subquery Scan on lfoo_12  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.029 rows=9 loops=6958)'
'                                    Filter: (lfoo_12.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                    Rows Removed by Filter: 7'
'                                    ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=6958)'
'                                          ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.007..0.018 rows=16 loops=6958)'
'                                                ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=6958)'
'                                                      Sort Key: (unnest(r_1.mins))'
'                                                      Sort Method: quicksort  Memory: 25kB'
'                                                      ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=6958)'
'  ->  Limit  (cost=0.85..0.85 rows=1 width=32) (actual time=2753.751..2753.751 rows=1 loops=1)'
'        ->  Sort  (cost=0.85..0.93 rows=31 width=32) (actual time=2753.749..2753.749 rows=1 loops=1)'
'              Sort Key: (array_length(r.res, 1))'
'              Sort Method: top-N heapsort  Memory: 25kB'
'              ->  CTE Scan on r  (cost=0.00..0.70 rows=31 width=32) (actual time=0.032..2752.229 rows=6959 loops=1)'
'Total runtime: 2754.553 ms'

-- дороговато выходит восстанавливать карту дырок всякий раз, даже когда их всего 15 (15 интервалов в массивах)
надо б удешевить

...

Рейтинг:

0 / 0

16.11.2014, 13:36:34

| Ответить | Цитировать | Написать

очередной велосипедист

#38807514

?Ы

Гость

PPS

если слегка добавить рядков -- в 5 раз примерно,
то наконец начинаем немного отыгрывать у full-scan- а

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.

SELECT trid FROM testrand 
ORDER BY random() LIMIT 14;
-----------------
'Limit  (cost=327624.25..327624.29 rows=14 width=8) (actual time=1795.577..1795.579 rows=14 loops=1)'
'  ->  Sort  (cost=327624.25..347620.08 rows=7998332 width=8) (actual time=1795.576..1795.577 rows=14 loops=1)'
'        Sort Key: (random())'
'        Sort Method: top-N heapsort  Memory: 25kB'
'        ->  Seq Scan on testrand  (cost=0.00..135370.15 rows=7998332 width=8) (actual time=0.021..963.140 rows=7998178 loops=1)'
'Total runtime: 1795.605 ms'

Код: sql

DEALLOCATE ALL;
PREPARE FOO (BIGINT,BIGINT) AS

WITH RECURSIVE
r (res,mins,maxs ,RRange,cnt ,rnd) AS (
SELECT array[]::BIGINT[] AS res, array[]::BIGINT[]||min(trid) AS mins, array[]::BIGINT[]||max(trid) AS maxs,max(trid) - min(trid) AS RRange, 0 AS cnt, NULL::BIGINT FROM testrand
UNION ALL
SELECT 
	CASE WHEN (trid IS NULL) THEN res ELSE res|| trid END AS res
	,CASE WHEN (trid IS NULL) and ((select MIN(trid) from testrand WHERE trid>rnd) - (select max(trid) from testrand WHERE trid<rnd))> $1
		THEN  ARRAY (SELECT unnest( RR.mins || (select MIN(trid) from testrand WHERE trid>rnd) ) AS u ORDER BY u ) 
		ELSE RR.mins END AS mins
	,CASE WHEN (trid IS NULL) and ((select MIN(trid) from testrand WHERE trid>rnd) - (select max(trid) from testrand WHERE trid<rnd))> $1
		THEN ARRAY (SELECT unnest(RR.maxs || (select max(trid) from testrand WHERE trid<rnd) ) AS u ORDER BY u ) 
		ELSE RR.maxs END AS maxs
	--,(SELECT SUM (Lmax - Lmin) ::BIGINT FROM (SELECT unnest(r.mins) Lmin , unnest(r.maxs) Lmax )) FOO )
	,RR.RRange
	-CASE WHEN (trid IS NULL) and ((select MIN(trid) from testrand WHERE trid>rnd) - (select max(trid) from testrand WHERE trid<rnd))> $1
		THEN (select MIN(trid) from testrand WHERE trid>rnd)
		ELSE 0 END
	+CASE WHEN (trid IS NULL) and ((select MIN(trid) from testrand WHERE trid>rnd) - (select max(trid) from testrand WHERE trid<rnd))> $1
		THEN (select max(trid) from testrand WHERE trid<rnd)
		ELSE 0 END
	AS RRange
	,CASE WHEN (trid IS NULL) THEN cnt ELSE cnt +1 END AS cnt
	--,cnt +1 
	,rnd
FROM 
(SELECT
 --/*
	((SELECT Lmin - LRange -0.5 FROM
		(SELECT Lmin , coalesce (lag(LRange)over(order by Lmin),0) as LRange FROM 
			(SELECT Lmin, sum(Lmax-Lmin)over (order by Lmin) ::BIGINT  as LRange FROM (SELECT unnest(R_FOO.mins) Lmin , unnest(R_FOO.maxs) Lmax) FOO order by Lmin)
		AS LF)		
	AS LFOO
	WHERE LRange < rnd_dlt
	ORDER BY Lmin DESC LIMIT 1
	) +rnd_dlt)::BIGINT
--*/	rnd_dlt 

	AS rnd
			
	,res ,mins,maxs,RRange,cnt FROM
		(SELECT 
		((r.RRange +1)* random())::BIGINT		
		AS rnd_dlt
		,res ,mins,maxs,RRange,cnt FROM r) AS R_FOO
) AS RR
LEFT JOIN testrand ON trid=rnd AND trid <> all(res) 
WHERE 
	cnt<$2
) 
--/*
SELECT unnest(res) FROM (
  SELECT res FROM r ORDER BY array_length(res,1) DESC NULLS LAST LIMIT 1
) AS t;
-- */ SELECT * from r;

EXECUTE foo(1E11,14);
--------------------------------------------------
'Subquery Scan on t  (cost=5403.34..5403.85 rows=100 width=32) (actual time=1048.640..1048.642 rows=14 loops=1)'
'  CTE r'
'    ->  Recursive Union  (cost=0.93..5402.49 rows=31 width=124) (actual time=0.035..1045.100 rows=2651 loops=1)'
'          ->  Result  (cost=0.93..0.95 rows=1 width=0) (actual time=0.034..0.034 rows=1 loops=1)'
'                InitPlan 1 (returns $1)'
'                  ->  Limit  (cost=0.43..0.47 rows=1 width=8) (actual time=0.017..0.017 rows=1 loops=1)'
'                        ->  Index Only Scan using testrand_pkey on testrand  (cost=0.43..263093.24 rows=7998332 width=8) (actual time=0.016..0.016 rows=1 loops=1)'
'                              Index Cond: (trid IS NOT NULL)'
'                              Heap Fetches: 1'
'                InitPlan 2 (returns $2)'
'                  ->  Limit  (cost=0.43..0.47 rows=1 width=8) (actual time=0.011..0.011 rows=1 loops=1)'
'                        ->  Index Only Scan Backward using testrand_pkey on testrand testrand_1  (cost=0.43..263093.24 rows=7998332 width=8) (actual time=0.011..0.011 rows=1 loops=1)'
'                              Index Cond: (trid IS NOT NULL)'
'                              Heap Fetches: 1'
'          ->  Nested Loop Left Join  (cost=11.69..540.09 rows=3 width=124) (actual time=0.393..0.393 rows=1 loops=2651)'
'                ->  WorkTable Scan on r r_1  (cost=0.00..0.26 rows=3 width=108) (actual time=0.001..0.001 rows=1 loops=2651)'
'                      Filter: (cnt < $2)'
'                      Rows Removed by Filter: 0'
'                ->  Index Only Scan using testrand_pkey on testrand testrand_14  (cost=11.69..19.72 rows=1 width=8) (actual time=0.005..0.005 rows=0 loops=2650)'
'                      Index Cond: (trid = (((SubPlan 42) + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint)'
'                      Filter: (trid <> ALL (r_1.res))'
'                      Heap Fetches: 14'
'                      SubPlan 42'
'                        ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.031..0.031 rows=1 loops=2650)'
'                              ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=2650)'
'                                    Sort Key: lfoo_13.lmin'
'                                    Sort Method: top-N heapsort  Memory: 25kB'
'                                    ->  Subquery Scan on lfoo_13  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.028 rows=8 loops=2650)'
'                                          Filter: (lfoo_13.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                          Rows Removed by Filter: 8'
'                                          ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=2650)'
'                                                ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.006..0.018 rows=16 loops=2650)'
'                                                      ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=2650)'
'                                                            Sort Key: (unnest(r_1.mins))'
'                                                            Sort Method: quicksort  Memory: 25kB'
'                                                            ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2650)'
'                      SubPlan 42'
'                        ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.031..0.031 rows=1 loops=2650)'
'                              ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=2650)'
'                                    Sort Key: lfoo_13.lmin'
'                                    Sort Method: top-N heapsort  Memory: 25kB'
'                                    ->  Subquery Scan on lfoo_13  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.028 rows=8 loops=2650)'
'                                          Filter: (lfoo_13.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                          Rows Removed by Filter: 8'
'                                          ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=2650)'
'                                                ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.006..0.018 rows=16 loops=2650)'
'                                                      ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=2650)'
'                                                            Sort Key: (unnest(r_1.mins))'
'                                                            Sort Method: quicksort  Memory: 25kB'
'                                                            ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2650)'
'                SubPlan 5'
'                  ->  Result  (cost=11.72..11.73 rows=1 width=0) (actual time=0.042..0.042 rows=1 loops=2636)'
'                        InitPlan 3 (returns $6)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.032..0.032 rows=1 loops=2636)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=2636)'
'                                      Sort Key: lfoo.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.029 rows=8 loops=2636)'
'                                            Filter: (lfoo.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 8'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=2636)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.007..0.018 rows=16 loops=2636)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=2636)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2636)'
'                        InitPlan 4 (returns $7)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.042..0.042 rows=1 loops=2636)'
'                                ->  Index Only Scan using testrand_pkey on testrand testrand_2  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.009..0.009 rows=1 loops=2636)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid > (($6 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2636'
'                SubPlan 8'
'                  ->  Result  (cost=11.72..11.73 rows=1 width=0) (actual time=0.039..0.040 rows=1 loops=2636)'
'                        InitPlan 6 (returns $11)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.032..0.032 rows=1 loops=2636)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=2636)'
'                                      Sort Key: lfoo_1.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_1  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.029 rows=8 loops=2636)'
'                                            Filter: (lfoo_1.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 8'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=2636)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.007..0.018 rows=16 loops=2636)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=2636)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2636)'
'                        InitPlan 7 (returns $12)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.039..0.039 rows=1 loops=2636)'
'                                ->  Index Only Scan Backward using testrand_pkey on testrand testrand_3  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=2636)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid < (($11 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2636'
'                SubPlan 12'
'                  ->  Sort  (cost=15.56..15.81 rows=100 width=0) (actual time=0.032..0.032 rows=9 loops=15)'
'                        Sort Key: (unnest((r_1.mins || $18)))'
'                        Sort Method: quicksort  Memory: 25kB'
'                        InitPlan 11 (returns $18)'
'                          ->  Result  (cost=11.72..11.73 rows=1 width=0) (actual time=0.027..0.027 rows=1 loops=15)'
'                                InitPlan 9 (returns $16)'
'                                  ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.018..0.018 rows=1 loops=15)'
'                                        ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.018..0.018 rows=1 loops=15)'
'                                              Sort Key: lfoo_2.lmin'
'                                              Sort Method: top-N heapsort  Memory: 25kB'
'                                              ->  Subquery Scan on lfoo_2  (cost=4.83..11.08 rows=33 width=16) (actual time=0.006..0.016 rows=5 loops=15)'
'                                                    Filter: (lfoo_2.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                    Rows Removed by Filter: 3'
'                                                    ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.006..0.014 rows=8 loops=15)'
'                                                          ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.005..0.011 rows=8 loops=15)'
'                                                                ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.004..0.004 rows=8 loops=15)'
'                                                                      Sort Key: (unnest(r_1.mins))'
'                                                                      Sort Method: quicksort  Memory: 25kB'
'                                                                      ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.002 rows=8 loops=15)'
'                                InitPlan 10 (returns $17)'
'                                  ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.027..0.027 rows=1 loops=15)'
'                                        ->  Index Only Scan using testrand_pkey on testrand testrand_4  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.007..0.007 rows=1 loops=15)'
'                                              Index Cond: ((trid IS NOT NULL) AND (trid > (($16 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                              Heap Fetches: 15'
'                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.029..0.030 rows=9 loops=15)'
'                SubPlan 15'
'                  ->  Result  (cost=11.72..11.73 rows=1 width=0) (actual time=0.039..0.039 rows=1 loops=2636)'
'                        InitPlan 13 (returns $22)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.031..0.031 rows=1 loops=2636)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=2636)'
'                                      Sort Key: lfoo_3.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_3  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.028 rows=8 loops=2636)'
'                                            Filter: (lfoo_3.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 8'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=2636)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.007..0.018 rows=16 loops=2636)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=2636)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2636)'
'                        InitPlan 14 (returns $23)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.039..0.039 rows=1 loops=2636)'
'                                ->  Index Only Scan using testrand_pkey on testrand testrand_5  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=2636)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid > (($22 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2636'
'                SubPlan 18'
'                  ->  Result  (cost=11.72..11.73 rows=1 width=0) (actual time=0.039..0.039 rows=1 loops=2636)'
'                        InitPlan 16 (returns $27)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.031..0.031 rows=1 loops=2636)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=2636)'
'                                      Sort Key: lfoo_4.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_4  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.028 rows=8 loops=2636)'
'                                            Filter: (lfoo_4.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 8'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=2636)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.007..0.018 rows=16 loops=2636)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=2636)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2636)'
'                        InitPlan 17 (returns $28)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.038..0.038 rows=1 loops=2636)'
'                                ->  Index Only Scan Backward using testrand_pkey on testrand testrand_6  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=2636)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid < (($27 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2636'
'                SubPlan 22'
'                  ->  Sort  (cost=15.56..15.81 rows=100 width=0) (actual time=0.031..0.031 rows=9 loops=15)'
'                        Sort Key: (unnest((r_1.maxs || $34)))'
'                        Sort Method: quicksort  Memory: 25kB'
'                        InitPlan 21 (returns $34)'
'                          ->  Result  (cost=11.72..11.73 rows=1 width=0) (actual time=0.026..0.026 rows=1 loops=15)'
'                                InitPlan 19 (returns $32)'
'                                  ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.018..0.018 rows=1 loops=15)'
'                                        ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.018..0.018 rows=1 loops=15)'
'                                              Sort Key: lfoo_5.lmin'
'                                              Sort Method: top-N heapsort  Memory: 25kB'
'                                              ->  Subquery Scan on lfoo_5  (cost=4.83..11.08 rows=33 width=16) (actual time=0.006..0.016 rows=5 loops=15)'
'                                                    Filter: (lfoo_5.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                    Rows Removed by Filter: 3'
'                                                    ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.006..0.014 rows=8 loops=15)'
'                                                          ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.005..0.010 rows=8 loops=15)'
'                                                                ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.003..0.003 rows=8 loops=15)'
'                                                                      Sort Key: (unnest(r_1.mins))'
'                                                                      Sort Method: quicksort  Memory: 25kB'
'                                                                      ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.002 rows=8 loops=15)'
'                                InitPlan 20 (returns $33)'
'                                  ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.025..0.025 rows=1 loops=15)'
'                                        ->  Index Only Scan Backward using testrand_pkey on testrand testrand_7  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=15)'
'                                              Index Cond: ((trid IS NOT NULL) AND (trid < (($32 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                              Heap Fetches: 15'
'                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.028..0.028 rows=9 loops=15)'
'                SubPlan 25'
'                  ->  Result  (cost=11.72..11.73 rows=1 width=0) (actual time=0.039..0.039 rows=1 loops=2636)'
'                        InitPlan 23 (returns $38)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.031..0.031 rows=1 loops=2636)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=2636)'
'                                      Sort Key: lfoo_6.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_6  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.028 rows=8 loops=2636)'
'                                            Filter: (lfoo_6.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 8'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=2636)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.007..0.018 rows=16 loops=2636)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=2636)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2636)'
'                        InitPlan 24 (returns $39)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.039..0.039 rows=1 loops=2636)'
'                                ->  Index Only Scan using testrand_pkey on testrand testrand_8  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=2636)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid > (($38 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2636'
'                SubPlan 28'
'                  ->  Result  (cost=11.72..11.73 rows=1 width=0) (actual time=0.039..0.039 rows=1 loops=2636)'
'                        InitPlan 26 (returns $43)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.032..0.032 rows=1 loops=2636)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=2636)'
'                                      Sort Key: lfoo_7.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_7  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.028 rows=8 loops=2636)'
'                                            Filter: (lfoo_7.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 8'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=2636)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.007..0.018 rows=16 loops=2636)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=2636)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2636)'
'                        InitPlan 27 (returns $44)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.039..0.039 rows=1 loops=2636)'
'                                ->  Index Only Scan Backward using testrand_pkey on testrand testrand_9  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=2636)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid < (($43 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2636'
'                SubPlan 31'
'                  ->  Result  (cost=11.72..11.73 rows=1 width=0) (actual time=0.027..0.027 rows=1 loops=15)'
'                        InitPlan 29 (returns $48)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.019..0.019 rows=1 loops=15)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.018..0.018 rows=1 loops=15)'
'                                      Sort Key: lfoo_8.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_8  (cost=4.83..11.08 rows=33 width=16) (actual time=0.007..0.016 rows=5 loops=15)'
'                                            Filter: (lfoo_8.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 3'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.006..0.014 rows=8 loops=15)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.005..0.010 rows=8 loops=15)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.003..0.004 rows=8 loops=15)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.002 rows=8 loops=15)'
'                        InitPlan 30 (returns $49)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.026..0.026 rows=1 loops=15)'
'                                ->  Index Only Scan using testrand_pkey on testrand testrand_10  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=15)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid > (($48 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 15'
'                SubPlan 34'
'                  ->  Result  (cost=11.72..11.73 rows=1 width=0) (actual time=0.039..0.039 rows=1 loops=2636)'
'                        InitPlan 32 (returns $53)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.031..0.031 rows=1 loops=2636)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=2636)'
'                                      Sort Key: lfoo_9.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_9  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.028 rows=8 loops=2636)'
'                                            Filter: (lfoo_9.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 8'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=2636)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.006..0.018 rows=16 loops=2636)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=2636)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2636)'
'                        InitPlan 33 (returns $54)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.039..0.039 rows=1 loops=2636)'
'                                ->  Index Only Scan using testrand_pkey on testrand testrand_11  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=2636)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid > (($53 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2636'
'                SubPlan 37'
'                  ->  Result  (cost=11.72..11.73 rows=1 width=0) (actual time=0.039..0.039 rows=1 loops=2636)'
'                        InitPlan 35 (returns $58)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.031..0.031 rows=1 loops=2636)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=2636)'
'                                      Sort Key: lfoo_10.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_10  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.028 rows=8 loops=2636)'
'                                            Filter: (lfoo_10.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 8'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=2636)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.006..0.018 rows=16 loops=2636)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=2636)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2636)'
'                        InitPlan 36 (returns $59)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.038..0.038 rows=1 loops=2636)'
'                                ->  Index Only Scan Backward using testrand_pkey on testrand testrand_12  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=2636)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid < (($58 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2636'
'                SubPlan 40'
'                  ->  Result  (cost=11.72..11.73 rows=1 width=0) (actual time=0.026..0.026 rows=1 loops=15)'
'                        InitPlan 38 (returns $63)'
'                          ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.018..0.018 rows=1 loops=15)'
'                                ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.018..0.018 rows=1 loops=15)'
'                                      Sort Key: lfoo_11.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lfoo_11  (cost=4.83..11.08 rows=33 width=16) (actual time=0.006..0.016 rows=5 loops=15)'
'                                            Filter: (lfoo_11.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                            Rows Removed by Filter: 3'
'                                            ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.006..0.014 rows=8 loops=15)'
'                                                  ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.005..0.010 rows=8 loops=15)'
'                                                        ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.003..0.004 rows=8 loops=15)'
'                                                              Sort Key: (unnest(r_1.mins))'
'                                                              Sort Method: quicksort  Memory: 25kB'
'                                                              ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.002 rows=8 loops=15)'
'                        InitPlan 39 (returns $64)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.026..0.026 rows=1 loops=15)'
'                                ->  Index Only Scan Backward using testrand_pkey on testrand testrand_13  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=15)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid < (($63 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 15'
'                SubPlan 41'
'                  ->  Limit  (cost=11.24..11.25 rows=1 width=16) (actual time=0.031..0.031 rows=1 loops=2650)'
'                        ->  Sort  (cost=11.24..11.33 rows=33 width=16) (actual time=0.031..0.031 rows=1 loops=2650)'
'                              Sort Key: lfoo_12.lmin'
'                              Sort Method: top-N heapsort  Memory: 25kB'
'                              ->  Subquery Scan on lfoo_12  (cost=4.83..11.08 rows=33 width=16) (actual time=0.008..0.028 rows=8 loops=2650)'
'                                    Filter: (lfoo_12.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                    Rows Removed by Filter: 8'
'                                    ->  WindowAgg  (cost=4.83..9.58 rows=100 width=16) (actual time=0.007..0.024 rows=16 loops=2650)'
'                                          ->  WindowAgg  (cost=4.83..7.08 rows=100 width=16) (actual time=0.006..0.018 rows=16 loops=2650)'
'                                                ->  Sort  (cost=4.83..5.08 rows=100 width=16) (actual time=0.005..0.006 rows=16 loops=2650)'
'                                                      Sort Key: (unnest(r_1.mins))'
'                                                      Sort Method: quicksort  Memory: 25kB'
'                                                      ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2650)'
'  ->  Limit  (cost=0.85..0.85 rows=1 width=32) (actual time=1048.636..1048.636 rows=1 loops=1)'
'        ->  Sort  (cost=0.85..0.93 rows=31 width=32) (actual time=1048.635..1048.635 rows=1 loops=1)'
'              Sort Key: (array_length(r.res, 1))'
'              Sort Method: top-N heapsort  Memory: 25kB'
'              ->  CTE Scan on r  (cost=0.00..0.70 rows=31 width=32) (actual time=0.039..1048.057 rows=2651 loops=1)'
'Total runtime: 1049.227 ms'

и если перенести расчет карты дырок на моменты попадания в большие дырки ( а не высчитывать всякий раз), то немного ускоряемся:

Код: sql

DEALLOCATE ALL;
PREPARE FOO2 (BIGINT,BIGINT) AS

WITH RECURSIVE
r (res, mins,maxs ,RRange,LRanges,cnt ,rnd) AS (
SELECT array[]::BIGINT[] AS res 
	,array[]::BIGINT[]||min(trid) AS mins, array[]::BIGINT[]||max(trid) AS maxs,max(trid) - min(trid) AS RRange
	,ARRAY[0::bigint] AS LRanges , 0 AS cnt, NULL::BIGINT FROM testrand
UNION ALL
SELECT 
	CASE WHEN (trid IS NULL) THEN res ELSE res|| trid END AS res
	,CASE WHEN (trid IS NULL) and ((select MIN(trid) from testrand WHERE trid>rnd) - (select max(trid) from testrand WHERE trid<rnd))> $1
		THEN  ARRAY (SELECT unnest( RR.mins || (select MIN(trid) from testrand WHERE trid>rnd) ) AS u ORDER BY u ) 
		ELSE RR.mins END AS mins
	,CASE WHEN (trid IS NULL) and ((select MIN(trid) from testrand WHERE trid>rnd) - (select max(trid) from testrand WHERE trid<rnd))> $1
		THEN ARRAY (SELECT unnest(RR.maxs || (select max(trid) from testrand WHERE trid<rnd) ) AS u ORDER BY u ) 
		ELSE RR.maxs END AS maxs
	--,(SELECT SUM (Lmax - Lmin) ::BIGINT FROM (SELECT unnest(r.mins) Lmin , unnest(r.maxs) Lmax )) FOO )
	,RR.RRange
	-CASE WHEN (trid IS NULL) and ((select MIN(trid) from testrand WHERE trid>rnd) - (select max(trid) from testrand WHERE trid<rnd))> $1
		THEN (select MIN(trid) from testrand WHERE trid>rnd)
		ELSE 0 END
	+CASE WHEN (trid IS NULL) and ((select MIN(trid) from testrand WHERE trid>rnd) - (select max(trid) from testrand WHERE trid<rnd))> $1
		THEN (select max(trid) from testrand WHERE trid<rnd)
		ELSE 0 END
	AS RRange
	,CASE WHEN (trid IS NULL) and ((select MIN(trid) from testrand WHERE trid>rnd) - (select max(trid) from testrand WHERE trid<rnd))> $1
		THEN 
			ARRAY [0::bigint] || ARRAY(
			(SELECT LRANGE FROM (
				SELECT sum(Lmax - Lmin) OVER(ORDER BY Lmin)::BIGINT  LRANGE,Lmin  FROM (
					SELECT 
					unnest( ARRAY (SELECT unnest(RR.maxs || (select max(trid) from testrand WHERE trid<rnd) ) AS u ORDER BY u ) )  AS Lmax
					,unnest(ARRAY (SELECT unnest(RR.mins || (select MIN(trid) from testrand WHERE trid>rnd) ) AS u ORDER BY u )) Lmin
					) fL 
				ORDER BY Lmin DESC OFFSET 1 --подгоняем кратность unnest-ов
				) FR ORDER BY Lmin
			)
			)
		
		ELSE LRanges END
	AS LRanges	
	,CASE WHEN (trid IS NULL) THEN cnt ELSE cnt +1 END AS cnt
	--,cnt +1 
	,rnd
FROM 
(SELECT
 --/*
	((SELECT Lmin - LRange -0.5 FROM
		(SELECT Lmin , Lrange FROM 
			(select * from (SELECT unnest(R_FOO.mins) Lmin , unnest(R_FOO.LRanges) Lrange) FOO order by Lmin)
		AS LF)	
	AS LFOO
	WHERE LRange < rnd_dlt
	ORDER BY Lmin DESC LIMIT 1
	) +rnd_dlt)::BIGINT
--*/	rnd_dlt 
	AS rnd
			
	,res,mins,maxs,RRange,LRanges,cnt FROM
		(SELECT 
		((r.RRange +1)* random())::BIGINT		
		AS rnd_dlt
		,res,mins,maxs,RRange,cnt,LRanges FROM r) AS R_FOO
) AS RR
LEFT JOIN testrand ON trid=rnd AND trid <> all(res) 
WHERE 
	cnt<$2
) 

--/*
SELECT unnest(res) FROM (
  SELECT res FROM r ORDER BY array_length(res,1) DESC NULLS LAST LIMIT 1
) AS t;
-- */ SELECT * from r;

EXECUTE foo2(3E8::bigint,14);
------------------------------------
'Subquery Scan on t  (cost=3284.61..3285.12 rows=100 width=32) (actual time=575.324..575.326 rows=14 loops=1)'
'  CTE r'
'    ->  Recursive Union  (cost=0.93..3283.76 rows=31 width=156) (actual time=0.055..571.556 rows=2274 loops=1)'
'          ->  Result  (cost=0.93..0.95 rows=1 width=0) (actual time=0.053..0.054 rows=1 loops=1)'
'                InitPlan 1 (returns $1)'
'                  ->  Limit  (cost=0.43..0.47 rows=1 width=8) (actual time=0.023..0.023 rows=1 loops=1)'
'                        ->  Index Only Scan using testrand_pkey on testrand  (cost=0.43..263093.24 rows=7998332 width=8) (actual time=0.023..0.023 rows=1 loops=1)'
'                              Index Cond: (trid IS NOT NULL)'
'                              Heap Fetches: 1'
'                InitPlan 2 (returns $2)'
'                  ->  Limit  (cost=0.43..0.47 rows=1 width=8) (actual time=0.019..0.019 rows=1 loops=1)'
'                        ->  Index Only Scan Backward using testrand_pkey on testrand testrand_1  (cost=0.43..263093.24 rows=7998332 width=8) (actual time=0.018..0.018 rows=1 loops=1)'
'                              Index Cond: (trid IS NOT NULL)'
'                              Heap Fetches: 1'
'          ->  Nested Loop Left Join  (cost=3.86..328.22 rows=3 width=156) (actual time=0.249..0.250 rows=1 loops=2274)'
'                ->  WorkTable Scan on r r_1  (cost=0.00..0.26 rows=3 width=140) (actual time=0.001..0.001 rows=1 loops=2274)'
'                      Filter: (cnt < $2)'
'                      Rows Removed by Filter: 0'
'                ->  Index Only Scan using testrand_pkey on testrand testrand_18  (cost=3.86..11.89 rows=1 width=8) (actual time=0.005..0.005 rows=0 loops=2273)'
'                      Index Cond: (trid = (((SubPlan 57) + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint)'
'                      Filter: (trid <> ALL (r_1.res))'
'                      Heap Fetches: 14'
'                      SubPlan 57'
'                        ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.013..0.013 rows=1 loops=2273)'
'                              ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.012..0.012 rows=1 loops=2273)'
'                                    Sort Key: lf_17.lmin'
'                                    Sort Method: top-N heapsort  Memory: 25kB'
'                                    ->  Subquery Scan on lf_17  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.010 rows=8 loops=2273)'
'                                          ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=8 loops=2273)'
'                                                Sort Key: foo_17.lmin'
'                                                Sort Method: quicksort  Memory: 25kB'
'                                                ->  Subquery Scan on foo_17  (cost=0.00..1.76 rows=33 width=16) (actual time=0.001..0.004 rows=8 loops=2273)'
'                                                      Filter: (foo_17.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                      Rows Removed by Filter: 8'
'                                                      ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2273)'
'                      SubPlan 57'
'                        ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.013..0.013 rows=1 loops=2273)'
'                              ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.012..0.012 rows=1 loops=2273)'
'                                    Sort Key: lf_17.lmin'
'                                    Sort Method: top-N heapsort  Memory: 25kB'
'                                    ->  Subquery Scan on lf_17  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.010 rows=8 loops=2273)'
'                                          ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=8 loops=2273)'
'                                                Sort Key: foo_17.lmin'
'                                                Sort Method: quicksort  Memory: 25kB'
'                                                ->  Subquery Scan on foo_17  (cost=0.00..1.76 rows=33 width=16) (actual time=0.001..0.004 rows=8 loops=2273)'
'                                                      Filter: (foo_17.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                      Rows Removed by Filter: 8'
'                                                      ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2273)'
'                SubPlan 5'
'                  ->  Result  (cost=3.89..3.90 rows=1 width=0) (actual time=0.023..0.023 rows=1 loops=2259)'
'                        InitPlan 3 (returns $6)'
'                          ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.013..0.013 rows=1 loops=2259)'
'                                ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.012..0.012 rows=1 loops=2259)'
'                                      Sort Key: lf.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lf  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.010 rows=8 loops=2259)'
'                                            ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=8 loops=2259)'
'                                                  Sort Key: foo.lmin'
'                                                  Sort Method: quicksort  Memory: 25kB'
'                                                  ->  Subquery Scan on foo  (cost=0.00..1.76 rows=33 width=16) (actual time=0.001..0.004 rows=8 loops=2259)'
'                                                        Filter: (foo.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                        Rows Removed by Filter: 8'
'                                                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2259)'
'                        InitPlan 4 (returns $7)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.023..0.023 rows=1 loops=2259)'
'                                ->  Index Only Scan using testrand_pkey on testrand testrand_2  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.009..0.009 rows=1 loops=2259)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid > (($6 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2259'
'                SubPlan 8'
'                  ->  Result  (cost=3.89..3.90 rows=1 width=0) (actual time=0.021..0.021 rows=1 loops=2259)'
'                        InitPlan 6 (returns $11)'
'                          ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.013..0.013 rows=1 loops=2259)'
'                                ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.013..0.013 rows=1 loops=2259)'
'                                      Sort Key: lf_1.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lf_1  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.010 rows=8 loops=2259)'
'                                            ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=8 loops=2259)'
'                                                  Sort Key: foo_1.lmin'
'                                                  Sort Method: quicksort  Memory: 25kB'
'                                                  ->  Subquery Scan on foo_1  (cost=0.00..1.76 rows=33 width=16) (actual time=0.001..0.004 rows=8 loops=2259)'
'                                                        Filter: (foo_1.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                        Rows Removed by Filter: 8'
'                                                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2259)'
'                        InitPlan 7 (returns $12)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.020..0.020 rows=1 loops=2259)'
'                                ->  Index Only Scan Backward using testrand_pkey on testrand testrand_3  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=2259)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid < (($11 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2259'
'                SubPlan 12'
'                  ->  Sort  (cost=7.73..7.98 rows=100 width=0) (actual time=0.033..0.034 rows=9 loops=15)'
'                        Sort Key: (unnest((r_1.mins || $18)))'
'                        Sort Method: quicksort  Memory: 25kB'
'                        InitPlan 11 (returns $18)'
'                          ->  Result  (cost=3.89..3.90 rows=1 width=0) (actual time=0.026..0.026 rows=1 loops=15)'
'                                InitPlan 9 (returns $16)'
'                                  ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.012..0.013 rows=1 loops=15)'
'                                        ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.012..0.012 rows=1 loops=15)'
'                                              Sort Key: lf_2.lmin'
'                                              Sort Method: top-N heapsort  Memory: 25kB'
'                                              ->  Subquery Scan on lf_2  (cost=2.59..3.25 rows=33 width=16) (actual time=0.008..0.010 rows=4 loops=15)'
'                                                    ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.007 rows=4 loops=15)'
'                                                          Sort Key: foo_2.lmin'
'                                                          Sort Method: quicksort  Memory: 25kB'
'                                                          ->  Subquery Scan on foo_2  (cost=0.00..1.76 rows=33 width=16) (actual time=0.002..0.004 rows=4 loops=15)'
'                                                                Filter: (foo_2.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                                Rows Removed by Filter: 4'
'                                                                ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=8 loops=15)'
'                                InitPlan 10 (returns $17)'
'                                  ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.025..0.025 rows=1 loops=15)'
'                                        ->  Index Only Scan using testrand_pkey on testrand testrand_4  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.010..0.010 rows=1 loops=15)'
'                                              Index Cond: ((trid IS NOT NULL) AND (trid > (($16 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                              Heap Fetches: 15'
'                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.029..0.030 rows=9 loops=15)'
'                SubPlan 15'
'                  ->  Result  (cost=3.89..3.90 rows=1 width=0) (actual time=0.021..0.021 rows=1 loops=2259)'
'                        InitPlan 13 (returns $22)'
'                          ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.013..0.013 rows=1 loops=2259)'
'                                ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.012..0.012 rows=1 loops=2259)'
'                                      Sort Key: lf_3.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lf_3  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.010 rows=8 loops=2259)'
'                                            ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=8 loops=2259)'
'                                                  Sort Key: foo_3.lmin'
'                                                  Sort Method: quicksort  Memory: 25kB'
'                                                  ->  Subquery Scan on foo_3  (cost=0.00..1.76 rows=33 width=16) (actual time=0.001..0.004 rows=8 loops=2259)'
'                                                        Filter: (foo_3.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                        Rows Removed by Filter: 8'
'                                                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2259)'
'                        InitPlan 14 (returns $23)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.020..0.020 rows=1 loops=2259)'
'                                ->  Index Only Scan using testrand_pkey on testrand testrand_5  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=2259)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid > (($22 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2259'
'                SubPlan 18'
'                  ->  Result  (cost=3.89..3.90 rows=1 width=0) (actual time=0.020..0.020 rows=1 loops=2259)'
'                        InitPlan 16 (returns $27)'
'                          ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.013..0.013 rows=1 loops=2259)'
'                                ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.012..0.012 rows=1 loops=2259)'
'                                      Sort Key: lf_4.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lf_4  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.010 rows=8 loops=2259)'
'                                            ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=8 loops=2259)'
'                                                  Sort Key: foo_4.lmin'
'                                                  Sort Method: quicksort  Memory: 25kB'
'                                                  ->  Subquery Scan on foo_4  (cost=0.00..1.76 rows=33 width=16) (actual time=0.001..0.004 rows=8 loops=2259)'
'                                                        Filter: (foo_4.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                        Rows Removed by Filter: 8'
'                                                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2259)'
'                        InitPlan 17 (returns $28)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.020..0.020 rows=1 loops=2259)'
'                                ->  Index Only Scan Backward using testrand_pkey on testrand testrand_6  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=2259)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid < (($27 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2259'
'                SubPlan 22'
'                  ->  Sort  (cost=7.73..7.98 rows=100 width=0) (actual time=0.031..0.031 rows=9 loops=15)'
'                        Sort Key: (unnest((r_1.maxs || $34)))'
'                        Sort Method: quicksort  Memory: 25kB'
'                        InitPlan 21 (returns $34)'
'                          ->  Result  (cost=3.89..3.90 rows=1 width=0) (actual time=0.023..0.023 rows=1 loops=15)'
'                                InitPlan 19 (returns $32)'
'                                  ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.012..0.012 rows=1 loops=15)'
'                                        ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.012..0.012 rows=1 loops=15)'
'                                              Sort Key: lf_5.lmin'
'                                              Sort Method: top-N heapsort  Memory: 25kB'
'                                              ->  Subquery Scan on lf_5  (cost=2.59..3.25 rows=33 width=16) (actual time=0.008..0.010 rows=4 loops=15)'
'                                                    ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=4 loops=15)'
'                                                          Sort Key: foo_5.lmin'
'                                                          Sort Method: quicksort  Memory: 25kB'
'                                                          ->  Subquery Scan on foo_5  (cost=0.00..1.76 rows=33 width=16) (actual time=0.002..0.005 rows=4 loops=15)'
'                                                                Filter: (foo_5.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                                Rows Removed by Filter: 4'
'                                                                ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=8 loops=15)'
'                                InitPlan 20 (returns $33)'
'                                  ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.022..0.022 rows=1 loops=15)'
'                                        ->  Index Only Scan Backward using testrand_pkey on testrand testrand_7  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.008..0.008 rows=1 loops=15)'
'                                              Index Cond: ((trid IS NOT NULL) AND (trid < (($32 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                              Heap Fetches: 15'
'                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.026..0.027 rows=9 loops=15)'
'                SubPlan 25'
'                  ->  Result  (cost=3.89..3.90 rows=1 width=0) (actual time=0.021..0.021 rows=1 loops=2259)'
'                        InitPlan 23 (returns $39)'
'                          ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.013..0.013 rows=1 loops=2259)'
'                                ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.013..0.013 rows=1 loops=2259)'
'                                      Sort Key: lf_6.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lf_6  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.010 rows=8 loops=2259)'
'                                            ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=8 loops=2259)'
'                                                  Sort Key: foo_6.lmin'
'                                                  Sort Method: quicksort  Memory: 25kB'
'                                                  ->  Subquery Scan on foo_6  (cost=0.00..1.76 rows=33 width=16) (actual time=0.001..0.004 rows=8 loops=2259)'
'                                                        Filter: (foo_6.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                        Rows Removed by Filter: 8'
'                                                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2259)'
'                        InitPlan 24 (returns $40)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.020..0.020 rows=1 loops=2259)'
'                                ->  Index Only Scan using testrand_pkey on testrand testrand_8  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=2259)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid > (($39 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2259'
'                SubPlan 28'
'                  ->  Result  (cost=3.89..3.90 rows=1 width=0) (actual time=0.020..0.020 rows=1 loops=2259)'
'                        InitPlan 26 (returns $44)'
'                          ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.013..0.013 rows=1 loops=2259)'
'                                ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.012..0.012 rows=1 loops=2259)'
'                                      Sort Key: lf_7.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lf_7  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.010 rows=8 loops=2259)'
'                                            ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=8 loops=2259)'
'                                                  Sort Key: foo_7.lmin'
'                                                  Sort Method: quicksort  Memory: 25kB'
'                                                  ->  Subquery Scan on foo_7  (cost=0.00..1.76 rows=33 width=16) (actual time=0.001..0.004 rows=8 loops=2259)'
'                                                        Filter: (foo_7.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                        Rows Removed by Filter: 8'
'                                                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2259)'
'                        InitPlan 27 (returns $45)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.020..0.020 rows=1 loops=2259)'
'                                ->  Index Only Scan Backward using testrand_pkey on testrand testrand_9  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=2259)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid < (($44 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2259'
'                SubPlan 31'
'                  ->  Result  (cost=3.89..3.90 rows=1 width=0) (actual time=0.025..0.025 rows=1 loops=15)'
'                        InitPlan 29 (returns $49)'
'                          ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.013..0.013 rows=1 loops=15)'
'                                ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.012..0.012 rows=1 loops=15)'
'                                      Sort Key: lf_8.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lf_8  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.009 rows=4 loops=15)'
'                                            ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=4 loops=15)'
'                                                  Sort Key: foo_8.lmin'
'                                                  Sort Method: quicksort  Memory: 25kB'
'                                                  ->  Subquery Scan on foo_8  (cost=0.00..1.76 rows=33 width=16) (actual time=0.002..0.004 rows=4 loops=15)'
'                                                        Filter: (foo_8.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                        Rows Removed by Filter: 4'
'                                                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=8 loops=15)'
'                        InitPlan 30 (returns $50)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.025..0.025 rows=1 loops=15)'
'                                ->  Index Only Scan using testrand_pkey on testrand testrand_10  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.010..0.010 rows=1 loops=15)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid > (($49 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 15'
'                SubPlan 34'
'                  ->  Result  (cost=3.89..3.90 rows=1 width=0) (actual time=0.021..0.021 rows=1 loops=2259)'
'                        InitPlan 32 (returns $54)'
'                          ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.013..0.013 rows=1 loops=2259)'
'                                ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.012..0.012 rows=1 loops=2259)'
'                                      Sort Key: lf_9.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lf_9  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.010 rows=8 loops=2259)'
'                                            ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=8 loops=2259)'
'                                                  Sort Key: foo_9.lmin'
'                                                  Sort Method: quicksort  Memory: 25kB'
'                                                  ->  Subquery Scan on foo_9  (cost=0.00..1.76 rows=33 width=16) (actual time=0.001..0.004 rows=8 loops=2259)'
'                                                        Filter: (foo_9.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                        Rows Removed by Filter: 8'
'                                                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2259)'
'                        InitPlan 33 (returns $55)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.020..0.020 rows=1 loops=2259)'
'                                ->  Index Only Scan using testrand_pkey on testrand testrand_11  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=2259)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid > (($54 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2259'
'                SubPlan 37'
'                  ->  Result  (cost=3.89..3.90 rows=1 width=0) (actual time=0.020..0.020 rows=1 loops=2259)'
'                        InitPlan 35 (returns $59)'
'                          ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.013..0.013 rows=1 loops=2259)'
'                                ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.012..0.012 rows=1 loops=2259)'
'                                      Sort Key: lf_10.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lf_10  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.010 rows=8 loops=2259)'
'                                            ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=8 loops=2259)'
'                                                  Sort Key: foo_10.lmin'
'                                                  Sort Method: quicksort  Memory: 25kB'
'                                                  ->  Subquery Scan on foo_10  (cost=0.00..1.76 rows=33 width=16) (actual time=0.001..0.004 rows=8 loops=2259)'
'                                                        Filter: (foo_10.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                        Rows Removed by Filter: 8'
'                                                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2259)'
'                        InitPlan 36 (returns $60)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.020..0.020 rows=1 loops=2259)'
'                                ->  Index Only Scan Backward using testrand_pkey on testrand testrand_12  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=2259)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid < (($59 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2259'
'                SubPlan 40'
'                  ->  Result  (cost=3.89..3.90 rows=1 width=0) (actual time=0.023..0.023 rows=1 loops=15)'
'                        InitPlan 38 (returns $64)'
'                          ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.012..0.013 rows=1 loops=15)'
'                                ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.012..0.012 rows=1 loops=15)'
'                                      Sort Key: lf_11.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lf_11  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.009 rows=4 loops=15)'
'                                            ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=4 loops=15)'
'                                                  Sort Key: foo_11.lmin'
'                                                  Sort Method: quicksort  Memory: 25kB'
'                                                  ->  Subquery Scan on foo_11  (cost=0.00..1.76 rows=33 width=16) (actual time=0.002..0.004 rows=4 loops=15)'
'                                                        Filter: (foo_11.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                        Rows Removed by Filter: 4'
'                                                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=8 loops=15)'
'                        InitPlan 39 (returns $65)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.022..0.023 rows=1 loops=15)'
'                                ->  Index Only Scan Backward using testrand_pkey on testrand testrand_13  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.008..0.008 rows=1 loops=15)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid < (($64 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 15'
'                SubPlan 43'
'                  ->  Result  (cost=3.89..3.90 rows=1 width=0) (actual time=0.020..0.021 rows=1 loops=2259)'
'                        InitPlan 41 (returns $69)'
'                          ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.013..0.013 rows=1 loops=2259)'
'                                ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.012..0.012 rows=1 loops=2259)'
'                                      Sort Key: lf_12.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lf_12  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.010 rows=8 loops=2259)'
'                                            ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=8 loops=2259)'
'                                                  Sort Key: foo_12.lmin'
'                                                  Sort Method: quicksort  Memory: 25kB'
'                                                  ->  Subquery Scan on foo_12  (cost=0.00..1.76 rows=33 width=16) (actual time=0.001..0.004 rows=8 loops=2259)'
'                                                        Filter: (foo_12.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                        Rows Removed by Filter: 8'
'                                                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2259)'
'                        InitPlan 42 (returns $70)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.020..0.020 rows=1 loops=2259)'
'                                ->  Index Only Scan using testrand_pkey on testrand testrand_14  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=2259)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid > (($69 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2259'
'                SubPlan 46'
'                  ->  Result  (cost=3.89..3.90 rows=1 width=0) (actual time=0.020..0.020 rows=1 loops=2259)'
'                        InitPlan 44 (returns $74)'
'                          ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.013..0.013 rows=1 loops=2259)'
'                                ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.012..0.012 rows=1 loops=2259)'
'                                      Sort Key: lf_13.lmin'
'                                      Sort Method: top-N heapsort  Memory: 25kB'
'                                      ->  Subquery Scan on lf_13  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.010 rows=8 loops=2259)'
'                                            ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=8 loops=2259)'
'                                                  Sort Key: foo_13.lmin'
'                                                  Sort Method: quicksort  Memory: 25kB'
'                                                  ->  Subquery Scan on foo_13  (cost=0.00..1.76 rows=33 width=16) (actual time=0.001..0.004 rows=8 loops=2259)'
'                                                        Filter: (foo_13.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                        Rows Removed by Filter: 8'
'                                                        ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2259)'
'                        InitPlan 45 (returns $75)'
'                          ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.020..0.020 rows=1 loops=2259)'
'                                ->  Index Only Scan Backward using testrand_pkey on testrand testrand_15  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.006..0.006 rows=1 loops=2259)'
'                                      Index Cond: ((trid IS NOT NULL) AND (trid < (($74 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                      Heap Fetches: 2259'
'                SubPlan 55'
'                  ->  Sort  (cost=30.89..31.14 rows=99 width=16) (actual time=0.097..0.097 rows=8 loops=15)'
'                        Sort Key: fr.lmin'
'                        Sort Method: quicksort  Memory: 25kB'
'                        ->  Subquery Scan on fr  (cost=26.38..27.61 rows=99 width=16) (actual time=0.092..0.095 rows=8 loops=15)'
'                              ->  Limit  (cost=26.38..26.62 rows=99 width=16) (actual time=0.092..0.093 rows=8 loops=15)'
'                                    ->  Sort  (cost=26.37..26.62 rows=100 width=16) (actual time=0.091..0.092 rows=9 loops=15)'
'                                          Sort Key: fl.lmin'
'                                          Sort Method: quicksort  Memory: 25kB'
'                                          ->  WindowAgg  (cost=20.80..23.05 rows=100 width=16) (actual time=0.079..0.088 rows=9 loops=15)'
'                                                ->  Sort  (cost=20.80..21.05 rows=100 width=16) (actual time=0.075..0.076 rows=9 loops=15)'
'                                                      Sort Key: fl.lmin'
'                                                      Sort Method: quicksort  Memory: 25kB'
'                                                      ->  Subquery Scan on fl  (cost=15.97..17.48 rows=100 width=16) (actual time=0.069..0.073 rows=9 loops=15)'
'                                                            ->  Result  (cost=15.97..16.48 rows=100 width=0) (actual time=0.068..0.071 rows=9 loops=15)'
'                                                                  InitPlan 50 (returns $83)'
'                                                                    ->  Sort  (cost=7.73..7.98 rows=100 width=0) (actual time=0.029..0.030 rows=9 loops=15)'
'                                                                          Sort Key: (unnest((r_1.maxs || $81)))'
'                                                                          Sort Method: quicksort  Memory: 25kB'
'                                                                          InitPlan 49 (returns $81)'
'                                                                            ->  Result  (cost=3.89..3.90 rows=1 width=0) (actual time=0.023..0.023 rows=1 loops=15)'
'                                                                                  InitPlan 47 (returns $79)'
'                                                                                    ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.012..0.012 rows=1 loops=15)'
'                                                                                          ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.011..0.011 rows=1 loops=15)'
'                                                                                                Sort Key: lf_14.lmin'
'                                                                                                Sort Method: top-N heapsort  Memory: 25kB'
'                                                                                                ->  Subquery Scan on lf_14  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.009 rows=4 loops=15)'
'                                                                                                      ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=4 loops=15)'
'                                                                                                            Sort Key: foo_14.lmin'
'                                                                                                            Sort Method: quicksort  Memory: 25kB'
'                                                                                                            ->  Subquery Scan on foo_14  (cost=0.00..1.76 rows=33 width=16) (actual time=0.002..0.005 rows=4 loops=15)'
'                                                                                                                  Filter: (foo_14.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                                                                                  Rows Removed by Filter: 4'
'                                                                                                                  ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.002..0.003 rows=8 loops=15)'
'                                                                                  InitPlan 48 (returns $80)'
'                                                                                    ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.022..0.022 rows=1 loops=15)'
'                                                                                          ->  Index Only Scan Backward using testrand_pkey on testrand testrand_16  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.008..0.008 rows=1 loops=15)'
'                                                                                                Index Cond: ((trid IS NOT NULL) AND (trid < (($79 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                                                                                Heap Fetches: 15'
'                                                                          ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.025..0.027 rows=9 loops=15)'
'                                                                  InitPlan 54 (returns $87)'
'                                                                    ->  Sort  (cost=7.73..7.98 rows=100 width=0) (actual time=0.031..0.032 rows=9 loops=15)'
'                                                                          Sort Key: (unnest((r_1.mins || $86)))'
'                                                                          Sort Method: quicksort  Memory: 25kB'
'                                                                          InitPlan 53 (returns $86)'
'                                                                            ->  Result  (cost=3.89..3.90 rows=1 width=0) (actual time=0.025..0.025 rows=1 loops=15)'
'                                                                                  InitPlan 51 (returns $84)'
'                                                                                    ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.012..0.012 rows=1 loops=15)'
'                                                                                          ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.012..0.012 rows=1 loops=15)'
'                                                                                                Sort Key: lf_15.lmin'
'                                                                                                Sort Method: top-N heapsort  Memory: 25kB'
'                                                                                                ->  Subquery Scan on lf_15  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.009 rows=4 loops=15)'
'                                                                                                      ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=4 loops=15)'
'                                                                                                            Sort Key: foo_15.lmin'
'                                                                                                            Sort Method: quicksort  Memory: 25kB'
'                                                                                                            ->  Subquery Scan on foo_15  (cost=0.00..1.76 rows=33 width=16) (actual time=0.002..0.004 rows=4 loops=15)'
'                                                                                                                  Filter: (foo_15.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                                                                                  Rows Removed by Filter: 4'
'                                                                                                                  ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=8 loops=15)'
'                                                                                  InitPlan 52 (returns $85)'
'                                                                                    ->  Limit  (cost=0.44..0.47 rows=1 width=8) (actual time=0.024..0.024 rows=1 loops=15)'
'                                                                                          ->  Index Only Scan using testrand_pkey on testrand testrand_17  (cost=0.44..94366.66 rows=2666111 width=8) (actual time=0.009..0.009 rows=1 loops=15)'
'                                                                                                Index Cond: ((trid IS NOT NULL) AND (trid > (($84 + ((((((r_1.rrange + 1))::double precision * random()))::bigint))::numeric))::bigint))'
'                                                                                                Heap Fetches: 15'
'                                                                          ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.027..0.028 rows=9 loops=15)'
'                SubPlan 56'
'                  ->  Limit  (cost=3.42..3.42 rows=1 width=16) (actual time=0.013..0.013 rows=1 loops=2273)'
'                        ->  Sort  (cost=3.42..3.50 rows=33 width=16) (actual time=0.012..0.012 rows=1 loops=2273)'
'                              Sort Key: lf_16.lmin'
'                              Sort Method: top-N heapsort  Memory: 25kB'
'                              ->  Subquery Scan on lf_16  (cost=2.59..3.25 rows=33 width=16) (actual time=0.007..0.010 rows=8 loops=2273)'
'                                    ->  Sort  (cost=2.59..2.67 rows=33 width=16) (actual time=0.006..0.006 rows=8 loops=2273)'
'                                          Sort Key: foo_16.lmin'
'                                          Sort Method: quicksort  Memory: 25kB'
'                                          ->  Subquery Scan on foo_16  (cost=0.00..1.76 rows=33 width=16) (actual time=0.001..0.004 rows=8 loops=2273)'
'                                                Filter: (foo_16.lrange < (((((r_1.rrange + 1))::double precision * random()))::bigint))'
'                                                Rows Removed by Filter: 8'
'                                                ->  Result  (cost=0.00..0.51 rows=100 width=0) (actual time=0.001..0.003 rows=16 loops=2273)'
'  ->  Limit  (cost=0.85..0.85 rows=1 width=32) (actual time=575.319..575.319 rows=1 loops=1)'
'        ->  Sort  (cost=0.85..0.93 rows=31 width=32) (actual time=575.319..575.319 rows=1 loops=1)'
'              Sort Key: (array_length(r.res, 1))'
'              Sort Method: top-N heapsort  Memory: 25kB'
'              ->  CTE Scan on r  (cost=0.00..0.70 rows=31 width=32) (actual time=0.059..574.761 rows=2274 loops=1)'
'Total runtime: 576.183 ms'

но не сильно

...

Рейтинг:

0 / 0

16.11.2014, 15:44:34

| Ответить | Цитировать | Написать

очередной велосипедист

#38807583

Alexius

Участник

Сообщения: 749

Рейтинг: 0 / 0

?Ы,

путем ковыряния в носу придумал такой алгоритм true рандома, который будет работать для этого случая.

условия:

1) поле, по которому выбираем уникально
2) элементы расположены близко друг к другу, но существуют значительные "дырки"
3) число больших дырок < значения statistics target/2 (а лучше выкручиваем statistics для поля в максимум 10000)
4) статистика относительно аккуратная (autoanalyze собирает)

take the best of both worlds:

1) выбираем границы диапазонов из имеющейся статистики, их у нас получится 10000 (если таблица большая конечно же)

Код: sql

1.
2.
3.
4.
5.

select lrange, rrange, rrange-lrange as len from 
    (select lrange, lead(lrange) over () as rrange from 
        (select unnest(histogram_bounds::text::bigint[]) as lrange from pg_stats where tablename = 'testrand' and attname='trid') t
    ) t2
where rrange is not null order by 3 desc;

2) сортируем диапазоны по их длине. тут нам нужно пометить те диапазоны, которые намного больше других - именно они и содержат дырки. можно по-разному это делать, например можно выделить те диапазоны, длины которых больше 2*median(len).
получится что-то вроде такого:

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.

    lrange      |     rrange      |      len
-----------------+-----------------+---------------
  20000096299773 |  30000014219577 | 9999917919804
 -39999909434160 | -29999992273738 | 9999917160422
  60000083023927 |  70000000026789 | 9999917002862
 -79999906563837 | -69999989911592 | 9999916652245
  40000093616658 |  50000010099671 | 9999916483013
  30000093947768 |  40000010395621 | 9999916447853
 -19999900962191 |  -9999984623150 | 9999916339041
  10000099704707 |  20000015885493 | 9999916180786
 -49999907812109 | -39999991951097 | 9999915861012
 -59999900370435 | -49999984691702 | 9999915678733
 -29999912634155 | -19999997336848 | 9999915297307
        89070880 |  10000004260465 | 9999915189585
  -9999904286211 |        10803289 | 9999915089500
 -69999909863467 | -59999994974918 | 9999914888549
  50000089175940 |  60000003979087 | 9999914803147
 -39999991951097 | -39999973606013 |      18345084
  60000065169412 |  60000083023927 |      17854515
 -39999927007752 | -39999909434160 |      17573592
 -69999943577273 | -69999926247222 |      17330051
  40000060060780 |  40000077380260 |      17319480
  70000000026789 |  70000017307232 |      17280443
  30000076780570 |  30000093947768 |      17167198
  70000065793557 |  70000082903411 |      17109854
  10000019437096 |  10000036518426 |      17081330
  30000043703602 |  30000060782447 |      17078845
  40000027327370 |  40000044336573 |      17009203
 -19999933412289 | -19999916453610 |      16958679
  10000066406512 |  10000083365038 |      16958526
  40000010395621 |  40000027327370 |      16931749
  -9999984623150 |  -9999967706540 |      16916610
  70000082903411 |  70000099772973 |      16869562
 -29999992273738 | -29999975506355 |      16767383
 -59999979836449 | -59999963098232 |      16738217
  20000048280431 |  20000064931898 |      16651467
  70000049151050 |  70000065793557 |      16642507
 -79999968745636 | -79999952232832 |      16512804
  70000017307232 |  70000033819718 |      16512486
 -19999964719134 | -19999948244851 |      16474283
 -79999937284848 | -79999920835301 |      16449547
  20000064931898 |  20000081361106 |      16429208
...

3) алгоритмом Максима выбираем N диапазонов (могут повторяться, группируем потом по диапазонам) = сколько чисел нам надо выбрать
4) цикл по помеченным диапазонам (выборка из диапазонов с дырками): тут мы выбираем обычным order by random() с условиями по границам диапазона сколько элементов нам нужно. для каждого такого диапазона это всего будет index scan по 1/10000 строк таблицы.
5) цикл по непомеченным диапазонам: выбираем алгоритмом Максима столько элементов для каждого диапазона, сколько нужно. т.к. дырок больших в этих диапазонах нет - будет быстро
6) объединяем результаты
7) profit

кодить это все не сильно хочется, но должно работать быстрее order by random (если только полтаблицы не выбирать конечно) и без краевых эффектов возле дырок.

не важно, открытый интервал у random() или закрытый, все равно вероятность попасть в точку почти 0. а вот при касте происходит неявное округление, так что по 0.5 добавить не помешает, да.

...

Рейтинг:

0 / 0

16.11.2014, 17:37:17

| Ответить | Цитировать | Написать

очередной велосипедист

#38807642

?Ы

Гость

Alexius, снкс.

разрабатывая ноздрю:

если разбить на 2 отдельных этапа
--1. вырезание дырок (наперёд не более некоего финитного кол-ва)
--2. выборка рандомов тыканием в единожды размеченное "картой" мн-ве

то :
1. на первом жестко получаем мн-во (TABLE) {Lmin,Lrange}, которое никогда не перевычисляем на 2-м
2. выбрасываем большинство накладных (на свертку/развертку array-ев) на 2-м этапе -- заменив (JOIN LATERAL (SELECT * FROM {L_CTE_table} ORDER BY .. LIMIT 1) с предподсчитанной CTE табличкой, про которую выше)

=>
вероятно будем иметь тот же профит
но -- без обращения к не обязательно актуальной статистике

тут важно -- отжать всё лишнее с каждого из этапов.

но при всюду редком заполнении (когда всюду дырки одного порядка) full scan на очень редких заполнениях (10^-6) выиграет всегда. (или надо уметь очень дёшево вырезать очень много дырок).

...

Рейтинг:

0 / 0

16.11.2014, 19:57:59

| Ответить | Цитировать | Написать

очередной велосипедист

#38807653

Alexius

Участник

Сообщения: 749

Рейтинг: 0 / 0

?Ы,

хм, при всюду редком заполнении можно ввести какое-нибудь поле с хешем небольшой длины, так получим более-менее равномерное распределение (при хорошей хеш функции), куда тыкать можно, но правда с дублями.

...

Рейтинг:

0 / 0

16.11.2014, 20:33:10

| Ответить | Цитировать | Написать

очередной велосипедист

#38807654

Alexius

Участник

Сообщения: 749

Рейтинг: 0 / 0

точнее поле можно и не создавать, только функциональный индекс.

...

Рейтинг:

0 / 0

16.11.2014, 20:36:37

| Ответить | Цитировать | Написать

очередной велосипедист

#38807669

Alexius

Участник

Сообщения: 749

Рейтинг: 0 / 0

вот как-то так например, берем первые 16 бит от md5 в качестве хеша

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.

CREATE OR REPLACE FUNCTION md5_part(bigint)
         RETURNS integer
         LANGUAGE sql
         IMMUTABLE
       AS $function$
           SELECT (('x'||md5($1::text))::bit(16)::integer);
       $function$;


create index testrand_trid_hash on testrand using btree(md5_part(trid));

WITH RECURSIVE
r AS (
    SELECT array[]::bigint[] AS res,min(md5_part(trid)) AS min, max(md5_part(trid))-min(md5_part(trid)) AS range FROM testrand
  UNION ALL
    SELECT res||ARRAY(SELECT trid FROM testrand WHERE md5_part(trid)=(SELECT (-0.5 + min+(1+range)*random())::int) AND NOT trid=ANY(res) order by random() limit 1), min, range
    FROM r WHERE coalesce(array_length(res,1),0)<100
)
SELECT unnest(res) FROM (
  SELECT res FROM r ORDER BY array_length(res,1) DESC NULLS LAST LIMIT 1
) AS t;

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.

Subquery Scan on t  (cost=239419.80..239420.31 rows=100 width=32) (actual time=26.389..26.637 rows=100 loops=1)
   CTE r
     ->  Recursive Union  (cost=0.98..239418.95 rows=31 width=40) (actual time=0.087..25.537 rows=101 loops=1)
           ->  Result  (cost=0.98..1.00 rows=1 width=0) (actual time=0.082..0.084 rows=1 loops=1)
                 InitPlan 1 (returns $1)
                   ->  Limit  (cost=0.45..0.49 rows=1 width=8) (actual time=0.046..0.048 rows=1 loops=1)
                         ->  Index Scan using testrand_trid_hash on testrand  (cost=0.45..73597.94 rows=1590714 width=8) (actual time=0.040..0.040 rows=1 loops=1)
                               Index Cond: (((('x'::text || md5((trid)::text)))::bit(16))::integer IS NOT NULL)
                 InitPlan 2 (returns $2)
                   ->  Limit  (cost=0.45..0.49 rows=1 width=8) (actual time=0.017..0.019 rows=1 loops=1)
                         ->  Index Scan Backward using testrand_trid_hash on testrand testrand_1  (cost=0.45..73597.94 rows=1590714 width=8) (actual time=0.013..0.013 rows=1 loops=1)
                               Index Cond: (((('x'::text || md5((trid)::text)))::bit(16))::integer IS NOT NULL)
           ->  WorkTable Scan on r r_1  (cost=0.00..23941.73 rows=3 width=40) (actual time=0.243..0.245 rows=1 loops=101)
                 Filter: (COALESCE(array_length(res, 1), 0) < 100)
                 Rows Removed by Filter: 0
                 SubPlan 4
                   ->  Limit  (cost=7980.49..7980.49 rows=1 width=8) (actual time=0.234..0.236 rows=1 loops=100)
                         InitPlan 3 (returns $5)
                           ->  Result  (cost=0.00..0.03 rows=1 width=0) (actual time=0.005..0.007 rows=1 loops=100)
                         ->  Sort  (cost=7980.46..8000.44 rows=7993 width=8) (actual time=0.230..0.230 rows=1 loops=100)
                               Sort Key: (random())
                               Sort Method: top-N heapsort  Memory: 25kB
                               ->  Bitmap Heap Scan on testrand testrand_2  (cost=150.40..7940.49 rows=7993 width=8) (actual time=0.073..0.169 rows=24 loops=100)
                                     Recheck Cond: (((('x'::text || md5((trid)::text)))::bit(16))::integer = $5)
                                     Filter: (trid <> ALL (r_1.res))
                                     ->  Bitmap Index Scan on testrand_trid_hash  (cost=0.00..148.40 rows=7994 width=0) (actual time=0.052..0.052 rows=24 loops=100)
                                           Index Cond: (((('x'::text || md5((trid)::text)))::bit(16))::integer = $5)
   ->  Limit  (cost=0.85..0.85 rows=1 width=32) (actual time=26.377..26.379 rows=1 loops=1)
         ->  Sort  (cost=0.85..0.93 rows=31 width=32) (actual time=26.372..26.372 rows=1 loops=1)
               Sort Key: (array_length(r.res, 1))
               Sort Method: top-N heapsort  Memory: 26kB
               ->  CTE Scan on r  (cost=0.00..0.70 rows=31 width=32) (actual time=0.096..26.038 rows=101 loops=1)
 Total runtime: 26.957 ms

100 строк, 26ms. game over?

...

Рейтинг:

0 / 0

16.11.2014, 21:16:45

| Ответить | Цитировать | Написать

очередной велосипедист

#38807681

Лопата

Участник

Сообщения: 142

Рейтинг: 0 / 0

Alexius<>

100 строк, 26ms. game over ?
до тез пор, пока я умышленно не прорежу именно по (('x'||md5($1::text))::bit(16)::integer); -- после чего игра потребует новой переиндексации (т.е. фуллскана ++) с новым хешем.

...

Рейтинг:

0 / 0

16.11.2014, 22:03:09

| Ответить | Цитировать | Написать

очередной велосипедист

#38807689

Maxim Boguk

Участник

Откуда: Melbourne, Австралия

Сообщения: 5 148

Рейтинг: 0 / 0

Alexius,

Hm не совсем.
Там где будут коллизии 16битного хеша - скорее всего будет всегда выбираться первый в индексе с этим хешом... а остальные с тем же хешом не будут выбираться НИКОГДА.
Достаточно неприятная особенность... учитывая что шанс коллизий на 16битах высокий.

...

Рейтинг:

0 / 0

16.11.2014, 22:17:47

| Ответить | Цитировать | Написать

очередной велосипедист

#38807692

Maxim Boguk

Участник

Откуда: Melbourne, Австралия

Сообщения: 5 148

Рейтинг: 0 / 0

Maxim BogukAlexius,

Hm не совсем.
Там где будут коллизии 16битного хеша - скорее всего будет всегда выбираться первый в индексе с этим хешом... а остальные с тем же хешом не будут выбираться НИКОГДА.
Достаточно неприятная особенность... учитывая что шанс коллизий на 16битах высокий.

А увидел... order by random() каюсь да этой проблемы нет.
Интересное решение факт.

...

Рейтинг:

0 / 0

16.11.2014, 22:20:00

| Ответить | Цитировать | Написать

очередной велосипедист

#38807781

Alexius

Участник

Сообщения: 749

Рейтинг: 0 / 0

Maxim Boguk,

тут еще важно правильно выбрать длину хешей. оптимальной наверное будет такая, при которой для каждого значения будет по 10 записей из таблицы (postgres для hash join'ов такое же правило использует).

т.е. вычисляем длину хеша по простой формуле (lg(N)-1)/lg(2), для моей таблицы в 1.6М записей получаем 17 бит. для 100 строк время снизилось до 18-20ms.

таким образом получаем почти константное время выборки одной строки, не зависящее от размера таблицы. правда при изменении числа строк в таблице на порядок и больше желательно перехешировать с новой длиной.

...

Рейтинг:

0 / 0

17.11.2014, 06:36:58

| Ответить | Цитировать | Написать

очередной велосипедист

#38807889

Misha Tyurin

Участник

Откуда: Тюмень

Сообщения: 2 279

Рейтинг: 0 / 0

Alexius,

Круто с хешом. Интересно, можно глянуть, если такого нету -- можно и на вики написать

...

Рейтинг:

0 / 0

17.11.2014, 10:11:23

| Ответить | Цитировать | Написать

очередной велосипедист

#38807954

Лопата

Участник

Сообщения: 142

Рейтинг: 0 / 0

Alexius
100 строк, 26ms. game over?

помедитируйте над:

Код: sql

1.
2.
3.
4.
5.
6.

SELECT 
	md5_part(trid)
	,COUNT(1)
FROM testrand
GROUP BY 1
ORDER BY 2;

//если сходу неясно -- фтыкать до посинения

резюме:
пассажыр велосипедист, гружёный лишним знанием -- опаснее велосипедиста без башни
[хотя бы тем, что врёт убедительней]

простите, если кого обидел.

...

Рейтинг:

0 / 0

17.11.2014, 10:52:43

| Ответить | Цитировать | Написать

очередной велосипедист

#38808096

Maxim Boguk

Участник

Откуда: Melbourne, Австралия

Сообщения: 5 148

Рейтинг: 0 / 0

лопата,

Интересное замечание.
Я почему то ожидал заметно более равномерного распределения первых 16 бит md5 относительно того что получилось.
Возможно первые биты md5 - неудачный алгоритм хеширования для этой задачи и надо что то другое делать (фундаментально оно может ситуацию не изменит но как минимум сделает ее достаточно плоской для практического применения).
Но тут уже начинается суровый computer science.

...

Рейтинг:

0 / 0

17.11.2014, 12:22:22

| Ответить | Цитировать | Написать

очередной велосипедист

#38808137

Alexius

Участник

Сообщения: 749

Рейтинг: 0 / 0

лопата,

вопросы выбора хеш функции, качества получившегося рандома и применимости подхода к конкретной задачи открытые.

я смотрел на это распределение и посчитал его удовлетворительным. у меня получилось как-то так:

Код: sql

1.
2.
3.
4.
5.
6.
7.

select cnt, count(*) from
(SELECT
md5_part(trid)
,COUNT(1) as cnt
FROM testrand
GROUP BY 1
ORDER BY 2) t group by 1 order by 1;

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.

 cnt | count
-----+-------
   1 |     4
   2 |    37
   3 |   198
   4 |   577
   5 |  1497
   6 |  3033
   7 |  5319
   8 |  8105
   9 | 10757
  10 | 13519
  11 | 14536
  12 | 14873
  13 | 14125
  14 | 12266
  15 |  9905
  16 |  7624
  17 |  5391
  18 |  3735
  19 |  2358
  20 |  1362
  21 |   866
  22 |   463
  23 |   277
  24 |   143
  25 |    62
  26 |    17
  27 |    15
  28 |     6
  30 |     1

вот тут есть некоторые исследования http://michiel.buddingh.eu/distribution-of-hash-values

если кто запилит хи квадрат тест и сравнит результат с другими хеш функциями будет хорошо. или найдет публикации, наверняка это сто раз уже исследовано.

ну и никто не запрещает ввести индексируемое поле и заполнять его при вставке каким-нибудь рандомным числом в заданном диапазоне.

...

Рейтинг:

0 / 0

17.11.2014, 12:46:03

| Ответить | Цитировать | Написать

очередной велосипедист

#38808140

Лопата

Участник

Сообщения: 142

Рейтинг: 0 / 0

Maxim Boguk,

я ожидал разброса sqrt(avg(count(1)) -- по теорверу, типа (т.к. мы не подгоняли распределение под хеш ф-ю ). что уже фиксирует неравенство раз и навсегда (для любого заранее данного хеша и заданного распределения набора id).

но, кажется, даже это ожЫдание не оправдалось (т.е. там другой собаки sqrt порылся)

кто-то может вспомнить, как это делаецца по науке ? Дисперсия там, то ,сё. От числа бросаний, ага.
Можно ж определить изначально ожидаемую "несправедливость" для случайно выбранной хеш ф-ии, и неизвестного наперёд распределения (через count(1))

...

Рейтинг:

0 / 0

17.11.2014, 12:47:33

| Ответить | Цитировать | Написать

очередной велосипедист

#38808152

Лопата

Участник

Сообщения: 142

Рейтинг: 0 / 0

Alexiusлопата,

<>
ну и никто не запрещает ввести индексируемое поле и заполнять его при вставке каким-нибудь рандомным числом в заданном диапазоне.

как бы помяхше

в общем рандом -- он несправедливый. [Если мы его взяли не один раз а повторили 100 раз один результат.]
как и хеш.
справедливо только 1-1.
и рендомная выборка из 1-1 -- как гарантии равновероятности исходов.

а вы замораживаете несправедливость (различие весов) для всех последующих якобы "рендомных" выборок.
что неверно.

поэтому предварительный рендом, рендом по невыстроенному мн-ву с фиксированными дырками, рендом по хешу -- одинаково гарантируют неравновероятность единожды замороженную на мн-ве. То, что несправедливость получена (раз за разом) случайным образом -- оно конечно греет.
того, кто от неё вкушает.
Ага.

честным это будет только если каждый раз вы начнете выбират заведомом произвольную "заморозку" (хеш ф-ю с проихвольными сдвигами, и т.п.) -- а это -- каждый раз -- фулл скан.

...

Рейтинг:

0 / 0

17.11.2014, 12:56:50

| Ответить | Цитировать | Написать

очередной велосипедист

#38808713

Лопата

Участник

Сообщения: 142

Рейтинг: 0 / 0

хехехе

на хабре этот малолетний далпайоп ещё и упирается, лять
http://habrahabr.ru/post/242999/#comment_8129565

убивать, убивать , убивать ржавой лопатой

только биореактор, только хардкор

...

Рейтинг:

0 / 0

17.11.2014, 18:36:07

| Ответить | Цитировать | Написать

очередной велосипедист

#38813493

vyegorov

Участник

Откуда: Баньоло-ин-Пьяно

Сообщения: 1 237

Рейтинг: 0 / 0

Maxim Boguk,

А подскажите, как такие сложные рекурсивные запросы отлаживать?

Мне в голову приходит только PL/pgSQL функция с `RAISE NOTICE` возвращающая константу, которую CROSS JOIN-ить
в рекурсивной части. Вот только что ей на вход давать?

...

Рейтинг:

0 / 0

21.11.2014, 16:59:30

| Ответить | Цитировать | Написать

очередной велосипедист

#38813531

Лопата

Участник

Сообщения: 142

Рейтинг: 0 / 0

vyegorovMaxim Boguk,

А подскажите, как такие сложные рекурсивные запросы отлаживать?

Мне в голову приходит только PL/pgSQL функция с `RAISE NOTICE` возвращающая константу, которую CROSS JOIN-ить
в рекурсивной части. Вот только что ей на вход давать?хотя там входит словцо recursive, никакой рекурсии нет, есть итерации (прямопроходные, а не обратный проход до корня, с возвратом), которые можно обрезать просто счетчиком итераций -- и смотреть за результатом.

т.е. каждая итерация возвращает очередной "слайс" т.н. "working table", с этим слайсом "рекурсивно" (итеративно) делается UNION [ALL] - и результат поступает в следующую итерацию. И тоько в конце (т.е. в наружнем селекте) выплёвывается всё накопленное на итерациях.

...

Рейтинг:

0 / 0

21.11.2014, 17:15:01

| Ответить | Цитировать | Написать

23 сообщений из 48, страница 2 из 2

все

Форумы / PostgreSQL [игнор отключен] [закрыт для гостей] / очередной велосипедист

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=53&gotonew=1&tid=1998334]:	0ms
get settings:	8ms
get forum list:	13ms
check forum access:	4ms
check topic access:	4ms
track hit:	231ms
get topic data:	10ms
get first new msg:	6ms
get forum data:	3ms
get page messages:	66ms
get tp. blocked users:	2ms
others:	241ms

total:	588ms

	Необходимые cookie
	Cookie для сбора статистики
	Cookie для маркетинга и рекламы