Small Datum

Tuesday, December 29, 2020

Sysbench: MyRocks in MySQL 5.6 vs 8.0

I revived my sysbench helper scripts and have started to get results for MySQL (InnoDB, MyRocks) and Postgres. The results here are from all_small.sh which uses a few Lua files that are in my sysbench fork but have yet to be contributed. Tests were run on my home NUC servers for in-memory and IO-bound workloads. The results here are limited to the in-memory workloads.

Disclaimer -- the tests here are microbenchmarks. While useful, be careful about assuming that the regressions here will reproduce on your workloads. The in-memory tests help me understand CPU overhead which tends to increase in newer releases.

Summary:

In most cases, MyRocks in 8.0.17 achieves between 75% and 100% of the throughput that it gets in 5.6.35. The regression tended to be larger for write-heavy tests than for read-only.
Many of the regressions are explained by new CPU overhead. But there is also variance that is likely caused by stalls from RocksDB and my scripts don't do a good job of showing that.
I don't understand why MyRocks was reading from storage for some of the tests. That doesn't reproduce with InnoDB and the database should have been cached.
There was one lousy, but still unexplained result -- a test that does point queries via a secondary index was much slower in 8.0.17. It got between 41% and 54% of the 5.6.35 throughput (search for 0.41 below). The problem occurs when the test is run after write-heavy tests. It does not occur when the test is run before the write-heavy tests. I need to debug this live but my test servers are busy.

Overview

The all_small.sh script run a variety of tests in a sequence that is interesting to me. One example is to run the read-only tests before and then after write-heavy tests to understand the impact of fragmentation on query performance. The tests include the traditional result from oltp_read_write.lua, and results from other Lua scripts focused on a single command (point lookup, range query, etc). These are microbenchmarks and the purpose is to spot regressions between releases. MySQL 8 has many improvements and a few regressions (like bug 102037, found via these scripts).

For the in-memory workload there is 1 table with 10M rows and each test is run for 90 seconds. For the IO-bound setup there is 1 table with 200M rows and each test is run for 300 seconds. In both cases tests are repeated for 1, 2, 3 and 4 threads. The test servers have 4 CPU cores with HT disabled. The in-memory table is small enough to fit in RAM, the IO-bound table is not.

Tests used FB MySQL 5.6.35 at git hash 4911e0 and 8.0.17 at git hash cf9dbc. These were latest as of early December 2020. The NUC servers use Ubuntu 20.04 and XFS.

Results

I pushed results to github with:

Result directories for in-memory and IO-bound workloads
Summaries with results for 1, 2, 3 and 4 threads

Absolute QPS by thread count in-memory and IO-bound workloads
Relative QPS by thread count for in-memory and IO-bound workloads. The results are relative to MyRocks in 5.6.35 (> 1.0 is an improvement, < 1.0 is a regression)
Metrics (CPU and IO per operation) for in-memory and IO-bound

my.cnf for 5.6 and 8.0 are as similar as possible. Fsync is not done on commit to keep this from being an fsync benchmark. Compression was not used.
Sysbench output and test scripts. The run.sh script maps the test names that are in the result summaries to the Lua scripts and per-script options.

In-memory

The tests are in 4 groups based on the sequence in which they are run: read-only run before write-heavy, write-heavy, read-only run after write-heavy and insert/delete.

The summaries focus on relative throughput and HW efficiency for the test with 1 thread. The results for more than 1 thread are similar although at 4 threads there were some tests with larger regressions for 8.0 and the likely cause was CPU saturation.

I use ratios to explain performance. In this case MyRocks in 5.6.35 is the denominator and 8.0.17 is the numerator. A QPS ratio < 1 means that 8.0.17 is slower. A HW efficiency metric, CPU/query, ratio > 1 means that 8.0.17 uses more CPU/query. I use CPU/query because it is correlated with QPS, the CPU/query overhead usually increases in new MySQL releases and that causes a reduction in QPS for low-concurrency workloads, especially when the database is cached and queries are simple.

Read-only before write-heavy:

QPS ratios are 0.89, 0.89, 0.90, 0.89 for the first 4 tests (up to here)

