Re: BUG #14161: reverse index scan cann't use double link?

HI,

This is the righest & leftest page's content.

postgres=# explain (analyze,verbose,costs,buffers,timing) select id from tbl4 order by id limit 1000;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.43..18.17 rows=1000 width=4) (actual time=0.055..0.674 rows=1000 loops=1)
Output: id
Buffers: shared hit=8
-> Index Only Scan using idx4 on public.tbl4 (cost=0.43..69815.43 rows=3934867 width=4) (actual time=0.042..0.290 rows=1000 loops=1)
Output: id
Heap Fetches: 0
Buffers: shared hit=8
Planning time: 0.192 ms
Execution time: 0.884 ms
(9 rows)
postgres=# explain (analyze,verbose,costs,buffers,timing) select id from tbl4 order by id desc limit 1000;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.43..18.17 rows=1000 width=4) (actual time=0.028..0.725 rows=1000 loops=1)
Output: id
Buffers: shared hit=19
-> Index Only Scan Backward using idx4 on public.tbl4 (cost=0.43..69815.43 rows=3934867 width=4) (actual time=0.027..0.316 rows=1000 loops=1)
Output: id
Heap Fetches: 0
Buffers: shared hit=19
Planning time: 0.079 ms
Execution time: 0.933 ms
(9 rows)
postgres=# \d+ tbl4
Table "public.tbl4"
Column | Type | Modifiers | Storage | Stats target | Description
--------+---------+-----------+----------+--------------+-------------
id | integer | | plain | |
info | text | | extended | |
Indexes:
"idx4" btree (id)
postgres=# select * from bt_metap('idx4');
magic | version | root | level | fastroot | fastlevel
--------+---------+------+-------+----------+-----------
340322 | 2 | 290 | 2 | 290 | 2
(1 row)
level 2
ostgres=# select * from bt_page_items('idx4', 290);
itemoffset | ctid | itemlen | nulls | vars | data
------------+-----------+---------+-------+------+-------------------------
1 | (3,1) | 8 | f | f |
2 | (289,1) | 16 | f | f | fc 03 04 00 00 00 00 00
3 | (575,1) | 16 | f | f | 6f 0c 08 00 00 00 00 00
...
38 | (10550,1) | 16 | f | f | d7 23 95 00 00 00 00 00
(38 rows)
level 1
rightest page
postgres=# select * from bt_page_items('idx4', 10550);
itemoffset | ctid | itemlen | nulls | vars | data
------------+-----------+---------+-------+------+-------------------------
1 | (10547,1) | 8 | f | f |
2 | (10548,1) | 16 | f | f | 9f 27 95 00 00 00 00 00
3 | (10549,1) | 16 | f | f | 1c 2b 95 00 00 00 00 00
...
228 | (10775,1) | 16 | f | f | 0d 5d 98 00 00 00 00 00
229 | (10776,1) | 16 | f | f | ea 60 98 00 00 00 00 00
230 | (10777,1) | 16 | f | f | 3c 64 98 00 00 00 00 00
231 | (10778,1) | 16 | f | f | 95 67 98 00 00 00 00 00
232 | (10779,1) | 16 | f | f | 01 6b 98 00 00 00 00 00
233 | (10780,1) | 16 | f | f | c0 6e 98 00 00 00 00 00
234 | (10781,1) | 16 | f | f | 7f 72 98 00 00 00 00 00
235 | (10782,1) | 16 | f | f | 28 76 98 00 00 00 00 00
236 | (10783,1) | 16 | f | f | a8 79 98 00 00 00 00 00
237 | (10784,1) | 16 | f | f | 18 7d 98 00 00 00 00 00
238 | (10785,1) | 16 | f | f | e9 80 98 00 00 00 00 00
239 | (10786,1) | 16 | f | f | 8f 84 98 00 00 00 00 00
240 | (10787,1) | 16 | f | f | 25 88 98 00 00 00 00 00
241 | (10788,1) | 16 | f | f | d0 8b 98 00 00 00 00 00
242 | (10789,1) | 16 | f | f | 78 8f 98 00 00 00 00 00
243 | (10790,1) | 16 | f | f | e0 92 98 00 00 00 00 00
244 | (10791,1) | 16 | f | f | 73 96 98 00 00 00 00 00
(244 rows)
level 0
rightest page
postgres=# select * from bt_page_items('idx4', 10791);
itemoffset | ctid | itemlen | nulls | vars | data
------------+------------+---------+-------+------+-------------------------
1 | (2411,46) | 16 | f | f | 73 96 98 00 00 00 00 00
2 | (12299,48) | 16 | f | f | 74 96 98 00 00 00 00 00
3 | (30270,56) | 16 | f | f | 77 96 98 00 00 00 00 00
4 | (2555,81) | 16 | f | f | 78 96 98 00 00 00 00 00
5 | (3891,28) | 16 | f | f | 7a 96 98 00 00 00 00 00
6 | (2380,83) | 16 | f | f | 7b 96 98 00 00 00 00 00
7 | (259,1) | 16 | f | f | 7c 96 98 00 00 00 00 00
8 | (23180,80) | 16 | f | f | 7d 96 98 00 00 00 00 00
9 | (8298,31) | 16 | f | f | 7e 96 98 00 00 00 00 00
(9 rows)
...
postgres=# select * from bt_page_items('idx4', 10790);
itemoffset | ctid | itemlen | nulls | vars | data
------------+-------------+---------+-------+------+-------------------------
1 | (2411,46) | 16 | f | f | 73 96 98 00 00 00 00 00
2 | (18361,30) | 16 | f | f | e0 92 98 00 00 00 00 00
3 | (23402,95) | 16 | f | f | e3 92 98 00 00 00 00 00
4 | (24062,66) | 16 | f | f | e7 92 98 00 00 00 00 00
...
365 | (1476,41) | 16 | f | f | 6e 96 98 00 00 00 00 00
366 | (28381,83) | 16 | f | f | 6f 96 98 00 00 00 00 00
367 | (22880,81) | 16 | f | f | 72 96 98 00 00 00 00 00
(367 rows)

