Initial INSERT...ON DUPLICATE KEY UPDATE commit.

Gave some basic shape to parser structure.

Earlier work on INSERT...ON DUPLICATE KEY UPDATE

Thought on serializability

Clarify comment. Diff minimization.

proceed_with_insert() modularity fix

Make index_proceed consistent with other indexam stuff

Refine thoughts on serializability

Remove defensive measure within ExecEvalScalarVar()

Use PhasedLockState pointer directly

Remove -AssertMyBuffer()

Palloc()'d state

Tweak grammar for consistency

indexam stylistic refinements

Remove now redundant DEBUG_TRACE_BTREE_OPS traces

Comment on amcanunique contract within nbtinsert

Be cleverer about managing state memory

Allocate from top-level btree functions (i.e. routines referenced in catalogs).
This is consistent with existing code, but also allows us to cache an index
tuple for multi-phased inserts.

Free when no state too

Clarify btree/am responsibilites around lockState

lockState rename

Clean up DUPLICATE DO NOTHING representation

This affects parser, planner and executor structs, and some associated
functions.

Change in order in node structs necessitates catversion bump, as stored rules
invalidated.

Note tuple caching within ExecLockIndexTuples

Avoid re-building index tuple datums

Within ExecInsertIndexTuples, we can elide the need to build index tuple datums
if we know that a full index tuple is already cached within phased lock state.

Do not support ON DUPLICATE KEY DO NOTHING for deferrable unique indexes

Rethink lockstate variable names

Add isolationtest for multiple tuples

Exercises both when the original inserter commits and aborts.

In passing, expand on description of PhasedLockState.

Rename tests

Tweak commit/abort isolationtests

Add insert+ insert dup key isolation test

Tweak isolation test spelling

More isolation tests

Add insert/insert dup key multi-tuple interaction isolation tests. Perform
permutations analogous to the existing ones (blocker aborts, blocker proceeds),
but for multiple tuples where some may fail.

Add new isolation test

INSERT...ON DUPLICATE KEY DO NOTHING/regular UPDATE interactions test.

Omitted to add new isolation test to testing.sh

Add isolate_lock_release_bug.sh

Improve instrumentation for debugging race

Perform lock escalation in first phase of locking

Escalate from read to write buffer lock sooner, in first phase, before
committing to inserting.

This fixes the problem with "lock n is not held" frequently seen when running
the testing.sh pgbench script.

This regresses one of the isolation tests (concerning interactions with
UPDATEs) - that test now deadlocks. This is something that will have to be
investigated separately. Comment that out within testing.sh for now.

Refine criteria for uniqueness check

Only block on other transactions when page item has storage - otherwise, assume
uniqueness and proceed.

Expand upon page split race checking in testing script.

Temporarily hack pgbench for determinism

Consistent srandom seed value of 42 allows for consistent outcomes when running
regression tests. Page split always occur on the same value, so conditional
breakpoints can be set.

Remove isolate_lock_release_bug.sh

Refactor btree insertion. Commonality analysis.

Both for phased locking and regular insertion of btree index tuples, there is a
need to search the tree using a scankey to find an appropriate page, and then
to escalate to a write lock. So spin this off into a dedicated routine that is
called in two different places.

Further clean-up.

Add artificial delay within pgbench to allow us to connect with a debugger in
time. Numerous other debugging enhancements for the benefit of tracking down
pagesplit problem.

Preserve BTStack across amcanunique method calls.

When UNIQUE_CHECK_DUP, avoid redundant check in second phase. Stash it in new
void* private, opaque state variable (within public state).

Checkpoint progress on debugging pagesplit.

Added notes

Tighten up issues around _bt_check_unique heap visibility

Note on the heap and visibility

Indentation

Perform ExecLockIndexTuples as late as possible

Lock index tuples immediately prior to heap insertion.

The exclusive write lock acquired on a buffer by the btree code has the
potential to wreck havoc with triggers, which could easily self-deadlock when
interacting in any way with a locked index.