These do point queries
CPU/query ratios are: 1.15, 1.14, 1.12, 1.13. See here to here

QPS ratios are 0.94, 1.00, 1.12 for the next 3 tests (here to here)

These have the range scans from oltp_read_write.lua with ranges of size 10, 100 & 10,000
CPU/query ratios are 1.09, 1.03, 0.92. Long scans are better in 8.0.17 while shorter ones are better in 5.6.35. See here to here.

QPS ratios are 0.91, 0.89 for the next 2 tests (here to here)

These do point queries via in-lists that are covering and then not covering for the primary index.
CPU/query ratios are 1.12, 1.15 (here to here)

QPS ratios are 0.82, 0.84 for the next 2 tests (here to here)

These are similar to the previous test, but use the secondary index. The regression in 8.0.17 is larger here than for the tests that use the PK index and CPU/query is the problem.
CPU/query ratios are 1.23, 1.23 (here to here)

QPS ratios are 0.95, 0.96 for the next 2 tests (here to here)

These do range queries that are covering and then not covering for the primary index
CPU/query ratios are 1.09, 1.04 (here to here)

QPS ratios are 0.98, 0.94 for the next 2 tests (here to here)

These are similar to the previous test, but use the secondary index.
CPU/query ratios are 1.04, 1.07 (here to here)

Write-heavy - many of these tests have more read IO than I expected given.

QPS ratios are 0.80, 0.84, 0.81, 0.77, 0.72 for the next 5 tests (here to here)

These are update-only
CPU/statement ratios are 1.40, 1.23, 1.39, 1.37, 1.38 (here to here).
IO/operation ratios are worse for 8.0.17. I don't understand why there are so many reads as the database should be cached. The update-zipf tests were the worst for IO and the IO problem occurs for both 5.6 and 8.0. I assume the problem is that new compaction output isn't in the OS page cache.

QPS ratio is 0.92 for the next test, write-only. See here.

This has the writes from oltp_read_write.lua.
CPU/transaction ratio is 1.17. See here. Read/write IO is also worse.

QPS ratios are 1.01, 0.98 for the next two tests, read-write (here to here)

These are the traditional sysbench tests (oltp_read_write.lua) with ranges of size 10 and 100
CPU/transaction ratios are 1.05, 1.06 (here to here)
IO/operation results confuse me as the test table should be cached (here to here)

Read-only after write-heavy includes tests that were run before write-heavy:

QPS ratio is 0.98, 0.94, 0.98 for the next 3 tests, read-only (here to here)

These have the range scans from oltp_read_write.lua with ranges of size 10, 100 and 10,000. These were also run before write-heavy, results here are slightly worse.
CPU/transaction ratios are 1.06, 1.09, 1.04 (here to here)

QPS ratios are 0.90, 0.88. 0.85, 0.85, 0.81 for the next 5 tests (here to here)

These do a variety of point queries. The first 4 were run in Read-only before write heavy, and results here are similar.
CPU/query ratios are 1.14, 1.15, 1.18, 1.18, 1.25 (here to here)

QPS ratios are 0.89, 0.87 for the next 2 tests (here to here)

These do point queries via in-lists that are covering and then not covering for the primary index. These were also run before write-heavy. Results here are slightly worse.
CPU/query ratios are 1.14, 1.16 (here to here)

QPS ratios are 0.41, 0.54 for the next 2 tests (here to here)

These are similar to the previous test, but use the secondary index. These were also run before write-heavy. The results here show a serious regression for 8.0.17.
CPU/query ratios are 2.26, 1.90 (here to here). This starts to explain the problem but I need stack traces and/or CPU profiles to really explain it.

QPS ratios are 0.74, 0.76 for the next 2 tests (here to here)

These do range queries that are covering and then not covering for the primary index
These were also run before write-heavy.
CPU/query ratios are 1.31, 1.27 (here to here)

QPS ratios are 0.80, 0.74 for the next 2 tests (here to here)

These are similar to the previous test, but use the secondary index. These were also run before write-heavy.
CPU/query ratios are 1.25, 1.25 (here to here)

Insert/delete

