Re: Allow ILIKE forward matching to use btree index

On Wed, 2025-01-15 at 01:40 +0900, Yugo NAGATA wrote:
> > > For example, "t ~~ '123foo%'" is converted to "(t >= '123foo' AND
> > > t < '123fop')"
> > > and index scan can be used for this condition. On the other hand,
> > > "t ~~* '123foo'"
> > > cannot be converted and sequential scan is used.
> > >
> > > Even in this case, we can use a bitmap index scan for the
> > > condition
> > > "(t >= '123f' AND t < '123g') OR "(t >= '123F' AND t < '123G')"
> > > followed by
> > > recheck by the original condition "t ~~* '123foo'", and this
> > > could be faster
> > > than seqscan.

In theory, there could be many OR clauses:

(t >= '123foo' AND t < '123fop') OR
(t >= '123foo' AND t < '123fop') OR
(t >= '123foo' AND t < '123fop') OR
(t >= '123foo' AND t < '123fop') OR
(t >= '123foo' AND t < '123fop') OR
(t >= '123foo' AND t < '123fop') OR
> > > The patch 0001 enables get_index_clause_from_support to receive
> > > OR clauses
> > > from support functions and use them to build bitmap index scan
> > > later. OR clauses
> > > returned by support functions are collected in the new argument
> > > 'orclauses" of
> > > match_restriction_clauses_to_index(), and they are passed to
> > > generate_bitmap_or_paths() later to build bitmap scan paths.

If I understand correctly, this

