Skip to content

The generated SQL does not uses indexes and performs sub-optimally #5949

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
mrkkrp opened this issue Oct 7, 2020 · 4 comments
Open

The generated SQL does not uses indexes and performs sub-optimally #5949

mrkkrp opened this issue Oct 7, 2020 · 4 comments
Assignees
Labels
a/performance c/server Related to server k/enhancement New feature or improve an existing feature p/high candidate for being included in the upcoming sprint

Comments

@mrkkrp
Copy link

mrkkrp commented Oct 7, 2020

We are experiencing a performance issue related to the fact that Hasura generates a sub-optional SQL query.

Simplified, let's say that we have order table which has id, supplierA, and supplierB fields. We also have supplier table with a, b, and name fields.

The relation is the following:

order . ( supplierA, supplierB ) → supplier . ( a, b )

We issue a query like this:

query MyQuery {
  order(
      order_by: {supplier: {name: asc}},
      limit: 10) {
    id
  }
}

The idea here is to get orders which are ordered by names of corresponding suppliers. Here is the SQL code that Hasura generates:

SELECT
  coalesce(
    json_agg(
      "root"
      ORDER BY
        "root.or.supplier.pg.name" ASC NULLS LAST
    ),
    '[]'
  ) AS "root"
FROM
  (
    SELECT
      "_2_root.or.supplier"."root.or.supplier.pg.name" AS "root.or.supplier.pg.name",
      row_to_json(
        (
          SELECT
            "_3_e"
          FROM
            (
              SELECT
                "_0_root.base"."id" AS "id"
            ) AS "_3_e"
        )
      ) AS "root"
    FROM
      (
        SELECT
          *
        FROM
          "public"."order"
        WHERE
          ('true')
      ) AS "_0_root.base"
      LEFT OUTER JOIN LATERAL (
        SELECT
          "_1_root.or.supplier.base"."name" AS "root.or.supplier.pg.name"
        FROM
          (
            SELECT
              *
            FROM
              "public"."supplier"
            WHERE
              (
                (
                  ("_0_root.base"."supplierB") = ("b")
                )
                AND (
                  ("_0_root.base"."supplierA") = ("a")
                )
              )
          ) AS "_1_root.or.supplier.base"
      ) AS "_2_root.or.supplier" ON ('true')
    ORDER BY
      "root.or.supplier.pg.name" ASC NULLS LAST
    LIMIT
      10
  ) AS "_4_root"

If we run EXPLAIN ANALYZE on it, we can see the following output:

Aggregate  (cost=186286.83..186286.84 rows=1 width=32) (actual time=2246.618..2246.618 rows=1 loops=1)
  ->  Limit  (cost=186286.68..186286.70 rows=10 width=52) (actual time=2246.584..2246.586 rows=10 loops=1)
        ->  Sort  (cost=186286.68..189446.60 rows=1263970 width=52) (actual time=2246.582..2246.583 rows=10 loops=1)
              Sort Key: supplier.name
              Sort Method: top-N heapsort  Memory: 26kB
              ->  Hash Left Join  (cost=645.57..158972.74 rows=1263970 width=52) (actual time=4.202..1961.412 rows=1269435 loops=1)
                    Hash Cond: (("order"."supplierB" = supplier."b") AND ("order"."supplierA" = supplier."a"))
                    ->  Seq Scan on "order"  (cost=0.00..135891.70 rows=1263970 width=19) (actual time=0.033..734.237 rows=1269435 loops=1)
                    ->  Hash  (cost=521.03..521.03 rows=8303 width=31) (actual time=4.115..4.116 rows=8303 loops=1)
                          Buckets: 16384  Batches: 1  Memory Usage: 662kB
                          ->  Seq Scan on supplier  (cost=0.00..521.03 rows=8303 width=31) (actual time=0.010..2.370 rows=8303 loops=1)
                    SubPlan 1
                      ->  Result  (cost=0.00..0.01 rows=1 width=32) (actual time=0.000..0.000 rows=1 loops=1269435)
Planning Time: 1.139 ms
Execution Time: 2246.722 ms

An important detail here is that there exist indexes:

CREATE INDEX "order_supplierKeys_idx" ON public."order" ("supplierB", "supplierA")
CREATE UNIQUE INDEX "supplier_keys" ON public.supplier ("a", "b")
CREATE INDEX supplier_name_idx ON public.supplier ("name")

Yet they seem to be unused in this case.

However, if we re-write the query manually:

select o.id
from "order" as o
join supplier as s on o."supplierB" = s."b" AND o."supplierA" = s."a"
order by s."name" asc
limit 10

The indexes are used and EXPLAIN ANALYZE returns the following result:

