search

kadena-io / chainweb-data

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

Missing information about indexes required for indexer's endpoints #79

Open blazesal opened 2 years ago

blazesal commented 2 years ago

Indexer performance problems

Investigation

Naming

In the description below following names are being used for:

Increase debug query size

Increase the query size, so it is possible to display large queries:

sudo -u postgres psql chainweb-data
ALTER SYSTEM SET track_activity_query_size = 16384;
quit
systemctl restart postgresql

Intercept long-running query

Invoke the indexer's endpoint, which fails to return the data quickly:

curl http://localhost:8080/txs/search?limit=200&search=k:5adb16663073280acf63bc2a4bf477ad1391736dcd6217b094926862c72d15c9

Connect to the database and display the running SQL queries:

sudo -u db_user psql -d chainweb-data -U db_user -W
SELECT pid, age(clock_timestamp(), query_start), usename, query FROM pg_stat_activity WHERE query != '<IDLE>' AND query NOT ILIKE '%pg_stat_activity%' ORDER BY query_start desc;

Then analyze the query:

explain analyze SELECT "t0"."chainid" AS "res0", "t1"."height" AS "res1", "t0"."block" AS "res2", "t0"."creationtime" AS "res3", "t0"."requestkey" AS "res4", "t0"."sender" AS "res5", "t0"."code" AS "res6", "t0"."continuation" AS "res7", "t0"."goodresult" AS "res8" FROM "transactions" AS "t0" CROSS JOIN "blocks" AS "t1" WHERE (("t0"."block") = ("t1"."hash")) AND (("t0"."code") LIKE ('%k:5adb16663073280acf63bc2a4bf477ad1391736dcd6217b094926862c72d15c9%')) ORDER BY "t1"."height" DESC LIMIT 100 OFFSET 0

Analysis gives the following query plan:

"QUERY PLAN"
"Limit  (cost=556941.22..556952.89 rows=100 width=1064) (actual time=2328.803..2336.257 rows=81 loops=1)"
"  ->  Gather Merge  (cost=556941.22..556990.92 rows=426 width=1064) (actual time=2105.215..2112.657 rows=81 loops=1)"
"        Workers Planned: 2"
"        Workers Launched: 2"
"        ->  Sort  (cost=555941.20..555941.73 rows=213 width=1064) (actual time=2093.093..2093.099 rows=27 loops=3)"
"              Sort Key: t1.height DESC"
"              Sort Method: quicksort  Memory: 64kB"
"              Worker 0:  Sort Method: quicksort  Memory: 55kB"
"              Worker 1:  Sort Method: quicksort  Memory: 52kB"
"              ->  Nested Loop  (cost=0.56..555933.06 rows=213 width=1064) (actual time=521.487..2093.012 rows=27 loops=3)"
"                    ->  Parallel Seq Scan on transactions t0  (cost=0.00..554104.98 rows=213 width=1056) (actual time=521.416..2078.174 rows=27 loops=3)"
"                          Filter: ((code)::text ~~ '%k:5adb16663073280acf63bc2a4bf477ad1391736dcd6217b094926862c72d15c9%'::text)"
"                          Rows Removed by Filter: 1824218"
"                    ->  Index Scan using blocks_pkey on blocks t1  (cost=0.56..8.58 rows=1 width=52) (actual time=0.546..0.546 rows=1 loops=81)"
"                          Index Cond: ((hash)::text = (t0.block)::text)"
"Planning Time: 9.838 ms"
"JIT:"
"  Functions: 26"
"  Options: Inlining true, Optimization true, Expressions true, Deforming true"
"  Timing: Generation 3.805 ms, Inlining 210.140 ms, Optimization 366.445 ms, Emission 201.074 ms, Total 781.465 ms"
"Execution Time: 2348.104 ms"

The line -> Parallel Seq Scan on transactions t0 (cost=0.00..554104.98 rows=213 width=1056) (actual time=521.416..2078.174 rows=27 loops=3)" indicates that the whole table needs to get sequentially scanned (Seq Scan) because of the lack of appropriate index on the code column. After adding the necessary index the query plan is the following:

