postgres: Make the initial type map query less expensive by fsateler · Pull Request #40876 · rails/rails

fsateler · 2020-12-17T22:45:20Z

Summary

When the pg_type table is large, the initial type map query is very expensive.
This is due to two reasons:

The complete query does not allow use of any indexes.
The complete query returns much more rows than we need

Point 1 is fixed by splitting up each OR into its own query. For reasons
unknown to me, the query plan is slower with OR instead of separate
queries. My suspicion is that reducing the number of checks to do on a full table scan is faster, because other checks are done with an index.

Point 2 is a problem when databases have lots of tables. This is because
for each table, postgres creates both a type for each record, and a type
for an array of records. The latter types are matched by the condition
t.typelem != 0. There is no easy way to filter out these types, but
since we already make a new query due to point 1, we can change our query
to bring us exactly the data we need: all the types that reference (via
typelem) a type we already know about. This way we greatly reduce the
number of rows returned.

This change brings a type map initialization performance improvement.
A production system with aprox 1.6MM rows in pg_type, improves from
2.5-4.1 seconds to 1.4-1.6 seconds.

Other Information

Additionally, we remove the condition
t.typinput = 'array_in(cstring,oid,integer)'::regprocedure, since it
appears to bring no value. Array types have a nonzero typelem. I'm marking this PR as Draft because I'm not 100% sure about this.

When the pg_type table is large, the initial type map query is very expensive. This is due to two reasons: 1. The complete query does not allow use of any indexes. 2. The complete query returns much more rows than we need Point 1 is fixed by splitting up each OR into its own query. For reasons unknown to me, the query plan is slower with OR instead of separate queries. Point 2 is a problem when databases have lots of tables. This is because for each table, postgres creates both a type for each record, and a type for an array of records. The latter types are matched by the condition `t.typelem != 0`. There is no easy way to filter out these types, but since we already make a new query due to point 1, we can change our query to bring us exactly the data we need: all the types that reference (via `typelem`) a type we already know about. This way we greatly reduce the number of rows returned. Additionally, we remove the condition `t.typinput = 'array_in(cstring,oid,integer)'::regprocedure`, since it brings no value. Array types have a nonzero `typelem`. This change brings a type map initialization performance improvement. A production system with aprox 1.6MM rows in `pg_type`, improves from 2.5-4.1 seconds to 1.4-1.6 seconds.

ghiculescu · 2022-10-26T18:56:30Z

FYI: https://discuss.rubyonrails.org/t/performance-issue-with-postgresql-after-upgrading-to-rails-7-0-4/81622

fsateler · 2022-10-26T20:33:07Z

I'm sorry to see that. I have pending to submit patch to (optionally) disable type map initialization. It turns out it's not strictly necessary, and (as seen in the linked discussion), can be quite costly in databases using apartment gem. Since typname is the only indexed column, I only leave query_conditions_for_known_type_names intact, and don't preload known type types or array types:

    def query_conditions_for_known_type_types
      known_type_types = %w('r' 'e' 'd')
      <<~SQL % known_type_types.join(", ")
        WHERE
          1 = 0
      SQL
    end

    def query_conditions_for_array_types
      known_type_oids = @store.keys.reject { |k| k.is_a?(String) }
      <<~SQL % [known_type_oids.join(", ")]
        WHERE
          1 = 0
      SQL
    end

lorint · 2022-10-27T05:04:57Z

Instead of the query ending up as:

