Re: proposed TODO: non-locking CREATE INDEX / REINDEX

On R, 2005-06-10 at 12:12 -0400, Tom Lane wrote:
> Hannu Krosing <hannu(at)skype(dot)net> writes:
> > As the number of tuples between CTID_INDEX_MIN and CTID_INDEX_MAX is
> > finite, they must be added in finite time, by which time the index will
> > be up-to-date and usable for querie planner. (i.e. (1) is done)
>
> ... and by which time, some more could have been added after
> CTID_INDEX_MAX.

But at that time they are inserted into the index as well, so that may
slow down the inserts, but they can't delay the index completion
indefinitely.

> Have you forgotten Zeno's paradox? I don't see a
> reason to assume the indexer can *ever* catch up --- it's entirely
> likely that adding a new unindexed row is faster than adding an index
> entry for it.

The same is true of doing a lazy vacuum over a table where tuples are
constantly added - there is no guarantee that the vacuum will ever
finish.

> > All tuples inserted after the initial fast-build-index has finished and
> > CTID_INDEX_MAX is fixed, are inserted into the index at the time of
> > inserting the tuple, like for any other index.
>
> This implies that you are hoping for an asynchronous change in the
> behavior of other processes, which you are not going to get without
> taking out locks, which is what you wanted to avoid.

One way to avoid locking, is to allow the "add tuple to index" routine
silently succeed if the index already has it.

Then we can announce the change in behaviour to running backends, wait
for all backends to confirm they have learned about it and only then
record CTID_INDEX_MAX.

This should work because all the backends which get the message start
adding their new tuples to both heap and index, and it is safe for them
to put tuples anywhere, including CTID_INDEX_MIN, those who have not yet
received it, will add between CTID_INDEX_MIN the final CTID_INDEX_MAX
and not the index.

The index entries for between CTID_INDEX_MIN and CTID_INDEX_MAX will be
added only after all running backends have confirmed the change.

And if those adding to heap and index happen to insert it between
CTID_INDEX_MIN and the eventual CTID_INDEX_MAX, then there is no harm
done, as the process inserting the index entry for it will silently
succeed if the index entry already exists.

--
Hannu Krosing <hannu(at)tm(dot)ee>