Re: Sequential scans

On Thu, 2007-05-03 at 19:27 +0100, Heikki Linnakangas wrote:
> I understand that the data structure keeps track of relations being
> scanned, with one entry per such relation. I think that's very good
> design, and I'm not suggesting to change that.
>
> But what's the right size for that? We don't know how many large tables
> there is in the database, so we can't use that. A hard-coded constant
> maybe? What would it be? I figured we could use NBackends, because there
> can't realistically be more than one large seq scan per backend going on
> at any point in time. That's an upper bound, in any real world
> application there's far less than that.

Ok, I understand you now. We'll choose the maximum size of the
table/list as the max_connections on startup.

> > Part of the reason I did this is because, with a Sync Scan, it seems
> > like there may be possible reasons to do multiple seq scans concurrently
> > in the same backend. This is completely contrived, but consider:
> >
> > SELECT * FROM bigtable UNION ALL SELECT * FROM bigtable;
> >
> > I'm not trying to argue for such a plan to exist right now, but if there
> > is a possibility that we'd want to create such plans in the future, I
> > think it's better to track by relation rather than by backend.
>
> Those two seqscans would be executed one after each other, not in
> parallel, so you would still have just one seq scan at any given point
> in time.

Right, I was just throwing out a hypothetical situation (if highly
contrived) in which it may help to do multiple scans at once. I think
this can be safely ignored for now though, since the planner would never
generate such a plan, and I can't think of a reasonable use case.

> >>> 100 is of course arbitrary, and that could grow or shrink automatically
> >>> at runtime.
> >> Except that it can't shrink, because we don't have any convenient moment
> >> to remove an entry from the list, other than dropping the least recently
> >> used entry out of the list when inserting a new one. And since it's in
> >> shared mem, the allocated size is fixed at boot up, so we can't grow it
> >> either.
> >>
> >
> > It can shrink when a new scan looks through the list and passes by
> > entries that don't need to be in the list.
>
> How do you identify an entry that doesn't need to be there?
>

Some type of clock-like algorithm where a counter was decremented when
an element is passed up and incremented when it's chosen might work.
It's probably easier to just use a hash table though.

> > I don't want to over-complicate things, so if you think having a hash
> > table is a better, simpler, or more readable design, I'll go with that
> > instead of the list-only approach. The only reason I suggested the list-
> > only approach was to see if the hash table was really gaining anything
> > for us. In practice, it will be quite rare that more than 10 different
> > big relations are being scanned at once, and I don't know how much of a
> > gain a hash table is when there are (in all but exceptional cases) only
> > a few entries.
>
> How about implementing the list-only approach first, since you're going
> to need the LRU list anyway, and we can add consider adding the hash
> table later?
>

Sounds good. Will do.

Regards,
Jeff Davis