Implement sharable row-level locks, and use them for foreign key references

to eliminate unnecessary deadlocks.  This commit adds SELECT ... FOR SHARE
paralleling SELECT ... FOR UPDATE.  The implementation uses a new SLRU
data structure (managed much like pg_subtrans) to represent multiple-
transaction-ID sets.  When more than one transaction is holding a shared
lock on a particular row, we create a MultiXactId representing that set
of transactions and store its ID in the row's XMAX.  This scheme allows
an effectively unlimited number of row locks, just as we did before,
while not costing any extra overhead except when a shared lock actually
has to be shared.   Still TODO: use the regular lock manager to control
the grant order when multiple backends are waiting for a row lock.

Alvaro Herrera and Tom Lane.

5 files changed, 129 insertions, 63 deletions

diff --git a/doc/src/sgml/ref/grant.sgml b/doc/src/sgml/ref/grant.sgml
index 5e9adaa805..45f384f486 100644
--- a/doc/src/sgml/ref/grant.sgml
+++ b/doc/src/sgml/ref/grant.sgml
@@ -1,5 +1,5 @@
 <!--
-$PostgreSQL: pgsql/doc/src/sgml/ref/grant.sgml,v 1.45 2005/01/22 23:22:18 momjian Exp $
+$PostgreSQL: pgsql/doc/src/sgml/ref/grant.sgml,v 1.46 2005/04/28 21:47:09 tgl Exp $
 PostgreSQL documentation
 -->
 
@@ -131,9 +131,10 @@ GRANT { CREATE | ALL [ PRIVILEGES ] }
      <term>UPDATE</term>
      <listitem>
       <para>