Limit  (cost=0.71..880.38 rows=10 width=28) (actual time=0.038..0.060 rows=10 loops=1)
  ->  Nested Loop  (cost=0.71..56299.45 rows=640 width=28) (actual time=0.037..0.058 rows=10 loops=1)
        ->  Index Scan using supplier_name_idx on supplier s  (cost=0.29..2244.82 rows=8303 width=31) (actual time=0.015..0.016 rows=1 loops=1)
        ->  Index Scan using "order_supplierKeys_idx" on "order" o  (cost=0.43..6.50 rows=1 width=19) (actual time=0.018..0.038 rows=10 loops=1)
              Index Cond: (("supplierB" = s."b") AND ("supplierA" = s."a"))
Planning Time: 1.317 ms
Execution Time: 0.106 ms

Would it be possible to improve performance of the generated SQL in the cases like this?

@0x777
Copy link
Member

0x777 commented Oct 7, 2020

This is interesting, I'm using a similar query

query {
  tracks (order_by: {album: {title:asc}} limit: 10) {
    id
  }
}

As expected, the SQL that is generated is:

explain analyze SELECT
  coalesce(
    json_agg(
      "root"
      ORDER BY
        "root.or.album.pg.title" ASC NULLS LAST
    ),
    '[]'
  ) AS "root"
FROM
  (
    SELECT
      "_2_root.or.album"."root.or.album.pg.title" AS "root.or.album.pg.title",
      row_to_json(
        (
          SELECT
            "_3_e"
          FROM
            (
              SELECT
                "_0_root.base"."id" AS "id"
            ) AS "_3_e"
        )
      ) AS "root"
    FROM
      (
        SELECT
          *
        FROM
          "public"."tracks"
        WHERE
          ('true')
      ) AS "_0_root.base"
      LEFT OUTER JOIN LATERAL (
        SELECT
          "_1_root.or.album.base"."title" AS "root.or.album.pg.title"
        FROM
          (
            SELECT
              *
            FROM
              "public"."albums"
            WHERE
              (("_0_root.base"."album_id") = ("id"))
          ) AS "_1_root.or.album.base"
      ) AS "_2_root.or.album" ON ('true')
    ORDER BY
      "root.or.album.pg.title" ASC NULLS LAST
    LIMIT
      10
  ) AS "_4_root"

when explained gives out a similar plan:

 Aggregate  (cost=219.78..219.79 rows=1 width=32) (actual time=2.757..2.758 rows=1 loops=1)
   ->  Limit  (cost=219.63..219.66 rows=10 width=55) (actual time=2.746..2.747 rows=10 loops=1)
         ->  Sort  (cost=219.63..228.39 rows=3503 width=55) (actual time=2.745..2.746 rows=10 loops=1)
               Sort Key: albums.title
               Sort Method: top-N heapsort  Memory: 26kB
               ->  Hash Left Join  (cost=10.81..143.93 rows=3503 width=55) (actual time=0.085..2.330 rows=3503 loops=1)
                     Hash Cond: (tracks.album_id = albums.id)
                     ->  Seq Scan on tracks  (cost=0.00..80.03 rows=3503 width=8) (actual time=0.003..0.186 rows=3503 loops=1)
                     ->  Hash  (cost=6.47..6.47 rows=347 width=27) (actual time=0.066..0.066 rows=347 loops=1)
                           Buckets: 1024  Batches: 1  Memory Usage: 29kB
                           ->  Seq Scan on albums  (cost=0.00..6.47 rows=347 width=27) (actual time=0.002..0.029 rows=347 loops=1)
                     SubPlan 1
                       ->  Result  (cost=0.00..0.01 rows=1 width=32) (actual time=0.000..0.000 rows=1 loops=3503)
 Planning Time: 0.463 ms
 Execution Time: 2.800 ms

A hand written query (like yours) generates a much better plan:

SELECT
  t.id
FROM
  tracks t
  INNER JOIN albums a ON (t.album_id = a.id)
ORDER BY
  a.title ASC NULLS LAST
LIMIT 10
Limit  (cost=0.55..1.85 rows=10 width=27) (actual time=0.033..0.043 rows=10 loops=1)
  ->  Nested Loop  (cost=0.55..454.05 rows=3503 width=27) (actual time=0.033..0.041 rows=10 loops=1)
        ->  Index Scan using albums_title_idx on albums a  (cost=0.27..33.47 rows=347 width=27) (actual time=0.017..0.018 rows=2 loops=1)
        ->  Index Scan using ifk_track_album_id on tracks t  (cost=0.28..1.11 rows=10 width=8) (actual time=0.008..0.009 rows=5 loops=2)
              Index Cond: (album_id = a.id)
Planning Time: 0.701 ms
Execution Time: 0.082 ms

However the two queries are semantically different - they don't fetch the same data, with INNER JOIN (same as JOIN) the rows that don't have an album are ignored while in LEFT OUTER JOIN (or LEFT JOIN) they will be part of the result set. What happens if we switch to INNER JOIN in the generated SQL query?

