4 ms·

Reducing Online Serving Latency from 1.11s to 123.6ms

39 points by jinqueeny 4y ago

deleted 4y ago
[deleted]
daneel_w 4y ago
Something the author(s) don't seem to fully consider when creating composite indices is how B-trees work. The leanest and almost always fastest composite index for MariaDB/MySQL is one where the columns are ordered first to last relative to lowest and highest cardinality, i.e. how divergent they are. You usually want a B-tree index that's as little branchy as possible in the start, and then branches out increasingly the deeper into it you get, in order to traverse its components as fast as possible. The performance difference between a correctly ordered composite index and one that's ordered seemingly on random, as in the article, can be not-insignificant.
- 8n4vidtmkvmk 4y ago
  I thought you wanted the highest cardinality at the start so as to reduce the result set as quickly as possible. For example, if you have a database of people with their first and last names, and let's say there are 1000 distinct first names and 100,000 distinct last names, you'd want the index to by (last, first) no? You're saying the opposite?
  - daneel_w 4y ago
    Yes, I'm saying the opposite. You want to be done scanning (discarding) each large branch (column) as soon as possible before you move on to the many twigs. Additionally, if you start at the branchiest end you cannot know what path leads you to each desired result along the composite tree until you've scanned all of the paths. Your example does not work because it's not in parity with the structure of a B-tree-indexed data set.
    - azurelake 4y ago
      I don't think what you're saying is correct, especially your last sentence (it definitely DOES work at least in terms of not being a table scan). Here's a stackoverflow answer that agrees with me and 8n4vidtmkvmk: https://stackoverflow.com/a/9537675 https://stackoverflow.com/a/9537675. Do you have any sources for what you're claiming? edit: Here a quote from Percona as well: "In the simplest case, we want to put the most selective column first in the index, so that the number of possible matching rows is the smallest, i.e. we find the rows as quickly as possible." - https://www.percona.com/blog/2009/06/05/a-rule-of-thumb-for-choosing-column-order-in-indexes/ https://www.percona.com/blog/2009/06/05/a-rule-of-thumb-for-...
      - daneel_w 4y ago
        My source is my experience from having worked with MariaDB and MySQL for about 15 years now. The two articles you cited are 10 and 13 years old, so let's run a fresh test with two identical test tables that have their columns indexed in opposite order of eachother: CREATE TABLE a/b ( x int, y int, z int, ) CREATE INDEX a ON a (x, y, z) CREATE INDEX b ON b (z, y, x) # index in reverse order Some pseudocode to illustrate how I filled the tables: for x = 1 to 10: for y = 1 to 1000: for z = 1 to 10000: INSERT INTO a/b VALUES (x, y, z) Table a took 25 minutes and 2 seconds to populate with 100 million rows. Table b took 37 hours and 40 minutes to populate. Something's up. I built table a a second time, again taking pretty much the same 25 minutes, and I tried building table b again as well but gave up after four hours. It's definitely not the computer acting up, nor the storage. +--------+------------+ | Table | Checksum | +--------+------------+ | test.a | 4243132544 | | test.b | 4243132544 | +--------+------------+ Not the data either. Both tables checksum identically. Here's what the storage looks like: -rw-rw---- 1 mysql mysql 6618611712 Jan 15 15:42 a.ibd -rw-rw---- 1 mysql mysql 8715763712 Jan 16 17:42 b.ibd +------------+-----------+-----------+ | table_name | data_mb | index_mb | +------------+-----------+-----------+ | a | 3478.0000 | 2132.0000 | | b | 3769.0000 | 4290.7344 | +------------+-----------+-----------+ So the index of table b is obviously a horrendous crow's nest. It's twice as large as the index of table a, and it's even occupying more space than the actual rows themselves. I ran 100k reproducible queries on each of the tables to see how the composite indices perform. More wonky pseudocode: srand ( 1234567 ) for i = 1 to 100000: # this includes 0 which is intentional xr = prng ( 0 to 10 ) yr = prng ( 0 to 1000 ) zr = prng ( 0 to 10000 ) SELECT * FROM a/b WHERE x = xr AND y = yr AND z = zr table a ======= 42 seconds 48 seconds 35 seconds table b ======= 87 seconds 71 seconds 69 seconds Some caching is of course involved. I queried the tables one after another just to see if rattling the cage a bit would have any effect: table a: 48 seconds table b: 83 seconds table a: 61 seconds table b: 72 seconds A little bit, but nowhere near enough to outperform the lean and correctly built index on table a. And this is just a simple three-column composite index - the problem I'm illustrating grows exponentially with every column you add to the composite.