Note the semantics of ON DUPLICATE KEY DO NOTHING, and how it interacts with
before and after triggers.

Formatting of comment

Expand on index_proceed comments

Add new pageinspect testing infrastructure

Tweak pageinspect query

Improve int4_btree_inspect.sql

Various sanitizing measures. Handle 2 page (1 metapage + 1 page) btrees.

Add duplicate instances to page inspect query

Cache first legal offset from first phase.

This doesn't fix the page-split bug, but it is a related buglet.

Add 'heap matches' column

Unregress update isolation tests. Rethink offset fallback.

Now, when there is no existing item on page (when offset is past end of page),
we invoke _bt_check_unique with a special "Don't look at heap" argument for our
ctid-lacking IndexTuple. This doesn't actually fix the page-split bug, but it's
very likely a prerequisite to doing so.

The update isolation tests have been broken for a few days now, but are fixed
in this commit.

Note on releasing buffers

Assert insertion item pointer is valid

Clean-up and rearrange tests a bit

Rename testing directory

Remove trace instrumentation.

This is not likely to be useful again.  If it turns out to be, I can always
revert this commit.

Fix bug seen with multiple unique indexes.

Previously, with inserts into tables with multiple unique indexes, it was
trivial to cause deadlocks and buffer ref leaks because there was a built-in
assumption that unlocking would occur either when we decided not to insert, or
after actually inserting. This did not account for the fact that there could be
disagreement among different unique indexes concerning the uniqueness of a
particular tuple.

Add a new mechanism for having the core system call into an amcanunique AM and
release write locks for some unique indexes as needed. Add some smoke testing
for that system in the form of a new isolation test.

Tweak

Make much phased lock state btree private

This has the useful property of minimizing the assumptions surrounding what
methods amcanunique AMs use to do phased locking. It might also simplify some
aspects of memory management slightly.

Comment clean-up

In passing, give up as soon as we have one would-be unique index violation -
that is sufficient.

Relocate genam functions

Clarify SSI issues

Simplify approach to uniqueness checking.

_bt_check_unique should never be passed existing tuples - this confers no
advantage over always carefully checking indexTuple with NULL heap ptr.

In passing, CheckForSerializableConflictIn() calls added in order to make the
DO NOTHING case care about SSI.

Tweaks

Invent "speculative insertion" nomenclature

Internally (essentially at layers lower than the high-level modify table
executor code) we now consistently refer to the infrastructure the feature
provides as offering "speculative insertion". This anticipates its use as
UPSERT infrastructure, and seems more consistent with extant code.

Missed one

Adjust grammar %type name

Consolidate isolationtest files for commit/abort

Notes on SSI

Tweak btinsert comments

Address previous concern with SSI

Address concerns about SSI

We always need to call _bt_lock if predicate locks are held, even if we already
know that we'll never proceed.

pg_stat_statements

Fix bugs with non-unique index tuple insertion

Rename function for consistency

Rename local variable

pgindent

Worry more about deadlocks

We now take the precaution of first acquiring buffer exclusive locks in reverse
order, so that when they are subsequently released in the usual order by either
insertion or callbacks, we can be sure that buffer locks are released in the
opposite order to the order they were originally acquired in. This will prevent
deadlock a concurrently vacuuming process, for example.

Be more careful about giving up on locking

Describe a more broad set of circumstances in which this is okay than the
amcanunique method doesn't support predicate locks. It's likely to help
performance a lot at read committed isolation level.

Remove references to old enum constant

Make speculative insertion abstraction prevalent

With this commit, the speculative insertion abstraction exists in all parts of
the system - it isn't appropriate for the executor code to refer to specific
types of upsert clauses. Prefer talk of an abstract policy with regards to how
to handle duplicates.

This has the effect of fixing a bug where with ON DUPLICATE KEY DO NOTHING,
uniqueness would be spuriously enforced for non-unique indexes.

Misc clean-up of executor functions.

Bump catversion due to change in stored rules representation.