QPS ratio is 0.78 for the delete test and 0.72 for the insert test
CPU/statement ratio is 1.27 for delete and 1.49 for insert

Friday, December 4, 2020

Tuning for the Insert Benchmark: Postgres, InnoDB & MyRocks

I used the Insert Benchmark and a small server to compare performance across many (11, 18 & 17) different configurations for Postgres, InnoDB and MyRocks. The goal is to determine which options matter for this scenario (workload + HW). The goal isn't to compare Postgres vs InnoDB vs MyRocks.

Results are here for Postgres, InnoDB and MyRocks. Conclusions are below. Some of these are specific to the workload + HW, so be careful about applying my findings.

For InnoDB

It is hard to improve on innodb_dedicated_server. This is great news for deployments as there is less to tune. I hope the perf test community does more to confirm that across more workloads and HW.
Performance with the minimal (default + a few things) configuration is lousy. The solution is to set innodb_dedicated_server.
Performance with 4kb and 8kb pages is lousy except for QPS with more IO-bound database size where it is better. I don't understand the CPU overhead when it is lousy.
QPS with the more IO-bound database is much worse than MyRocks and Postgres. I don't know why.

For MyRocks

For the in-memory and less IO-bound databases the configurations didn't matter as perf was good for all. For the more IO-bound database all configurations except the minimal were good.
Tuning MyRocks was easy

For Postgres

Vacuum is needed, even for insert-only workloads, to set visibility map bits
wal_compression=on was bad for perf in many cases. Is PGLZ overhead too large?
Using a larger WAL helps by reducing checkpoint IO. This is standard advice.

A next step is to repeat the experiment with bigger HW and/or more concurrency. I want to try running iibench.py with PyPy and probably should upgrade the Python connector for MySQL.

Tuning for the Insert Benchmark: MyRocks

This presents performance and efficiency results for MyRocks on the Insert Benchmark using MySQL 5.6.35 and a small server with 4 CPU cores, 16G of RAM and a fast SSD. The goal is to understand the impact of my.cnf options and I have results for 17 different configurations.

Summary

I use scripts to generate the performance reports. The reports are here for the in-memory, less IO-bound and more IO-bound database sizes. My summary of the results is below. Some of the conclusions are specific to this workload and HW so be careful about applying this advice.

A summary of the results is below. This one is easy.

Configurations have little impact on throughput for the in-memory and less IO-bound databases
Throughput is lousy with the minimal configuration for the more IO-bound database size

My focus in on throughput. There are larger impacts on HW efficiency metrics that I ignore. The impact of configuration should be more interesting for the benchmark run on larger HW with more concurrency, but that is for a future post.

Tests

The insert benchmark was run for three database sizes that I call in-memory, less IO-bound and more IO-bound. The database was cached in memory for the in-memory size but not for the others. The initial load size was 20M rows for in-memory, 100M rows for less IO-bound and 500M rows for more IO-bound. Additional rows were inserted after the initial load, but most of the inserts were done by the initial load.

Tests were run at most 2 threads/connections -- one for inserts and another for queries -- and I consider that to be 1 insert benchmark client.

The benchmark has several steps as described here -- initial load, create 3 secondary indexes, load more data, read+write. Each read+write step is run for 30 minutes with a query thread that runs as fast as possible and a writer that that is rate limited to 100, 100, 200, 200, 400, 400, 600, 600, 800, 800, 1000 and 1000 inserts/s. The load more data step inserts 20M, 10M and 10M more rows for the in-memory, less IO-bound and more IO-bound workloads.

In the performance reports, the steps are named:

l.i0 - initial load
l.x - create 3 secondary indexes
l.i1 - load more data
q100.2, q200.2, ..., q1000.2 - read+write where the insert rate limit is 100, 200, ..., 1000 and the .2 means the second run at each rate. The reports focus on the second run.

Configurations

All tests were done with fsync-on-commit disabled to avoid becoming an fsync latency benchmark. The option names below leave off rocksdb_ to save space. I also leave off my.cnf. when naming config files.

my.cnf.cx0 - minimal configuration
my.cnf.cx1 - cx0 + block_cache_size=10G
my.cnf.cx3 - cx1 +

