adjust_limit_rows_costs algorithm - Mailing list pgsql-hackers

    There should be many people who have encountered the problem of order by col limit 1 without index filtering,Here is an example of my test

create extension pg_trgm ;

CREATE TABLE public.dba_users (
userid integer primary key,
username character varying(64),
password character varying(64)
);

sysbench=# create extension pg_trgm ;
CREATE EXTENSION
sysbench=# CREATE TABLE public.dba_users (
sysbench(#
sysbench(#     userid integer primary key,
sysbench(#
sysbench(#     username character varying(64),
sysbench(#
sysbench(#     password character varying(64)
sysbench(#
sysbench(# );
CREATE TABLE
sysbench=# insert into dba_users select generate_series(1,6000000),md5(random()::varchar(64)),md5(random()::varchar(64));
INSERT 0 6000000
sysbench=# CREATE INDEX dba_users_username_idx ON public.dba_users USING gin (username gin_trgm_ops);
CREATE INDEX
sysbench=#
sysbench=#
sysbench=#
sysbench=#
sysbench=# explain analyze  select userid from dba_users where  username like '%aaaaaaaaaaaa%' order by userid limit 1;
                                                                 QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.43..408.59 rows=1 width=4) (actual time=1433.469..1433.470 rows=0 loops=1)
   ->  Index Scan using dba_users_pkey on dba_users  (cost=0.43..244892.51 rows=600 width=4) (actual time=1433.468..1433.468 rows=0 loops=1)
         Filter: ((username)::text ~~ '%aaaaaaaaaaaa%'::text)
         Rows Removed by Filter: 6000000
 Planning Time: 0.384 ms
 Execution Time: 1433.489 ms
(6 rows)

sysbench=# explain analyze  select userid from dba_users where  username like '%aaaaaaaaaaaa%' order by userid+0 limit 1;
                                                                    QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=2300.03..2300.03 rows=1 width=8) (actual time=54.562..54.563 rows=0 loops=1)
   ->  Sort  (cost=2300.03..2301.53 rows=600 width=8) (actual time=54.560..54.561 rows=0 loops=1)
         Sort Key: ((userid + 0))
         Sort Method: quicksort  Memory: 25kB
         ->  Bitmap Heap Scan on dba_users  (cost=57.22..2297.03 rows=600 width=8) (actual time=54.526..54.527 rows=0 loops=1)
               Recheck Cond: ((username)::text ~~ '%aaaaaaaaaaaa%'::text)
               Rows Removed by Index Recheck: 41310
               Heap Blocks: exact=31810
               ->  Bitmap Index Scan on dba_users_username_idx  (cost=0.00..57.07 rows=600 width=0) (actual time=7.307..7.307 rows=41310 loops=1)
                     Index Cond: ((username)::text ~~ '%aaaaaaaaaaaa%'::text)
 Planning Time: 0.238 ms
 Execution Time: 54.625 ms
(12 rows)

I think the total_cost calculation method cannot be linear, because the data distribution is not linear in reality. I try to change it to a logarithmic 

$ git diff
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 4f74caf..2ab59e9 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -4074,7 +4074,7 @@ adjust_limit_rows_costs(double *rows,     /* in/out parameter */
                if (input_rows > 0)
                        *total_cost = *startup_cost +
                                (input_total_cost - input_startup_cost)
-                               * count_rows / input_rows;
+                               * log2(1+count_rows) / log2(1+input_rows);
                *rows = count_rows;
                if (*rows < 1)
                        *rows = 1;

$ source env_pg.sh 5466 pg18limit pgdatalimit
postgres@db-benchmark-master-> pg_ctl -D /data/pgsql/pgdatalimit -m fast stop
waiting for server to shut down..... done
server stopped
postgres@db-benchmark-master-> /opt/app/pg18limit/bin/pg_ctl -D /data/pgsql/pgdatalimit start
waiting for server to start....2024-12-24 14:01:28.653 +08 [276263] LOG:  redirecting log output to logging collector process
2024-12-24 14:01:28.653 +08 [276263] HINT:  Future log output will appear in directory "log".
 done
server started
postgres@db-benchmark-master-> psql
psql (18devel)
Type "help" for help.

postgres=# \c sysbench
You are now connected to database "sysbench" as user "postgres".



sysbench=# explain analyze  select userid from dba_users where  username like '%aaaaaaaaaaaa%' order by userid limit 1;
                                                                    QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=2298.53..2298.69 rows=1 width=4) (actual time=200.202..200.204 rows=0 loops=1)
   Buffers: shared hit=12958 read=18851
   ->  Sort  (cost=2298.53..2300.03 rows=600 width=4) (actual time=200.200..200.202 rows=0 loops=1)
         Sort Key: userid
         Sort Method: quicksort  Memory: 25kB
         Buffers: shared hit=12958 read=18851
         ->  Bitmap Heap Scan on dba_users  (cost=57.22..2295.53 rows=600 width=4) (actual time=200.195..200.196 rows=0 loops=1)
               Recheck Cond: ((username)::text ~~ '%aaaaaaaaaaaa%'::text)
               Rows Removed by Index Recheck: 41242
               Heap Blocks: exact=31795
               Buffers: shared hit=12958 read=18851
               ->  Bitmap Index Scan on dba_users_username_idx  (cost=0.00..57.07 rows=600 width=0) (actual time=7.992..7.993 rows=41242 loops=1)
                     Index Cond: ((username)::text ~~ '%aaaaaaaaaaaa%'::text)
                     Buffers: shared hit=1 read=13
 Planning:
   Buffers: shared hit=24 read=5
 Planning Time: 0.569 ms
 Execution Time: 200.283 ms
(18 rows)

sysbench=# explain analyze  select userid from dba_users where  username like '%aaaaaaaaaaaa%' order by userid+0 limit 1;
                                                                    QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=2300.03..2300.19 rows=1 width=8) (actual time=55.165..55.166 rows=0 loops=1)
   Buffers: shared hit=31809
   ->  Sort  (cost=2300.03..2301.53 rows=600 width=8) (actual time=55.164..55.165 rows=0 loops=1)
         Sort Key: ((userid + 0))
         Sort Method: quicksort  Memory: 25kB
         Buffers: shared hit=31809
         ->  Bitmap Heap Scan on dba_users  (cost=57.22..2297.03 rows=600 width=8) (actual time=55.160..55.160 rows=0 loops=1)
               Recheck Cond: ((username)::text ~~ '%aaaaaaaaaaaa%'::text)
               Rows Removed by Index Recheck: 41242
               Heap Blocks: exact=31795
               Buffers: shared hit=31809
               ->  Bitmap Index Scan on dba_users_username_idx  (cost=0.00..57.07 rows=600 width=0) (actual time=7.080..7.080 rows=41242 loops=1)
                     Index Cond: ((username)::text ~~ '%aaaaaaaaaaaa%'::text)
                     Buffers: shared hit=14
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.119 ms
 Execution Time: 55.187 ms
(18 rows)

sysbench=# explain analyze  select userid from dba_users where  username like '%aaaaaaaaaaaa%' order by userid limit 1;
                                                                    QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=2298.53..2298.69 rows=1 width=4) (actual time=56.483..56.484 rows=0 loops=1)
   Buffers: shared hit=31809
   ->  Sort  (cost=2298.53..2300.03 rows=600 width=4) (actual time=56.481..56.483 rows=0 loops=1)
         Sort Key: userid
         Sort Method: quicksort  Memory: 25kB
         Buffers: shared hit=31809
         ->  Bitmap Heap Scan on dba_users  (cost=57.22..2295.53 rows=600 width=4) (actual time=56.476..56.477 rows=0 loops=1)
               Recheck Cond: ((username)::text ~~ '%aaaaaaaaaaaa%'::text)
               Rows Removed by Index Recheck: 41242
               Heap Blocks: exact=31795
               Buffers: shared hit=31809
               ->  Bitmap Index Scan on dba_users_username_idx  (cost=0.00..57.07 rows=600 width=0) (actual time=7.284..7.285 rows=41242 loops=1)
                     Index Cond: ((username)::text ~~ '%aaaaaaaaaaaa%'::text)
                     Buffers: shared hit=14
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.145 ms
 Execution Time: 56.531 ms
(18 rows)

#

The reality may be more complicated, I mean there is no better way for the community leaders to solve this problem, because the community will never say no to the hint, and there are so many such problems

Thanks