Difference between a composite index and an "equivalent" expression index?

Question

I need help understanding the difference between two kinds of indices:

• one that is applied on two columns
• and one that is applied on the concatenation of these two columns

It's best illustrated with an example of the tables I am dealing with:

create table potatos (
    potato_id integer not null,
    version_id integer not null,
    potato_name varchar not null,
    CONSTRAINT potatos_pkey PRIMARY KEY (potato_id, version_id)
);

Given this table, I should have a unique index because of the composite primary key.

Now consider this index:

create index potatos_composite_index on potatos ((potato_id || '|' || version_id));

With some sample data:

insert into potatos (potato_id, version_id, potato_name) 
SELECT generate_series(1,10000) AS potato_id, (generate_series(1,1000) * random())::int AS version_id, md5(random()::text) AS potato_name;

And these two queries with their results:

explain analyze
SELECT potatos.potato_id, potatos.version_id, potatos.potato_name 
FROM potatos
where
    (potatos.potato_id, potatos.version_id) IN ((1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60), (7, 70), (8, 80), (9, 90), (10, 100), (11, 110), (12, 120), (13, 130), (14, 140), (15, 150));

Result:

QUERY PLAN                                                                                                                                                                                                                                                     |
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
Bitmap Heap Scan on potatos  (cost=64.43..68.51 rows=1 width=41) (actual time=0.020..0.020 rows=0 loops=1)                                                                                                                                                     |
  Recheck Cond: (((potato_id = 1) AND (version_id = 10)) OR ((potato_id = 2) AND (version_id = 20)) OR ((potato_id = 3) AND (version_id = 30)) OR ((potato_id = 4) AND (version_id = 40)) OR ((potato_id = 5) AND (version_id = 50)) OR ((potato_id = 6) AND ( |
  ->  BitmapOr  (cost=64.43..64.43 rows=1 width=0) (actual time=0.020..0.020 rows=0 loops=1)                                                                                                                                                                   |
        ->  Bitmap Index Scan on potatos_pkey  (cost=0.00..4.29 rows=1 width=0) (actual time=0.007..0.007 rows=0 loops=1)                                                                                                                                      |
              Index Cond: ((potato_id = 1) AND (version_id = 10))                                                                                                                                                                                              |
        ->  Bitmap Index Scan on potatos_pkey  (cost=0.00..4.29 rows=1 width=0) (actual time=0.001..0.001 rows=0 loops=1)                                                                                                                                      |
              Index Cond: ((potato_id = 2) AND (version_id = 20))                                                                                                                                                                                              |
        ->  Bitmap Index Scan on potatos_pkey  (cost=0.00..4.29 rows=1 width=0) (actual time=0.001..0.001 rows=0 loops=1)                                                                                                                                      |
              Index Cond: ((potato_id = 3) AND (version_id = 30))                                                                                                                                                                                              |
        ->  Bitmap Index Scan on potatos_pkey  (cost=0.00..4.29 rows=1 width=0) (actual time=0.001..0.001 rows=0 loops=1)                                                                                                                                      |
              Index Cond: ((potato_id = 4) AND (version_id = 40))                                                                                                                                                                                              |
        ->  Bitmap Index Scan on potatos_pkey  (cost=0.00..4.29 rows=1 width=0) (actual time=0.001..0.001 rows=0 loops=1)                                                                                                                                      |
              Index Cond: ((potato_id = 5) AND (version_id = 50))                                                                                                                                                                                              |
        ->  Bitmap Index Scan on potatos_pkey  (cost=0.00..4.29 rows=1 width=0) (actual time=0.001..0.001 rows=0 loops=1)                                                                                                                                      |
              Index Cond: ((potato_id = 6) AND (version_id = 60))                                                                                                                                                                                              |
        ->  Bitmap Index Scan on potatos_pkey  (cost=0.00..4.29 rows=1 width=0) (actual time=0.001..0.001 rows=0 loops=1)                                                                                                                                      |
              Index Cond: ((potato_id = 7) AND (version_id = 70))                                                                                                                                                                                              |
        ->  Bitmap Index Scan on potatos_pkey  (cost=0.00..4.29 rows=1 width=0) (actual time=0.000..0.000 rows=0 loops=1)                                                                                                                                      |
              Index Cond: ((potato_id = 8) AND (version_id = 80))                                                                                                                                                                                              |
        ->  Bitmap Index Scan on potatos_pkey  (cost=0.00..4.29 rows=1 width=0) (actual time=0.001..0.001 rows=0 loops=1)                                                                                                                                      |
              Index Cond: ((potato_id = 9) AND (version_id = 90))                                                                                                                                                                                              |
        ->  Bitmap Index Scan on potatos_pkey  (cost=0.00..4.29 rows=1 width=0) (actual time=0.001..0.001 rows=0 loops=1)                                                                                                                                      |
              Index Cond: ((potato_id = 10) AND (version_id = 100))                                                                                                                                                                                            |
        ->  Bitmap Index Scan on potatos_pkey  (cost=0.00..4.29 rows=1 width=0) (actual time=0.001..0.001 rows=0 loops=1)                                                                                                                                      |
              Index Cond: ((potato_id = 11) AND (version_id = 110))                                                                                                                                                                                            |
        ->  Bitmap Index Scan on potatos_pkey  (cost=0.00..4.29 rows=1 width=0) (actual time=0.001..0.001 rows=0 loops=1)                                                                                                                                      |
              Index Cond: ((potato_id = 12) AND (version_id = 120))                                                                                                                                                                                            |
        ->  Bitmap Index Scan on potatos_pkey  (cost=0.00..4.29 rows=1 width=0) (actual time=0.000..0.000 rows=0 loops=1)                                                                                                                                      |
              Index Cond: ((potato_id = 13) AND (version_id = 130))                                                                                                                                                                                            |
        ->  Bitmap Index Scan on potatos_pkey  (cost=0.00..4.29 rows=1 width=0) (actual time=0.001..0.001 rows=0 loops=1)                                                                                                                                      |
              Index Cond: ((potato_id = 14) AND (version_id = 140))                                                                                                                                                                                            |
        ->  Bitmap Index Scan on potatos_pkey  (cost=0.00..4.29 rows=1 width=0) (actual time=0.001..0.001 rows=0 loops=1)                                                                                                                                      |
              Index Cond: ((potato_id = 15) AND (version_id = 150))                                                                                                                                                                                            |
Planning time: 0.149 ms                                                                                                                                                                                                                                        |
Execution time: 0.060 ms                                                                                                                                                                                                                                       |

Second query:

explain analyze
SELECT potatos.potato_id, potatos.version_id, potatos.potato_name 
FROM potatos
where
    (potatos.potato_id || '|' || potatos.version_id) IN ('1|10', '2|20', '3|30', '4|40', '5|50', '6|60', '7|70', '8|80', '9|90', '10|100', '11|110', '12|120', '13|130', '14|140', '15|150');

Result:

QUERY PLAN                                                                                                                                                                          |
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
Index Scan using potatos_composite_index on potatos  (cost=0.29..81.75 rows=15 width=41) (actual time=0.076..0.076 rows=0 loops=1)                                                  |
  Index Cond: ((((potato_id)::text || '|'::text) || (version_id)::text) = ANY ('{1|10,2|20,3|30,4|40,5|50,6|60,7|70,8|80,9|90,10|100,11|110,12|120,13|130,14|140,15|150}'::text[])) |
Planning time: 0.134 ms                                                                                                                                                             |
Execution time: 0.110 ms                                                                                                                                                            |

What I gathered so far is the following:

• The first query is using the primary key index several times because of the disjunction (same thing happens when using a sequence of ORs instead of the IN operator)

• The second query is using the new index because it cannot use the composite index due to the expression

• The second query will have an impact on the performance of the INSERT/UPDATE/DELETE and it will consume even more disk space, but let's assume this is an acceptable price for better performance

What I am having trouble with:

• shouldn't the second query perform better than using the composite index 15 times?

• Is this something that depends on the number of records in the database?

• Or is it due to the width of the index?

• What do the cost parameters mean in this context?

Update:

Tried it with one more index (assuming some arbitrary upper bound on version_id):

create index potatos_composite_int_index on potatos ((potato_id * 2000 + version_id));

And that query:

explain analyze
SELECT potatos.potato_id, potatos.version_id, potatos.potato_name 
FROM potatos
where
    (potatos.potato_id * 2000 + potatos.version_id) IN (1 * 2000 + 10, 2 * 2000 + 20, 3 * 2000 + 30, 4 * 2000 + 40, 5 * 2000 + 50, 6 * 2000 + 60, 7 * 2000 + 70, 8 * 2000 + 80, 9 * 2000 + 90, 10 * 2000 + 100, 11 * 2000 + 110, 12 * 2000 + 120, 13 * 2000 + 130, 14 * 2000 + 140, 15 * 2000 + 150);

Result:

QUERY PLAN                                                                                                                                                     |
---------------------------------------------------------------------------------------------------------------------------------------------------------------|
Index Scan using potatos_composite_int_index on potatos  (cost=0.29..56.54 rows=15 width=41) (actual time=0.025..0.025 rows=0 loops=1)                         |
  Index Cond: (((potato_id * 2000) + version_id) = ANY ('{2010,4020,6030,8040,10050,12060,14070,16080,18090,20100,22110,24120,26130,28140,30150}'::integer[])) |
Planning time: 0.139 ms                                                                                                                                        |
Execution time: 0.049 ms                                                                                                                                       |

And now the results make some sense, i.e. third better than first, both better than second.

More details as requested in comments: (tangentially related to the main question)

Given that I have a list of potatoes/tomatoes/etc. (each one in a different table) with their respective versions, I want to be able to get their information at that version from all of these tables. Which version to get is dictated by some other set of tables based on the business logic of the application. The two approaches I'm considering:

1. Query each table (potato/tomato/etc.) with a set of id/version tuples (similar to the above SELECT query)

2. Join those tables (potato/tomato/etc.) with the other tables where I'm getting the versions from.

While considering approach 1, I was wondering which of those indices are more appropriate and experimenting a bit. (hence that question)

Approach 2 I haven't tested yet, but might be worse that separate queries since it will involve a JOIN for every one of the (potato/tomato/etc.) tables.

Tested on Postgresql 9.5 (PostgreSQL 9.5.6 on x86_64-redhat-linux-gnu, compiled by gcc (GCC) 6.3.1 20161221 (Red Hat 6.3.1-1), 64-bit)

Answer 1

Here are the sizes for comparison, using \di+ potato*

 Schema |          Name           | Type  |  Owner   |  Table  |  Size  | Description 
--------+-------------------------+-------+----------+---------+--------+-------------
 public | potatos_composite_index | index | ecarroll | potatos | 296 kB | 
 public | potatos_pkey            | index | ecarroll | potatos | 240 kB | 

potatos_composite_index is

• badly ordered,
• a text type and comparison (rather than ints)
• larger
• badly named too: the pkey is technically composite and the "composite" one is technically not.

What you're calling composite has to scan all this stuff

'10|100', '11|110', '12|120', '13|130', '14|140', '15|150'

To scan '1|10' because it has to check that the second digit in the potato_id is not |.

Also keep in mind that the real composite indexes, like your pkey, are still only one index scan. The reason why it's doing a bitmap scan is so in one full scan of the index it can test all of those conditions. And why not, when the full index is 240kb.

Keep in mind here too that you're talking about a query that runs in 0.060 ms.