max_background_jobs=2, default_cf_options=level_compaction_dynamic_level_bytes=true

my.cnf.cx4a - cx3 +

default_cf_options += block_based_table_factory= {cache_index_and_filter_blocks=1}

my.cnf.cx4b - cx3 +

default_cf_options += block_based_table_factory= {cache_index_and_filter_blocks=1; filter_policy=bloomfilter:10: false; whole_key_filtering=1}; optimize_filters_for_hits=true

my.cnf.cx5a - cx4b +

default_cf_options += max_write_buffer_number=4; write_buffer_size=64m; max_bytes_for_level_base=256m

my.cnf.cx5b - cx4b +

default_cf_options += max_write_buffer_number=4; write_buffer_size=128m; max_bytes_for_level_base=512m

my.cnf.cx5c - cx4b +

default_cf_options += max_write_buffer_number=4; write_buffer_size=256m; max_bytes_for_level_base=1024m

my.cnf.cx6a - cx5c +

default_cf_options += compression_per_level=kNoCompression

my.cnf.cx6b - cx5c +

default_cf_options += compression_per_level=kNoCompression; bottommost_compression=kLZ4Compression

my.cnf.cx6c - cx5c +

default_cf_options += compression_per_level=kNoCompression; bottommost_compression=kZSTD

my.cnf.cx8 - cx6b + default_cf_options += format_version=5
my.cnf.cx9a - cx6b + block_size=8192
my.cnf.cx9b - cx6b + block_size=16384
my.cnf.cx10 - cx6b + bytes_per_sync=1M, wal_bytes_per_sync=1M
my.cnf.cx11 - cx6b + delayed_write_rate=32M
my.cnf.cx12 - cx6b + max_open_files=-1

Tuning for the Insert Benchmark: Postgres

This presents performance and efficiency results for Postgres on the Insert Benchmark using release 12.3 and a small server with 4 CPU cores, 16G of RAM and a fast SSD. The goal is to understand the impact of my.cnf options and I have results for 11 different configurations.

Summary

I didn't try as many configurations for Postgres as I did for InnoDB and MyRocks. I am not sure that is because there is less tuning opportunity in Postgres. Notice that I didn't try to tune vacuum, which has many options, and instead my test scripts did a manual non-blocking vacuum after each test step. While the only writes in this test are inserts, vacuum is still needed to set bits in the visibility map. I think Postgres can be more clever about setting those bits after inserts.

A summary of the results is below.

With wal_compression=on, see configs cx2 through cx4b, performance drops for create index (l.x) and load more data (l.i1). The drop was larger than I expected. The compression method is PGLZ and I wonder if lz4 would help. The benefit from WAL compression should be fewer checkpoints and less checkpoint IO. See the summaries for in-memory, less and more IO-bound. For create index (l.x) the cpu overhead (cpupq) doubles from 4 to 8 (or 9) when WAL compression is enabled from cx1 to cx2 for in-memory, less and more IO-bound but there isn't a significant reduction in KB written per row (wkbpi). The impact on CPU overhead (cpupq) is even larger for the load more data (l.i1) step for in-memory, less and more IO-bound.
With a small WAL, see max_wal_size not set for cx2 and =2G for cx3a, performance suffers during load more data (l.i1). This is expected as a larger WAL means fewer checkpoints and less checkpoint IO and KB written to storage per insert (wkbpi) is lower with a larger WAL for in-memory, less and more IO-bound. The benefit is smaller for more IO-bound because page writeback there is triggered more from buffer pool pressure than from checkpoint.
QPS during the read+write tests didn't vary much with different configurations.

There is much detail in the reports that I mostly ignore, including response time histograms and the HW efficiency metrics. But they can be used to explain the results and answer questions.

Tests

Tests were run at most 2 threads/connections -- one for inserts and another for queries -- and I consider that to be 1 insert benchmark client.

In the performance reports, the steps are named:

l.i0 - initial load
l.x - create 3 secondary indexes
l.i1 - load more data
q100.2, q200.2, ..., q1000.2 - read+write where the insert rate limit is 100, 200, ..., 1000 and the .2 means the second run at each rate. The reports focus on the second run.

Configurations