SELECT t.oid, t.typname, t.typelem, t.typdelim, t.typinput, r.rngsubtype, t.typtype, t.typbasetype
	FROM pg_type as t
	LEFT JOIN pg_range as r ON oid = rngtypid
	WHERE
	  t.typelem IN (16, 17, 18, 19, 20, ...

if it could be this then it might run quite a bit faster:

SELECT t.oid, t.typname, t.typelem, t.typdelim, t.typinput, r.rngsubtype, t.typtype, t.typbasetype
	FROM pg_type AS t
	LEFT JOIN (SELECT rngtypid, rngsubtype FROM pg_range AS r1
      JOIN (VALUES (16),(17),(18),(19),(20), ...
             ) AS r2(oid) ON r1.rngtypid = r2.oid) AS r ON t.oid = r.rngtypid

jorgearimitsu · 2022-11-14T16:04:52Z

FIY: As suggested by an user on stack overflow, upgrading to PostgreSQL 14 did the trick:
https://stackoverflow.com/a/74198628/13529288

After the upgrade the execution time of this query decreased from 9656.222 ms to 60.618 ms

berniechiu · 2023-01-19T08:13:16Z

This change also makes our app query extremely slower, we're also on AWS RDS Aurora

We haven't had the chance to upgrade Postgres to 14 yet.

lorint · 2023-01-19T08:26:24Z

@jorgearimitsu - would you like to try the version that (for me at least) works faster under Postgres < 14? The general idea is in the post above from October 27 :)
Here's a link to your gist which has the full query from your example:
https://gist.github.com/jorgearimitsu/bb4aa460af55bbe0bb54f9d0aa594eda?permalink_comment_id=4348584#gistcomment-4348584

jcoleman · 2024-08-08T14:01:43Z

For reasons unknown to me, the query plan is slower with OR instead of separate queries.

@fsateler I have an idea on how to optimize this as a single query, which we're interested in to reduce the number of query roundtrips at boot. Would you be willing to help verify performance of an updated query if I provided that?

BTW I'm the author of the "use hashtable for IN () queries" performance improvement in Postgres, so it was interesting to see that show up here.

fsateler · 2024-08-08T18:46:26Z

Hi @jcoleman, I would be glad to help.

jcoleman · 2024-08-13T13:37:45Z

@fsateler Here's a branch with changes; would love your feedback prior to my opening a PR.

It looks like you never ended up adding an option to disable loading array types and types by type, but maybe I'm missing something. Either way, my patch should make array loading more performant (by turning that into an index scan) and retain the ability to disable loading types by type. If you disable that by overriding query_conditions_for_known_type_types then you're get an index scan on pg_types for the typname loading; otherwise you'll (correctly) get a seq scan, since it doesn't make sense to do both a seq scan and an index scan on the same table -- if you're going to scan the entire table you might as well make the most of it.

fsateler · 2024-08-23T22:28:08Z

Hi @jcoleman ! Sorry for the delay, busy weeks. I scheduled some time for wednesday to check it out.

fsateler · 2024-08-29T22:21:08Z

Hi! I have news to report. On a database with 4_986_377 elements in pg_type, rails generates the following queries:

SCHEMA (2.1ms) SELECT t.oid, t.typname, t.typelem, t.typdelim, t.typinput, r.rngsubtype, t.typtype, t.typbasetype FROM pg_type as t LEFT JOIN pg_range as r ON oid = rngtypid WHERE   t.typname IN ('int2', 'int4', 'int8', 'oid', 'float4', 'float8', 'text', 'varchar', 'char', 'name', 'bpchar', 'bool', 'bit', 'varbit', 'timestamptz', 'date', 'money', 'bytea', 'point', 'hstore', 'json', 'jsonb', 'cidr', 'inet', 'uuid', 'xml', 'tsvector', 'macaddr', 'citext', 'ltree', 'line', 'lseg', 'box', 'path', 'polygon', 'circle', 'time', 'timestamp', 'numeric', 'interval')
SCHEMA (1965.3ms) SELECT t.oid, t.typname, t.typelem, t.typdelim, t.typinput, r.rngsubtype, t.typtype, t.typbasetype FROM pg_type as t LEFT JOIN pg_range as r ON oid = rngtypid WHERE         t.typtype IN ('r', 'e', 'd')
SCHEMA (1167.9ms) SELECT t.oid, t.typname, t.typelem, t.typdelim, t.typinput, r.rngsubtype, t.typtype, t.typbasetype FROM pg_type as t LEFT JOIN pg_range as r ON oid = rngtypid WHERE         t.typelem IN (16, 17, 18, 19, 20, 21, 23, 25, 26, 114, 142, 600, 601, 602, 603, 604, 628, 700, 701, 718, 790, 829, 869, 650, 1042, 1043, 1082, 1083, 1114, 1184, 1186, 1560, 1562, 1700, 2950, 3614, 3802, 16414, 14027, 14030, 14032, 14037, 14039, 3904, 3906, 3908, 3910, 3912, 3926)