level 1
leftest page
postgres=# select * from bt_page_items('idx4', 3);
itemoffset | ctid | itemlen | nulls | vars | data
------------+---------+---------+-------+------+-------------------------
1 | (286,1) | 16 | f | f | fc 03 04 00 00 00 00 00
2 | (1,1) | 8 | f | f |
3 | (2,1) | 16 | f | f | d0 03 00 00 00 00 00 00
4 | (4,1) | 16 | f | f | 69 07 00 00 00 00 00 00
...
285 | (285,1) | 16 | f | f | 63 00 04 00 00 00 00 00
(285 rows)
level 0
leftest page
postgres=# select * from bt_page_items('idx4', 1);
itemoffset | ctid | itemlen | nulls | vars | data
------------+-------------+---------+-------+------+-------------------------
1 | (8411,8) | 16 | f | f | d0 03 00 00 00 00 00 00
2 | (4606,10) | 16 | f | f | 00 00 00 00 00 00 00 00
3 | (9849,10) | 16 | f | f | 01 00 00 00 00 00 00 00
...
367 | (9596,32) | 16 | f | f | cf 03 00 00 00 00 00 00
(367 rows)

best regards,
digoal

--
公益是一辈子的事,I'm Digoal,Just Do It.

At 2016-05-28 23:03:11, "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>digoal(at)126(dot)com writes:
>> in btree, leaf page has prev and next page. but when i use order by desc,
>> it's not use the prev page link? it scan from root per leaf page.
>
>You've provided no evidence whatsoever to support that claim.
>
>> 9 page hint = meta + root + branch + 6 leaf
>> 19 page hint = meta + 6(root + branch + leaf)
>
>I think more likely what's happening is that one end of the index is
>packed full and the other end is about 50% full.
>
> regards, tom lane