All tests were done with fsync-on-commit disabled to avoid becoming an fsync latency benchmark. To save space. I also leave off conf.diff. when naming config files.

conf.diff.cx0 - minimal configuration
conf.diff.cx1 - cx0 + shared_buffers=10G
conf.diff.cx2 - cx1 + wal_compression=on
conf.diff.cx3a - cx2 + max_wal_size=2G
conf.diff.cx3b - cx2 + max_wal_size=10G
conf.diff.cx3c - cx2 + max_wal_size=20G
conf.diff.cx3d - cx2 + max_wal_size=40G
conf.diff.cx4a - cx3c + bgwriter_lru_maxpages=2000, bgwriter_delay=100ms
conf.diff.cx4b - cx3c + bgwriter_lru_maxpages=1000, bgwriter_delay=50ms
conf.diff.cx5 - cx4a + wal_compression=off
conf.diff.cx6 - cx4a + shared_buffers=2G

Tuning for the Insert Benchmark: InnoDB

This presents performance and efficiency results for InnoDB on the Insert Benchmark using MySQL 8.0.21 and a small server with 4 CPU cores, 16G of RAM and a fast SSD. The goal is to understand the impact of my.cnf options and I have results for 18 different configurations.

Summary

I use scripts to generate the performance reports. The reports are here for the in-memory, less IO-bound and more IO-bound database sizes. Some of the conclusions are specific to this workload and HW so be careful about applying this advice, but I suspect that innodb_dedicated_server should be used in most cases. A summary of the results is below.

It is hard to improve on innodb_dedicated_server. Much of the benefit for innodb_dedicated_server comes from using a large enough value for innodb_log_files_in_group. See the summaries for the in-memory, less IO-bound and more IO-bound database sizes.
The minimal configuration, my.cnf.cx0, is lousy. This isn't a big deal because it is trivial to add innodb_dedicated_server=ON to my.cnf.
The configs that use 8kb and 4kb for innodb_page_size, my.cnf.cx10a and my.cnf.cx10b, have poor create index performance (see l.x) for the in-memory and less IO-bound database sizes. I can't explain that but the HW efficiency metrics are worse for the context switch rate (cspq) and CPU overhead (cpupq).
Query throughput (qps) with the more IO-bound database was best for the configs that use 8kb and 4kb page sizes, cx10a and cx10b. The reason is less storage read IO, see rpq.
Setting innodb_buffer_pool_instances=1 also hurts the create index performance as it increases the CPU overhead (cpupq) for the in-memory and less IO-bound database sizes.
While my purpose isn't to compare InnoDB, MyRocks and Postgres the QPS results for InnoDB on the more IO-bound (500M rows) database size are odd. InnoDB does ~4 disk reads per query (see rpq) and is therefore limited to ~650 QPS per client. For Postgres, QPS is much better while rpq is close to zero.

There is much detail in the reports that I mostly ignore, including response time histograms and the HW efficiency metrics. But they can be used to explain the results and answer questions.

Tests

Tests were run at most 2 threads/connections -- one for inserts and another for queries -- and I consider that to be 1 insert benchmark client.

In the performance reports, the steps are named:

l.i0 - initial load
l.x - create 3 secondary indexes
l.i1 - load more data
q100.2, q200.2, ..., q1000.2 - read+write where the insert rate limit is 100, 200, ..., 1000 and the .2 means the second run at each rate. The reports focus on the second run.

Configurations

All tests were done with fsync-on-commit disabled to avoid becoming an fsync latency benchmark. The option names below leave off innodb_ to save space. I also leave off my.cnf. when naming config files.

