Postgres 16

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.
/*CREATE COLLATION numeric_ignore_accents_case_punct_whitespace (
  provider = icu, 
  locale = 'und-u-ks-level1-kc-true-ka-shifted-kn', 
  deterministic = true);
*/
CREATE TABLE song(
   id     int generated always as identity primary key,
   title  text --collate numeric_ignore_accents_case_punct_whitespace
);
INSERT INTO song(title) VALUES 
('itsy bitsy spider'),
('itsy bitsy'),
('itsy bitsy'),
('row row row your boat'),
('twinkle twinkle'),
('twinkle twinkle little star')
returning *;

insert into song(title) select gen_random_uuid() from generate_series(1,1e4);
create extension pg_trgm;
create index idx_gin on song using gin(title gin_trgm_ops);

CREATE TABLE

id
title

1
itsy bitsy spider

2
itsy bitsy

3
itsy bitsy

4
row row row your boat

5
twinkle twinkle

6
twinkle twinkle little star

INSERT 0 6

INSERT 0 10000

CREATE EXTENSION

CREATE INDEX

vacuum analyze song;

VACUUM

prepare trgm as 
select * from song s1 
inner join song s2 
 on s1.title ~ s2.title;

explain analyze verbose execute trgm;

PREPARE

QUERY PLAN

Nested Loop  (cost=1.15..62958.79 rows=500600 width=80) (actual time=0.140..1442.270 rows=10011 loops=1)

  Output: s1.id, s1.title, s2.id, s2.title

  ->  Seq Scan on public.song s2  (cost=0.00..194.06 rows=10006 width=40) (actual time=0.004..2.752 rows=10006 loops=1)

        Output: s2.id, s2.title

  ->  Bitmap Heap Scan on public.song s1  (cost=1.15..5.77 rows=50 width=40) (actual time=0.140..0.141 rows=1 loops=10006)

        Output: s1.id, s1.title

        Recheck Cond: (s1.title ~ s2.title)

        Heap Blocks: exact=10006

        ->  Bitmap Index Scan on idx_gin  (cost=0.00..1.14 rows=50 width=0) (actual time=0.107..0.107 rows=1 loops=10006)

              Index Cond: (s1.title ~ s2.title)

Planning Time: 0.623 ms

Execution Time: 1443.888 ms

EXPLAIN

prepare trgm2 as
select * from song s1 
inner join song s2 
  on s1.id <> s2.id 
 and s1.title ~* s2.title;

explain analyze verbose execute trgm2;

execute trgm2;

PREPARE

QUERY PLAN

Nested Loop  (cost=1.15..64209.54 rows=500550 width=80) (actual time=0.161..1396.962 rows=5 loops=1)

  Output: s1.id, s1.title, s2.id, s2.title

  ->  Seq Scan on public.song s2  (cost=0.00..194.06 rows=10006 width=40) (actual time=0.004..2.892 rows=10006 loops=1)

        Output: s2.id, s2.title

  ->  Bitmap Heap Scan on public.song s1  (cost=1.15..5.90 rows=50 width=40) (actual time=0.137..0.137 rows=0 loops=10006)

        Output: s1.id, s1.title

        Recheck Cond: (s1.title ~* s2.title)

        Filter: (s1.id <> s2.id)

        Rows Removed by Filter: 1

        Heap Blocks: exact=10006

        ->  Bitmap Index Scan on idx_gin  (cost=0.00..1.14 rows=50 width=0) (actual time=0.102..0.102 rows=1 loops=10006)

              Index Cond: (s1.title ~* s2.title)

Planning Time: 0.221 ms

Execution Time: 1397.005 ms

EXPLAIN

id
title
id
title

1
itsy bitsy spider
2
itsy bitsy

3
itsy bitsy
2
itsy bitsy

1
itsy bitsy spider
3
itsy bitsy

2
itsy bitsy
3
itsy bitsy

6
twinkle twinkle little star
5
twinkle twinkle

SELECT 5
id	title
1	itsy bitsy spider
2	itsy bitsy
3	itsy bitsy
4	row row row your boat
5	twinkle twinkle
6	twinkle twinkle little star