-       Allows <xref linkend="sql-update" endterm="sql-update-title"> of any column of the
-       specified table.  <literal>SELECT ... FOR UPDATE</literal>
-       also requires this privilege (besides the
+       Allows <xref linkend="sql-update" endterm="sql-update-title"> of any
+       column of the specified table.  <literal>SELECT ... FOR UPDATE</literal>
+       and <literal>SELECT ... FOR SHARE</literal>
+       also require this privilege (besides the
        <literal>SELECT</literal> privilege).  For sequences, this
        privilege allows the use of the <function>nextval</function> and
        <function>setval</function> functions.
diff --git a/doc/src/sgml/ref/lock.sgml b/doc/src/sgml/ref/lock.sgml
index 3c762ac48b..9dfa85b180 100644
--- a/doc/src/sgml/ref/lock.sgml
+++ b/doc/src/sgml/ref/lock.sgml
@@ -1,5 +1,5 @@
 <!--
-$PostgreSQL: pgsql/doc/src/sgml/ref/lock.sgml,v 1.46 2005/01/22 23:22:19 momjian Exp $
+$PostgreSQL: pgsql/doc/src/sgml/ref/lock.sgml,v 1.47 2005/04/28 21:47:10 tgl Exp $
 PostgreSQL documentation
 -->
 
@@ -177,8 +177,8 @@ where <replaceable class="PARAMETER">lockmode</replaceable> is one of:
    <command>LOCK TABLE</> is concerned, differing only in the rules
    about which modes conflict with which. For information on how to
    acquire an actual row-level lock, see <xref linkend="locking-rows">
-   and the <xref linkend="sql-for-update"
-   endterm="sql-for-update-title"> in the <command>SELECT</command>
+   and the <xref linkend="sql-for-update-share"
+   endterm="sql-for-update-share-title"> in the <command>SELECT</command>
    reference documentation.
   </para>
  </refsect1>
diff --git a/doc/src/sgml/ref/pg_resetxlog.sgml b/doc/src/sgml/ref/pg_resetxlog.sgml
index 6651a0b588..f5915adacd 100644
--- a/doc/src/sgml/ref/pg_resetxlog.sgml
+++ b/doc/src/sgml/ref/pg_resetxlog.sgml
@@ -1,5 +1,5 @@
 <!--
-$PostgreSQL: pgsql/doc/src/sgml/ref/pg_resetxlog.sgml,v 1.9 2004/12/20 01:42:09 tgl Exp $
+$PostgreSQL: pgsql/doc/src/sgml/ref/pg_resetxlog.sgml,v 1.10 2005/04/28 21:47:10 tgl Exp $
 PostgreSQL documentation
 -->
 
@@ -22,6 +22,7 @@ PostgreSQL documentation
    <arg> -n </arg>
    <arg> -o <replaceable class="parameter">oid</replaceable> </arg>
    <arg> -x <replaceable class="parameter">xid</replaceable> </arg>
+   <arg> -m <replaceable class="parameter">mxid</replaceable> </arg>
    <arg> -l <replaceable class="parameter">timelineid</replaceable>,<replaceable class="parameter">fileid</replaceable>,<replaceable class="parameter">seg</replaceable> </arg>
    <arg choice="plain"><replaceable>datadir</replaceable></arg>
   </cmdsynopsis>
@@ -73,34 +74,65 @@ PostgreSQL documentation
   </para>
 
   <para>
-   The <literal>-o</>, <literal>-x</>, and <literal>-l</> switches allow
-   the next OID, next transaction ID, and WAL starting address values to
+   The <literal>-o</>, <literal>-x</>, <literal>-m</>, and <literal>-l</>
+   switches allow the next OID, next transaction ID, next multi-transaction
+   ID, and WAL starting address values to
    be set manually.  These are only needed when
    <command>pg_resetxlog</command> is unable to determine appropriate values
-   by reading <filename>pg_control</>.  A safe value for the
-   next transaction ID may be determined by looking for the numerically largest
-   file name in the directory <filename>pg_clog</> under the data directory,
-   adding one,
-   and then multiplying by 1048576.  Note that the file names are in
-   hexadecimal.  It is usually easiest to specify the switch value in
-   hexadecimal too. For example, if <filename>0011</> is the largest entry
-   in <filename>pg_clog</>, <literal>-x 0x1200000</> will work (five trailing
-   zeroes provide the proper multiplier).
-   The WAL starting address should be
-   larger than any file name currently existing in
-   the directory <filename>pg_xlog</> under the data directory.
-   These names are also in hexadecimal and have three parts.  The first
-   part is the <quote>timeline ID</> and should usually be kept the same.
-   Do not choose a value larger than 255 (<literal>0xFF</>) for the third
-   part; instead increment the second part and reset the third part to 0.
-   For example, if <filename>00000001000000320000004A</> is the
-   largest entry in <filename>pg_xlog</>, <literal>-l 0x1,0x32,0x4B</> will
-   work; but if the largest entry is
-   <filename>000000010000003A000000FF</>, choose <literal>-l 0x1,0x3B,0x0</>
-   or more.
-   There is no comparably easy way to determine a next OID that's beyond
-   the largest one in the database, but fortunately it is not critical to
-   get the next-OID setting right.
+   by reading <filename>pg_control</>.  Safe values may be determined as
+   follows:
+
+   <itemizedlist>
+    <listitem>
+     <para>
+      A safe value for the next transaction ID (<literal>-x</>)
+      may be determined by looking for the numerically largest
+      file name in the directory <filename>pg_clog</> under the data directory,
+      adding one,
+      and then multiplying by 1048576.  Note that the file names are in
+      hexadecimal.  It is usually easiest to specify the switch value in
+      hexadecimal too. For example, if <filename>0011</> is the largest entry
+      in <filename>pg_clog</>, <literal>-x 0x1200000</> will work (five
+      trailing zeroes provide the proper multiplier).
+     </para>
+    </listitem>
+
+    <listitem>
+     <para>
+      A safe value for the next multi-transaction ID (<literal>-m</>)
+      may be determined by looking for the numerically largest
+      file name in the directory <filename>pg_multixact/offsets</> under the
+      data directory, adding one, and then multiplying by 65536.  As above,
+      the file names are in hexadecimal, so the easiest way to do this is to
+      specify the switch value in hexadecimal and add four zeroes.
+     </para>
+    </listitem>
+
+    <listitem>
+     <para>
+      The WAL starting address (<literal>-l</>) should be
+      larger than any file name currently existing in
+      the directory <filename>pg_xlog</> under the data directory.
+      These names are also in hexadecimal and have three parts.  The first
+      part is the <quote>timeline ID</> and should usually be kept the same.
+      Do not choose a value larger than 255 (<literal>0xFF</>) for the third
+      part; instead increment the second part and reset the third part to 0.
+      For example, if <filename>00000001000000320000004A</> is the
+      largest entry in <filename>pg_xlog</>, <literal>-l 0x1,0x32,0x4B</> will
+      work; but if the largest entry is
+      <filename>000000010000003A000000FF</>, choose <literal>-l 0x1,0x3B,0x0</>
+      or more.
+     </para>
+    </listitem>
+
+    <listitem>
+     <para>
+      There is no comparably easy way to determine a next OID that's beyond
+      the largest one in the database, but fortunately it is not critical to
+      get the next-OID setting right.
+     </para>
+    </listitem>
+   </itemizedlist>
   </para>
 
   <para>
diff --git a/doc/src/sgml/ref/select.sgml b/doc/src/sgml/ref/select.sgml
index 78e591acd7..9b8b90bb16 100644
--- a/doc/src/sgml/ref/select.sgml
+++ b/doc/src/sgml/ref/select.sgml
@@ -1,5 +1,5 @@
 <!--
-$PostgreSQL: pgsql/doc/src/sgml/ref/select.sgml,v 1.85 2005/04/22 15:32:58 momjian Exp $
+$PostgreSQL: pgsql/doc/src/sgml/ref/select.sgml,v 1.86 2005/04/28 21:47:10 tgl Exp $
 PostgreSQL documentation
 -->
 
@@ -30,7 +30,7 @@ SELECT [ ALL | DISTINCT [ ON ( <replaceable class="parameter">expression</replac
     [ ORDER BY <replaceable class="parameter">expression</replaceable> [ ASC | DESC | USING <replaceable class="parameter">operator</replaceable> ] [, ...] ]
     [ LIMIT { <replaceable class="parameter">count</replaceable> | ALL } ]
     [ OFFSET <replaceable class="parameter">start</replaceable> ]
-    [ FOR UPDATE [ OF <replaceable class="parameter">table_name</replaceable> [, ...] ] ]
+    [ FOR { UPDATE | SHARE } [ OF <replaceable class="parameter">table_name</replaceable> [, ...] ] ]
 
 where <replaceable class="parameter">from_item</replaceable> can be one of:
 
@@ -142,10 +142,11 @@ where <replaceable class="parameter">from_item</replaceable> can be one of:
 
     <listitem>
      <para>
-      The <literal>FOR UPDATE</literal> clause causes the
-      <command>SELECT</command> statement to lock the selected rows
-      against concurrent updates.  (See <xref linkend="sql-for-update"
-      endterm="sql-for-update-title"> below.)
+      If the <literal>FOR UPDATE</literal> or <literal>FOR SHARE</literal>
+      clause is specified, the
+      <command>SELECT</command> statement locks the selected rows
+      against concurrent updates.  (See <xref linkend="sql-for-update-share"
+      endterm="sql-for-update-share-title"> below.)
      </para>
     </listitem>
    </orderedlist>
@@ -153,7 +154,8 @@ where <replaceable class="parameter">from_item</replaceable> can be one of:
    
   <para>
    You must have <literal>SELECT</literal> privilege on a table to
-   read its values.  The use of <literal>FOR UPDATE</literal> requires
+   read its values.  The use of <literal>FOR UPDATE</literal> or
+   <literal>FOR SHARE</literal> requires
    <literal>UPDATE</literal> privilege as well.
   </para>
  </refsect1>
@@ -503,7 +505,8 @@ HAVING <replaceable class="parameter">condition</replaceable>
 </synopsis>
     <replaceable class="parameter">select_statement</replaceable> is
     any <command>SELECT</command> statement without an <literal>ORDER
-    BY</>, <literal>LIMIT</>, or <literal>FOR UPDATE</literal> clause.
+    BY</>, <literal>LIMIT</>, <literal>FOR UPDATE</literal>, or
+    <literal>FOR SHARE</literal> clause. 
     (<literal>ORDER BY</> and <literal>LIMIT</> can be attached to a
     subexpression if it is enclosed in parentheses.  Without
     parentheses, these clauses will be taken to apply to the result of
@@ -537,8 +540,9 @@ HAVING <replaceable class="parameter">condition</replaceable>
    </para>
     
    <para>
-    Currently, <literal>FOR UPDATE</> may not be specified either for
-    a <literal>UNION</> result or for any input of a <literal>UNION</>.
+    Currently, <literal>FOR UPDATE</> and <literal>FOR SHARE</> may not be
+    specified either for a <literal>UNION</> result or for any input of a
+    <literal>UNION</>.
    </para>
   </refsect2>
 
@@ -552,7 +556,8 @@ HAVING <replaceable class="parameter">condition</replaceable>
 </synopsis>
     <replaceable class="parameter">select_statement</replaceable> is
     any <command>SELECT</command> statement without an <literal>ORDER
-    BY</>, <literal>LIMIT</>, or <literal>FOR UPDATE</literal> clause.
+    BY</>, <literal>LIMIT</>, <literal>FOR UPDATE</literal>, or
+    <literal>FOR SHARE</literal> clause.
    </para>
 
    <para>
@@ -581,8 +586,9 @@ HAVING <replaceable class="parameter">condition</replaceable>
    </para>
     
    <para>
-    Currently, <literal>FOR UPDATE</> may not be specified either for
-    an <literal>INTERSECT</> result or for any input of an <literal>INTERSECT</>.
+    Currently, <literal>FOR UPDATE</> and <literal>FOR SHARE</> may not be
+    specified either for an <literal>INTERSECT</> result or for any input of
+    an <literal>INTERSECT</>.
    </para>
   </refsect2>
 
@@ -596,7 +602,8 @@ HAVING <replaceable class="parameter">condition</replaceable>
 </synopsis>
     <replaceable class="parameter">select_statement</replaceable> is
     any <command>SELECT</command> statement without an <literal>ORDER
-    BY</>, <literal>LIMIT</>, or <literal>FOR UPDATE</literal> clause.
+    BY</>, <literal>LIMIT</>, <literal>FOR UPDATE</literal>, or
+    <literal>FOR SHARE</literal> clause.
    </para>
 
    <para>
@@ -621,8 +628,9 @@ HAVING <replaceable class="parameter">condition</replaceable>
    </para>
     
    <para>
-    Currently, <literal>FOR UPDATE</> may not be specified either for
-    an <literal>EXCEPT</> result or for any input of an <literal>EXCEPT</>.
+    Currently, <literal>FOR UPDATE</> and <literal>FOR SHARE</> may not be
+    specified either for an <literal>EXCEPT</> result or for any input of
+    an <literal>EXCEPT</>.
    </para>
   </refsect2>
 
@@ -789,8 +797,8 @@ OFFSET <replaceable class="parameter">start</replaceable>
    </para>
   </refsect2>
 
-  <refsect2 id="SQL-FOR-UPDATE">
-   <title id="sql-for-update-title"><literal>FOR UPDATE</literal> Clause</title>
+  <refsect2 id="SQL-FOR-UPDATE-SHARE">
+   <title id="sql-for-update-share-title"><literal>FOR UPDATE</literal>/<literal>FOR SHARE</literal> Clause</title>
 
    <para>
     The <literal>FOR UPDATE</literal> clause has this form:
@@ -800,6 +808,13 @@ FOR UPDATE [ OF <replaceable class="parameter">table_name</replaceable> [, ...]
    </para>
 
    <para>
+    The closely related <literal>FOR SHARE</literal> clause has this form:
+<synopsis>
+FOR SHARE [ OF <replaceable class="parameter">table_name</replaceable> [, ...] ]
+</synopsis>
+   </para>
+
+   <para>
     <literal>FOR UPDATE</literal> causes the rows retrieved by the
     <command>SELECT</command> statement to be locked as though for
     update.  This prevents them from being modified or deleted by
@@ -817,26 +832,44 @@ FOR UPDATE [ OF <replaceable class="parameter">table_name</replaceable> [, ...]
    </para>
 
    <para>
-    If specific tables are named in <literal>FOR UPDATE</literal>,
+    <literal>FOR SHARE</literal> behaves similarly, except that it
+    acquires a shared rather than exclusive lock on each retrieved
+    row.  A shared lock blocks other transactions from performing
+    <command>UPDATE</command>, <command>DELETE</command>, or <command>SELECT
+    FOR UPDATE</command> on these rows, but it does not prevent them
+    from performing <command>SELECT FOR SHARE</command>.
+   </para>
+
+   <para>
+    It is currently not allowed for a single <command>SELECT</command>
+    statement to include both <literal>FOR UPDATE</literal> and
+    <literal>FOR SHARE</literal>.
+   </para>
+
+   <para>
+    If specific tables are named in <literal>FOR UPDATE</literal>
+    or <literal>FOR SHARE</literal>,
     then only rows coming from those tables are locked; any other
     tables used in the <command>SELECT</command> are simply read as
     usual.
    </para>
 
    <para>
-    <literal>FOR UPDATE</literal> cannot be used in contexts where
-    returned rows can't be clearly identified with individual table
-    rows; for example it can't be used with aggregation.
+    <literal>FOR UPDATE</literal> and <literal>FOR SHARE</literal> cannot be
+    used in contexts where returned rows can't be clearly identified with
+    individual table rows; for example they can't be used with aggregation.
    </para>
 
    <para>
     It is possible for a <command>SELECT</> command using both 
-    <literal>LIMIT</literal> and  <literal>FOR UPDATE</literal> 
+    <literal>LIMIT</literal> and  <literal>FOR UPDATE/SHARE</literal> 
     clauses to return fewer rows than specified by <literal>LIMIT</literal>.
-    This is because <literal>LIMIT</> selects a number of rows,
-    but might then block requesting a <literal>FOR UPDATE</literal> lock.
-    Once the <literal>SELECT</> unblocks, the query qualification might not
-    be met and the row not be returned by <literal>SELECT</>.
+    This is because <literal>LIMIT</> is applied first.  The command
+    selects the specified number of rows,
+    but might then block trying to obtain lock on one or more of them.
+    Once the <literal>SELECT</> unblocks, the row might have been deleted
+    or updated so that it does not meet the query <literal>WHERE</> condition
+    anymore, in which case it will not be returned.
    </para>
   </refsect2>
  </refsect1>
diff --git a/doc/src/sgml/ref/select_into.sgml b/doc/src/sgml/ref/select_into.sgml
index 9198a02e4c..7e6a4807b7 100644
--- a/doc/src/sgml/ref/select_into.sgml
+++ b/doc/src/sgml/ref/select_into.sgml
@@ -1,5 +1,5 @@
 <!--
-$PostgreSQL: pgsql/doc/src/sgml/ref/select_into.sgml,v 1.34 2005/03/13 09:36:31 neilc Exp $
+$PostgreSQL: pgsql/doc/src/sgml/ref/select_into.sgml,v 1.35 2005/04/28 21:47:10 tgl Exp $
 PostgreSQL documentation
 -->
 
@@ -31,7 +31,7 @@ SELECT [ ALL | DISTINCT [ ON ( <replaceable class="PARAMETER">expression</replac
     [ ORDER BY <replaceable class="PARAMETER">expression</replaceable> [ ASC | DESC | USING <replaceable class="PARAMETER">operator</replaceable> ] [, ...] ]
     [ LIMIT { <replaceable class="PARAMETER">count</replaceable> | ALL } ]
     [ OFFSET <replaceable class="PARAMETER">start</replaceable> ]
-    [ FOR UPDATE [ OF <replaceable class="PARAMETER">tablename</replaceable> [, ...] ] ]
+    [ FOR { UPDATE | SHARE } [ OF <replaceable class="PARAMETER">tablename</replaceable> [, ...] ] ]
 </synopsis>
  </refsynopsisdiv>