1 files changed, 59 insertions, 14 deletions

diff --git a/src/backend/utils/adt/tsvector_op.c b/src/backend/utils/adt/tsvector_op.c
index 38c1401398c..b7a822d3544 100644
--- a/src/backend/utils/adt/tsvector_op.c
+++ b/src/backend/utils/adt/tsvector_op.c
@@ -525,7 +525,8 @@ tsvector_concat(PG_FUNCTION_ARGS)
 
 /*
  * Compare two strings by tsvector rules.
- * if isPrefix = true then it returns not-zero value if b has prefix a
+ *
+ * if isPrefix = true then it returns zero value iff b has prefix a
  */
 int4
 tsCompareString(char *a, int lena, char *b, int lenb, bool prefix)
@@ -535,8 +536,7 @@ tsCompareString(char *a, int lena, char *b, int lenb, bool prefix)
 	if (lena == 0)
 	{
 		if (prefix)
-			cmp = 0;			/* emtry string is equal to any if a prefix
-								 * match */
+			cmp = 0;			/* empty string is prefix of anything */
 		else
 			cmp = (lenb > 0) ? -1 : 0;
 	}
@@ -551,14 +551,9 @@ tsCompareString(char *a, int lena, char *b, int lenb, bool prefix)
 		if (prefix)
 		{
 			if (cmp == 0 && lena > lenb)
-			{
-				/*
-				 * b argument is not beginning with argument a
-				 */
-				cmp = 1;
-			}
+				cmp = 1;		/* a is longer, so not a prefix of b */
 		}
-		else if ((cmp == 0) && (lena != lenb))
+		else if (cmp == 0 && lena != lenb)
 		{
 			cmp = (lena < lenb) ? -1 : 1;
 		}
@@ -650,13 +645,13 @@ checkcondition_str(void *checkval, QueryOperand *val)
 }
 
 /*
- * check for boolean condition.
+ * Evaluate tsquery boolean expression.
  *
- * if calcnot is false, NOT expressions are always evaluated to be true. This is used in ranking.
+ * chkcond is a callback function used to evaluate each VAL node in the query.
  * checkval can be used to pass information to the callback. TS_execute doesn't
  * do anything with it.
- * chkcond is a callback function used to evaluate each VAL node in the query.
- *
+ * if calcnot is false, NOT expressions are always evaluated to be true. This
+ * is used in ranking.
  */
 bool
 TS_execute(QueryItem *curitem, void *checkval, bool calcnot,
@@ -675,6 +670,7 @@ TS_execute(QueryItem *curitem, void *checkval, bool calcnot,
 				return !TS_execute(curitem + 1, checkval, calcnot, chkcond);
 			else
 				return true;
+
 		case OP_AND:
 			if (TS_execute(curitem + curitem->qoperator.left, checkval, calcnot, chkcond))
 				return TS_execute(curitem + 1, checkval, calcnot, chkcond);
@@ -696,6 +692,55 @@ TS_execute(QueryItem *curitem, void *checkval, bool calcnot,
 }
 
 /*
+ * Detect whether a tsquery boolean expression requires any positive matches
+ * to values shown in the tsquery.
+ *
+ * This is needed to know whether a GIN index search requires full index scan.
+ * For example, 'x & !y' requires a match of x, so it's sufficient to scan
+ * entries for x; but 'x | !y' could match rows containing neither x nor y.
+ */
+bool
+tsquery_requires_match(QueryItem *curitem)
+{
+	/* since this function recurses, it could be driven to stack overflow */
+	check_stack_depth();
+
+	if (curitem->type == QI_VAL)
+		return true;
+
+	switch (curitem->qoperator.oper)
+	{
+		case OP_NOT:
+			/*
+			 * Assume there are no required matches underneath a NOT.  For
+			 * some cases with nested NOTs, we could prove there's a required
+			 * match, but it seems unlikely to be worth the trouble.
+			 */
+			return false;
+
+		case OP_AND:
+			/* If either side requires a match, we're good */
+			if (tsquery_requires_match(curitem + curitem->qoperator.left))
+				return true;
+			else
+				return tsquery_requires_match(curitem + 1);
+
+		case OP_OR:
+			/* Both sides must require a match */
+			if (tsquery_requires_match(curitem + curitem->qoperator.left))
+				return tsquery_requires_match(curitem + 1);
+			else
+				return false;
+
+		default:
+			elog(ERROR, "unrecognized operator: %d", curitem->qoperator.oper);
+	}
+
+	/* not reachable, but keep compiler quiet */
+	return false;
+}
+
+/*
  * boolean operations
  */
 Datum