Tweak comment

Forbid speculative insertion into catalogs

The possibility of creating a deadlock due to exclusive-locking an insertion
point into an index, and subsequent innocently accessing the catalogs is spooky
and hard to reason about --- even if I get it right now, things may change in
the future. So simply forbid speculative index insertion of catalogs.

In passing, add extensive commentary about why we don't do better with BEFORE
ROW triggers.

Tweak

Standardize nomenclature around second phase

Tidy up comments, rename index_proceed to reflect its responsibility to release
"insertion point" locks.

ereport rather than elog catalog insertion error

Inserting into catalogs isn't out of the question - it's not a "can't happen"
failure - so give it a proper ereport call instead.

Use higher level IsSystemRelation() facility

Typo

Move speculative inserion catalog check into nodeModifyTable.c

This seems to respect modularity better.

Clarification

Acknowledge SSI uncertainty

I'm not totally confident that the SSI-related calls within _btlock are truly
all necessary in the event of early indication of a duplicate. This is a
question that I may or may not get the opportunity to look at in more detail
before submission.

Now it's spelt INSERT...ON DUPLICATE KEY IGNORE

I felt that INSERT...ON DUPLICATE KEY DO NOTHING has too much baggage from
CREATE RULE. So create a new unreserved keyword, IGNORE, and use this syntax
instead.

Remove old comment

INSERT...ON DUPLICATE KEY IGNORE RETURNING REJECTS

It was previously possible to have RETURNING return "affected rows" in respect
of all INSERT STATEMENTS; this could easily be used to indicate which rows were
successfully inserted when combined with ON DUPLICATE KEY IGNORE.

However, in practice I anticipate that it'll be more useful to return rows that
were rejected, as when inserting data in bulk of dubious quality. So create a
new parsenode representation of RETURNING, ReturningClause, and have that carry
around whether or not the new REJECTS reserved keyword was specified.  If so,
return rows that were rejected, not affected by the speculative insertion -
exactly the inverse of the default.

This is only meaningful in the context of INSERT...ON DUPLICATE KEY IGNORE.

Case tweak

Remove default in case statements.

In passing, free state earlier, and move code comments around so things are
noted at the appropriate level.

Remove most isolation tests from schedule

These will not make it into official submission, but will continue to be useful
for detecting regressions for the time being.

Variability analysis

Refactor code common to ExecInsertIndexTuples and ExecLockIndexTuples into new
function, ExecCheckPartialPredicate.

Whitespace

Remove page inspect test code

This hasn't been useful in some time. If it becomes useful again, there's
always git revert...

Be more careful about freeing resources earlier

Move comment

Move comment again

Don't allow the return of bogus system columns

Tweak

Remove non-submission testing stuff

Correct comment

Revert "Remove non-submission testing stuff"

This reverts commit 81235d98baa70884fa7e9c1d572c08766f7bd475.

Prevent waiting on another transaction.

This could sometimes occur with previous one or more previous indexes' buffer
locks in the second or subsequent index locked.

In passing, clean-up AM definitions so lock function comes first, just like
everywhere else. Bump catversion.

Ordering

Checkpoint progress on KEY LOCK FOR UPDATE variant

This code is of pretty low quality, and should not be taken as representative
of a later submission.

Tweaks to grammar

Checkpoint progress on row locking

Handle more cases by blocking on other xids.

Clean-up htid retrieval logic

Comment clean-up

Firm up on extra SSI checks

Consolidate ExecInsert switch

Explicitly initialize spec clause everywhere

Re-order again

Don't hold value locks so long

Assume that it isn't useful to hold value locks when locking rows. Immediately
release value locks when it's clear that an insertion won't proceed.

Checkpoint progress on new LWLock semantics

These allow buffer locks to be weakened and strengthened under specific
circumstances, and will allows us to not sit on an exclusive lock during heap
insertion - a shared buffer lock ought to be sufficient.

Isolation tests pass, but more intense pgbench testing still falls over.