"QUERY PLAN"
"Limit  (cost=7239.73..7239.98 rows=100 width=1064) (actual time=145.033..145.048 rows=81 loops=1)"
"  ->  Sort  (cost=7239.73..7241.01 rows=511 width=1064) (actual time=145.032..145.040 rows=81 loops=1)"
"        Sort Key: t1.height DESC"
"        Sort Method: quicksort  Memory: 123kB"
"        ->  Nested Loop  (cost=832.52..7220.20 rows=511 width=1064) (actual time=121.291..144.978 rows=81 loops=1)"
"              ->  Bitmap Heap Scan on transactions t0  (cost=831.96..2834.55 rows=511 width=1056) (actual time=121.263..144.195 rows=81 loops=1)"
"                    Recheck Cond: ((code)::text ~~ '%k:5adb16663073280acf63bc2a4bf477ad1391736dcd6217b094926862c72d15c9%'::text)"
"                    Rows Removed by Index Recheck: 376"
"                    Heap Blocks: exact=405"
"                    ->  Bitmap Index Scan on ""transactions-code""  (cost=0.00..831.83 rows=511 width=0) (actual time=113.783..113.783 rows=457 loops=1)"
"                          Index Cond: ((code)::text ~~ '%k:5adb16663073280acf63bc2a4bf477ad1391736dcd6217b094926862c72d15c9%'::text)"
"              ->  Index Scan using blocks_pkey on blocks t1  (cost=0.56..8.58 rows=1 width=52) (actual time=0.009..0.009 rows=1 loops=81)"
"                    Index Cond: ((hash)::text = (t0.block)::text)"
"Planning Time: 0.405 ms"
"Execution Time: 145.100 ms"

The Seq Scan is now gone in favour of scanning the index Bitmap Index Scan on ""transactions-code"".

Solution

The discussion about the right index supporting generic LIKE queries is here: https://stackoverflow.com/questions/1566717/postgresql-like-query-performance-variations In summary, the use of GIN or GiST trigram index with the special operator classes provided by the additional module pg_trgm is the solution.

Install additional Postgres module

To install the needed module, log into database with super-user: 

sudo -u postgres psql chainweb-data
create extension pg_trgm;
quit

Identify missing indexes

The analysis of the queries resulted in the following list of the indexes that need to get created:

Indexer endpoint Table Column Index
/txs/tx?requestkey=[...] transactions requestkey btree
/txs/tx?requestkey=[...] events requestkey btree
/txs/search?search=[...] transactions code gin_trgm_ops
/txs/events?search=[...] events qualname gin_trgm_ops
/txs/events?search=[...] events paramtext gin_trgm_ops

Create appropriate indexes

The commands to create the above indexes:

sudo -u db_user psql -d chainweb-data -U db_user -W

CREATE INDEX "transactions-requestkey" ON public.transactions USING btree (requestkey);
CREATE INDEX "events-requestkey" ON public.events USING btree (requestkey);

CREATE INDEX "transactions-code" ON public.transactions USING gin (code gin_trgm_ops);
CREATE INDEX "events-qualname" ON public.events USING gin (qualname gin_trgm_ops);
CREATE INDEX "events-paramtext" ON public.events USING gin (paramtext gin_trgm_ops);

quit

Should this section get included in the README?


** Performance
Some endpoints require the creation of additional indexes in order to work efficiently:

| Indexer endpoint         | Table        | Column     | Index          |
|--------------------------+--------------+------------+----------------|
| /txs/tx?requestkey=[...] | transactions | requestkey | `btree`        |
| /txs/tx?requestkey=[...] | events | requestkey | `btree`        |
| /txs/search?search=[...] | transactions | code       | `gin_trgm_ops` |
| /txs/events?search=[...] | events       | qualname   | `gin_trgm_ops` |
| /txs/events?search=[...] | events       | paramtext  | `gin_trgm_ops` |

The use of GIN or GiST trigram index with the special operator classes provided
by the additional Postgresql module `pg_trgm` is the solution.

*** Install additional Postgres module
To install the needed module, log into database with super-user:
#+begin_example
sudo -u postgres psql chainweb-data
create extension pg_trgm;
quit
#+end_example

*** Create appropriate indexes
The commands to create the above indexes:
#+begin_example
sudo -u db_user psql -d chainweb-data-db -U db_user -W

CREATE INDEX "transactions-requestkey" ON public.transactions USING btree (requestkey);

CREATE INDEX "transactions-code" ON public.transactions USING gin (code gin_trgm_ops);
CREATE INDEX "events-qualname" ON public.events USING gin (qualname gin_trgm_ops);
CREATE INDEX "events-paramtext" ON public.events USING gin (paramtext gin_trgm_ops);

quit
#+end_example
mightybyte commented 2 years ago

Thanks for the in-depth analysis! We do have some code for setting up indexes. I think we can add these there.

blazesal commented 2 years ago