> > > The patch 0002 modifies the support function to return OR clauses
> > > as an example
> > > above when ILIKE's pattern has case-varying characters in forward
> > > matching. The
> > > OR clauses contains two index conditions for the upper and the
> > > lower letter of
> > > the first case-varying character in the pattern respectively.
> > > Although the
> > > subsequent characters are not considered in the index scans, it
> > > could enough be
> > > faster then sequent scan.
> > >
> > > Here is an example.
> > >
> > > 1. Create a table with random text records
> > >
> > > =# CREATE TABLE tbl (t text);
> > > =# INSERT INTO tbl SELECT CASE WHEN i%2=1 THEN upper(x) ELSE x
> > > END
> > >                   FROM (SELECT i, md5(i::text) x FROM
> > > generate_series(1,5000000) i);
> > >
> > > 2. Create an index
> > > =# CREATE INDEX ON tbl (t text_pattern_ops);
> > >
> > > 3. Before applying patch: Seq Scan was selected. It takes about 4
> > > sec.
> > >
> > > =# EXPLIN ANALYZE SELECT * FROM tbl WHERE t ILIKE '12ab%';
> >
> > I am sorry, the example in my previous main was wrong. I showed the
> > plan
> > with enable_index_scan = off. Indead, if the pattern starts with
> > case-insensitive characters like '12', an index scan can be used
> > even with
> > ILIKE.
> >
> > postgres=# EXPLAIN ANALYZE SELECT * FROM tbl WHERE t ILIKE 'abc%';
> >                                                        QUERY
> > PLAN                                                       
> > -------------------------------------------------------------------
> > ------------------------------------------------------
> >  Gather  (cost=1000.00..69129.61 rows=500 width=33) (actual
> > time=36.317..4034.770 rows=1188 loops=1)
> >    Workers Planned: 2
> >    Workers Launched: 2
> >    Buffers: shared hit=99 read=41939
> >    ->  Parallel Seq Scan on tbl  (cost=0.00..68079.61 rows=208
> > width=33) (actual time=19.908..4023.668 rows=396 loops=3)
> >          Filter: (t ~~* 'abc%'::text)
> >          Rows Removed by Filter: 1666271
> >          Buffers: shared hit=99 read=41939
> >  Planning Time: 0.726 ms
> >  Execution Time: 4035.101 ms
> > (10 rows)
> >
> > 4. After applying patch: Bitmap Index Scan was selected.
> >
> > postgres=# EXPLAIN ANALYZE SELECT * FROM tbl WHERE t ILIKE 'abc%';
> >                                                                    
> >        QUERY
> > PLAN                                                               
> >           
> > -------------------------------------------------------------------
> > -------------------------------------------------------------------
> > ------------------------
> >  Bitmap Heap Scan on tbl  (cost=12563.66..58314.53 rows=500
> > width=33) (actual time=156.485..1266.789 rows=1188 loops=1)
> >    Recheck Cond: (((t ~>=~ 'A'::text) AND (t ~<~ 'B'::text) AND (t
> > ~~* 'abc%'::text)) OR ((t ~>=~ 'a'::text) AND (t ~<~ 'b'::text) AND
> > (t ~~* 'abc%'::text)))
> >    Filter: (t ~~* 'abc%'::text)
> >    Rows Removed by Filter: 311473
> >    Heap Blocks: exact=42010
> >    Buffers: shared hit=1 read=44600
> >    ->  BitmapOr  (cost=12563.66..12563.66 rows=297029 width=0)
> > (actual time=136.979..136.980 rows=0 loops=1)
> >          Buffers: shared hit=1 read=2590
> >          ->  Bitmap Index Scan on tbl_t_idx  (cost=0.00..6281.71
> > rows=148515 width=0) (actual time=80.548..80.549 rows=158375
> > loops=1)
> >                Index Cond: ((t ~>=~ 'A'::text) AND (t ~<~
> > 'B'::text))
> >                Buffers: shared read=1272
> >          ->  Bitmap Index Scan on tbl_t_idx  (cost=0.00..6281.71
> > rows=148515 width=0) (actual time=56.427..56.427 rows=157042
> > loops=1)
> >                Index Cond: ((t ~>=~ 'a'::text) AND (t ~<~
> > 'b'::text))
> >                Buffers: shared hit=1 read=1318
> >  Planning Time: 0.592 ms
> >  Execution Time: 1267.162 ms
> > (16 rows)
> >
> >  
> > > What do you think about it?
> > >
> > > I think another application of OR-clause returning support
> > > function might be
> > > allowing to use an index for NOT LIKE (!~~) expression  because,
> > > for example,
> > > "t !~~ '123foo%'" could be converted to "(t < '123foo' OR t >=
> > > '123fooz')".
> > > (The second condition is a bit loose but this would be safe and
> > > not problem
> > > since tuples are filtered by the original condition after the
> > > index scan.)
> > > However, it would not very useful unless the distribution is much
> > > skew so that
> > > NOT LIKE expression's selectivity is enough small.
>
> I added a new patch 0003 that enables ILIKE forward matching to use a
> SP-Gist index.
> Similar to 0002, this generates BitmapOr Index Scan for two index
> clauses that use
> "^@" operator for upper letter and lower letter pattern respectively.
>
> * Before applying the patch:
>
> postgres=# explain analyze select* from tbl where t ilike 'abc%';
>                                                       QUERY
> PLAN                                                     
> ---------------------------------------------------------------------
> -------------------------------------------------
>  Gather  (cost=1000.00..18899.52 rows=101 width=33) (actual
> time=41.799..930.382 rows=253 loops=1)
>    Workers Planned: 2
>    Workers Launched: 2
>    Buffers: shared hit=96 read=12533
>    ->  Parallel Seq Scan on tbl  (cost=0.00..17889.42 rows=42
> width=33) (actual time=26.041..917.570 rows=84 loops=3)
>          Filter: (t ~~* 'abc%'::text)
>          Rows Removed by Filter: 336582
>          Buffers: shared hit=96 read=12533
>  Planning Time: 0.690 ms
>  Execution Time: 930.545 ms
> (10 rows)
>
>
> * After applying the patch:
>
> postgres=# explain analyze select* from tbl where t ilike 'abc%';
>                                                              QUERY
> PLAN                                                             
> ---------------------------------------------------------------------
> ----------------------------------------------------------------
>  Bitmap Heap Scan on tbl  (cost=3307.96..16702.11 rows=101 width=33)
> (actual time=69.449..215.636 rows=253 loops=1)
>    Recheck Cond: (((t ^@ 'A'::text) AND (t ~~* 'abc%'::text)) OR ((t
> ^@ 'a'::text) AND (t ~~* 'abc%'::text)))
>    Filter: (t ~~* 'abc%'::text)
>    Rows Removed by Filter: 62992
>    Heap Blocks: exact=12437
>    Buffers: shared hit=18529
>    ->  BitmapOr  (cost=3307.96..3307.96 rows=61212 width=0) (actual
> time=62.567..62.568 rows=0 loops=1)
>          Buffers: shared hit=6092
>          ->  Bitmap Index Scan on tbl_t_idx  (cost=0.00..1653.96
> rows=30606 width=0) (actual time=41.893..41.893 rows=31536 loops=1)
>                Index Cond: (t ^@ 'A'::text)
>                Buffers: shared hit=2461
>          ->  Bitmap Index Scan on tbl_t_idx  (cost=0.00..1653.96
> rows=30606 width=0) (actual time=20.671..20.671 rows=31709 loops=1)
>                Index Cond: (t ^@ 'a'::text)
>                Buffers: shared hit=3631
>  Planning Time: 1.414 ms
>  Execution Time: 215.903 ms
> (16 rows)
>
>