Fix a few more obvious LWLockStrengthen bugs

This new approach mostly works, but there are still some bugs under a lot of
concurrent load.

Add useful assertions

Remove spurious SpinLockRelease

Remove old probes. Make weakening release others.

Don't manipulate interrupt handling

Tweak cut-in-line logic

Comment tweak

Check uniqueness redundantly in second phase

Formalize that offset isn't recorded

Change re-verification assertions into a PANIC

As long as we are going to the trouble of re-verifying, we might as well get
the benefit of additional error checking with assertions off.

PANIC is too severe

Round of comment editorialization

Tweak test

Revert "Formalize that offset isn't recorded"

This reverts commit 65ce242021474032a28fa0f48f2d0fdee0bdb39e.

Conflicts:
	dup_key_testing/maintests.sh
	src/backend/access/nbtree/nbtinsert.c

Checkpoint progress on LWLock strengthening

This appears to work now. Haven't been able to break this.

Remove unnecessary for(;;)

Review round

ExecInsert() tweaks

Rename files

Rename file in tests

Add lock for update isolation tests

Remove crud

Tweak

Removing dev testing infrastructure

Further tweaks

Simplify LWLockRelease()

Revert "Removing dev testing infrastructure"

This reverts commit c8e7570d3ea9e7782f164a6bf399b604fa061996.

Revert "Simplify LWLockRelease()"

This reverts commit 856750e4ea6d2f4859761a9341991ed6ce9ffd69.

Tweaks

Fix LWLockWeaken to match LWLockRelease closer.

This appears to reduce the frequency of deadlock.

Set releaseOk = false upon removing strengthening waiter.

In passing, have test script loop with smallish pgbench workload with lots of
clients.  This seems to most reliably create deadlock.

Tweak strength ordering

Always have strengthener go to front of queue

Code shouldn't have matched LWLockAcquire in second and subsequent iterations
of loop.

In passing, add new smoke testing pgbench script to simulate complex
transaction with upsert.

v3 submission

Revert "v3 submission"

This reverts commit de1e2cc54f41902cd7c9a9b853dabfb7ed2eebdf.

Comment tweaks

First cut at doing TOASTing without value locks

This is probably quite broken in the IGNORE case; need to think about the
visibility of the items in the TOAST table, and how VACUUM ought to handle them
- we could end up with bloat in the TOAST table that cannot be VACUUMed because
  the originating transaction committed.

Style tweaks

Tweak

Big clean-up of row locking - follow chain

Update retry comments

First cut at modifying MVCC semantics

Regular MVCC snapshots now see rows only locked by the snapshot's own XID, iff
the originating xact committed.  When the row is updated, the original row
version is no longer "just locked", and thus the original row isn't visible.

The idea here is to solve the problem of no row being visible to our snapshot,
even as it is locked.

Fix formatting

rough

cleanup

Re-order prototype

Restructure special MVCC snapshot rule

Tighten up seriazable behavior

Remove some ill-advised serialization stuff

Cut deadlock comment

Expert
v4 submission
Fix oid clash
protect against invisible tuple locking; PANIC
Visibility bug
Add ctid projection

For parity with Heikki's patch, add ability to project out ctid column on
conflicter physical tuple.  This is an abuse of notation, because it isn't the
ctid of the proposed-for-insertion tuple, which, as a reject, does not and will
not have a ctid in any meaningful sense.
Add same test cases
Tweak comment wording
min testcase
same testcase as 2-heikki
HeapTupleSatifiesUpdate() visibility hack
More useful testcase
change test case to serial
Revert "change test case to serial"

This reverts commit 2c9e5f85e66a676f2f17a29debfc8ca4b29e989c.
Fix? test case
Simple testcase
Is special HeapTupleSatisfiesUpdate rule really necessary?
Testcase with probable unprincipled deadlocking, instrumentation to count processed tuples

Conflicts:
	src/backend/executor/execMain.c
	src/backend/executor/nodeModifyTable.c
unlogged testcase
Explicit scale