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

   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@sss.pgh.pa.us> wrote:
>digoal@126.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