my.cnf.cx0 - minimal configuration
my.cnf.cx1 - my.cnf.cx0 + dedicated_server=ON, buffer_pool_size=10G to cx0
my.cnf.cx2a - cx1 + log_files_in_group=20
my.cnf.cx2b - cx1 + log_files_in_group=40
my.cnf.cx2c - cx1 + log_files_in_group=2
my.cnf.cx6a - cx2b + idle_flush_pct=1, io_capacity=200, io_capacity_max=2000
my.cnf.cx6b - cx2b + idle_flush_pct=1, io_capacity=2500, io_capacity_max=5000
my.cnf.cx6c - cx2b + idle_flush_pct=1, io_capacity=5000, io_capacity_max=10000
my.cnf.cx6d - cx2b + idle_flush_pct=1, io_capacity=1000, io_capacity_max=2000
my.cnf.cx8 - cx6d + adaptive_hash_index=OFF
my.cnf.cx10a - cx6d + page_size=8192
my.cnf.cx10b - cx6d + page_size=4096
my.cnf.cx11a - cx6d + lru_scan_depth=2048
my.cnf.cx13 - cx6d + doublewrite=OFF
my.cnf.cx14 - cx6d + use_native_aio=OFF
my.cnf.cx15a - cx6d + buffer_pool_instances=1
my.cnf.cx16 - cx6d + log_writeahead_size=4096
my.cnf.cx18 - cx6d + purge_threads=1

Monday, November 30, 2020

Blind-writes and an LSM

Blind-writes for an LSM can be a challenge in the presence of secondary indexes. This post was inspired by an interesting but unpublished paper based on Tarantool and a blog post on SAI in DataStax Cassandra. Some of this restates ideas from the Tarantool paper.

Contributions of this post are:

Explains blind-writes
Explains a new way to do blind-writes for some SQL-ish statements. The new way doesn't require readers to validate secondary index entries, which is required with the Tarantool approach. The new approach only works for some types of statements while the Tarantool approach had fewer limits.

Longer introduction

Non-unique secondary index maintenance is read-free for MyRocks during a write (insert, update, delete). By this I mean that nothing is read from the secondary index so there is no chance of doing a storage read during index maintenance. This makes secondary indexes cheaper with MyRocks than the typical DBMS that uses a B-Tree. The InnoDB change buffer also reduces the chance of storage reads during index maintenance, which is nice but not as significant as the MyRocks benefit. I ignore the reads that MyRocks might do during LSM compaction so index maintenance is eventually not read-free so allow me to be truthy. Regardless, with an LSM there is (almost always) less read and write IO per write compared to a B-Tree.

If you only want to provide SQL semantics and support write-heavy workloads with secondary indexes, then it is hard to be more efficient than MyRocks as it doesn't do reads other than those required for SQL -- fetching the row(s). There are several reasons for fetching the row(s) during processing of an UPDATE or DELETE statement including returning the affected row count and validating constraints. Getting the row requires a read from the table (if heap organized) or the PK index (if using a clustered PK index like MyRocks and InnoDB).

If you are willing to give up SQL semantics then it is possible to be read-free -- no reads for secondary index maintenance, no reads to get the base row. This is explained in the Tarantool paper but that solution has a cost -- all secondary index entries must be validated by reading the base row because they can be stale (invalid). The validation isn't that different from what can happen in Postgres and InnoDB when vacuum and purge get behind and index-only queries might not be index-only.

There was also a feature in TokuDB for blind writes but I am not sure whether that avoided reads to get the base row.

Blind writes

A blind write is done without hidden or explicit reads. But I need to add an exception for some reads, because an LSM has to search the memtable to insert key-value pairs. So I limit this post to disk-based DBMS and allow a blind-write to read in-memory search structures. The Put operation in the LevelDB and RocksDB API is a blind write.

An explicit read is done explicitly by the user or implied by the operation. A read-modify-write sequence includes an explicit read and an example is SELECT ... FOR UPDATE followed by UPDATE. Reads done to process the WHERE clause for UPDATE and DELETE statements are explicit reads.

A hidden read is a read that isn't explicit and done while processing an operation. Examples include:

Read an index to validate a unique constraint. A bloom filter makes this fast for an LSM.
Determine the number of affected rows to provide SQL semantics for UPDATE & DELETE
Read B-Tree secondary index leaf pages to maintain them after a write

Secondary Index Maintenance

An index entry is composed (indexed column values, row pointer). The row pointer is usually a row ID or the value of the row's primary key columns. The typical index maintenance after a write consists of some of remove old index entry, insert new index entry. To perform these steps both the index column values and row pointer must be known. When a DBMS has the row then it has the required information, but a read must be done to get the row and we are discussing ways to avoid that read.

