9

I'm currently exploring the use of PARTITION, for a specific use case I have.
I use InnoDB, file per table. MariaDB 10.8.

I was reading Rick's PARTITION Maintenance in MySQL webpage.

I'd like to highlight this bit:

WHERE X = 1234 -- This lets "partition pruning" look only in that one partition. But that's no better than INDEX(x) on a non-partitioned table. And you probably need that index anyway; after first 'pruning' down to the desired partition, you still need the index. No faster.
A common fallacy: "Partitioning will make my queries run faster". It won't. Ponder what it takes for a 'point query'. Without partitioning, but with an appropriate index, there is a BTree (the index) to drill down to find the desired row. For a billion rows, this might be 5 levels deep. With partitioning, first the partition is chosen and "opened", then a smaller BTree (of say 4 levels) is drilled down. Well, the savings of the shallower BTree is consumed by having to open the partition. Similarly, if you look at the disk blocks that need to be touched, and which of those are likely to be cached, you come to the conclusion that about the same number of disk hits is likely. Since disk hits are the main cost in a query, Partitioning does not gain any performance (at least for this typical case). The 2D case (below) gives the main contradiction to this discussion.

I totally understand what it means, but I have a question:

In MySQL/MariaDB, do Indexes' performance degrade as they become larger and larger?

For a billion rows, or for 100 billion rows, is a good Index always better than Partitions, in terms of Performance?

--

There is also this bit which is closest to what I'm trying to benefit:

Use case #3 -- Hot spot. This is a bit complicated to explain. Given this combination:
⚈ A table's index is too big to be cached, but the index for one partition is cacheable, and
⚈ The index is randomly accessed, and
⚈ Data ingestion would normally be I/O bound due to updating the index
Partitioning can keep all the index "hot" in RAM, thereby avoiding a lot of I/O.

The big win for Case #3: Improving caching to decrease I/O to speed up operations.

Is "index cached" valid for InnoDB too? My understanding is CACHE INDEX only applies to MyISAM.
Or does this relate to it being in the InnoDB Buffer Pool?

And in relation to decreasing I/O, does this apply to NVMe servers? My %iowait is 0.00, while my application is write-intensive.

11
  • Yes, indexes' performance degrade as they become larger and larger. Does it matter? Is it noticeable? Usually not. However, if you randomly delete lots of lines, you index may become fragmented. Usually, that's not an issue with MariaDB/InnoDB, but you try an OPTIMIZE TABLE (which will also rebuild the indexes). Note that this might lock up your database operations until it finishes, so try it on a test machine with production-like data - not just a copy of the data, but with a database which has aged due to real-life-like inserts/deletes. Compare before/after performance.
    – Klaws
    Dec 29, 2022 at 11:59
  • Thank you very much. Yep, I'm aware of OPTIMIZE TABLE, but it locks the whole table which isn't acceptable. I've tried the Percona Tools, but there is always something with the tables that prevents us from being able to use this tool :) (causing a crash, etc)
    – Nuno
    Dec 29, 2022 at 14:37
  • 1
    For normal random deletes/updates, OPTIMIZE TABLE is unlikely to provide more than a trivial improvement. The fear of fragmentation is mostly a myth in InnoDB.
    – Rick James
    Dec 29, 2022 at 20:09
  • @Nuno - Please tell us what type of data you have. The discussions so far are too general for you to give you many actionable tips.
    – Rick James
    Dec 29, 2022 at 20:11
  • Sorry @RickJames, only now I saw your question. It's basically Groups, Posts and Replies. There will always be "random accesses" (due to crawlers or users going back to old posts), but what needs to be "cached" in the pool is mostly the recent posts, to show on the user Feeds :) (the Feeds follow a complex algorithm, friends, relevancy, privacy, blocks, etc - not the same Feed shown to everyone)
    – Nuno
    Dec 30, 2022 at 12:39

3 Answers 3

9

