11 ms·

Index Merges vs. Composite Indexes in Postgres and MySQL

175 points by Sirupsen 4y ago

bawolff 4y ago
Honestly im kind of surprised that they are even that close. I wonder if this changes at scale when the intersection is larger.
- Sirupsen 4y ago
  Ideally, I would add three graphs to the post: (1) Table size on the x-axis, and time on the y-axis for index merge vs composite index (2) Number of columns on the x-axis, and time on the y-axis for both (3) Number of final matches on the x-axis, and time on the y-axis for both But ran out of time and decided to test with the table size of 10M rows, and a 100-ish result set. That's in my experience a decent representation for what you might be doing with a relational database.
Lukas1994 4y ago
Good stuff! What's the size difference between the composite index vs the two separate indices?
- Sirupsen 4y ago
  I've added this to the article, thanks! Composite index (int64, int64): ~70 MiB in Postgres, ~350 MiB in MySQL Single index (int64): ~70 MiB in Postgres, ~240 MiB in MySQL If you assume the majority of an index are index entries of (int64, int64, int64) where the third number is some sort of identifier for the record on the heap, you'd expect this to be ~230 MiB. So Postgres does some compression very well here, and MySQL has a bit more overhead for its indexes it seems.
  - fabian2k 4y ago
    Could be the deduplication newer Postgres versions have for B-Tree indexes: https://www.postgresql.org/docs/current/btree-implementation.html https://www.postgresql.org/docs/current/btree-implementation... > 67.4.3. Deduplication > A duplicate is a leaf page tuple (a tuple that points to a table row) where all indexed key columns have values that match corresponding column values from at least one other leaf page tuple in the same index. Duplicate tuples are quite common in practice. B-Tree indexes can use a special, space-efficient representation for duplicates when an optional technique is enabled: deduplication. > Deduplication works by periodically merging groups of duplicate tuples together, forming a single posting list tuple for each group. The column key value(s) only appear once in this representation. This is followed by a sorted array of TIDs that point to rows in the table. This significantly reduces the storage size of indexes where each value (or each distinct combination of column values) appears several times on average. The latency of queries can be reduced significantly. Overall query throughput may increase significantly. The overhead of routine index vacuuming may also be reduced significantly.
    - Sirupsen 4y ago
      Excellent, thank you! I'll add that to the article.
      - fabian2k 4y ago
        This is a guess on my part, though I think a plausible one. To verify you'd probably have to compare an index with unique values to one with many identical ones.
  - libraryofbabel 4y ago
    As you mention in the article, this is small by modern hardware standards and means the indexes can be entirely held in memory. Curious how things look for much larger tables where the index has to be read from disk?
  - masklinn 4y ago
    An other thing which might be of interest: what if you use convering indexes for the two single indexes? Is postgres able to do an index-only scan then, thanks to the coverage? Or does it decide to use only one index and filter based on the covered values?
