Re: Adding skip scan (including MDAM style range skip scan) to nbtree

Hi,

Apologies for the delayed response. I've confirmed that the costing is 
significantly
improved for multicolumn indexes in the case I provided. Thanks!
https://www.postgresql.org/message-id/TYWPR01MB10982A413E0EC4088E78C0E11B1A62%40TYWPR01MB10982.jpnprd01.prod.outlook.com

I have some comments and questions regarding the v14 patch.

(1)

> v14-0001-Show-index-search-count-in-EXPLAIN-ANALYZE.patch

As a user, I agree with adding a counter for skip scans
(though it might be better to reply to the different thread).

I believe this will help users determine whether the skip scan 
optimization is
effective. If the ratio of (actual rows)/(index searches) becomes small, 
it
suggests that many traversals are occurring, indicating that the skip 
scan
optimization is not working efficiently. In such cases, users might 
benefit
from replacing the multi-column index with an optimized leading column 
index.

IIUC, why not add it to the documentation? It would clearly help users
understand how to tune their queries using the counter, and it would
also show that the counter is not just for developers.

(2)

> v14-0001-Show-index-search-count-in-EXPLAIN-ANALYZE.patch

 From the perspective of consistency, wouldn't it be better to align the 
naming
between the EXPLAIN output and pg_stat_all_indexes.idx_scan, even though 
the
documentation states they refer to the same concept?

I personally prefer something like "search" instead of "scan", as "scan" 
is
commonly associated with node names like Index Scan and similar terms. 
To maintain
consistency, how about renaming pg_stat_all_indexes.idx_scan to
pg_stat_all_indexes.idx_search?

(3)

> v14-0001-Show-index-search-count-in-EXPLAIN-ANALYZE.patch

The counter should be added in blgetbitmap().

(4)

> v14-0001-Show-index-search-count-in-EXPLAIN-ANALYZE.patch
> doc/src/sgml/bloom.sgml

The below forgot "Index Searches: 1".

          ->  Bitmap Index Scan on btreeidx2  (cost=0.00..12.04 
rows=500 width=0) (never executed)
                Index Cond: (i2 = 898732)
  Planning Time: 0.491 ms
  Execution Time: 0.055 ms
(10 rows)

Although we may not need to fix it, due to the support for skip scan, 
the B-tree
index is now selected over the Bloom index in my environment.

(5)

> v14-0002-Add-skip-scan-to-nbtree.patch

Although I tested with various data types such as int, uuid, oid, and 
others on my
local PC, I could only identify the regression case that you already 
mentioned.

The case is that Index(Only)Scan is selected instead of SeqScan. 
Although the performance
of the full index scan is almost the same as that of SeqScan, the skip 
scan degrades by
a factor of 4, despite the number of accessed pages being almost the 
same. The flamegraph
indicates that the ratio of _bt_advance_array_keys() and 
_bt_tuple_before_array_skeys()
becomes high.

Although it's not an optimal solution and would only reduce the degree 
of performance
degradation, how about introducing a threshold per page to switch from 
skip scan to full
index scan? For example, switch to full index scan after 
_bt_tuple_before_array_skeys() in
_bt_checkkeys() fails 30 times per page. While 30 is just an example, I 
referenced the
following case, which seems close to the worst-case scenario. In that 
case,
_bt_advance_array_keys() and _bt_tuple_before_array_skeys() are called 
almost 333 times per
page (1,000,000 records / 2,636 pages), and 30 is about 1/10 of that 
number.

# Example case (see test.sql)
# master: 51.612ms
                                                       QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
  Gather  (cost=1000.00..10633.43 rows=1 width=8) (actual 
time=0.160..51.612 rows=1 loops=1)
    Output: id1, id2
    Workers Planned: 2
    Workers Launched: 2
    Buffers: shared hit=4425
    ->  Parallel Seq Scan on public.t  (cost=0.00..9633.33 rows=1 
width=8) (actual time=31.728..48.378 rows=0 loops=3)
          Output: id1, id2
          Filter: (t.id2 = 100)
          Rows Removed by Filter: 333333
          Buffers: shared hit=4425
          Worker 0:  actual time=47.583..47.583 rows=0 loops=1
            Buffers: shared hit=1415
          Worker 1:  actual time=47.568..47.569 rows=0 loops=1
            Buffers: shared hit=1436
  Settings: effective_cache_size = '7932MB', work_mem = '15MB'
  Planning Time: 0.078 ms
  Execution Time: 51.630 ms
(17 rows)

# master with v14patch: 199.328ms. 4x slower
SET skipscan_prefix_cols=32;
                                                         QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------
  Index Only Scan using t_idx on public.t  (cost=0.42..3535.75 rows=1 
width=8) (actual time=0.090..199.328 rows=1 loops=1)
    Output: id1, id2
    Index Cond: (t.id2 = 100)
    Index Searches: 1
    Heap Fetches: 0
    Buffers: shared hit=2736
  Settings: effective_cache_size = '7932MB', work_mem = '15MB'
  Planning Time: 0.069 ms
  Execution Time: 199.348 ms
(9 rows)

# master with v14patch: 54.665ms.
SET skipscan_prefix_cols=0;  // disable skip scan
                                                        QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------
  Index Only Scan using t_idx on public.t  (cost=0.42..3535.75 rows=1 
width=8) (actual time=0.031..54.665 rows=1 loops=1)
    Output: id1, id2
    Index Cond: (t.id2 = 100)
    Index Searches: 1
    Heap Fetches: 0
    Buffers: shared hit=2736
  Settings: effective_cache_size = '7932MB', work_mem = '15MB'
  Planning Time: 0.067 ms
  Execution Time: 54.685 ms
(9 rows)


(6)

> v14-0002-Add-skip-scan-to-nbtree.patch
> src/backend/access/nbtree/nbtutils.c

+static int
+_bt_preprocess_num_array_keys(IndexScanDesc scan, BTSkipPreproc 
*skipatts,
+							  int *numSkipArrayKeys)
(snip)
+		int			prev_numSkipArrayKeys = *numSkipArrayKeys;
+
+		/*
+		 * Backfill skip arrays for any wholly omitted attributes prior to
+		 * attno_inkey
+		 */
+		while (attno_skip < attno_inkey)

Is it better to move prev_numSkipArrayKeys =*numSkipArrayKeys after the 
while loop?
For example, the index below should return *numSkipArrayKeys = 0 instead 
of 1
if the id3 type does not support eq_op.

* index: CREATE INDEX test_idx on TEST (id1 int, id2 int, id3 no_eq_op, 
id4 int);
* query: SELECT * FROM test WHERE id4 = 10;


Regards,
-- 
Masahiro Ikeda
NTT DATA CORPORATION