(In addition to Bill's comments...)

Another way to analyze performance -- "Count the disk hits".

  • InnoDB caches 16KB blocks (data and index) in its buffer_pool.
  • The cache is on-demand and roughly least-recently-used.
  • All activity (read, write, lookup, etc) is done in the buffer_pool, not directly on disk.
  • A simple Rule of Thumb is that the fanout of any InnoDB BTree is about 100. (Percona used 128--essentially the same.) A billion rows (of data or index) will have 5 levels. That means that 5 blocks must be fetched (if not already cached) to do a simple point-query. Or 10 blocks for a lookup via a secondary key. (6 and 12 for 100 billion rows.)
  • If you are fetching 101 'consecutive' rows from that BTree, you will need 2 leaf nodes (the one you start with plus the next one.) Another Rule of Thumb: All the non-leaf nodes are probably cached.
  • If your activity is random (as with a UUID or hash for the PK) and the buffer_pool cannot hold the entire BTree, the cache becomes mostly useless. This leads to each point-query taking at least 1 disk hit. In this case, "too big is terrible for performance".
  • If on the other hand, you are only touching "recent" rows (and the PK is AUTO_INCREMENT or time-based), then the cache buffer_pool has the desired data 99 times out of 100. That is, there is essentially no degradation as the table grows, even when much bigger than the buffer_pool.

(I did a lot of 'hand-waving' in those last two statements.)

I hope I have given you some clues on how to judge for yourself whether your table will or won't suffer as it grows. If you would like further discussion, please provide the CREATE TABLE. When someone talks about bilion-row tables, I like to shrink datatypes, restructure the schema, normalize, add Summary tables, consider sharding, etc. But I rarely recommend Partitioning. Sometimes, I recommend "keep the summary tables, but toss the Fact table." This eliminates all sorts of scaling and performance problems.

20
  • 1
    Thank you very much, Rick. So far, I've been scaling vertically, but the conclusion I'm taking from the replies here is that Indexes and Partitions on their own will not resolve the scalability issue. Sharding (scaling horizontally) seems to be where this is heading. Something like Vitess or MariaDB CONNECT, from what I'm researching. This obviously brings a number of other headaches & cons.
    – Nuno
    Dec 29, 2022 at 9:30
  • 1
    I like your suggestion of "keep the summary tables, but toss the Fact table". Does this mean something like moving the "TEXT columns" of the "Posts" table into partitioned/sharded tables split into multiple servers ([ID, TEXT]), but keep the "meta data" table (with all the entries & indexes, without the Text) in just 1 server? This way, this table is a lot smaller in size, can still be used for JOINs and all that stuff, without any performance impact, and then once we have the final result of "Posts" to display to the user, that's when we go fetch the text for each of those posts. Is that it?
    – Nuno
    Dec 29, 2022 at 9:30
  • 1
    @J.D. Ah, there's the rub. Yes, if the active portion of your table fits in the cache, it will all work out. So it depends strongly on the workload pattern. If the table has more or less random access pattern, or if it has table-scans for doing aggregation queries, it's a different story. Dec 29, 2022 at 17:19
  • 1
    @BillKarwin Yes, in regards to Memory, indeed. But even uncached data (especially with NVMes these days) takes trivial time to load off disk. The problem most people run into is index scans when the data they need doesn't actually warrant a scan. Scanning the entire index from disk will hurt, with insufficient Memory. But I usually find that being either an architectural problem (improperly designed tables or improperly designed indexes) or a query tuning problem. So usually these are solvable without throwing hardware at it. The only exception is aggregative queries like you mentioned. In...
    – J.D.
    Dec 29, 2022 at 18:57
  • 1
    @J.D. MySQL itself does not provide a columnstore engine or index type. But it does provide an extensible architecture, and some third-party companies have developed columnstores that can be plugged into MySQL. Dec 29, 2022 at 19:03
10

For a billion rows, or for 100 billion rows, is a good Index always better than Partitions, in terms of Performance?

There are several things I can say about this.

  • We can't make this generalization, because it depends on the query. In general, every kind of optimization is a great help to the right type of query, at the expense of other types of queries. So you must be very specific about which query you want to optimize before choosing the method of optimization.

  • It's not an either-or choice. You can partition a table, and also define an index, so searches will be optimized in a given partition.

  • I don't think you have 100 billion rows. If you did, you wouldn't be asking this question on Stack Exchange, you'd be assigning your full-time database architect team the task of optimizing it. They would undoubtedly come back with a design that uses many servers. It's impractical to store 100 billion rows in a single table. How would you back it up? How would you add a column?

InnoDB uses B-tree indexes (also fulltext and spatial indexes, but for this discussion we assume the default type of index).

B-tree indexes have complexity O(log2n) for both inserting and searching, where n is the number of entries in the data structure. Inserting or searching therefore does get more expensive as the index gets larger.

The I/O required by an index search is a function of the depth of the B-tree. That is, how many levels of non-terminal nodes must be traversed to get to the leaf node. The depth depends on how many index entries there are, and also depends on how large the data type of a given entry, because InnoDB page sizes are fixed, so only so many index nodes can fit on a page. See: https://www.percona.com/blog/2009/04/28/the_depth_of_a_b_tree/

I/O cost can be mitigated by keeping subsets of the index pages in RAM, in the InnoDB buffer pool. But if the index grows much larger than RAM, there's not enough buffer pool to hold the whole index, so if you do searches randomly over the whole index, InnoDB is likely to evict pages that you will need again soon. Those pages will be re-loaded from storage when you need them, but this can lead to extra overhead as pages are swapped in and out of RAM.

Caching indexes only applies to MyISAM. InnoDB caches pages on demand, which may include a subset of a given index. Forget about any manual command to load indexes into cache. To be honest, I recommend to forget about MyISAM for any purpose. I haven't seen it used appropriately since the 2000's.

You asked about NVMe storage. NVMe is of course faster than old SATA interfaces, but how does it compare to RAM? It depends what you measure but for both access time and throughput (MB/second) you can count on RAM being several times faster than the latest generation of NVMe. Also the InnoDB code is written to assume that pages must be in RAM before they can be read. It's still a win to keep data and index pages cached in RAM.

I agree with Rick's general statement that partitioning is usually not going to help performance as much as you think it will. It is useful in the right scenario, but it's not a magic "everything go fast" solution. This is true of every other type of optimization too!

5
  • 1
    Thank you very much. Sure, I don't have a table with 100B rows, but I have a few with over 1B and growing fairly quickly. So far, I've been scaling vertically, but the conclusion I'm taking from the replies here is that Indexes and Partitions on their own will not resolve the scalability issue. Sharding (scaling horizontally) seems to be where this is heading. Something like Vitess or MariaDB CONNECT, from what I'm researching. This obviously brings a number of other headaches & cons.
    – Nuno
    Dec 29, 2022 at 9:21
  • @Nuno I actually disagree with Bill on "It's impractical to store 100 billion rows in a single table.". (I do like the rest of the answer though.) There's nothing inherently wrong with storing 100 billion or even 100 trillion rows in a table. It just depends on your use cases. Some people might find that normalizing that data to reduce it in the table is helpful for their particular use cases. But objectively speaking, on its own there's nothing wrong with a table that size and it just depends on how you plan to use it. I didn't have issues with the tables I worked with that approached that.
    – J.D.
    Dec 29, 2022 at 15:25
  • 1
    @J.D. You have done database operations on a MySQL instance with a table that approached 100 billion rows? Like backups, schema changes, adding indexes when needed, archiving data — not just software development tasks such as writing queries to search it? Dec 29, 2022 at 17:09
  • 1
    @BillKarwin Yes, except on SQL Server not MySQL - but I wouldn't believe MySQL isn't able to handle a table of the same magnitude almost just as well. Nightly Full Backups (which keep in mind, the performance of isn't really measured by the number of rows of the table, rather is a factor of the physical size of the table instead), schema changes (which depending on the change can be done online - e.g. adding nullable columns, otherwise applied via alternative solutions to minimize any downtime). We never archived data (hence the big table) but archiving is easy on an indexed table.
    – J.D.
    Dec 29, 2022 at 18:49
  • 2
    @J.D. Okay that's really great that SQL Server is so capable. MySQL is not. I have supported databases with tables of 1-5 billion rows, and at that scale, it's pretty urgent that the project needs to refactor so they can scale out to multiple database servers. I agree backup time is a function of table size, which varies. But a table that grows over 500GB is starting to get hard to work with. We actually implemented an alert, to urge the developers to either archive some data, or else split up such tables. Dec 29, 2022 at 18:59
5

In MySQL/MariaDB, do Indexes' performance degrade as they become larger and larger?

It depends what you mean by "performance"...

If you mean "finding one row or a range of rows based on the indexed key" then the answer would be "a little bit". As the others have explained, as long as the working set of the index remain in cache, "large" may get a little slower than "small", but that is likely to be swamped by the rest of query time used by logistics, network, parsing, etc. If leaf pages are not cached, that would add one random IO, so you'd have to ask your IO system about how long that will take.

But you ask about index vs partitioning, so in this case, if the data is the same in the "partitioned" case and the "single table" case, the total size of indices on partitions would be pretty much the same as the the index on the single table. With the same query load, there's no reason why one would be cached better than the other, so there would likely be no difference between the two. If you access only the latest rows, then both scenarii would benefit in the same way from needing to cache only the corresponding parts of the indices.

However if you take a global view of performance and add stuff like "delete all rows older than 12 months", and you have a billion rows to delete when running this archiving operation, then huge tables and huge indices become an Extremely Bad Idea (TM). If it's an index on date, maybe it will be tolerable because the deletion will hit a contiguous chunk of it. However if it's an index on a rather random column, then every deleted row will trigger random writes somewhere in your index, all over the place, and that will grind forever.

Whereas, if you use partitioning, "DROP PARTITION" is almost instantaneous because behind the scenes, it's just deleting the corresponding files. Unless there are ON DELETE triggers to be fired, there is no point in even reading the rows to delete if the database knows we're dropping the whole partition.

If there are no writes to older partitions, this may make backups a lot faster, if the backup tool can exploit the fact that there is no need to backup a partition that did not change.

I'm editing to add other circumstances when partitioning can make your queries faster:

You don't have enough money to put the whole table on a SSD, so you put the old partitions (and indices) that are seldom accessed on a clunky slow spinning RAID, and the most recent partitions (and indices) that see most of the action on some vert fast SSDs. That's a good "cash vs performance" optimization, but you will have to move partitions once in a while. Maybe you could even replicate just the recent partitions, or put one partition per server and run them in parallel, if the database supports it, stuff like that.

Also if the query optimizer screws it up and decides to do a full table scan or something of the sort, maybe if your table is partitioned and the query has a condition on the partition key, the size of the screwup can be limited to just a few partitions instead of the whole table.

1
  • 1
    Thank you very much. Yeah, I'm aware of the example you gave about purging old data, that Partitions are a very good use for that, versus deleting on a big table. (I appreciate your comment here still) The first 2 paragraphs also make sense, and good to know. Thank you again.
    – Nuno
    Dec 29, 2022 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.