diff --git a/config/initializers/0_postgresql_primary_keys.rb b/config/initializers/0_postgresql_primary_keys.rb
new file mode 100644
index 0000000000000000000000000000000000000000..817a432478d10ddb945943c65d68e253d5a5bd93
--- /dev/null
+++ b/config/initializers/0_postgresql_primary_keys.rb
@@ -0,0 +1,35 @@
+# frozen_string_literal: true
+
+# Adds patch for ActiveRecord `primary_keys` method
+# to optimize the query for primary key retrieval.
+
+# Rails commit: https://github.com/rails/rails/commit/c93d1b09fcc013033af506b10fd60829267be85c
+# Issue: https://gitlab.com/gitlab-org/gitlab/-/work_items/579305
+module PostgreSQLAdapterCustomPrimaryKeys
+  if Rails.gem_version >= Gem::Version.new('8.1')
+    raise <<~ERROR
+      PostgreSQLAdapterCustomPrimaryKeys patch is no longer needed!
+
+      This patch was a backport of a Rails 7.2 fix for the primary_keys method.
+
+      Please remove this file and its associated test:
+      - config/initializers/0_postgresql_primary_keys.rb
+      - spec/initializers/0_postgresql_primary_keys_spec.rb
+
+    ERROR
+  end
+
+  def primary_keys(table_name)
+    query_values(<<~SQL.squish, "SCHEMA")
+      SELECT a.attname
+      FROM pg_index i
+      JOIN pg_attribute a
+        ON a.attrelid = i.indrelid
+        AND a.attnum = ANY(i.indkey)
+        WHERE i.indrelid = #{quote(quote_table_name(table_name))}::regclass
+        AND i.indisprimary
+       ORDER BY array_position(i.indkey, a.attnum)
+    SQL
+  end
+end
+ActiveRecord::ConnectionAdapters::PostgreSQLAdapter.prepend(PostgreSQLAdapterCustomPrimaryKeys)
diff --git a/spec/initializers/0_postgresql_primary_keys_spec.rb b/spec/initializers/0_postgresql_primary_keys_spec.rb
new file mode 100644
index 0000000000000000000000000000000000000000..6bf778dcaff008ca8f2adab7d3b4adde25b07b1c
--- /dev/null
+++ b/spec/initializers/0_postgresql_primary_keys_spec.rb
@@ -0,0 +1,112 @@
+# frozen_string_literal: true
+
+require 'spec_helper'
+RSpec.describe 'PostgreSQL primary keys', feature_category: :database do
+  let(:connection) { ApplicationRecord.connection }
+
+  describe 'Rails version guard' do
+    it 'raises error if Rails 8.1 or higher is detected' do
+      allow(Rails).to receive(:gem_version).and_return(Gem::Version.new('8.1'))
+
+      expect do
+        load Rails.root.join('config/initializers/0_postgresql_primary_keys.rb')
+      end.to raise_error(RuntimeError, /PostgreSQLAdapterCustomPrimaryKeys patch is no longer needed/)
+    end
+
+    it 'does not raise error for Rails 7.x' do
+      expect(Rails.gem_version).to be < Gem::Version.new('8.1')
+    end
+  end
+
+  describe 'patch application' do
+    it 'prepends PostgreSQLAdapterCustomPrimaryKeys module' do
+      expect(ActiveRecord::ConnectionAdapters::PostgreSQLAdapter.ancestors)
+        .to include(PostgreSQLAdapterCustomPrimaryKeys)
+    end
+
+    it 'patch is applied before the original ActiveRecord method' do
+      ancestors = ActiveRecord::ConnectionAdapters::PostgreSQLAdapter.ancestors
+      patch_index = ancestors.index(PostgreSQLAdapterCustomPrimaryKeys)
+      schema_statements_index = ancestors.index(ActiveRecord::ConnectionAdapters::PostgreSQL::SchemaStatements)
+
+      expect(patch_index).to be < schema_statements_index
+    end
+  end
+
+  describe '#primary_keys' do
+    context 'with single column primary key' do
+      let(:table_name) { :_test_single_pk }
+
+      before do
+        connection.execute(<<~SQL)
+          CREATE TABLE #{table_name} (
+            id bigserial PRIMARY KEY,
+            name text
+          )
+        SQL
+      end
+
+      after do
+        connection.execute("DROP TABLE IF EXISTS #{table_name}")
+      end
+
+      it 'returns the primary key column name' do
+        expect(connection.primary_keys(table_name)).to eq(['id'])
+      end
+    end
+
+    context 'with composite primary key' do
+      let(:table_name) { :_test_composite_pk }
+
+      before do
+        connection.execute(<<~SQL)
+          CREATE TABLE #{table_name} (
+            organization_id bigint NOT NULL,
+            resource_id bigint NOT NULL,
+            name text,
+            PRIMARY KEY (organization_id, resource_id)
+          )
+        SQL
+      end
+
+      after do
+        connection.execute("DROP TABLE IF EXISTS #{table_name}")
+      end
+
+      it 'returns all primary key columns in correct order' do
+        expect(connection.primary_keys(table_name))
+          .to eq(%w[organization_id resource_id])
+      end
+
+      it 'preserves the order defined in PRIMARY KEY constraint' do
+        primary_keys = connection.primary_keys(table_name)
+
+        expect(primary_keys.first).to eq('organization_id')
+        expect(primary_keys.second).to eq('resource_id')
+      end
+    end
+
+    context 'with reversed composite primary key order' do
+      let(:table_name) { :_test_reversed_pk }
+
+      before do
+        connection.execute(<<~SQL)
+          CREATE TABLE #{table_name} (
+            organization_id bigint NOT NULL,
+            resource_id bigint NOT NULL,
+            PRIMARY KEY (resource_id, organization_id)
+          )
+        SQL
+      end
+
+      after do
+        connection.execute("DROP TABLE IF EXISTS #{table_name}")
+      end
+
+      it 'returns columns in PRIMARY KEY definition order' do
+        expect(connection.primary_keys(table_name))
+          .to eq(%w[resource_id organization_id])
+      end
+    end
+  end
+end