An the resulting type map has 140 elements.

After applying the patch, rails generates:

SCHEMA (3.8ms) SELECT types.*, r.rngsubtype FROM (   WITH non_array_types AS (   SELECT t.oid, t.typname, t.typelem, t.typdelim, t.typinput, t.typtype, t.typbasetype, t.typarray FROM pg_type as t WHERE t.typname IN ('r', 'e', 'd')  OR t.typname IN ('int2', 'int4', 'int8', 'oid', 'float4', 'float8', 'text', 'varchar', 'char', 'name', 'bpchar', 'bool', 'bit', 'varbit', 'timestamptz', 'date', 'money', 'bytea', 'point', 'hstore', 'json', 'jsonb', 'cidr', 'inet', 'uuid', 'xml', 'tsvector', 'macaddr', 'citext', 'ltree', 'line', 'lseg', 'box', 'path', 'polygon', 'circle', 'time', 'timestamp', 'numeric', 'interval')   ) (   SELECT oid, typname, typelem, typdelim, typinput, typtype, typbasetype   FROM non_array_types   UNION   SELECT oid, typname, typelem, typdelim, typinput, typtype, typbasetype   FROM pg_type   WHERE oid = ANY ((SELECT array_agg(nat.typarray) FROM non_array_types nat)::oid[]) )  ) types LEFT JOIN pg_range as r ON oid = rngtypid

But the resulting type map has only 116 elements 🤔

Overriding query_conditions_for_known_type_types results in:

SELECT types.*, r.rngsubtype FROM (   WITH non_array_types AS (   SELECT t.oid, t.typname, t.typelem, t.typdelim, t.typinput, t.typtype, t.typbasetype, t.typarray FROM pg_type as t WHERE 1 = 0  OR t.typname IN ('int2', 'int4', 'int8', 'oid', 'float4', 'float8', 'text', 'varchar', 'char', 'name', 'bpchar', 'bool', 'bit', 'varbit', 'timestamptz', 'date', 'money', 'bytea', 'point', 'hstore', 'json', 'jsonb', 'cidr', 'inet', 'uuid', 'xml', 'tsvector', 'macaddr', 'citext', 'ltree', 'line', 'lseg', 'box', 'path', 'polygon', 'circle', 'time', 'timestamp', 'numeric', 'interval')   ) (   SELECT oid, typname, typelem, typdelim, typinput, typtype, typbasetype   FROM non_array_types   UNION   SELECT oid, typname, typelem, typdelim, typinput, typtype, typbasetype   FROM pg_type   WHERE oid = ANY ((SELECT array_agg(nat.typarray) FROM non_array_types nat)::oid[]) )  ) types LEFT JOIN pg_range as r ON oid = rngtypid

And a type_map size of 116 as well 🤔 .

This is on

PostgreSQL 12.17 on aarch64-unknown-linux-gnu, compiled by gcc (GCC) 7.3.1 20180712 (Red Hat 7.3.1-6), 64-bit

Note: I couldn't get to run with a rails fork, so I monkeypatched according to the linked branch. In the interest of verifiability, here is my monkey patch:

Monkey Patch

