Postgres Pro
Downloads
Home   >   mailing lists

Thread: Re: [GENERAL] Backwards index scan

Re: [GENERAL] Backwards index scan

From
Tom Lane
Date:
[ reply redirected to a more appropriate list ]

Dmitry Tkach <dmitry@openratings.com> writes:
> I am not sure if this is really a bug, but it certainly looks like one 
> to me...

It's not a bug, but I agree that _bt_first can be inefficient if there
are lots of matching keys.

> This is because there are *lots* (a few million) of matches for x=10, 
> and _bt_first () scans through them *all* sequentually to get to the 
> last one.
> I understand that with the generic approach to operators in postgres it 
> is, probably, not very feasible to try and teach _bt_first () to handle 
> this situation automatically (it would need to know how to get 
> next/previous value for every indexable type)...

I think what we'd want is variant versions of _bt_search and _bt_binsrch
that locate the first entry greater than the specified target key,
rather than the first entry greater than or equal to it.  Given such
positioning, all the _bt_first cases that involve stepping over more
than one entry could be improved to require no more than one step.

Not sure whether it'd be better to make clone versions of these
functions, or to add a parameter to tell them which behavior is wanted.
        regards, tom lane

Re: [GENERAL] Backwards index scan

From
Bruce Momjian
Date:
Is this a TODO?

---------------------------------------------------------------------------

Tom Lane wrote:
> [ reply redirected to a more appropriate list ]
> 
> Dmitry Tkach <dmitry@openratings.com> writes:
> > I am not sure if this is really a bug, but it certainly looks like one 
> > to me...
> 
> It's not a bug, but I agree that _bt_first can be inefficient if there
> are lots of matching keys.
> 
> > This is because there are *lots* (a few million) of matches for x=10, 
> > and _bt_first () scans through them *all* sequentually to get to the 
> > last one.
> > I understand that with the generic approach to operators in postgres it 
> > is, probably, not very feasible to try and teach _bt_first () to handle 
> > this situation automatically (it would need to know how to get 
> > next/previous value for every indexable type)...
> 
> I think what we'd want is variant versions of _bt_search and _bt_binsrch
> that locate the first entry greater than the specified target key,
> rather than the first entry greater than or equal to it.  Given such
> positioning, all the _bt_first cases that involve stepping over more
> than one entry could be improved to require no more than one step.
> 
> Not sure whether it'd be better to make clone versions of these
> functions, or to add a parameter to tell them which behavior is wanted.
> 
>             regards, tom lane
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 6: Have you searched our list archives?
> 
>                http://archives.postgresql.org
> 

--  Bruce Momjian                        |  http://candle.pha.pa.us pgman@candle.pha.pa.us               |  (610)
359-1001+  If your life is a hard drive,     |  13 Roberts Road +  Christ can be your backup.        |  Newtown Square,
Pennsylvania19073

Re: [GENERAL] Backwards index scan

From
Tom Lane
Date:
Tom Lane <tgl@sss.pgh.pa.us> writes:
> Dmitry Tkach <dmitry@openratings.com> writes:
>> This is because there are *lots* (a few million) of matches for x=10, 
>> and _bt_first () scans through them *all* sequentually to get to the 
>> last one.

> It's not a bug, but I agree that _bt_first can be inefficient if there
> are lots of matching keys.

> I think what we'd want is variant versions of _bt_search and _bt_binsrch
> that locate the first entry greater than the specified target key,
> rather than the first entry greater than or equal to it.  Given such
> positioning, all the _bt_first cases that involve stepping over more
> than one entry could be improved to require no more than one step.

I have committed a fix into 7.5devel to do this properly.  I think this
is the last case wherein btree is unnecessarily inefficient for large
numbers of equal keys.
        regards, tom lane

Re: [GENERAL] Backwards index scan

From
Gaetano Mendola
Date:
Tom Lane wrote:


> I have committed a fix into 7.5devel to do this properly.  I think this
> is the last case wherein btree is unnecessarily inefficient for large
> numbers of equal keys.


Any chance to have it on 7.4.1 ?


Regards
Gaetano Mendola

Re: [GENERAL] Backwards index scan

From
Tom Lane
Date:
Gaetano Mendola <mendola@bigfoot.com> writes:
> Tom Lane wrote:
>> I have committed a fix into 7.5devel to do this properly.  I think this
>> is the last case wherein btree is unnecessarily inefficient for large
>> numbers of equal keys.

> Any chance to have it on 7.4.1 ?

No.  It's inadequately tested to go into a stable release, and anyway
I'm not sure what the interactions are with previous 7.5-only changes
for cross-datatype indexing.
        regards, tom lane