magicalhippo 4y ago
A composite index can also be used for a partial index scan[1], so if you're frequently looking for just int100 as well as the int100,int1000 combination (as per the article's example), then a composite index int100,int1000 can be used for queries just filtering on int100. The order of the columns in the composite index might matter then. We got some nice savings by reordering columns in indexes and changing the join order in queries (our DB wasn't that smart) or adding a "useless" filters to the where clause, allowing us to consolidate multiple indexes into one composite one. [1]: might be using the wrong terminology here, I'm not talking about a partial index[2], but using only the first N dimensions of a M-dimensional index. [2]: https://www.postgresql.org/docs/current/indexes-partial.html https://www.postgresql.org/docs/current/indexes-partial.html
- winrid 4y ago
  There are some DBs where the order of fields doesn't matter in the compound index if you're just searching by one field (but of course is less efficient). I think Oracle supports this.
  - magicalhippo 4y ago
    Good point, I reworded it to be more general. Can't recall seeing our DB being that clever.
  - thom 4y ago
    Postgres is capable of doing this with some index types, but generally more slowly than a B-tree index being asked about its leftmost columns: https://www.postgresql.org/docs/current/indexes-multicolumn.html https://www.postgresql.org/docs/current/indexes-multicolumn.... Also worth noting that for very complex workloads that need to support arbitrary subsets of equality matches over columns, a Bloom filter might work best: https://www.postgresql.org/docs/current/bloom.html https://www.postgresql.org/docs/current/bloom.html
  - mattashii 4y ago
    This dependz on the index type, but PostgreSQL also supports queries based on arbitrary attributes of multi-attribute indexes: both GIN and BRIN can be used for queries on any of the indexed expressions. Maybe eventually PG will also get index skip scans for btrees, which could allow for arbitrary columns searches in the btree; but we're not there yet by a large margin.
pdhborges 4y ago
For these 64-bit index entries we’d expect to have to scan roughly: index_row_size⋅rows=2⋅64bit⋅10^5=1.5MiB Where do the 10^5 rows come from? With a composite index and a point query doesn't the database scan just the 100 returned rows?
- Sirupsen 4y ago
  You're absolutely right! I forgot to move this around when I updated the article's structure. This is only relevant when doing the index merge. The article has been updated
deleted 4y ago
[deleted]
arynda 4y ago
Comparison on Clickhouse, also runs in about 30-40ms, however there's no indexing being used and this is a full-table scan. create table if not exists test_table ( id UInt64, text1 String, text2 String, int1000 UInt64, int100 UInt64, int10 UInt64, int10_2 UInt64 ) engine = MergeTree() order by (id) ; insert into test_table with repeat('b', 1024) as one_kib, repeat('b', 255) as bytes_255 select number as id, one_kib, bytes_255, rand() % 1000 as int1000, rand() % 100 as int100, rand() % 10 as int10, rand() % 10 as int10_2 from numbers(10e6) ; > select count(*) from test_table where int1000 = 1 and int100 = 1; ┌─count()─┐ │ 9949 │ └─────────┘ 1 row in set. Elapsed: 0.034 sec. Processed 10.00 million rows, 160.00 MB (290.93 million rows/s., 4.65 GB/s.) The same table but with 1B rows instead, runs in ~1800ms > select count(*) from test_table where int1000 = 1 and int100 = 1; ┌─count()─┐ │ 999831 │ └─────────┘ 1 row in set. Elapsed: 1.804 sec. Processed 1.00 billion rows, 16.00 GB (554.24 million rows/s., 8.87 GB/s.) [1] Converted the table create and insert logic from here: https://github.com/sirupsen/napkin-math/blob/master/newsletter/20-compound-vs-combining-indexes/test.rb https://github.com/sirupsen/napkin-math/blob/master/newslett...
- Sirupsen 4y ago
  Are you aware of a good write-up on how Clickhouse/other columnar databases do the intersection?
  - twoodfin 4y ago
    One obvious way is to build a bitmap indexed by row position for each filter. Both the "&" intersect and the final bit count can be rocket fast on modern CPU vector units.
  - arynda 4y ago
    Not in particular sorry, most of the good content I've found is on Altinity [1] and Alibaba's technical blogs [2][3]. These tend to be mostly focused on how the data itself is stored and how to use Clickhouse, but don't really dive into the specifics of how query processing is performed. [1] https://altinity.com/blog/ https://altinity.com/blog/ [2] https://www.alibabacloud.com/blog/clickhouse-kernel-analysis-storage-structure-and-query-acceleration-of-mergetree_597727 https://www.alibabacloud.com/blog/clickhouse-kernel-analysis... [3] https://www.alibabacloud.com/blog/clickhouse-analysis-of-the-core-technologies-behind-cloud-hosting-to-cloud-native_599190 https://www.alibabacloud.com/blog/clickhouse-analysis-of-the...
scotty79 4y ago
Isn't the cause of the difference between MySQL and PostgreSQL in this particular case is that COUNT is (was?) implemented weirdly in PostgreSQL and was always slower than in MySQL? Can PostgreSQL respond to any query straight from index without touching the rows if the index contains all necessary fields?

175 points by Sirupsen 4y ago

Honestly im kind of surprised that they are even that close. I wonder if this changes at scale when the intersection is larger.

Sirupsen 4y ago
Ideally, I would add three graphs to the post: (1) Table size on the x-axis, and time on the y-axis for index merge vs composite index (2) Number of columns on the x-axis, and time on the y-axis for both (3) Number of final matches on the x-axis, and time on the y-axis for both But ran out of time and decided to test with the table size of 10M rows, and a 100-ish result set. That's in my experience a decent representation for what you might be doing with a relational database.

Lukas1994 4y ago

Good stuff! What's the size difference between the composite index vs the two separate indices?

Sirupsen 4y ago
I've added this to the article, thanks! Composite index (int64, int64): ~70 MiB in Postgres, ~350 MiB in MySQL Single index (int64): ~70 MiB in Postgres, ~240 MiB in MySQL If you assume the majority of an index are index entries of (int64, int64, int64) where the third number is some sort of identifier for the record on the heap, you'd expect this to be ~230 MiB. So Postgres does some compression very well here, and MySQL has a bit more overhead for its indexes it seems.
- fabian2k 4y ago
  Could be the deduplication newer Postgres versions have for B-Tree indexes: https://www.postgresql.org/docs/current/btree-implementation.html https://www.postgresql.org/docs/current/btree-implementation... > 67.4.3. Deduplication > A duplicate is a leaf page tuple (a tuple that points to a table row) where all indexed key columns have values that match corresponding column values from at least one other leaf page tuple in the same index. Duplicate tuples are quite common in practice. B-Tree indexes can use a special, space-efficient representation for duplicates when an optional technique is enabled: deduplication. > Deduplication works by periodically merging groups of duplicate tuples together, forming a single posting list tuple for each group. The column key value(s) only appear once in this representation. This is followed by a sorted array of TIDs that point to rows in the table. This significantly reduces the storage size of indexes where each value (or each distinct combination of column values) appears several times on average. The latency of queries can be reduced significantly. Overall query throughput may increase significantly. The overhead of routine index vacuuming may also be reduced significantly.
  - Sirupsen 4y ago
    Excellent, thank you! I'll add that to the article.
    - fabian2k 4y ago
      This is a guess on my part, though I think a plausible one. To verify you'd probably have to compare an index with unique values to one with many identical ones.
- libraryofbabel 4y ago
  As you mention in the article, this is small by modern hardware standards and means the indexes can be entirely held in memory. Curious how things look for much larger tables where the index has to be read from disk?
- masklinn 4y ago
  An other thing which might be of interest: what if you use convering indexes for the two single indexes? Is postgres able to do an index-only scan then, thanks to the coverage? Or does it decide to use only one index and filter based on the covered values?

magicalhippo 4y ago

A composite index can also be used for a partial index scan[1], so if you're frequently looking for just int100 as well as the int100,int1000 combination (as per the article's example), then a composite index int100,int1000 can be used for queries just filtering on int100. The order of the columns in the composite index might matter then. We got some nice savings by reordering columns in indexes and changing the join order in queries (our DB wasn't that smart) or adding a "useless" filters to the where clause, allowing us to consolidate multiple indexes into one composite one. [1]: might be using the wrong terminology here, I'm not talking about a partial index[2], but using only the first N dimensions of a M-dimensional index. [2]: https://www.postgresql.org/docs/current/indexes-partial.html https://www.postgresql.org/docs/current/indexes-partial.html

winrid 4y ago
There are some DBs where the order of fields doesn't matter in the compound index if you're just searching by one field (but of course is less efficient). I think Oracle supports this.
- magicalhippo 4y ago
  Good point, I reworded it to be more general. Can't recall seeing our DB being that clever.
- thom 4y ago
  Postgres is capable of doing this with some index types, but generally more slowly than a B-tree index being asked about its leftmost columns: https://www.postgresql.org/docs/current/indexes-multicolumn.html https://www.postgresql.org/docs/current/indexes-multicolumn.... Also worth noting that for very complex workloads that need to support arbitrary subsets of equality matches over columns, a Bloom filter might work best: https://www.postgresql.org/docs/current/bloom.html https://www.postgresql.org/docs/current/bloom.html
- mattashii 4y ago
  This dependz on the index type, but PostgreSQL also supports queries based on arbitrary attributes of multi-attribute indexes: both GIN and BRIN can be used for queries on any of the indexed expressions. Maybe eventually PG will also get index skip scans for btrees, which could allow for arbitrary columns searches in the btree; but we're not there yet by a large margin.

pdhborges 4y ago

For these 64-bit index entries we’d expect to have to scan roughly: index_row_size⋅rows=2⋅64bit⋅10^5=1.5MiB Where do the 10^5 rows come from? With a composite index and a point query doesn't the database scan just the 100 returned rows?

Sirupsen 4y ago
You're absolutely right! I forgot to move this around when I updated the article's structure. This is only relevant when doing the index merge. The article has been updated

deleted 4y ago

[deleted]

arynda 4y ago

Comparison on Clickhouse, also runs in about 30-40ms, however there's no indexing being used and this is a full-table scan. create table if not exists test_table ( id UInt64, text1 String, text2 String, int1000 UInt64, int100 UInt64, int10 UInt64, int10_2 UInt64 ) engine = MergeTree() order by (id) ; insert into test_table with repeat('b', 1024) as one_kib, repeat('b', 255) as bytes_255 select number as id, one_kib, bytes_255, rand() % 1000 as int1000, rand() % 100 as int100, rand() % 10 as int10, rand() % 10 as int10_2 from numbers(10e6) ; > select count(*) from test_table where int1000 = 1 and int100 = 1; ┌─count()─┐ │ 9949 │ └─────────┘ 1 row in set. Elapsed: 0.034 sec. Processed 10.00 million rows, 160.00 MB (290.93 million rows/s., 4.65 GB/s.) The same table but with 1B rows instead, runs in ~1800ms > select count(*) from test_table where int1000 = 1 and int100 = 1; ┌─count()─┐ │ 999831 │ └─────────┘ 1 row in set. Elapsed: 1.804 sec. Processed 1.00 billion rows, 16.00 GB (554.24 million rows/s., 8.87 GB/s.) [1] Converted the table create and insert logic from here: https://github.com/sirupsen/napkin-math/blob/master/newsletter/20-compound-vs-combining-indexes/test.rb https://github.com/sirupsen/napkin-math/blob/master/newslett...

Sirupsen 4y ago
Are you aware of a good write-up on how Clickhouse/other columnar databases do the intersection?
- twoodfin 4y ago
  One obvious way is to build a bitmap indexed by row position for each filter. Both the "&" intersect and the final bit count can be rocket fast on modern CPU vector units.
- arynda 4y ago
  Not in particular sorry, most of the good content I've found is on Altinity [1] and Alibaba's technical blogs [2][3]. These tend to be mostly focused on how the data itself is stored and how to use Clickhouse, but don't really dive into the specifics of how query processing is performed. [1] https://altinity.com/blog/ https://altinity.com/blog/ [2] https://www.alibabacloud.com/blog/clickhouse-kernel-analysis-storage-structure-and-query-acceleration-of-mergetree_597727 https://www.alibabacloud.com/blog/clickhouse-kernel-analysis... [3] https://www.alibabacloud.com/blog/clickhouse-analysis-of-the-core-technologies-behind-cloud-hosting-to-cloud-native_599190 https://www.alibabacloud.com/blog/clickhouse-analysis-of-the...

scotty79 4y ago

Isn't the cause of the difference between MySQL and PostgreSQL in this particular case is that COUNT is (was?) implemented weirdly in PostgreSQL and was always slower than in MySQL? Can PostgreSQL respond to any query straight from index without touching the rows if the index contains all necessary fields?