ActiveSupport::Reloader.to_prepare do

  class ActiveRecord::ConnectionAdapters::PostgreSQL::OID::TypeMapInitializer
    def query_conditions_for_known_type_names
      known_type_names = @store.keys.map { |n| "'#{n}'" }
      <<~SQL % known_type_names.join(", ")
          t.typname IN (%s)
      SQL
    end

    def query_conditions_for_known_type_types
      known_type_types = %w('r' 'e' 'd')
      <<~SQL % known_type_types.join(", ")
                1 = 0
      SQL
    end

    def query_conditions_for_array_types
      known_type_oids = @store.keys.reject { |k| k.is_a?(String) }
      <<~SQL % [known_type_oids.join(", ")]
                t.typtype IN (%s)
      SQL
    end
  end

  class ActiveRecord::ConnectionAdapters::PostgreSQLAdapter
    def load_additional_types(oids = nil)
      initializer = OID::TypeMapInitializer.new(type_map)
      load_types_queries(initializer, oids) do |query|
        execute_and_clear(query, "SCHEMA", []) do |records|
          initializer.run(records)
        end
      end
    end

    def pg_types_scan_sql(where_conditions_sql, select_typarray: false)
      <<~SQL % where_conditions_sql
        SELECT t.oid, t.typname, t.typelem, t.typdelim, t.typinput, t.typtype, t.typbasetype, t.typarray
        FROM pg_type as t
        WHERE %s
      SQL
    end

    def load_types_queries(initializer, oids)
      outer_query = <<~SQL
            SELECT types.*, r.rngsubtype
            FROM (
              %s
            ) types
            LEFT JOIN pg_range as r ON oid = rngtypid
          SQL
      if oids
        yield outer_query % pg_types_scan_sql("t.oid IN (%s)" % oids.join(", "))
      else
        # We want to keep this as a single query to prevent unnecessary
        # round trips to the database when a connection starts up. We also
        # want to keep the query performing optimally when there are lots
        # of entries in pg_types.
        #
        # This was previously split into multiple queries because Postgres
        # doesn't optimize OR clauses well, so if we just OR the conditions
        # together we lose the index scan on `pg_types.typname`. However if we have to
        # scan on `pg_types.typtype` we're going to have to use a seq scan
        # regardless, and we might as well do a single scan to find all of
        # the entries. Some people want to
        # avoid the seq scan entirely, so we retain the extraction of
        # `TypeMapInitializer#query_conditions_for_known_type_types` so that
        # that portion can be disabled by overriding it to return `"1=0"`.
        #
        # We're able to fold in the array types query in a performant way
        # in the single query by using a CTE -- instead of doing a seq scan
        # on `pg_types.typelem` we work the opposite direction and can look
        # up entries using the `oid` index based on `typarray` values from
        # the rows we're otherwise returning.
        pg_types_conditions_sql = [
          initializer.query_conditions_for_known_type_types,
          initializer.query_conditions_for_known_type_names,
        ].join " OR "
        inner_query = <<~SQL
          WITH non_array_types AS (
            #{pg_types_scan_sql(pg_types_conditions_sql, select_typarray: true)}
          )
          (
            SELECT oid, typname, typelem, typdelim, typinput, typtype, typbasetype
            FROM non_array_types
            UNION
            SELECT oid, typname, typelem, typdelim, typinput, typtype, typbasetype
            FROM pg_type
            WHERE oid = ANY ((SELECT array_agg(nat.typarray) FROM non_array_types nat)::oid[])
          )
        SQL
        yield outer_query % inner_query

        Rails.logger.info "type_map_size: #{type_map.instance_variable_get(:@mapping).size}"
      end
    end
  end
end

jcoleman · 2024-08-30T13:55:46Z

@fsateler Thanks for testing! Would you be able to run the following query on that database to find what rows are being left out?

 (
SELECT types.*, r.rngsubtype FROM
(
  WITH non_array_types AS (
    SELECT t.oid, t.typname, t.typelem, t.typdelim, t.typinput, t.typtype, t.typbasetype, t.typarray
    FROM pg_type as t
    WHERE t.typname IN ('r', 'e', 'd')
      OR t.typname IN ('int2', 'int4', 'int8', 'oid', 'float4', 'float8', 'text', 'varchar', 'char', 'name', 'bpchar', 'bool', 'bit', 'varbit', 'timestamptz', 'date', 'money', 'bytea', 'point', 'hstore', 'json', 'jsonb', 'cidr', 'inet', 'uuid', 'xml', 'tsvector', 'macaddr', 'citext', 'ltree', 'line', 'lseg', 'box', 'path', 'polygon', 'circle', 'time', 'timestamp', 'numeric', 'interval')
  )
  (
    SELECT oid, typname, typelem, typdelim, typinput, typtype, typbasetype
    FROM non_array_types
    UNION
    SELECT oid, typname, typelem, typdelim, typinput, typtype, typbasetype
    FROM pg_type
    WHERE oid = ANY ((SELECT array_agg(nat.typarray) FROM non_array_types nat)::oid[])
    UNION
    SELECT oid, typname, typelem, typdelim, typinput, typtype, typbasetype
    FROM pg_type
    WHERE typelem IN (SELECT oid FROM non_array_types)
  )
) types
LEFT JOIN pg_range as r ON oid = rngtypid
EXCEPT
SELECT types.*, r.rngsubtype FROM
(
  WITH non_array_types AS (
    SELECT t.oid, t.typname, t.typelem, t.typdelim, t.typinput, t.typtype, t.typbasetype, t.typarray
    FROM pg_type as t
    WHERE t.typname IN ('r', 'e', 'd')
      OR t.typname IN ('int2', 'int4', 'int8', 'oid', 'float4', 'float8', 'text', 'varchar', 'char', 'name', 'bpchar', 'bool', 'bit', 'varbit', 'timestamptz', 'date', 'money', 'bytea', 'point', 'hstore', 'json', 'jsonb', 'cidr', 'inet', 'uuid', 'xml', 'tsvector', 'macaddr', 'citext', 'ltree', 'line', 'lseg', 'box', 'path', 'polygon', 'circle', 'time', 'timestamp', 'numeric', 'interval')
  )
  (
    SELECT oid, typname, typelem, typdelim, typinput, typtype, typbasetype
    FROM non_array_types
    UNION
    SELECT oid, typname, typelem, typdelim, typinput, typtype, typbasetype
    FROM pg_type
    WHERE oid = ANY ((SELECT array_agg(nat.typarray) FROM non_array_types nat)::oid[])
  )
) types
LEFT JOIN pg_range as r ON oid = rngtypid
)
ORDER BY oid;

