search

kadena-io / chainweb-data

Data ingestion for Chainweb.
BSD 3-Clause "New" or "Revised" License
14 stars 8 forks source link

Refactor accountQueryStmt for bounded scans #117

Closed enobayram closed 1 year ago

enobayram commented 1 year ago

This PR refactors accountQueryStmt to decompose it into the parts that define a bounded scan. We'll be pushing another PR to actually convert the accounts endpoint into a bounded scan, but this refactor makes sure that Postgres is able to produce an equivalent query plan for this new shape that's ready to be turned into a bounded scan.

Note that in addition to moving WHERE (guard_) conditions around, this refactor also removes the limit_ clause on the individual branches of the transfers subquery. The reason for the existence of that inner limit_ was that we had initially thought Postgres would end up fetching all the rows on both branches of the UNION ALL and then merge the rows from the two branches, so we wanted to put an upper bound on how many rows it would fetch from those branches. However, it turns out that Postgres is actually much smarter than that: It uses a Merge Append node in the query plan for implementing the UNION ALL and Merge Append walks through the branches in lock step and fetches them and zips them based on the sort order simultaneously, so that means no inner LIMIT clause was necessary (and thankfully so, since that wouldn't be bounded-scan friendly!).

enobayram commented 1 year ago

I've used the following accountQueryStmt invocation to compare the generated queries before and after this PR:

accountQueryStmt 
  (Limit 100) 
  "k:22fbc926b497bf3ecc7199b923039e74cdeda12726e1dc4f443953007cf8cc43" 
  "coin" 
  (Just $ ChainId 0) (AQSContinue 3344678 RKCB_Coinbase 0)

Note that the account k:22fbc926b497bf3ecc7199b923039e74cdeda12726e1dc4f443953007cf8cc43 has 1976018 transfers as of now, so it's a good account for checking that these queries don't end up reading the whole set of transfers of an account.

This invocation results in the following query before this refactor:

EXPLAIN ANALYZE 
(
  SELECT "t0"."res0" AS "res0", "t0"."res1" AS "res1", "t0"."res2" AS "res2", "t0"."res3" AS "res3", "t0"."res4" AS "res4", "t0"."res5" AS "res5", "t0"."res6" AS "res6", "t0"."res7" AS "res7", "t0"."res8" AS "res8", "t0"."res9" AS "res9", "t0"."res10" AS "res10" 
  FROM (
    SELECT "t0"."block" AS "res0", "t0"."requestkey" AS "res1", "t0"."chainid" AS "res2", "t0"."height" AS "res3", "t0"."idx" AS "res4", "t0"."modulename" AS "res5", "t0"."modulehash" AS "res6", "t0"."from_acct" AS "res7", "t0"."to_acct" AS "res8", "t0"."amount" AS "res9", "t1"."creationtime" AS "res10" 
    FROM "transfers" AS "t0" 
    CROSS JOIN "blocks" AS "t1" 
    WHERE ((((("t0"."block") = ("t1"."hash")) 
      AND (("t0"."from_acct") = ('k:22fbc926b497bf3ecc7199b923039e74cdeda12726e1dc4f443953007cf8cc43'))) 
      AND (("t0"."modulename") = ('coin'))) AND (("t0"."chainid") = (0))) 
      AND ((("t0"."height", "t0"."requestkey", -("t0"."idx"))) < ((3344678, 'cb', -(0)))) 
    ORDER BY "t0"."height" DESC, "t0"."requestkey" DESC, "t0"."idx" ASC 
    LIMIT 100
  ) AS "t0"
) 
UNION ALL 
(
  SELECT "t0"."res0" AS "res0", "t0"."res1" AS "res1", "t0"."res2" AS "res2", "t0"."res3" AS "res3", "t0"."res4" AS "res4", "t0"."res5" AS "res5", "t0"."res6" AS "res6", "t0"."res7" AS "res7", "t0"."res8" AS "res8", "t0"."res9" AS "res9", "t0"."res10" AS "res10" 
  FROM (
    SELECT "t0"."block" AS "res0", "t0"."requestkey" AS "res1", "t0"."chainid" AS "res2", "t0"."height" AS "res3", "t0"."idx" AS "res4", "t0"."modulename" AS "res5", "t0"."modulehash" AS "res6", "t0"."from_acct" AS "res7", "t0"."to_acct" AS "res8", "t0"."amount" AS "res9", "t1"."creationtime" AS "res10" 
    FROM "transfers" AS "t0" 
    CROSS JOIN "blocks" AS "t1" 
    WHERE ((((("t0"."block") = ("t1"."hash")) 
      AND (("t0"."to_acct") = ('k:22fbc926b497bf3ecc7199b923039e74cdeda12726e1dc4f443953007cf8cc43'))) 
      AND (("t0"."modulename") = ('coin'))) 
      AND (("t0"."chainid") = (0))) 
      AND ((("t0"."height", "t0"."requestkey", -("t0"."idx"))) < ((3344678, 'cb', -(0)))) 
    ORDER BY "t0"."height" DESC, "t0"."requestkey" DESC, "t0"."idx" ASC 
    LIMIT 100
  ) AS "t0"
) 
ORDER BY "res3" DESC, "res1" DESC, "res4" ASC 
LIMIT 100 
OFFSET 0;
                                                                                          QUERY PLAN                                                                                          
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=79.44..2258.75 rows=100 width=229) (actual time=0.967..1.594 rows=100 loops=1)
   ->  Merge Append  (cost=79.44..4438.05 rows=200 width=229) (actual time=0.966..1.586 rows=100 loops=1)
         Sort Key: t0.height DESC, t0.requestkey DESC, t0.idx
         ->  Limit  (cost=23.70..2278.56 rows=100 width=229) (actual time=0.462..0.463 rows=1 loops=1)
               ->  Incremental Sort  (cost=23.70..9629.42 rows=426 width=229) (actual time=0.462..0.462 rows=1 loops=1)
                     Sort Key: t0.height DESC, t0.requestkey DESC, t0.idx
                     Presorted Key: t0.height
                     Full-sort Groups: 1  Sort Method: quicksort  Average Memory: 42kB  Peak Memory: 42kB
                     ->  Nested Loop  (cost=1.13..9610.25 rows=426 width=229) (actual time=0.051..0.428 rows=34 loops=1)
                           ->  Index Scan using transfers_from_acct_height_idx on transfers t0  (cost=0.56..5954.11 rows=426 width=221) (actual time=0.040..0.179 rows=34 loops=1)
                                 Index Cond: (((from_acct)::text = 'k:22fbc926b497bf3ecc7199b923039e74cdeda12726e1dc4f443953007cf8cc43'::text) AND (height <= 3344678))
                                 Filter: (((modulename)::text = 'coin'::text) AND (chainid = 0) AND (ROW(height, (requestkey)::text, (- idx)) < ROW(3344678, 'cb'::text, 0)))
                                 Rows Removed by Filter: 232
                           ->  Index Scan using blocks_pkey on blocks t1  (cost=0.56..8.58 rows=1 width=52) (actual time=0.007..0.007 rows=1 loops=34)
                                 Index Cond: ((hash)::text = (t0.block)::text)
         ->  Limit  (cost=55.74..2155.48 rows=100 width=229) (actual time=0.503..1.110 rows=100 loops=1)
               ->  Incremental Sort  (cost=55.74..9632431.55 rows=458740 width=229) (actual time=0.503..1.103 rows=100 loops=1)
                     Sort Key: t0_1.height DESC, t0_1.requestkey DESC, t0_1.idx
                     Presorted Key: t0_1.height
                     Full-sort Groups: 2  Sort Method: quicksort  Average Memory: 58kB  Peak Memory: 58kB
                     Pre-sorted Groups: 2  Sort Method: quicksort  Average Memory: 36kB  Peak Memory: 36kB
                     ->  Nested Loop  (cost=1.13..9615837.90 rows=458740 width=229) (actual time=0.049..0.920 rows=138 loops=1)
                           ->  Index Scan using transfers_to_acct_height_idx_idx on transfers t0_1  (cost=0.56..5979265.85 rows=458740 width=221) (actual time=0.038..0.156 rows=138 loops=1)
                                 Index Cond: (((to_acct)::text = 'k:22fbc926b497bf3ecc7199b923039e74cdeda12726e1dc4f443953007cf8cc43'::text) AND (height <= 3344678))
                                 Filter: (((modulename)::text = 'coin'::text) AND (chainid = 0) AND (ROW(height, (requestkey)::text, (- idx)) < ROW(3344678, 'cb'::text, 0)))
                                 Rows Removed by Filter: 175
                           ->  Index Scan using blocks_pkey on blocks t1_1  (cost=0.56..7.93 rows=1 width=52) (actual time=0.005..0.005 rows=1 loops=138)
                                 Index Cond: ((hash)::text = (t0_1.block)::text)
 Planning Time: 0.624 ms
 Execution Time: 1.639 ms
