Thread: Refactoring the API for amgetmulti
One of the complaints I had about the bitmap index patch was the extent
to which it wants to modify (and largely create duplicate code paths in)
the existing executor support for bitmap scans. Now maybe I'm missing
something but I don't think that's where the value-add of this patch is.
It strikes me that some of the problem comes from the current definition
of the API for index AM getmulti functions: they're supposed to return
heap TIDs into a caller-supplied array. Now the only caller of
index_getmulti is nodeBitmapIndexscan.c, which simply turns around and
stuffs the TIDs into a tidbitmap --- and tbm_add_tuples() has no
calculation it can amortize across multiple tuples per call, so there's
no efficiencies of scale there. AFAICS the only thing this protocol is
doing for us is incurring an extra index AM call per thousand tuples
(or whatever the intermediate array size is).
What if we dropped the array convention, and simply passed the tidbitmap
object to the index AM's getmulti function, with the instructions "stuff
all the TIDs into this bitmap, and don't come back till you're done"?
For the existing index AMs this'd be only trivially different, but it
should result in some fractional savings of call overhead when scanning
a large number of index entries.
But for a bitmap index this is considerably more interesting, because
it could stuff its data into the tidbitmap without the overhead of
converting to an explicit array-of-TID format. In particular we could
imagine adding some entry points to tidbitmap.c that accept data in a
more friendly format, and that would all be between tidbitmap.c and the
bitmap index AM, without the need to invade large swaths of the executor
to make it happen.
Comments? For the existing AMs this is a pretty trivial change, and
I'd be willing to commit to making it happen before feature freeze if
it seems useful.
regards, tom lane
On Tue, 2006-07-25 at 18:49 -0400, Tom Lane wrote: > One of the complaints I had about the bitmap index patch was the extent > to which it wants to modify (and largely create duplicate code paths in) > the existing executor support for bitmap scans. Now maybe I'm missing > something but I don't think that's where the value-add of this patch is. Agreed > What if we dropped the array convention, and simply passed the tidbitmap > object to the index AM's getmulti function, with the instructions "stuff > all the TIDs into this bitmap, and don't come back till you're done"? > For the existing index AMs this'd be only trivially different, but it > should result in some fractional savings of call overhead when scanning > a large number of index entries. Good idea. > But for a bitmap index this is considerably more interesting, because > it could stuff its data into the tidbitmap without the overhead of > converting to an explicit array-of-TID format. In particular we could > imagine adding some entry points to tidbitmap.c that accept data in a > more friendly format, and that would all be between tidbitmap.c and the > bitmap index AM, without the need to invade large swaths of the executor > to make it happen. > > Comments? For the existing AMs this is a pretty trivial change, and > I'd be willing to commit to making it happen before feature freeze if > it seems useful. Bitmap indexes are worth having, but they must be well integrated. This sounds like the way to go. -- Simon Riggs EnterpriseDB http://www.enterprisedb.com
On Tue, Jul 25, 2006 at 06:49:02PM -0400, Tom Lane wrote: > What if we dropped the array convention, and simply passed the tidbitmap > object to the index AM's getmulti function, with the instructions "stuff > all the TIDs into this bitmap, and don't come back till you're done"? > For the existing index AMs this'd be only trivially different, but it > should result in some fractional savings of call overhead when scanning > a large number of index entries. Well, my only thoughtis that this pretty means you can't use index_getmulti for anything else. For example, when I was playing with async i/o I was using index_getmulti to get a list of TIDs, submitting all the read requests in parallel and then waiting on them. What you lose by storing straight into bitmaps is the *order*. Mind you, index_getmulti never supported backward scans either so its not a great loss but just thought I'd throw it in the rink. Have a nice day, -- Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/ > From each according to his ability. To each according to his ability to litigate.
Martijn van Oosterhout <kleptog@svana.org> writes:
> On Tue, Jul 25, 2006 at 06:49:02PM -0400, Tom Lane wrote:
>> What if we dropped the array convention, and simply passed the tidbitmap
>> object to the index AM's getmulti function, with the instructions "stuff
>> all the TIDs into this bitmap, and don't come back till you're done"?
> Well, my only thoughtis that this pretty means you can't use
> index_getmulti for anything else. For example, when I was playing with
> async i/o I was using index_getmulti to get a list of TIDs, submitting
> all the read requests in parallel and then waiting on them. What you
> lose by storing straight into bitmaps is the *order*.
Right, part of the reason for defining getmulti as it is was the idea
of preserving flexibility. However it's not apparent that that
flexibility is buying us anything.
What I'm actually thinking of doing is replacing amgetmulti with an
"amgetbitmap" entry point. We could leave amgetmulti in place alongside
that if there's any prospect of near-term use for it. But I kinda doubt
there will be, so I'm inclined to remove it instead. We can always
re-add it from the CVS archives if a use appears.
regards, tom lane
On Wed, Jul 26, 2006 at 11:37:01AM -0400, Tom Lane wrote: > Martijn van Oosterhout <kleptog@svana.org> writes: > > Well, my only thoughtis that this pretty means you can't use > > index_getmulti for anything else. For example, when I was playing with > > async i/o I was using index_getmulti to get a list of TIDs, submitting > > all the read requests in parallel and then waiting on them. What you > > lose by storing straight into bitmaps is the *order*. > > Right, part of the reason for defining getmulti as it is was the idea > of preserving flexibility. However it's not apparent that that > flexibility is buying us anything. Yeah, off the top of my head I can't think of any other uses. Since you're not able to do backwards scans with getmulti, there's really no advantage at all over stuff into a bitmap: you could never uses it anywhere requiring order anyway. I've considered whether it's worthwhile going to other way: getting the IndexScan executer node to uses getmulti to reduce index AM overhead. But that requires backward scan support also... Have a nice day, -- Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/ > From each according to his ability. To each according to his ability to litigate.
Martijn van Oosterhout <kleptog@svana.org> writes:
> I've considered whether it's worthwhile going to other way: getting the
> IndexScan executer node to uses getmulti to reduce index AM overhead.
> But that requires backward scan support also...
I think Heikki got most of the low-hanging fruit already with that patch
for page-at-a-time scanning in btree. There's some wasted overhead just
from multiple levels of function call, but I doubt it's really a big
deal anymore.
regards, tom lane