On one PG database of ours that yields:

 oid |  typname   | typelem | typdelim |   typinput   | typtype | typbasetype | rngsubtype 
-----+------------+---------+----------+--------------+---------+-------------+------------
  22 | int2vector |      21 | ,        | int2vectorin | b       |           0 |           
  30 | oidvector  |      26 | ,        | oidvectorin  | b       |           0 |

but our pg_type count is substantially lower than yours (a couple thousand entries).

You could also find the differences between the type maps and query on those OIDs. The difference here I think is going to boil down to the fact that typarray references the array type of a given type, but typelem not only has the reference in the opposite direction, it's also slightly different: it's the type you'd get if you subscripted the type. I suspect we only need the narrower array types loading from ActiveRecord's perspective, but it would be good to be able to verify.

fsateler · 2024-08-30T19:49:56Z

oid	typname	typelem	typdelim	typinput	typtype	typbasetype	rngsubtype
22	int2vector	21	,	int2vectorin	b	0
30	oidvector	26	,	oidvectorin	b	0

Does this validate your hipothesis?

jcoleman · 2024-08-31T01:37:53Z

Those are the only two I see also — and ActiveRecord shouldn’t need to see those ones. Hmm. Are you able to introspect the schema cache itself and see what oid values are missing (and then query pg_type to see what types those represent)?

rails-bot bot added the activerecord label Dec 17, 2020

rafaelfranca marked this pull request as ready for review December 18, 2020 21:14

rafaelfranca merged commit 3cff5e7 into rails:master Dec 18, 2020

fsateler deleted the performance/type-map-initialize branch December 21, 2020 14:00

piecehealth mentioned this pull request Feb 2, 2021

Cache the result of type-related queries for PostgreSQL adapter. #41288

Closed

Conversation

fsateler commented Dec 17, 2020

Summary

Other Information

Uh oh!

ghiculescu commented Oct 26, 2022

Uh oh!

fsateler commented Oct 26, 2022

Uh oh!

lorint commented Oct 27, 2022

Uh oh!

jorgearimitsu commented Nov 14, 2022

Uh oh!

berniechiu commented Jan 19, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

lorint commented Jan 19, 2023

Uh oh!

jcoleman commented Aug 8, 2024

Uh oh!

fsateler commented Aug 8, 2024

Uh oh!

jcoleman commented Aug 13, 2024

Uh oh!

fsateler commented Aug 23, 2024

Uh oh!

fsateler commented Aug 29, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jcoleman commented Aug 30, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

fsateler commented Aug 30, 2024

Uh oh!

jcoleman commented Aug 31, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

berniechiu commented Jan 19, 2023 •

edited

Loading

fsateler commented Aug 29, 2024 •

edited

Loading

jcoleman commented Aug 30, 2024 •

edited

Loading