diff --git a/contrib/pg_trgm/expected/pg_trgm.out b/contrib/pg_trgm/expected/pg_trgm.out index e7af7d4..250d853 100644 --- a/contrib/pg_trgm/expected/pg_trgm.out +++ b/contrib/pg_trgm/expected/pg_trgm.out @@ -3486,6 +3486,16 @@ explain (costs off) Index Cond: (t ~~* '%BCD%'::text) (4 rows) +explain (costs off) + select * from test2 where t like any ('{%bcd%,qua%}'); + QUERY PLAN +--------------------------------------------------------- + Bitmap Heap Scan on test2 + Recheck Cond: (t ~~ ANY ('{%bcd%,qua%}'::text[])) + -> Bitmap Index Scan on test2_idx_gin + Index Cond: (t ~~ ANY ('{%bcd%,qua%}'::text[])) +(4 rows) + select * from test2 where t like '%BCD%'; t --- @@ -3509,6 +3519,13 @@ select * from test2 where t ilike 'qua%'; quark (1 row) +select * from test2 where t like any ('{%bcd%,qua%}'); + t +-------- + abcdef + quark +(2 rows) + drop index test2_idx_gin; create index test2_idx_gist on test2 using gist (t gist_trgm_ops); set enable_seqscan=off; @@ -3528,6 +3545,16 @@ explain (costs off) Index Cond: (t ~~* '%BCD%'::text) (2 rows) +explain (costs off) + select * from test2 where t like any ('{%bcd%,qua%}'); + QUERY PLAN +--------------------------------------------------------- + Bitmap Heap Scan on test2 + Recheck Cond: (t ~~ ANY ('{%bcd%,qua%}'::text[])) + -> Bitmap Index Scan on test2_idx_gist + Index Cond: (t ~~ ANY ('{%bcd%,qua%}'::text[])) +(4 rows) + select * from test2 where t like '%BCD%'; t --- @@ -3551,3 +3578,10 @@ select * from test2 where t ilike 'qua%'; quark (1 row) +select * from test2 where t like any ('{%bcd%,qua%}'); + t +-------- + abcdef + quark +(2 rows) + diff --git a/contrib/pg_trgm/sql/pg_trgm.sql b/contrib/pg_trgm/sql/pg_trgm.sql index ea902f6..ac969e6 100644 --- a/contrib/pg_trgm/sql/pg_trgm.sql +++ b/contrib/pg_trgm/sql/pg_trgm.sql @@ -47,10 +47,13 @@ explain (costs off) select * from test2 where t like '%BCD%'; explain (costs off) select * from test2 where t ilike '%BCD%'; +explain (costs off) + select * from test2 where t like any ('{%bcd%,qua%}'); select * from test2 where t like '%BCD%'; select * from test2 where t like '%bcd%'; select * from test2 where t ilike '%BCD%'; select * from test2 where t ilike 'qua%'; +select * from test2 where t like any ('{%bcd%,qua%}'); drop index test2_idx_gin; create index test2_idx_gist on test2 using gist (t gist_trgm_ops); set enable_seqscan=off; @@ -58,7 +61,10 @@ explain (costs off) select * from test2 where t like '%BCD%'; explain (costs off) select * from test2 where t ilike '%BCD%'; +explain (costs off) + select * from test2 where t like any ('{%bcd%,qua%}'); select * from test2 where t like '%BCD%'; select * from test2 where t like '%bcd%'; select * from test2 where t ilike '%BCD%'; select * from test2 where t ilike 'qua%'; +select * from test2 where t like any ('{%bcd%,qua%}'); diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c index d06809e..64b732e 100644 --- a/src/backend/utils/adt/selfuncs.c +++ b/src/backend/utils/adt/selfuncs.c @@ -6591,6 +6591,70 @@ find_index_column(Node *op, IndexOptInfo *index) } /* + * Estimate gin costs for a single search value. Returns false if no match + * is possible, true otherwise. All pointer arguments must be initialized by + * the caller. + */ +static bool +gin_costestimate_search(Oid extractProcOid, Datum value, int strategy_op, + double numEntries, double *partialEntriesInQuals, + double *exactEntriesInQuals, + double *searchEntriesInQuals, bool *haveFullScan) +{ + int32 nentries = 0; + bool *partial_matches = NULL; + Pointer *extra_data = NULL; + bool *nullFlags = NULL; + int32 searchMode = GIN_SEARCH_MODE_DEFAULT; + int32 i; + + OidFunctionCall7(extractProcOid, + value, + PointerGetDatum(&nentries), + UInt16GetDatum(strategy_op), + PointerGetDatum(&partial_matches), + PointerGetDatum(&extra_data), + PointerGetDatum(&nullFlags), + PointerGetDatum(&searchMode)); + + if (nentries <= 0 && searchMode == GIN_SEARCH_MODE_DEFAULT) + return false; + + for (i = 0; i < nentries; i++) + { + /* + * For partial match we haven't any information to estimate + * number of matched entries in index, so, we just estimate it + * as 100 + */ + if (partial_matches && partial_matches[i]) + *partialEntriesInQuals += 100; + else + (*exactEntriesInQuals)++; + + (*searchEntriesInQuals)++; + } + + if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY) + { + /* Treat "include empty" like an exact-match item */ + (*exactEntriesInQuals)++; + (*searchEntriesInQuals)++; + } + else if (searchMode != GIN_SEARCH_MODE_DEFAULT) + { + /* + * It's GIN_SEARCH_MODE_ALL, full index scan will be required. We + * treat this as if every key in the index had been listed in the + * query; is that reasonable? + */ + *searchEntriesInQuals += numEntries; + } + + return true; +} + +/* * GIN has search behavior completely different from other index types */ Datum @@ -6613,7 +6677,8 @@ gincostestimate(PG_FUNCTION_ARGS) numDataPages, numPendingPages, numEntries; - bool haveFullScan = false; + bool haveFullScan = false, + matchPossible = true; double partialEntriesInQuals = 0.0; double searchEntriesInQuals = 0.0; double exactEntriesInQuals = 0.0; @@ -6623,7 +6688,8 @@ gincostestimate(PG_FUNCTION_ARGS) double qual_op_cost, qual_arg_cost, spc_random_page_cost, - num_scans; + outer_scans, + array_scans = 1.0; QualCost index_qual_cost; Relation indexRel; GinStatsData ginStats; @@ -6721,19 +6787,31 @@ gincostestimate(PG_FUNCTION_ARGS) int strategy_op; Oid lefttype, righttype; - int32 nentries = 0; - bool *partial_matches = NULL; - Pointer *extra_data = NULL; - bool *nullFlags = NULL; - int32 searchMode = GIN_SEARCH_MODE_DEFAULT; int indexcol; Assert(IsA(rinfo, RestrictInfo)); clause = rinfo->clause; - Assert(IsA(clause, OpExpr)); - leftop = get_leftop(clause); - rightop = get_rightop(clause); - clause_op = ((OpExpr *) clause)->opno; + + if (IsA(clause, OpExpr)) + { + leftop = get_leftop(clause); + rightop = get_rightop(clause); + clause_op = ((OpExpr *) clause)->opno; + } + else if (IsA(clause, ScalarArrayOpExpr)) + { + ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause; + + leftop = (Node *) linitial(saop->args); + rightop = (Node *) lsecond(saop->args); + clause_op = saop->opno; + } + else + { + elog(ERROR, "unsupported GIN indexqual type: %d", + (int) nodeTag(clause)); + continue; /* keep compiler quiet */ + } if ((indexcol = find_index_column(leftop, index)) >= 0) { @@ -6761,16 +6839,18 @@ gincostestimate(PG_FUNCTION_ARGS) if (!IsA(operand, Const)) { searchEntriesInQuals++; + + if (IsA(rinfo->clause, ScalarArrayOpExpr)) + array_scans *= estimate_array_length(operand); + continue; } /* If Const is null, there can be no matches */ if (((Const *) operand)->constisnull) { - *indexStartupCost = 0; - *indexTotalCost = 0; - *indexSelectivity = 0; - PG_RETURN_VOID(); + matchPossible = false; + break; } /* @@ -6800,57 +6880,102 @@ gincostestimate(PG_FUNCTION_ARGS) get_rel_name(index->indexoid)); } - OidFunctionCall7(extractProcOid, - ((Const *) operand)->constvalue, - PointerGetDatum(&nentries), - UInt16GetDatum(strategy_op), - PointerGetDatum(&partial_matches), - PointerGetDatum(&extra_data), - PointerGetDatum(&nullFlags), - PointerGetDatum(&searchMode)); - - if (nentries <= 0 && searchMode == GIN_SEARCH_MODE_DEFAULT) + if (IsA(rinfo->clause, OpExpr)) { - /* No match is possible */ - *indexStartupCost = 0; - *indexTotalCost = 0; - *indexSelectivity = 0; - PG_RETURN_VOID(); + matchPossible = + gin_costestimate_search(extractProcOid, + ((Const *) operand)->constvalue, + strategy_op, + numEntries, + &partialEntriesInQuals, + &exactEntriesInQuals, + &searchEntriesInQuals, + &haveFullScan); + if (!matchPossible) + break; } - else + else if (IsA(rinfo->clause, ScalarArrayOpExpr)) { - int32 i; - - for (i = 0; i < nentries; i++) + ArrayType *arrayval; + int16 elmlen; + bool elmbyval; + char elmalign; + int numElems; + Datum *elemValues; + bool *elemNulls; + int numPossible = 0; + int i; + double partialEntries = 0.0, + exactEntries = 0.0, + searchEntries = 0.0; + + arrayval = DatumGetArrayTypeP(((Const *) operand)->constvalue); + get_typlenbyvalalign(ARR_ELEMTYPE(arrayval), + &elmlen, &elmbyval, &elmalign); + deconstruct_array(arrayval, + ARR_ELEMTYPE(arrayval), + elmlen, elmbyval, elmalign, + &elemValues, &elemNulls, &numElems); + + for (i = 0; i < numElems; i++) { - /* - * For partial match we haven't any information to estimate - * number of matched entries in index, so, we just estimate it - * as 100 - */ - if (partial_matches && partial_matches[i]) - partialEntriesInQuals += 100; - else - exactEntriesInQuals++; + bool elemMatchPossible; + + /* NULL can't match anything */ + if (elemNulls[i]) + continue; - searchEntriesInQuals++; + elemMatchPossible = + gin_costestimate_search(extractProcOid, + elemValues[i], + strategy_op, + numEntries, + &partialEntries, + &exactEntries, + &searchEntries, + &haveFullScan); + + /* We only count array elements that can return any results */ + if (elemMatchPossible) + numPossible++; } - } - if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY) - { - /* Treat "include empty" like an exact-match item */ - exactEntriesInQuals++; - searchEntriesInQuals++; - } - else if (searchMode != GIN_SEARCH_MODE_DEFAULT) - { - /* It's GIN_SEARCH_MODE_ALL */ - haveFullScan = true; + if (numPossible == 0) + { + /* No useful searches in the array */ + matchPossible = false; + break; + } + + /* + * When there are multiple scalar expressions in an index scan, + * the executor repeats the index scan for all possible + * combinations (cartesian product) of input arrays. Instead of + * doing that here, we only do a single pass over input arrays and + * calculate the average entries for each scan. That allows us to + * estimate startup cost too. + * + * Later, we multiply average cost by array_scans (the product of + * effective array lengths) + */ + partialEntriesInQuals += partialEntries / numPossible; + exactEntriesInQuals += exactEntries / numPossible; + searchEntriesInQuals += searchEntries / numPossible; + + array_scans *= numPossible; } } - if (haveFullScan || indexQuals == NIL) + if (!matchPossible) + { + /* No match is possible */ + *indexStartupCost = 0; + *indexTotalCost = 0; + *indexSelectivity = 0; + PG_RETURN_VOID(); + } + + if (indexQuals == NIL) { /* * Full index scan will be required. We treat this as if every key in @@ -6861,9 +6986,9 @@ gincostestimate(PG_FUNCTION_ARGS) /* Will we have more than one iteration of a nestloop scan? */ if (outer_rel != NULL && outer_rel->rows > 1) - num_scans = outer_rel->rows; + outer_scans = outer_rel->rows; else - num_scans = 1; + outer_scans = 1; /* * cost to begin scan, first of all, pay attention to pending list. @@ -6888,13 +7013,13 @@ gincostestimate(PG_FUNCTION_ARGS) /* * Partial match algorithm reads all data pages before doing actual scan, - * so it's a startup cost. Again, we havn't any useful stats here, so, + * so it's a startup cost. Again, we haven't any useful stats here, so, * estimate it as proportion */ dataPagesFetched = ceil(numDataPages * partialEntriesInQuals / numEntries); /* calculate cache effects */ - if (num_scans > 1 || searchEntriesInQuals > 1) + if (outer_scans > 1 || array_scans > 1 || searchEntriesInQuals > 1) { entryPagesFetched = index_pages_fetched(entryPagesFetched, (BlockNumber) numEntryPages, @@ -6910,6 +7035,14 @@ gincostestimate(PG_FUNCTION_ARGS) */ *indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost; + /* + * Startup cost was estimated with per-scan averages (first scan), but + * total cost needs to account for all rescans of ScalarArrayOpExprs. + */ + partialEntriesInQuals *= array_scans; + exactEntriesInQuals *= array_scans; + searchEntriesInQuals *= array_scans; + /* cost to scan data pages for each exact (non-partial) matched entry */ dataPagesFetched = ceil(numDataPages * exactEntriesInQuals / numEntries); @@ -6932,7 +7065,7 @@ gincostestimate(PG_FUNCTION_ARGS) dataPagesFetched = dataPagesFetchedBySel; } - if (num_scans > 1) + if (outer_scans > 1 || array_scans > 1) dataPagesFetched = index_pages_fetched(dataPagesFetched, (BlockNumber) numDataPages, numDataPages, root); diff --git a/src/test/regress/expected/tsearch.out b/src/test/regress/expected/tsearch.out index e1d7646..9341dbe 100644 --- a/src/test/regress/expected/tsearch.out +++ b/src/test/regress/expected/tsearch.out @@ -142,6 +142,12 @@ SELECT count(*) FROM test_tsvector WHERE a @@ 'w:*|q:*'; 494 (1 row) +SELECT count(*) FROM test_tsvector WHERE a @@ any ('{wr,qh}'); + count +------- + 158 +(1 row) + RESET enable_seqscan; DROP INDEX wowidx; CREATE INDEX wowidx ON test_tsvector USING gin (a); @@ -188,6 +194,12 @@ SELECT count(*) FROM test_tsvector WHERE a @@ 'w:*|q:*'; 494 (1 row) +SELECT count(*) FROM test_tsvector WHERE a @@ any ('{wr,qh}'); + count +------- + 158 +(1 row) + RESET enable_seqscan; INSERT INTO test_tsvector VALUES ('???', 'DFG:1A,2B,6C,10 FGH'); SELECT * FROM ts_stat('SELECT a FROM test_tsvector') ORDER BY ndoc DESC, nentry DESC, word LIMIT 10; diff --git a/src/test/regress/sql/tsearch.sql b/src/test/regress/sql/tsearch.sql index d261da2..9fd1207 100644 --- a/src/test/regress/sql/tsearch.sql +++ b/src/test/regress/sql/tsearch.sql @@ -60,6 +60,7 @@ SELECT count(*) FROM test_tsvector WHERE a @@ 'eq|yt'; SELECT count(*) FROM test_tsvector WHERE a @@ '(eq&yt)|(wr&qh)'; SELECT count(*) FROM test_tsvector WHERE a @@ '(eq|yt)&(wr|qh)'; SELECT count(*) FROM test_tsvector WHERE a @@ 'w:*|q:*'; +SELECT count(*) FROM test_tsvector WHERE a @@ any ('{wr,qh}'); RESET enable_seqscan; @@ -76,6 +77,7 @@ SELECT count(*) FROM test_tsvector WHERE a @@ 'eq|yt'; SELECT count(*) FROM test_tsvector WHERE a @@ '(eq&yt)|(wr&qh)'; SELECT count(*) FROM test_tsvector WHERE a @@ '(eq|yt)&(wr|qh)'; SELECT count(*) FROM test_tsvector WHERE a @@ 'w:*|q:*'; +SELECT count(*) FROM test_tsvector WHERE a @@ any ('{wr,qh}'); RESET enable_seqscan; INSERT INTO test_tsvector VALUES ('???', 'DFG:1A,2B,6C,10 FGH');