There are two remarks.

  1. Those indexes may be created after the initial data ingestion, if that can speed up the process. Did you resign from the --disable-indexes option?
  2. The index of type gin_trgm_ops requires the admin to install additional Posgres module. Only then the index may get created by the application. Should you create a README entry about it and create a second migration command -m2?
mightybyte commented 2 years ago

How does the gin_trgm_ops index impact the results that are matched? The current behavior of exactly matching arbitrary substrings is pretty useful for code search. Is this index strictly a performance improvement with no change to search results or will it impact the results returned?

blazesal commented 2 years ago

Adding an index or changing its type should not change the semantics of a SQL query. Standard indexes support fast searching of open-ended patterns LIKE 'abde%'. In the transaction search endpoint, the column code is being searched for the pattern LIKE '%abdce%', hence another type of index is required that supports it in an efficient manner. I executed the endpoint with and without the index to compare execution times and the results:

http://{{indexer}}:8080/txs/search?limit=200&search=k:5adb16663073280acf63bc2a4bf477ad1391736dcd6217b094926862c72d15c9

Without the index endpoint takes around 60 second to complete. With the index it takes about 3-6 seconds. The query sorts the transactions by the block height, but within a single height the transactions may be (and are) in a different order.

Transctions for block height 2210429 - query results with no index:

Zj0meNG6rZKUqvGxZxMjW-bUEbQBIX-duRPDpuEOvKs
o9GzLWNqji5gndkLOP44wy3V_pTnq6HZZbaDmR-BXOQ
l0STasLY3eh_7n4xzinSfqSdEAi7RItsm_xa_2eUOm4
tTVAzxG6Z_OR8x7WqsM1lPnNhNc2odMCAX3uTbEGoLc
7oGhKqC7lVfpM0-8vfGNRXp3L1F5F7x0qI93NFT4zRo
Wox2ao4bCtFT-W2E17sA0Nh6JmHCN0y-KWQPYMMuiqw
2c00Kr23LYNUV7ldLovYJzrDqAFTpL8SeSxTXd-OjNE

Transctions for block height 2210429 - query results with the gin_trgm_ops index:

2c00Kr23LYNUV7ldLovYJzrDqAFTpL8SeSxTXd-OjNE
7oGhKqC7lVfpM0-8vfGNRXp3L1F5F7x0qI93NFT4zRo
o9GzLWNqji5gndkLOP44wy3V_pTnq6HZZbaDmR-BXOQ
l0STasLY3eh_7n4xzinSfqSdEAi7RItsm_xa_2eUOm4
Zj0meNG6rZKUqvGxZxMjW-bUEbQBIX-duRPDpuEOvKs
tTVAzxG6Z_OR8x7WqsM1lPnNhNc2odMCAX3uTbEGoLc
Wox2ao4bCtFT-W2E17sA0Nh6JmHCN0y-KWQPYMMuiqw

That difference between results is acceptable because the query execution with an index may deliver results in different order than no index query execution and there is no additional constrain on the results order. I recommend you execute the queries in those two variants on your end and confirm my findings.

enobayram commented 2 years ago

Hi @blazesal, thank you very much for opening this ticket with valuable analyses, insights and recommendations. I wanted to let you know that this is something we've been discussing internally. As you've suggested the GIN index is a very big aid to the query planner for running a search query like the one you're focusing on here. But unfortunately, that index can hurt as much as it helps for search queries with different characteristics. Let me expand;

Consider the long-running query you've identified in your issue description. In particular the ORDER BY "t1"."height" DESC clause. For your query, that ORDER BY clause doesn't hurt, because the term you're searching for results in a tiny number of rows to be selected before ordering. Then Postgres can easily sort those rows by height.

However, imagine the opposite case of a search query that will pick millions of rows. Like "give me any transaction that has "transfer" in it". Currently, such a query runs fast, because the query planner will just walk backwards over the height index of the transactions table and it will quickly find, say 100 transactions (for a request with limit = 100) that contain the string transfer and return them. Now, if we add the GIN index you're suggesting here, the query planner will instead walk over that GIN index and find all the transactions that contain "transfer" (millions) and then it will sort them to find the first 100 by height, which will probably have an even worse run time since scanning a GIN index is slower than scanning the table.

Just wanted to let you know that this problem with the opposite case is what held us back from applying your insightful suggestion right away.

enobayram commented 1 year ago

@blazesal Note that the requestkey indexes you've suggested in your comment above have become a part of the indexes chainweb-data creates by default with #98. Thanks again for pointing them out.