SQL

The rest of this post assumes a SQL DBMS and a simple schema.

create table T (id primary key, a int, b int)
create index xa on T(a)

I am interested in whether blind writes can be done for the following statements. The example statements are listed below. The first 3 statements use the PK index to evaluate the WHERE clause. The traditional way to evaluate these statements is to use the PK index to find the qualifying row, and then perform secondary index maintenance. Secondary index maintenance with a B-Tree means doing a read-modify-write on index leaf pages. With an LSM it can be read-free.

P1 - UPDATE T set a = 5 WHERE id=3
P2 - UPDATE T set a = a + 1 WHERE id=3
P3 - DELETE from T WHERE id=3

The next 3 statements use the secondary index, xa, to evaluate the WHERE clause. The traditional way to evaluate these statements is to use the secondary index to find qualifying index entries, then using the row pointer in each index entry to find the base row and finally performing index maintenance.

S1 - UPDATE T set b = 5 WHERE a=4
S2 - UPDATE T set b = b + 1 WHERE a=4
S3 - DELETE from T WHERE a=4

Truly read-free

I promised an approach that was truly read-free and after many words have yet to deliver. An LSM makes this possible, but since this is LSM-based there will still be reads during compaction so I am truthy here rather than true. Also, I assume reads can be done from an index to evaluate the WHERE clause.

With a SQL DBMS that uses an LSM, the base row doesn't have to be fetched for statements S1, S2 and S3 above if SQL semantics aren't required. The base row still has to be fetched for statements P1, P2 and P3. For S1, S2 and S3 I assume that the secondary index xa is scanned to find matching index entries, for each matching index entry the remaining work is:

S1 - Put a delta for the clustered PK index via the merge operator. The delta encodes b=5.
S2 - Put a delta for the clustered PK index via the merge operator. The delta encodes b=b+1.
S3 - Put a tombstone for the clustered PK index to delete the row

I have no idea about the effort required to get this into MySQL. I assume it always reads the base row for UPDATE and DELETE statements.

Friday, November 6, 2020

Max row per group, sad answers only

Today I learned that frequently asked questions on StackOverflow get their own tag. The tag greatest-n-per-group is for answers to questions about writing SQL to find the max row per group. By max row I mean the aggregated columns, group by columns and other columns for the row that has the max or min value in a group. By sad answers only I mean there is a lot of confusion about this, StackOverflow has over 3000 posts, and the query is harder to write than it needs to be.

I am writing about SQL rather than SQL engines and I am not an expert on writing SQL queries, but that might be appropriate given that I am writing about something that confuses users and could be easier. My motivation for writing this was a slow query plan for MySQL 8.0.22 while implementing the Time Series Benchmark Suite (TSBS) for MySQL.

Reproduction SQL is here and here and output from MySQL 8.0.22 is here and here. I updated the output for the queries with SHOW STATUS printed after each query.

The easy way

The answer is easy if you only want the aggregated and group by columns:

SELECT MAX(agg_col), gb_col FROM t GROUP BY gb_col

But it isn't easy when you want other columns -- columns that are not used for group by or aggregation. This would be easy had MySQL continued on the ANY_VALUE theme by adding FIRST_VALUE and LAST_VALUE as MongoDB does via the $first and $last aggregation accumulator operators. Well, MySQL has FIRST_VALUE and LAST_VALUE, but for window functions and they don't provide the desired semantics. If they existed with semantics similar to MongoDB then the following query would work and is easy to write:

SELECT MAX(agg_col), gb_col, FIRST_VALUE(other_col) FROM t GROUP BY gb_col

I am not an expert. Perhaps one day I will learn why there isn't an easy way to do this. MySQL docs have a useful page on this type of query. I have yet to try a variant that uses LATERAL.

The less easy ways

There are many ways to write this query. None of them are easy as the example I wrote above that isn't valid SQL. I tried: left join, correlated subquery, uncorrelated subquery and a rank() window function. The performant solutions were uncorrelated subquery and rank() window function. I was surprised that the rank() window function approach was performant because the explain output looked slow. But the runtime and slow log output were OK. By performant I mean a query plan that examines few rows, and loose index scan is an example of that.

