Dimitri Fontaine <dimitri@2ndQuadrant.fr> writes:
> Alvaro Herrera <alvherre@2ndquadrant.com> writes:
>> Could we use some adaptive mechanism here? Say we use a list for the
>> first ten entries, and if an eleventh one comes in, we create a hash
>> table for that one and all subsequent ones. All future calls would
>> have to examine both the list for the first few and then the hash table.
> Is it necessary to do so? Do we know for sure that a 10 elements hash
> table is slower than a 10 elements list when only doing key based
> lookups, for the object data type we're interested into here?
Well, we'd want to do some testing to choose the cutover point.
Personally I'd bet on that point being quite a bit higher than ten,
for the case that sequence.c is using where the key being compared is
just an OID. You can compare a lot of OIDs in the time it takes
dynahash.c to do something.
(I think the above sketch is wrong in detail, btw. What we should do
once we decide to create a hash table is move all the existing entries
into the hash table, not continue to scan a list for them. There's a
similar case in the planner for tracking join RelOptInfos.)
regards, tom lane