(30 rows)

And after the refactor:

EXPLAIN ANALYZE 
SELECT "t0"."res0" AS "res0", "t0"."res1" AS "res1", "t0"."res2" AS "res2", "t0"."res3" AS "res3", "t0"."res4" AS "res4", "t0"."res5" AS "res5", "t0"."res6" AS "res6", "t0"."res7" AS "res7", "t0"."res8" AS "res8", "t0"."res9" AS "res9", "t1"."creationtime" AS "res10" 
FROM (
  (
    SELECT "t0"."res0" AS "res0", "t0"."res1" AS "res1", "t0"."res2" AS "res2", "t0"."res3" AS "res3", "t0"."res4" AS "res4", "t0"."res5" AS "res5", "t0"."res6" AS "res6", "t0"."res7" AS "res7", "t0"."res8" AS "res8", "t0"."res9" AS "res9" 
    FROM (
      SELECT "t0"."block" AS "res0", "t0"."requestkey" AS "res1", "t0"."chainid" AS "res2", "t0"."height" AS "res3", "t0"."idx" AS "res4", "t0"."modulename" AS "res5", "t0"."modulehash" AS "res6", "t0"."from_acct" AS "res7", "t0"."to_acct" AS "res8", "t0"."amount" AS "res9" 
      FROM "transfers" AS "t0" 
      WHERE ("t0"."from_acct") = ('k:22fbc926b497bf3ecc7199b923039e74cdeda12726e1dc4f443953007cf8cc43') 
      ORDER BY "t0"."height" DESC, "t0"."requestkey" DESC, "t0"."idx" ASC
    ) AS "t0"
  ) 
  UNION ALL 
  (
    SELECT "t0"."res0" AS "res0", "t0"."res1" AS "res1", "t0"."res2" AS "res2", "t0"."res3" AS "res3", "t0"."res4" AS "res4", "t0"."res5" AS "res5", "t0"."res6" AS "res6", "t0"."res7" AS "res7", "t0"."res8" AS "res8", "t0"."res9" AS "res9" 
    FROM (
      SELECT "t0"."block" AS "res0", "t0"."requestkey" AS "res1", "t0"."chainid" AS "res2", "t0"."height" AS "res3", "t0"."idx" AS "res4", "t0"."modulename" AS "res5", "t0"."modulehash" AS "res6", "t0"."from_acct" AS "res7", "t0"."to_acct" AS "res8", "t0"."amount" AS "res9" 
      FROM "transfers" AS "t0" 
      WHERE ("t0"."to_acct") = ('k:22fbc926b497bf3ecc7199b923039e74cdeda12726e1dc4f443953007cf8cc43') 
      ORDER BY "t0"."height" DESC, "t0"."requestkey" DESC, "t0"."idx" ASC
    ) AS "t0"
  )
) AS "t0" 
CROSS JOIN "blocks" AS "t1" 
WHERE ((((("t0"."res3", "t0"."res1", -("t0"."res4"))) < ((3344678, 'cb', -(0)))) 
  AND (("t0"."res5") = ('coin'))) AND (("t0"."res2") = (0))) 
  AND (("t0"."res0") = ("t1"."hash")) 
