Thread: why choosing an hash index instead of the btree version even if the cost is lower?

Hi all,
I'm just having a doubt about the choice of the planner for a small
example table.
I've a table with a numeric column (integer), and I've created two
indexes on such column, one btree and one hash. The hash results much
larger as the btree, but what puzzles me is that executing an equality
simple query, the system chooses the hash index (that has a final cost
of 8984.08 while the btree index would have a final cost a little
lower (8901.94).

The only difference I can spot in the EXPLAIN plans is that the btree
index has an initial cost, but I don't think this is the reason, since
it should be the final cost what matters, right?

Now, even if the two costs are comparable, why does the optimizer
chooses to use the larger hash index? What am I missing here and where
do I have to dig?
Using EXPLAIN ANALYZE shows that the two indexes are very similar
timings, so while using the hash index is clearly not a wrong choice,
I'm wondering why preferring a bigger index.

Please note that the table has been manually ANALYZEd and is not clustered.


Thanks,
Luca


testdb=> select version();
version
----------------------------------------------------------------------------------------------------------
PostgreSQL 14.5 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 11.2.1
20220127 (Red Hat 11.2.1-9), 64-bit

testdb=> select relname, pg_size_pretty( pg_relation_size( oid )) from
pg_class where relname = 'articoli';
relname  | pg_size_pretty
----------+----------------
articoli | 134 MB

testdb=> \d articoli
Table "public.articoli"
Column   |  Type   | Collation | Nullable |           Default
-----------+---------+-----------+----------+------------------------------
pk        | integer |           | not null | generated always as identity
codice    | text    |           | not null |
prezzo    | integer |           |          | 0
citta     | text    |           |          |
magazzino | integer |           |          | 1
visibile  | boolean |           |          | true




testdb=> create index articoli_prezzo_idx on articoli(prezzo);
testdb=> create index articoli_prezzo_hash_idx on articoli using hash (prezzo);
CREATE INDEX
testdb=> select relname, pg_size_pretty( pg_relation_size( oid )) from
pg_class where relname like 'articoli%idx%';
relname          | pg_size_pretty
--------------------------+----------------
articoli_prezzo_idx      | 15 MB
articoli_prezzo_hash_idx | 47 MB


testdb=> explain select * from articoli where prezzo = 77;
QUERY PLAN
------------------------------------------------------------------------------------------------
Index Scan using articoli_prezzo_hash_idx on articoli
(cost=0.00..8984.08 rows=5033 width=28)
Index Cond: (prezzo = 77)



testdb=> begin;
BEGIN
testdb=*> drop index articoli_prezzo_hash_idx;
DROP INDEX
testdb=*> explain select * from articoli where prezzo = 77;
QUERY PLAN
-------------------------------------------------------------------------------------------
Index Scan using articoli_prezzo_idx on articoli  (cost=0.42..8901.94
rows=5033 width=28)
Index Cond: (prezzo = 77)
(2 rows)

testdb=*> rollback;
ROLLBACK



If it does matter, these is an excerpt from the pg_stats:

testdb=> select tablename, attname, n_distinct, most_common_vals,
most_common_freqs from pg_stats where tablename = 'articoli' and
attname = 'prezzo';
tablename | attname | n_distinct | most_common_vals |
most_common_freqs
-----------+---------+------------+------------------+-----------------------------------
articoli  | prezzo  |        200 | {62,147,154}     |
{0.0062666666,0.0060333335,0.006}


And here the EXPLAIN ANALYZE outputs:

testdb=> explain analyze select * from articoli where prezzo = 77;
                                                                 QUERY
PLAN

---------------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using articoli_prezzo_hash_idx on articoli
(cost=0.00..8971.95 rows=5026 width=27) (actual time=0.013..5.821
rows=5200 loops=1)
   Index Cond: (prezzo = 77)
 Planning Time: 0.108 ms
 Execution Time: 6.037 ms
(4 rows)

testdb=> begin;
BEGIN
testdb=*> drop index articoli_prezzo_hash_idx;
DROP INDEX
testdb=*> explain analyze select * from articoli where prezzo = 77;
                                                               QUERY
PLAN

----------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using articoli_prezzo_idx on articoli  (cost=0.42..8891.65
rows=5026 width=27) (actual time=0.034..6.561 rows=5200 loops=1)
   Index Cond: (prezzo = 77)
 Planning Time: 0.165 ms
 Execution Time: 6.843 ms
(4 rows)

testdb=*> rollback;
ROLLBACK

On 11/18/22 13:15, Luca Ferrari wrote:
> Hi all,
> I'm just having a doubt about the choice of the planner for a small
> example table.
> I've a table with a numeric column (integer), and I've created two
> indexes on such column, one btree and one hash. The hash results much
> larger as the btree, but what puzzles me is that executing an equality
> simple query, the system chooses the hash index (that has a final cost
> of 8984.08 while the btree index would have a final cost a little
> lower (8901.94).
> 
> The only difference I can spot in the EXPLAIN plans is that the btree
> index has an initial cost, but I don't think this is the reason, since
> it should be the final cost what matters, right?
> 
> Now, even if the two costs are comparable, why does the optimizer
> chooses to use the larger hash index? What am I missing here and where
> do I have to dig?
> Using EXPLAIN ANALYZE shows that the two indexes are very similar
> timings, so while using the hash index is clearly not a wrong choice,
> I'm wondering why preferring a bigger index.
> 
> Please note that the table has been manually ANALYZEd and is not clustered.
> 

My guess is this is due to STD_FUZZ_FACTOR, see [1] and [2].

That is, when comparing costs, we require the cost to be at least 1%,
because we have a cheapest path, and we're checking if it's worth
building another one (which is not free - we have to allocate stuff
etc.). And if the difference is tiny, it's not worth it.

In this case we have the indexscan for the hash index, with cost
8971.95, and we're considering to build indexacan path for the btree
index. We haven't built it yet, we only calculate cost 8891.65. But

    8971.95/8891.65 = 1.009

So it's close to 1.01, but just a little bit less. So we conclude it's
not worth building the second path, and we keep the hash index scan.

Now, this is based on the idea that

    small cost difference => small runtime difference

And from the timings you shared, this seems to be the case - 6.0 vs. 6.8
ms is fairly close.

I'd say btree/hash estimates this close are not very common in practice,
considering the costing formulas for the index types is quite different.
You may try tweaking the different cost parameters (e.g. operator cost,
random page cost) to make the difference larger.


regards

[1]
https://github.com/postgres/postgres/blob/master/src/backend/optimizer/util/pathnode.c#L51

[2]
https://github.com/postgres/postgres/blob/master/src/backend/optimizer/util/pathnode.c#L166

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Tomas Vondra <tomas.vondra@enterprisedb.com> writes:
> On 11/18/22 13:15, Luca Ferrari wrote:
>> I've a table with a numeric column (integer), and I've created two
>> indexes on such column, one btree and one hash. The hash results much
>> larger as the btree, but what puzzles me is that executing an equality
>> simple query, the system chooses the hash index (that has a final cost
>> of 8984.08 while the btree index would have a final cost a little
>> lower (8901.94).
>> 
>> The only difference I can spot in the EXPLAIN plans is that the btree
>> index has an initial cost, but I don't think this is the reason, since
>> it should be the final cost what matters, right?

> My guess is this is due to STD_FUZZ_FACTOR, see [1] and [2].

> That is, when comparing costs, we require the cost to be at least 1%,
> because we have a cheapest path, and we're checking if it's worth
> building another one (which is not free - we have to allocate stuff
> etc.). And if the difference is tiny, it's not worth it.

Even more to the point: if the total costs are fuzzily the same,
then the next point of comparison will be the startup costs,
which is where the hash index wins.  I'm not sure if it's quite
fair to give hash a zero startup cost; but it doesn't have to
descend a search tree, so it is fair that its startup cost is
less than btree's.

            regards, tom lane

On Fri, Nov 18, 2022 at 2:23 PM Tomas Vondra
<tomas.vondra@enterprisedb.com> wrote:
> That is, when comparing costs, we require the cost to be at least 1%,
> because we have a cheapest path, and we're checking if it's worth
> building another one (which is not free - we have to allocate stuff
> etc.). And if the difference is tiny, it's not worth it.
>
> In this case we have the indexscan for the hash index, with cost
> 8971.95, and we're considering to build indexacan path for the btree
> index. We haven't built it yet, we only calculate cost 8891.65. But
>
>     8971.95/8891.65 = 1.009
>
> So it's close to 1.01, but just a little bit less. So we conclude it's
> not worth building the second path, and we keep the hash index scan.
>


An excellent explanation, it totally does make sense to me and
explains what I felt (i.e., similar costs lead to a kind of equality
in choosing the index).


Thanks,
Luca

On Fri, Nov 18, 2022 at 3:55 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Even more to the point: if the total costs are fuzzily the same,
> then the next point of comparison will be the startup costs,
> which is where the hash index wins.

Thanks, it is clear now.

Luca