0002-patch-1-gin_check_parent_keys_consistency.patch

From e4a6292ff262e754c32fd26325bf386dec3a2981 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@vondra.me>
Date: Mon, 9 Jun 2025 01:44:59 +0200
Subject: [PATCH 2/5] patch 1: gin_check_parent_keys_consistency

This commit address several issues:
- Current code doesn't take into account attribute number when comparing index entries, but for multicolumn indexes attnum defines order.
- Add check that root page entries are ordered (there is nothing special about the root page that would prevent us from checking the order)
- Add checking order for the rightmost entry of the leaf level and skip it only for inner level.
- Split detection fix: in the case of a split, the cached parent key is greater than the current child key, not less.
---
 contrib/amcheck/meson.build         |   1 +
 contrib/amcheck/t/006_verify_gin.pl | 200 ++++++++++++++++++++++++++++
 contrib/amcheck/verify_gin.c        |  37 ++---
 3 files changed, 220 insertions(+), 18 deletions(-)
 create mode 100644 contrib/amcheck/t/006_verify_gin.pl

diff --git a/contrib/amcheck/meson.build b/contrib/amcheck/meson.build
index b33e8c9b062..1f0c347ed54 100644
--- a/contrib/amcheck/meson.build
+++ b/contrib/amcheck/meson.build
@@ -49,6 +49,7 @@ tests += {
       't/003_cic_2pc.pl',
       't/004_verify_nbtree_unique.pl',
       't/005_pitr.pl',
+      't/006_verify_gin.pl',
     ],
   },
 }