ORDER BY "t0"."res3" DESC, "t0"."res1" DESC, "t0"."res4" ASC 
LIMIT 100 
OFFSET 0;
                                                                                       QUERY PLAN                                                                                       
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=43.13..2097.42 rows=100 width=229) (actual time=0.688..1.639 rows=100 loops=1)
   ->  Nested Loop  (cost=43.13..7861955.25 rows=382708 width=229) (actual time=0.686..1.629 rows=100 loops=1)
         ->  Merge Append  (cost=42.57..4859339.84 rows=382708 width=221) (actual time=0.656..0.970 rows=100 loops=1)
               Sort Key: t0_1.height DESC, t0_1.requestkey DESC, t0_1.idx
               ->  Incremental Sort  (cost=14.55..5973.28 rows=426 width=221) (actual time=0.413..0.414 rows=1 loops=1)
                     Sort Key: t0_1.height DESC, t0_1.requestkey DESC, t0_1.idx
                     Presorted Key: t0_1.height
                     Full-sort Groups: 1  Sort Method: quicksort  Average Memory: 42kB  Peak Memory: 42kB
                     ->  Index Scan using transfers_from_acct_height_idx on transfers t0_1  (cost=0.56..5954.11 rows=426 width=221) (actual time=0.096..0.377 rows=34 loops=1)
                           Index Cond: (((from_acct)::text = 'k:22fbc926b497bf3ecc7199b923039e74cdeda12726e1dc4f443953007cf8cc43'::text) AND (height <= 3344678))
                           Filter: (((modulename)::text = 'coin'::text) AND (chainid = 0) AND (ROW(height, (requestkey)::text, (- idx)) < ROW(3344678, 'cb'::text, 0)))
                           Rows Removed by Filter: 232
               ->  Incremental Sort  (cost=28.01..4845712.39 rows=458739 width=221) (actual time=0.241..0.538 rows=100 loops=1)
                     Sort Key: t0_2.height DESC, t0_2.requestkey DESC, t0_2.idx
                     Presorted Key: t0_2.height
                     Full-sort Groups: 2  Sort Method: quicksort  Average Memory: 58kB  Peak Memory: 58kB
                     Pre-sorted Groups: 2  Sort Method: quicksort  Average Memory: 36kB  Peak Memory: 36kB
                     ->  Index Scan using transfers_to_acct_height_idx_idx on transfers t0_2  (cost=0.56..4829118.78 rows=458739 width=221) (actual time=0.073..0.292 rows=138 loops=1)
                           Index Cond: (((to_acct)::text = 'k:22fbc926b497bf3ecc7199b923039e74cdeda12726e1dc4f443953007cf8cc43'::text) AND (height <= 3344678))
                           Filter: (((modulename)::text = 'coin'::text) AND (chainid = 0) AND (ROW(height, (requestkey)::text, (- idx)) < ROW(3344678, 'cb'::text, 0)))
                           Rows Removed by Filter: 175
         ->  Index Scan using blocks_pkey on blocks t1  (cost=0.56..7.85 rows=1 width=52) (actual time=0.006..0.006 rows=1 loops=100)
               Index Cond: ((hash)::text = (t0_1.block)::text)
 Planning Time: 0.591 ms
 Execution Time: 1.724 ms
(25 rows)

The query plans are almost the same except for the join on the blocks table moving outside the inner query that finds the relevant transfers rows.