ngaut 4y ago
Keeping low latency for an online data service with more than 5 billion records can be a challenge. Features like query the database with natural language(https://ossinsight.io/explore).This https://ossinsight.io/explore).This makes it easier for users to access the data without having to know SQL. But the generate SQL could be pretty heavy(many Full table scan and index scan).
- snuxoll 4y ago
  We've got a in-house LOB app that can be boiled down to a giant todo-list/work history for accounts, virtually every task that needs to be done for an account gets logged into this system. A whole bunch of assorted data is pulled in from various systems into this for the explicit purpose of letting employees filter data, and there's a filter builder in the UI that lets them use whatever combination of criteria they might need. Needless to say, the database servers absolutely hate this application. Because queries are completely dynamic based on filters there's no way to index things, so full table scans are not uncommon (we've at least got some conditional indexes to filter active accounts out from inactive ones to limit the most common queries to just those accounts that haven't been paid down). So yeah, database servers hate these kinds of workloads, and not much you can do to make them happy :/
  - ngaut 4y ago
    Totally agree.Database with both row and column storage engine could help a lot.T hat's the reason OSSInsight like workload can run on top of TiDB easily, whether scan the whole table or scan part of the index.
mayli 4y ago
Shouldn't this be some common sense?
- AdrianB1 4y ago
  It looks like, to me, but I thought I missed something.
andrejguran 4y ago
TLDR: indexes make your DB go BRrrrrr

39 points by jinqueeny 4y ago

deleted 4y ago

[deleted]

Something the author(s) don't seem to fully consider when creating composite indices is how B-trees work. The leanest and almost always fastest composite index for MariaDB/MySQL is one where the columns are ordered first to last relative to lowest and highest cardinality, i.e. how divergent they are. You usually want a B-tree index that's as little branchy as possible in the start, and then branches out increasingly the deeper into it you get, in order to traverse its components as fast as possible. The performance difference between a correctly ordered composite index and one that's ordered seemingly on random, as in the article, can be not-insignificant.

8n4vidtmkvmk 4y ago
I thought you wanted the highest cardinality at the start so as to reduce the result set as quickly as possible. For example, if you have a database of people with their first and last names, and let's say there are 1000 distinct first names and 100,000 distinct last names, you'd want the index to by (last, first) no? You're saying the opposite?
- daneel_w 4y ago
  Yes, I'm saying the opposite. You want to be done scanning (discarding) each large branch (column) as soon as possible before you move on to the many twigs. Additionally, if you start at the branchiest end you cannot know what path leads you to each desired result along the composite tree until you've scanned all of the paths. Your example does not work because it's not in parity with the structure of a B-tree-indexed data set.
  - azurelake 4y ago
    I don't think what you're saying is correct, especially your last sentence (it definitely DOES work at least in terms of not being a table scan). Here's a stackoverflow answer that agrees with me and 8n4vidtmkvmk: https://stackoverflow.com/a/9537675 https://stackoverflow.com/a/9537675. Do you have any sources for what you're claiming? edit: Here a quote from Percona as well: "In the simplest case, we want to put the most selective column first in the index, so that the number of possible matching rows is the smallest, i.e. we find the rows as quickly as possible." - https://www.percona.com/blog/2009/06/05/a-rule-of-thumb-for-choosing-column-order-in-indexes/ https://www.percona.com/blog/2009/06/05/a-rule-of-thumb-for-...
    - daneel_w 4y ago
      My source is my experience from having worked with MariaDB and MySQL for about 15 years now. The two articles you cited are 10 and 13 years old, so let's run a fresh test with two identical test tables that have their columns indexed in opposite order of eachother: CREATE TABLE a/b ( x int, y int, z int, ) CREATE INDEX a ON a (x, y, z) CREATE INDEX b ON b (z, y, x) # index in reverse order Some pseudocode to illustrate how I filled the tables: for x = 1 to 10: for y = 1 to 1000: for z = 1 to 10000: INSERT INTO a/b VALUES (x, y, z) Table a took 25 minutes and 2 seconds to populate with 100 million rows. Table b took 37 hours and 40 minutes to populate. Something's up. I built table a a second time, again taking pretty much the same 25 minutes, and I tried building table b again as well but gave up after four hours. It's definitely not the computer acting up, nor the storage. +--------+------------+ | Table | Checksum | +--------+------------+ | test.a | 4243132544 | | test.b | 4243132544 | +--------+------------+ Not the data either. Both tables checksum identically. Here's what the storage looks like: -rw-rw---- 1 mysql mysql 6618611712 Jan 15 15:42 a.ibd -rw-rw---- 1 mysql mysql 8715763712 Jan 16 17:42 b.ibd +------------+-----------+-----------+ | table_name | data_mb | index_mb | +------------+-----------+-----------+ | a | 3478.0000 | 2132.0000 | | b | 3769.0000 | 4290.7344 | +------------+-----------+-----------+ So the index of table b is obviously a horrendous crow's nest. It's twice as large as the index of table a, and it's even occupying more space than the actual rows themselves. I ran 100k reproducible queries on each of the tables to see how the composite indices perform. More wonky pseudocode: srand ( 1234567 ) for i = 1 to 100000: # this includes 0 which is intentional xr = prng ( 0 to 10 ) yr = prng ( 0 to 1000 ) zr = prng ( 0 to 10000 ) SELECT * FROM a/b WHERE x = xr AND y = yr AND z = zr table a ======= 42 seconds 48 seconds 35 seconds table b ======= 87 seconds 71 seconds 69 seconds Some caching is of course involved. I queried the tables one after another just to see if rattling the cage a bit would have any effect: table a: 48 seconds table b: 83 seconds table a: 61 seconds table b: 72 seconds A little bit, but nowhere near enough to outperform the lean and correctly built index on table a. And this is just a simple three-column composite index - the problem I'm illustrating grows exponentially with every column you add to the composite.

ngaut 4y ago

Keeping low latency for an online data service with more than 5 billion records can be a challenge. Features like query the database with natural language(https://ossinsight.io/explore).This https://ossinsight.io/explore).This makes it easier for users to access the data without having to know SQL. But the generate SQL could be pretty heavy(many Full table scan and index scan).

snuxoll 4y ago
We've got a in-house LOB app that can be boiled down to a giant todo-list/work history for accounts, virtually every task that needs to be done for an account gets logged into this system. A whole bunch of assorted data is pulled in from various systems into this for the explicit purpose of letting employees filter data, and there's a filter builder in the UI that lets them use whatever combination of criteria they might need. Needless to say, the database servers absolutely hate this application. Because queries are completely dynamic based on filters there's no way to index things, so full table scans are not uncommon (we've at least got some conditional indexes to filter active accounts out from inactive ones to limit the most common queries to just those accounts that haven't been paid down). So yeah, database servers hate these kinds of workloads, and not much you can do to make them happy :/
- ngaut 4y ago
  Totally agree.Database with both row and column storage engine could help a lot.T hat's the reason OSSInsight like workload can run on top of TiDB easily, whether scan the whole table or scan part of the index.

mayli 4y ago

Shouldn't this be some common sense?

AdrianB1 4y ago
It looks like, to me, but I thought I missed something.

andrejguran 4y ago

TLDR: indexes make your DB go BRrrrrr