diff --git a/contrib/amcheck/t/006_verify_gin.pl b/contrib/amcheck/t/006_verify_gin.pl
new file mode 100644
index 00000000000..46f693fbb08
--- /dev/null
+++ b/contrib/amcheck/t/006_verify_gin.pl
@@ -0,0 +1,200 @@
+
+# Copyright (c) 2021-2025, PostgreSQL Global Development Group
+
+use strict;
+use warnings FATAL => 'all';
+
+use PostgreSQL::Test::Cluster;
+use PostgreSQL::Test::Utils;
+
+use Test::More;
+
+my $node;
+my $blksize;
+
+#
+# Test set-up
+#
+$node = PostgreSQL::Test::Cluster->new('test');
+$node->init(no_data_checksums => 1);
+$node->append_conf('postgresql.conf', 'autovacuum=off');
+$node->start;
+$blksize = int($node->safe_psql('postgres', 'SHOW block_size;'));
+$node->safe_psql('postgres', q(CREATE EXTENSION amcheck));
+$node->safe_psql(
+	'postgres', q(
+		CREATE OR REPLACE FUNCTION  random_string( INT ) RETURNS text AS $$
+		SELECT string_agg(substring('0123456789bcdfghjkmnpqrstvwxyz', ceil(random() * 30)::integer, 1), '') from generate_series(1, $1);
+		$$ LANGUAGE SQL;));
+
+# Tests
+invalid_entry_order_leaf_page_test();
+invalid_entry_order_inner_page_test();
+invalid_entry_columns_order_test();
+
+sub invalid_entry_order_leaf_page_test
+{
+	my $relname = "test";
+	my $indexname = "test_gin_idx";
+
+	$node->safe_psql(
+		'postgres', qq(
+		DROP TABLE IF EXISTS $relname;
+		CREATE TABLE $relname (a text[]);
+		CREATE INDEX $indexname ON $relname USING gin (a);
+		INSERT INTO $relname (a) VALUES ('{aaaaa,bbbbb}');
+		SELECT gin_clean_pending_list('$indexname');
+	 ));
+	my $relpath = relation_filepath($indexname);
+
+	$node->stop;
+
+	my $blkno = 1;  # root
+
+	# produce wrong order by replacing aaaaa with ccccc
+	string_replace_block(
+		$relpath,
+		'aaaaa',
+		'ccccc',
+		$blksize,
+		$blkno
+	);
+
+	$node->start;
+
+	my ($result, $stdout, $stderr) = $node->psql('postgres', qq(SELECT gin_index_check('$indexname')));
+	my $expected = "index \"$indexname\" has wrong tuple order on entry tree page, block 1, offset 2, rightlink 4294967295";
+	like($stderr, qr/$expected/);
+}
+
+sub invalid_entry_order_inner_page_test
+{
+	my $relname = "test";
+	my $indexname = "test_gin_idx";
+
+	$node->safe_psql(
+		'postgres', qq(
+		DROP TABLE IF EXISTS $relname;
+		CREATE TABLE $relname (a text[]);
+		CREATE INDEX $indexname ON $relname USING gin (a);
+		INSERT INTO $relname (a) VALUES (('{' || 'pppppppppp' || random_string(1870) ||'}')::text[]);
+		INSERT INTO $relname (a) VALUES (('{' || 'qqqqqqqqqq' || random_string(1870) ||'}')::text[]);
+		INSERT INTO $relname (a) VALUES (('{' || 'rrrrrrrrrr' || random_string(1870) ||'}')::text[]);
+		INSERT INTO $relname (a) VALUES (('{' || 'ssssssssss' || random_string(1870) ||'}')::text[]);
+		INSERT INTO $relname (a) VALUES (('{' || 'tttttttttt' || random_string(1870) ||'}')::text[]);
+		INSERT INTO $relname (a) VALUES (('{' || 'uuuuuuuuuu' || random_string(1870) ||'}')::text[]);
+		INSERT INTO $relname (a) VALUES (('{' || 'vvvvvvvvvv' || random_string(1870) ||'}')::text[]);
+		INSERT INTO $relname (a) VALUES (('{' || 'wwwwwwwwww' || random_string(1870) ||'}')::text[]);
+		SELECT gin_clean_pending_list('$indexname');
+	));
+	my $relpath = relation_filepath($indexname);
+
+	$node->stop;
+
+	my $blkno = 1;  # root
+
+	# we have rrrrrrrrr... and tttttttttt... as keys in the root, so produce wrong order by replacing rrrrrrrrrr....
+	string_replace_block(
+		$relpath,
+		'rrrrrrrrrr',
+		'zzzzzzzzzz',
+		$blksize,
+		$blkno
+	);
+
+	$node->start;
+
+	my ($result, $stdout, $stderr) = $node->psql('postgres', qq(SELECT gin_index_check('$indexname')));
+	my $expected = "index \"$indexname\" has wrong tuple order on entry tree page, block 1, offset 2, rightlink 4294967295";
+	like($stderr, qr/$expected/);
+}
+
+sub invalid_entry_columns_order_test
+{
+	my $relname = "test";
+	my $indexname = "test_gin_idx";
+
+	$node->safe_psql(
+		'postgres', qq(
+		DROP TABLE IF EXISTS $relname;
+		CREATE TABLE $relname (a text[],b text[]);
+		CREATE INDEX $indexname ON $relname USING gin (a,b);
+		INSERT INTO $relname (a,b) VALUES ('{aaa}','{bbb}');
+		SELECT gin_clean_pending_list('$indexname');
+	));
+	my $relpath = relation_filepath($indexname);
+
+	$node->stop;
+
+	my $blkno = 1;  # root
+
+	# mess column numbers
+	# root items order before: (1,aaa), (2,bbb)
+	# root items order after:  (2,aaa), (1,bbb)
+	my $attrno_1 = pack('s', 1);
+	my $attrno_2 = pack('s', 2);
+
+	my $find = qr/($attrno_1)(.)(aaa)/s;
+	my $replace = $attrno_2 . '$2$3';
+	string_replace_block(
+		$relpath,
+		$find,
+		$replace,
+		$blksize,
+		$blkno
+	);
+
+	$find = qr/($attrno_2)(.)(bbb)/s;
+	$replace = $attrno_1 . '$2$3';
+	string_replace_block(
+		$relpath,
+		$find,
+		$replace,
+		$blksize,
+		$blkno
+	);
+
+	$node->start;
+
+	my ($result, $stdout, $stderr) = $node->psql('postgres', qq(SELECT gin_index_check('$indexname')));
+	my $expected = "index \"$indexname\" has wrong tuple order on entry tree page, block 1, offset 2, rightlink 4294967295";
+	like($stderr, qr/$expected/);
+}
+
+# Returns the filesystem path for the named relation.
+sub relation_filepath
+{
+	my ($relname) = @_;
+
+	my $pgdata = $node->data_dir;
+	my $rel = $node->safe_psql('postgres',
+		qq(SELECT pg_relation_filepath('$relname')));
+	die "path not found for relation $relname" unless defined $rel;
+	return "$pgdata/$rel";
+}
+
+sub string_replace_block
+{
+	my ($filename, $find, $replace, $blksize, $blkno) = @_;
+
+	my $fh;
+	open($fh, '+<', $filename) or BAIL_OUT("open failed: $!");
+	binmode $fh;
+
+	my $offset = $blkno * $blksize;
+	my $buffer;
+
+	sysseek($fh, $offset, 0) or BAIL_OUT("seek failed: $!");
+	sysread($fh, $buffer, $blksize) or BAIL_OUT("read failed: $!");
+
+	$buffer =~ s/$find/'"' . $replace . '"'/gee;
+
+	sysseek($fh, $offset, 0) or BAIL_OUT("seek failed: $!");
+	syswrite($fh, $buffer) or BAIL_OUT("write failed: $!");
+
+	close($fh) or BAIL_OUT("close failed: $!");
+
+	return;
+}
+
+done_testing();
diff --git a/contrib/amcheck/verify_gin.c b/contrib/amcheck/verify_gin.c
index b5f363562e3..26b98571b56 100644
--- a/contrib/amcheck/verify_gin.c
+++ b/contrib/amcheck/verify_gin.c
@@ -463,17 +463,18 @@ gin_check_parent_keys_consistency(Relation rel,
 			Datum		parent_key = gintuple_get_key(&state,
 													  stack->parenttup,
 													  &parent_key_category);
+			OffsetNumber parent_key_attnum = gintuple_get_attrnum(&state, stack->parenttup);
 			ItemId		iid = PageGetItemIdCareful(rel, stack->blkno,
 												   page, maxoff);
 			IndexTuple	idxtuple = (IndexTuple) PageGetItem(page, iid);
-			OffsetNumber attnum = gintuple_get_attrnum(&state, idxtuple);
+			OffsetNumber page_max_key_attnum = gintuple_get_attrnum(&state, idxtuple);
 			GinNullCategory page_max_key_category;
 			Datum		page_max_key = gintuple_get_key(&state, idxtuple, &page_max_key_category);
 
 			if (rightlink != InvalidBlockNumber &&
-				ginCompareEntries(&state, attnum, page_max_key,
-								  page_max_key_category, parent_key,
-								  parent_key_category) > 0)
+				ginCompareAttEntries(&state, page_max_key_attnum, page_max_key,
+									 page_max_key_category, parent_key_attnum,
+									 parent_key, parent_key_category) < 0)
 			{
 				/* split page detected, install right link to the stack */
 				GinScanItem *ptr;
@@ -528,20 +529,18 @@ gin_check_parent_keys_consistency(Relation rel,
 			current_key = gintuple_get_key(&state, idxtuple, &current_key_category);
 
 			/*
-			 * First block is metadata, skip order check. Also, never check
-			 * for high key on rightmost page, as this key is not really
-			 * stored explicitly.
+			 * Never check for high key on rightmost inner page, as this key
+			 * is not really stored explicitly.
 			 *
 			 * Also make sure to not compare entries for different attnums,
 			 * which may be stored on the same page.
 			 */
-			if (i != FirstOffsetNumber && attnum == prev_attnum && stack->blkno != GIN_ROOT_BLKNO &&
-				!(i == maxoff && rightlink == InvalidBlockNumber))
+			if (i != FirstOffsetNumber && !(i == maxoff && rightlink == InvalidBlockNumber && !GinPageIsLeaf(page)))
 			{
 				prev_key = gintuple_get_key(&state, prev_tuple, &prev_key_category);
-				if (ginCompareEntries(&state, attnum, prev_key,
-									  prev_key_category, current_key,
-									  current_key_category) >= 0)
+				if (ginCompareAttEntries(&state, prev_attnum, prev_key,
+										 prev_key_category, attnum,
+										 current_key, current_key_category) >= 0)
 					ereport(ERROR,
 							(errcode(ERRCODE_INDEX_CORRUPTED),
 							 errmsg("index \"%s\" has wrong tuple order on entry tree page, block %u, offset %u, rightlink %u",
@@ -556,13 +555,14 @@ gin_check_parent_keys_consistency(Relation rel,
 				i == maxoff)
 			{
 				GinNullCategory parent_key_category;
+				OffsetNumber parent_key_attnum = gintuple_get_attrnum(&state, stack->parenttup);
 				Datum		parent_key = gintuple_get_key(&state,
 														  stack->parenttup,
 														  &parent_key_category);
 
-				if (ginCompareEntries(&state, attnum, current_key,
-									  current_key_category, parent_key,
-									  parent_key_category) > 0)
+				if (ginCompareAttEntries(&state, attnum, current_key,
+										 current_key_category, parent_key_attnum,
+										 parent_key, parent_key_category) > 0)
 				{
 					/*
 					 * There was a discrepancy between parent and child
@@ -581,6 +581,7 @@ gin_check_parent_keys_consistency(Relation rel,
 							 stack->blkno, stack->parentblk);
 					else
 					{
+						parent_key_attnum = gintuple_get_attrnum(&state, stack->parenttup);
 						parent_key = gintuple_get_key(&state,
 													  stack->parenttup,
 													  &parent_key_category);
@@ -589,9 +590,9 @@ gin_check_parent_keys_consistency(Relation rel,
 						 * Check if it is properly adjusted. If succeed,
 						 * proceed to the next key.
 						 */
-						if (ginCompareEntries(&state, attnum, current_key,
-											  current_key_category, parent_key,
-											  parent_key_category) > 0)
+						if (ginCompareAttEntries(&state, attnum, current_key,
+												 current_key_category, parent_key_attnum,
+												 parent_key, parent_key_category) > 0)
 							ereport(ERROR,
 									(errcode(ERRCODE_INDEX_CORRUPTED),
 									 errmsg("index \"%s\" has inconsistent records on page %u offset %u",
-- 
2.43.0