This table shows the response time for each query type and the number of rows examined from the slow log. For the window function approach I am confused both by the low value for rows examined and the plan that shows a table scan. I am curious if there is a bug.

Approach	Response time (secs)	Rows examined
Uncorrelated	0.00	20
Window function	0.10	10
Left join	1.07	245750
Correlated	134.11	671170560

Loose index scan

Update - when I published this I claimed the index was on (j DESC, pk) but that was a mistake.

Before I show the queries, my goal is to get a plan that uses the loose index scan optimization. The test table is: create table tq(pk int primary key, j int, k int), there is an index on (j, pk DESC) and a NOT NULL constraint on j. This query uses a loose index scan, however it can't provide the value for the column k. The loose index scan is performant because it fetches one entry from the index per distinct value for (j,pk).

SELECT max(pk), j FROM tq GROUP BY j
EXPLAIN: -> Group aggregate (computed in earlier step): max(tq.pk)
-> Index range scan on tq using index_for_group_by(x) (cost=13.00 rows=10)

Uncorrelated subquery

This plan is performant because t2 is materialized via a loose index scan and the result from that does one point query per distinct value in j.

SELECT t1.pk, t1.j, t1.k

FROM tq t1, (SELECT max(pk) as maxpk, j FROM tq GROUP BY j) t2

WHERE t2.maxpk = t1.pk

EXPLAIN: -> Nested loop inner join
-> Filter: (t2.maxpk is not null)
-> Table scan on t2 (cost=3.62 rows=10)
-> Materialize
-> Group aggregate (computed in earlier step): max(tq.pk)
-> Index range scan on tq using index_for_group_by(x) (cost=13.00 rows=10)
-> Single-row index lookup on t1 using PRIMARY (pk=t2.maxpk) (cost=0.26 rows=1)

Rank window function

This query is slightly slower than the uncorrelated subquery above. I didn't expect that given the plan that has a table scan on tq. Adding hints to use the index on (j,pk) don't change the query plan. I wonder if this explain outpout is correct as the query doesn't do a full scan when run. Also the query is almost as fast as the uncorrelated approach.

WITH t1 AS (SELECT pk, j, k,

RANK() OVER (PARTITION by j ORDER BY pk DESC) AS myrank FROM tq)

SELECT pk, j, k from t1 WHERE myrank=1

EXPLAIN: -> Index lookup on t1 using <auto_key0> (myrank=1)
-> Materialize CTE t1
-> Window aggregate: rank() OVER (PARTITION BY tq.j ORDER BY tq.pk desc )
-> Sort: tq.j, tq.pk DESC (cost=8273.25 rows=82170)
-> Table scan on tq (cost=8273.25 rows=82170)

Left join

I don't expect this query to be performant because there isn't an equality predicate on pk. This might be a useful approach when there isn't an index on (j,pk), but that is not the case here and this plan examines too many rows.

SELECT t1.pk, t1.j, t1.k FROM tq t1

LEFT JOIN tq t2 ON t1.j = t2.j AND t1.pk < t2.pk

WHERE t2.j IS NULL

EXPLAIN: -> Filter: (t2.j is null) (cost=76209940.12 rows=750212100)

-> Nested loop antijoin (cost=76209940.12 rows=750212100)

-> Table scan on t1 (cost=8273.25 rows=82170)

-> Filter: (t1.pk < t2.pk) (cost=14.38 rows=9130)

-> Index lookup on t2 using x (j=t1.j) (cost=14.38 rows=9130)

Correlated subquery

The correlated subquery isn't performant. It examines too many rows. That isn't a surprise.

SELECT pk, j, k FROM tq t1
WHERE pk=(SELECT MAX(t2.pk) FROM tq t2 WHERE t1.j = t2.j)

EXPLAIN: -> Filter: (t1.pk = (select #2)) (cost=8273.25 rows=82170)

-> Table scan on t1 (cost=8273.25 rows=82170)

-> Select #2 (subquery in condition; dependent)

-> Aggregate: max(t2.pk)

-> Index lookup on t2 using x (j=t1.j) (cost=927.37 rows=9130)