explain analyze SELECT
  coalesce(
    json_agg(
      "root"
      ORDER BY
        "root.or.album.pg.title" ASC NULLS LAST
    ),
    '[]'
  ) AS "root"
FROM
  (
    SELECT
      "_2_root.or.album"."root.or.album.pg.title" AS "root.or.album.pg.title",
      row_to_json(
        (
          SELECT
            "_3_e"
          FROM
            (
              SELECT
                "_0_root.base"."id" AS "id"
            ) AS "_3_e"
        )
      ) AS "root"
    FROM
      (
        SELECT
          *
        FROM
          "public"."tracks"
        WHERE
          ('true')
      ) AS "_0_root.base"
      INNER JOIN LATERAL (
        SELECT
          "_1_root.or.album.base"."title" AS "root.or.album.pg.title"
        FROM
          (
            SELECT
              *
            FROM
              "public"."albums"
            WHERE
              (("_0_root.base"."album_id") = ("id"))
          ) AS "_1_root.or.album.base"
      ) AS "_2_root.or.album" ON ('true')
    ORDER BY
      "root.or.album.pg.title" ASC NULLS LAST
    LIMIT 
      10
  ) AS "_4_root"

The explain output is similar to that of the hand-written query

 Aggregate  (cost=2.10..2.11 rows=1 width=32) (actual time=0.101..0.102 rows=1 loops=1)
   ->  Limit  (cost=0.55..1.97 rows=10 width=55) (actual time=0.041..0.061 rows=10 loops=1)
         ->  Nested Loop  (cost=0.55..497.84 rows=3503 width=55) (actual time=0.040..0.059 rows=10 loops=1)
               ->  Index Scan using albums_title_idx on albums  (cost=0.27..33.47 rows=347 width=27) (actual time=0.018..0.018 rows=2 loops=1)
               ->  Index Scan using ifk_track_album_id on tracks  (cost=0.28..1.11 rows=10 width=8) (actual time=0.008..0.010 rows=5 loops=2)
                     Index Cond: (album_id = albums.id)
               SubPlan 1
                 ->  Result  (cost=0.00..0.01 rows=1 width=32) (actual time=0.000..0.000 rows=1 loops=10)
 Planning Time: 0.832 ms
 Execution Time: 0.171 ms

So the question now remains - what should graphql-engine generate when it sees a query such as this:

query {
  tracks (order_by: {album: {title:asc}} limit: 10) {
    id
  }
}

LEFT OUTER JOIN is the correct behaviour, otherwise we would be ignoring rows that haven't been asked to be ignored by the query. Now to the interesting aspect, say album_id column of track table has a NOT NULL constraint along with a FOREGIN KEY constraint to albumss id, these two queries are semantically the same.

SELECT
  t.id
FROM
  tracks t
  INNER JOIN albums a ON (t.album_id = a.id)
ORDER BY
  a.title ASC NULLS LAST
LIMIT 10
SELECT
  t.id
FROM
  tracks t
  LEFT JOIN albums a ON (t.album_id = a.id)
ORDER BY
  a.title ASC NULLS LAST
LIMIT 10

Unfortunately though Postgres's query planner doesn't seem to account for this and as a result we see a sub-optimal plan. Can this be fixed at graphql-engine's layer? Sure, we can generate INNER JOINs instead of LEFT JOINs when the join columns are non nullable with a foreign key constraint. However this I believe is something that should go into Postgres's query optimizer than graphql-engine's.

@0x777 0x777 added c/server Related to server k/enhancement New feature or improve an existing feature labels Oct 7, 2020
@mrkkrp
Copy link
Author

mrkkrp commented Oct 9, 2020

Would it be possible to include it in GraphQL engine? We could try to take a stab at implementing this. The reason for this initiative is that we need the optimization because it blocks certain functionality in a project of ours. At the same time we do not know how hard it would be to include the optimization in Postgres and how long such a change would take.

@0x777
Copy link
Member

0x777 commented Oct 13, 2020

Looks like this is fairly simple to implement in graphql-engine. We already have nullability information attached to each relationship which is something that can be used to switch to an inner join. I have a WIP branch here: https://github.com/0x777/graphql-engine/commit/e57e881d540de0f907e3db819c45acae7c345358. However the generation of nullabilility information of an object relationship can use some improvements - currently we determine the nullability of an object relationship solely based on whether or not is specified through a foreign key constraint.

@mrkkrp
Copy link
Author

mrkkrp commented Oct 22, 2020

@0x777 What should be done to merge the work from that branch into graphql engine? How long could it take?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
a/performance c/server Related to server k/enhancement New feature or improve an existing feature p/high candidate for being included in the upcoming sprint
Projects
None yet
Development

No branches or pull requests

4 participants