agora inbox for [email protected]
help / color / mirror / Atom feed[PATCH v36 1/6] Introduce RelOptInfo->notnullattrs attribute
11+ messages / 4 participants
[nested] [flat]
* [PATCH v36 1/6] Introduce RelOptInfo->notnullattrs attribute
@ 2020-05-03 14:37 一挃 <[email protected]>
0 siblings, 0 replies; 11+ messages in thread
From: 一挃 @ 2020-05-03 14:37 UTC (permalink / raw)
The notnullattrs is calculated from catalog and run-time query. That
infomation is translated to child relation as well for partitioned
table.
---
src/backend/optimizer/path/allpaths.c | 31 ++++++++++++++++++++++++++
src/backend/optimizer/plan/initsplan.c | 10 +++++++++
src/backend/optimizer/util/plancat.c | 10 +++++++++
src/include/nodes/pathnodes.h | 2 ++
4 files changed, 53 insertions(+)
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 6da0dcd61c..484dab0a1a 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -1005,6 +1005,7 @@ set_append_rel_size(PlannerInfo *root, RelOptInfo *rel,
RelOptInfo *childrel;
ListCell *parentvars;
ListCell *childvars;
+ int i = -1;
/* append_rel_list contains all append rels; ignore others */
if (appinfo->parent_relid != parentRTindex)
@@ -1061,6 +1062,36 @@ set_append_rel_size(PlannerInfo *root, RelOptInfo *rel,
(Node *) rel->reltarget->exprs,
1, &appinfo);
+ /* Copy notnullattrs. */
+ while ((i = bms_next_member(rel->notnullattrs, i)) > 0)
+ {
+ AttrNumber attno = i + FirstLowInvalidHeapAttributeNumber;
+ AttrNumber child_attno;
+ if (attno == 0)
+ {
+ /* Whole row is not null, so must be same for child */
+ childrel->notnullattrs = bms_add_member(childrel->notnullattrs,
+ attno - FirstLowInvalidHeapAttributeNumber);
+ break;
+ }
+ if (attno < 0 )
+ /* no need to translate system column */
+ child_attno = attno;
+ else
+ {
+ Node * node = list_nth(appinfo->translated_vars, attno - 1);
+ if (!IsA(node, Var))
+ /* This may happens at UNION case, like (SELECT a FROM t1 UNION SELECT a + 3
+ * FROM t2) t and we know t.a is not null
+ */
+ continue;
+ child_attno = castNode(Var, node)->varattno;
+ }
+
+ childrel->notnullattrs = bms_add_member(childrel->notnullattrs,
+ child_attno - FirstLowInvalidHeapAttributeNumber);
+ }
+
/*
* We have to make child entries in the EquivalenceClass data
* structures as well. This is needed either if the parent
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index e978b491f6..95b1b14cd3 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -830,6 +830,16 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
{
Node *qual = (Node *) lfirst(l);
+ /* Set the not null info now */
+ ListCell *lc;
+ List *non_nullable_vars = find_nonnullable_vars(qual);
+ foreach(lc, non_nullable_vars)
+ {
+ Var *var = lfirst_node(Var, lc);
+ RelOptInfo *rel = root->simple_rel_array[var->varno];
+ rel->notnullattrs = bms_add_member(rel->notnullattrs,
+ var->varattno - FirstLowInvalidHeapAttributeNumber);
+ }
distribute_qual_to_rels(root, qual,
false, below_outer_join, JOIN_INNER,
root->qual_security_level,
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 25545029d7..0b2f9d398a 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -117,6 +117,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
Relation relation;
bool hasindex;
List *indexinfos = NIL;
+ int i;
/*
* We need not lock the relation since it was already locked, either by
@@ -463,6 +464,15 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
if (inhparent && relation->rd_rel->relkind == RELKIND_PARTITIONED_TABLE)
set_relation_partition_info(root, rel, relation);
+ Assert(rel->notnullattrs == NULL);
+ for(i = 0; i < relation->rd_att->natts; i++)
+ {
+ FormData_pg_attribute attr = relation->rd_att->attrs[i];
+ if (attr.attnotnull)
+ rel->notnullattrs = bms_add_member(rel->notnullattrs,
+ attr.attnum - FirstLowInvalidHeapAttributeNumber);
+ }
+
table_close(relation, NoLock);
/*
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 485d1b06c9..9e3ebd488a 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -709,6 +709,8 @@ typedef struct RelOptInfo
PlannerInfo *subroot; /* if subquery */
List *subplan_params; /* if subquery */
int rel_parallel_workers; /* wanted number of parallel workers */
+ /* Not null attrs, start from -FirstLowInvalidHeapAttributeNumber */
+ Bitmapset *notnullattrs;
/* Information about foreign tables and foreign joins */
Oid serverid; /* identifies server for the table or join */
--
2.21.0
--op7mf2i72xk5yu7c
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment;
filename="v36-0002-Introduce-UniqueKey-attributes-on-RelOptInfo-str.patch"
^ permalink raw reply [nested|flat] 11+ messages in thread
* [PATCH 2/2] Allow ILIKE forward matching to use btree index
@ 2024-12-19 14:41 Yugo Nagata <[email protected]>
0 siblings, 0 replies; 11+ messages in thread
From: Yugo Nagata @ 2024-12-19 14:41 UTC (permalink / raw)
Previously, ILIKE could not use btree index if the pattern
has case-varying characters. To enable it, the planner
support function converts an ILINK operator expression to OR
clause that contains two index clauses for the upper letter and
the lower letter respectively.
For example, "t ILIKE '123foo%'" can be converted to
"(t <= '123F'AND t > '123G') OR (t <= '123f' AND t < '123g')",
and bitmap index scan plan could be used for this.
---
src/backend/utils/adt/like_support.c | 141 ++++++++++++++----
src/test/regress/expected/btree_index.out | 15 +-
.../regress/expected/collate.icu.utf8.out | 22 ++-
src/test/regress/sql/collate.icu.utf8.sql | 4 +-
4 files changed, 137 insertions(+), 45 deletions(-)
diff --git a/src/backend/utils/adt/like_support.c b/src/backend/utils/adt/like_support.c
index ee71ca89ff..06cf4eb8d2 100644
--- a/src/backend/utils/adt/like_support.c
+++ b/src/backend/utils/adt/like_support.c
@@ -66,7 +66,10 @@ typedef enum
typedef enum
{
- Pattern_Prefix_None, Pattern_Prefix_Partial, Pattern_Prefix_Exact,
+ Pattern_Prefix_None,
+ Pattern_Prefix_Partial,
+ Pattern_Prefix_Partial_IC,
+ Pattern_Prefix_Exact,
} Pattern_Prefix_Status;
static Node *like_regex_support(Node *rawreq, Pattern_Type ptype);
@@ -245,7 +248,7 @@ match_pattern_prefix(Node *leftop,
Oid opfamily,
Oid indexcollation)
{
- List *result;
+ List *result = NIL;
Const *patt;
Const *prefix;
Pattern_Prefix_Status pstatus;
@@ -259,6 +262,8 @@ match_pattern_prefix(Node *leftop,
Expr *expr;
FmgrInfo ltproc;
Const *greaterstr;
+ List *prefixes;
+ ListCell *lc;
/*
* Can't do anything with a non-constant or NULL pattern argument.
@@ -434,35 +439,112 @@ match_pattern_prefix(Node *leftop,
return NIL;
/*
- * We can always say "x >= prefix".
+ * If the pattern for case-insensiive matching has a case-varying
+ * character, make two prefixes including the upper letter and the
+ * lower letter respectively. For example, if the pattern is
+ * '123foo%', we get '123F' and '123f' as prefixes.
*/
- if (!op_in_opfamily(geopr, opfamily))
- return NIL;
- expr = make_opclause(geopr, BOOLOID, false,
- (Expr *) leftop, (Expr *) prefix,
- InvalidOid, indexcollation);
- result = list_make1(expr);
-
- /*-------
- * If we can create a string larger than the prefix, we can say
- * "x < greaterstr". NB: we rely on make_greater_string() to generate
- * a guaranteed-greater string, not just a probably-greater string.
- * In general this is only guaranteed in C locale, so we'd better be
- * using a C-locale index collation.
- *-------
- */
- if (!op_in_opfamily(ltopr, opfamily))
- return result;
- fmgr_info(get_opcode(ltopr), <proc);
- greaterstr = make_greater_string(prefix, <proc, indexcollation);
- if (greaterstr)
+ if (pstatus == Pattern_Prefix_Partial_IC)
+ {
+ int prefix_len;
+ Datum first_letter;
+ Datum upper_letter;
+ Datum lower_letter;
+ const char *prefix_l;
+ const char *prefix_u;
+
+ Assert(ptype == Pattern_Type_Like_IC);
+
+ /* get the first case-varying characketer in the pattern */
+ prefix_len = DatumGetInt32(DirectFunctionCall1Coll(textlen,
+ indexcollation,
+ prefix->constvalue));
+ first_letter = DirectFunctionCall3Coll(text_substr, indexcollation,
+ patt->constvalue,
+ Int32GetDatum(prefix_len + 1),
+ Int32GetDatum(1));
+
+
+ /* prefix followed by the upper letter */
+ upper_letter = DirectFunctionCall1Coll(upper, indexcollation,
+ first_letter);
+ prefix_u = TextDatumGetCString(DirectFunctionCall2Coll(textcat,
+ indexcollation,
+ prefix->constvalue,
+ upper_letter));
+ prefixes = list_make1(string_to_const(prefix_u, prefix->consttype));
+
+ /* prefix followed by the lower letter */
+ lower_letter = DirectFunctionCall1Coll(lower, indexcollation,
+ first_letter);
+ prefix_l = TextDatumGetCString(DirectFunctionCall2Coll(textcat,
+ indexcollation,
+ prefix->constvalue,
+ lower_letter));
+ if (!DatumGetBool(DirectFunctionCall2Coll(texteq,
+ indexcollation,
+ CStringGetTextDatum(prefix_u),
+ CStringGetTextDatum(prefix_l))))
+ prefixes = lappend(prefixes, string_to_const(prefix_l, prefix->consttype));
+ }
+ else
+ prefixes = list_make1(prefix);
+
+ foreach (lc, prefixes)
{
- expr = make_opclause(ltopr, BOOLOID, false,
- (Expr *) leftop, (Expr *) greaterstr,
+ List *clauses;
+
+ prefix = (Const *) lfirst(lc);
+
+ /*
+ * We can always say "x >= prefix".
+ */
+ if (!op_in_opfamily(geopr, opfamily))
+ return NIL;
+ expr = make_opclause(geopr, BOOLOID, false,
+ (Expr *) leftop, (Expr *) prefix,
InvalidOid, indexcollation);
- result = lappend(result, expr);
+ clauses = list_make1(expr);
+
+ /*-------
+ * If we can create a string larger than the prefix, we can say
+ * "x < greaterstr". NB: we rely on make_greater_string() to generate
+ * a guaranteed-greater string, not just a probably-greater string.
+ * In general this is only guaranteed in C locale, so we'd better be
+ * using a C-locale index collation.
+ *-------
+ */
+ if (op_in_opfamily(ltopr, opfamily))
+ {
+ fmgr_info(get_opcode(ltopr), <proc);
+ greaterstr = make_greater_string(prefix, <proc, indexcollation);
+ if (greaterstr)
+ {
+ expr = make_opclause(ltopr, BOOLOID, false,
+ (Expr *) leftop, (Expr *) greaterstr,
+ InvalidOid, indexcollation);
+ clauses = lappend(clauses, expr);
+ }
+ }
+
+ /*
+ * If case-insensitive pattern matching generated two clauses for
+ * uppder and lower letters, convert them to explicit AND because
+ * they will be under OR later.
+ */
+ if (pstatus == Pattern_Prefix_Partial_IC && list_length(prefixes) > 1)
+ result = lappend(result, make_ands_explicit(clauses));
+ else
+ result = clauses;
}
+ /*
+ * If case-insensitive pattern matching generated two clauses for upper and
+ * lower letters, OR them.
+ */
+ if (pstatus == Pattern_Prefix_Partial_IC && list_length(prefixes) > 1)
+ result = list_make1(make_orclause(result));
+
return result;
}
@@ -997,6 +1079,7 @@ like_fixed_prefix(Const *patt_const, bool case_insensitive, Oid collation,
match_pos;
bool is_multibyte = (pg_database_encoding_max_length() > 1);
pg_locale_t locale = 0;
+ bool has_case_varying = false;
/* the right-hand const is type text or bytea */
Assert(typeid == BYTEAOID || typeid == TEXTOID);
@@ -1058,7 +1141,10 @@ like_fixed_prefix(Const *patt_const, bool case_insensitive, Oid collation,
/* Stop if case-varying character (it's sort of a wildcard) */
if (case_insensitive &&
pattern_char_isalpha(patt[pos], is_multibyte, locale))
+ {
+ has_case_varying = true;
break;
+ }
match[match_pos++] = patt[pos];
}
@@ -1077,6 +1163,9 @@ like_fixed_prefix(Const *patt_const, bool case_insensitive, Oid collation,
pfree(patt);
pfree(match);
+ if (case_insensitive && has_case_varying)
+ return Pattern_Prefix_Partial_IC;
+
/* in LIKE, an empty pattern is an exact match! */
if (pos == pattlen)
return Pattern_Prefix_Exact; /* reached end of pattern, so exact */
diff --git a/src/test/regress/expected/btree_index.out b/src/test/regress/expected/btree_index.out
index def78ef858..244d6d999e 100644
--- a/src/test/regress/expected/btree_index.out
+++ b/src/test/regress/expected/btree_index.out
@@ -332,14 +332,19 @@ select proname from pg_proc where proname ilike '00%foo' order by 1;
explain (costs off)
select proname from pg_proc where proname ilike 'ri%foo' order by 1;
- QUERY PLAN
-----------------------------------------------
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Sort
Sort Key: proname
- -> Seq Scan on pg_proc
- Disabled: true
+ -> Bitmap Heap Scan on pg_proc
+ Recheck Cond: (((proname >= 'R'::text) AND (proname < 'S'::text) AND (proname ~~* 'ri%foo'::text)) OR ((proname >= 'r'::text) AND (proname < 's'::text) AND (proname ~~* 'ri%foo'::text)))
Filter: (proname ~~* 'ri%foo'::text)
-(5 rows)
+ -> BitmapOr
+ -> Bitmap Index Scan on pg_proc_proname_args_nsp_index
+ Index Cond: ((proname >= 'R'::text) AND (proname < 'S'::text))
+ -> Bitmap Index Scan on pg_proc_proname_args_nsp_index
+ Index Cond: ((proname >= 'r'::text) AND (proname < 's'::text))
+(10 rows)
reset enable_seqscan;
reset enable_indexscan;
diff --git a/src/test/regress/expected/collate.icu.utf8.out b/src/test/regress/expected/collate.icu.utf8.out
index d4f327636f..f13f9e1245 100644
--- a/src/test/regress/expected/collate.icu.utf8.out
+++ b/src/test/regress/expected/collate.icu.utf8.out
@@ -988,14 +988,13 @@ SELECT relname, pg_get_indexdef(oid) FROM pg_class WHERE relname LIKE 'collate_t
set enable_seqscan = off;
explain (costs off)
select * from collate_test1 where b ilike 'abc';
- QUERY PLAN
--------------------------------
- Seq Scan on collate_test1
- Disabled: true
+ QUERY PLAN
+------------------------------------------------------
+ Index Scan using collate_test1_idx3 on collate_test1
Filter: (b ~~* 'abc'::text)
-(3 rows)
+(2 rows)
-select * from collate_test1 where b ilike 'abc';
+select * from collate_test1 where b ilike 'abc' order by 1;
a | b
---+-----
1 | abc
@@ -1004,14 +1003,13 @@ select * from collate_test1 where b ilike 'abc';
explain (costs off)
select * from collate_test1 where b ilike 'ABC';
- QUERY PLAN
--------------------------------
- Seq Scan on collate_test1
- Disabled: true
+ QUERY PLAN
+------------------------------------------------------
+ Index Scan using collate_test1_idx3 on collate_test1
Filter: (b ~~* 'ABC'::text)
-(3 rows)
+(2 rows)
-select * from collate_test1 where b ilike 'ABC';
+select * from collate_test1 where b ilike 'ABC' order by 1;
a | b
---+-----
1 | abc
diff --git a/src/test/regress/sql/collate.icu.utf8.sql b/src/test/regress/sql/collate.icu.utf8.sql
index 5ee2da4e0e..948201c3e1 100644
--- a/src/test/regress/sql/collate.icu.utf8.sql
+++ b/src/test/regress/sql/collate.icu.utf8.sql
@@ -344,10 +344,10 @@ SELECT relname, pg_get_indexdef(oid) FROM pg_class WHERE relname LIKE 'collate_t
set enable_seqscan = off;
explain (costs off)
select * from collate_test1 where b ilike 'abc';
-select * from collate_test1 where b ilike 'abc';
+select * from collate_test1 where b ilike 'abc' order by 1;
explain (costs off)
select * from collate_test1 where b ilike 'ABC';
-select * from collate_test1 where b ilike 'ABC';
+select * from collate_test1 where b ilike 'ABC' order by 1;
reset enable_seqscan;
--
2.34.1
--Multipart=_Fri__20_Dec_2024_03_22_26_+0900_fuUlFrF3xpUebxjW
Content-Type: text/x-diff;
name="0001-Allow-planner-support-function-to-return-index-condi.patch"
Content-Disposition: attachment;
filename="0001-Allow-planner-support-function-to-return-index-condi.patch"
Content-Transfer-Encoding: 7bit
^ permalink raw reply [nested|flat] 11+ messages in thread
* [PATCH v2 2/3] Allow ILIKE forward matching to use btree index
@ 2024-12-19 14:41 Yugo Nagata <[email protected]>
0 siblings, 0 replies; 11+ messages in thread
From: Yugo Nagata @ 2024-12-19 14:41 UTC (permalink / raw)
Previously, ILIKE could not use btree index if the pattern
has case-varying characters. To enable it, the planner
support function converts an ILINK operator expression to OR
clause that contains two index clauses for the upper letter and
the lower letter respectively.
For example, "t ILIKE '123foo%'" can be converted to
"(t <= '123F'AND t > '123G') OR (t <= '123f' AND t < '123g')",
and bitmap index scan plan could be used for this.
---
src/backend/utils/adt/like_support.c | 141 ++++++++++++++----
src/test/regress/expected/btree_index.out | 15 +-
.../regress/expected/collate.icu.utf8.out | 22 ++-
src/test/regress/sql/collate.icu.utf8.sql | 4 +-
4 files changed, 137 insertions(+), 45 deletions(-)
diff --git a/src/backend/utils/adt/like_support.c b/src/backend/utils/adt/like_support.c
index 8fdc677371..2344615038 100644
--- a/src/backend/utils/adt/like_support.c
+++ b/src/backend/utils/adt/like_support.c
@@ -66,7 +66,10 @@ typedef enum
typedef enum
{
- Pattern_Prefix_None, Pattern_Prefix_Partial, Pattern_Prefix_Exact,
+ Pattern_Prefix_None,
+ Pattern_Prefix_Partial,
+ Pattern_Prefix_Partial_IC,
+ Pattern_Prefix_Exact,
} Pattern_Prefix_Status;
static Node *like_regex_support(Node *rawreq, Pattern_Type ptype);
@@ -245,7 +248,7 @@ match_pattern_prefix(Node *leftop,
Oid opfamily,
Oid indexcollation)
{
- List *result;
+ List *result = NIL;
Const *patt;
Const *prefix;
Pattern_Prefix_Status pstatus;
@@ -259,6 +262,8 @@ match_pattern_prefix(Node *leftop,
Expr *expr;
FmgrInfo ltproc;
Const *greaterstr;
+ List *prefixes;
+ ListCell *lc;
/*
* Can't do anything with a non-constant or NULL pattern argument.
@@ -434,35 +439,112 @@ match_pattern_prefix(Node *leftop,
return NIL;
/*
- * We can always say "x >= prefix".
+ * If the pattern for case-insensiive matching has a case-varying
+ * character, make two prefixes including the upper letter and the
+ * lower letter respectively. For example, if the pattern is
+ * '123foo%', we get '123F' and '123f' as prefixes.
*/
- if (!op_in_opfamily(geopr, opfamily))
- return NIL;
- expr = make_opclause(geopr, BOOLOID, false,
- (Expr *) leftop, (Expr *) prefix,
- InvalidOid, indexcollation);
- result = list_make1(expr);
-
- /*-------
- * If we can create a string larger than the prefix, we can say
- * "x < greaterstr". NB: we rely on make_greater_string() to generate
- * a guaranteed-greater string, not just a probably-greater string.
- * In general this is only guaranteed in C locale, so we'd better be
- * using a C-locale index collation.
- *-------
- */
- if (!op_in_opfamily(ltopr, opfamily))
- return result;
- fmgr_info(get_opcode(ltopr), <proc);
- greaterstr = make_greater_string(prefix, <proc, indexcollation);
- if (greaterstr)
+ if (pstatus == Pattern_Prefix_Partial_IC)
+ {
+ int prefix_len;
+ Datum first_letter;
+ Datum upper_letter;
+ Datum lower_letter;
+ const char *prefix_l;
+ const char *prefix_u;
+
+ Assert(ptype == Pattern_Type_Like_IC);
+
+ /* get the first case-varying characketer in the pattern */
+ prefix_len = DatumGetInt32(DirectFunctionCall1Coll(textlen,
+ indexcollation,
+ prefix->constvalue));
+ first_letter = DirectFunctionCall3Coll(text_substr, indexcollation,
+ patt->constvalue,
+ Int32GetDatum(prefix_len + 1),
+ Int32GetDatum(1));
+
+
+ /* prefix followed by the upper letter */
+ upper_letter = DirectFunctionCall1Coll(upper, indexcollation,
+ first_letter);
+ prefix_u = TextDatumGetCString(DirectFunctionCall2Coll(textcat,
+ indexcollation,
+ prefix->constvalue,
+ upper_letter));
+ prefixes = list_make1(string_to_const(prefix_u, prefix->consttype));
+
+ /* prefix followed by the lower letter */
+ lower_letter = DirectFunctionCall1Coll(lower, indexcollation,
+ first_letter);
+ prefix_l = TextDatumGetCString(DirectFunctionCall2Coll(textcat,
+ indexcollation,
+ prefix->constvalue,
+ lower_letter));
+ if (!DatumGetBool(DirectFunctionCall2Coll(texteq,
+ indexcollation,
+ CStringGetTextDatum(prefix_u),
+ CStringGetTextDatum(prefix_l))))
+ prefixes = lappend(prefixes, string_to_const(prefix_l, prefix->consttype));
+ }
+ else
+ prefixes = list_make1(prefix);
+
+ foreach (lc, prefixes)
{
- expr = make_opclause(ltopr, BOOLOID, false,
- (Expr *) leftop, (Expr *) greaterstr,
+ List *clauses;
+
+ prefix = (Const *) lfirst(lc);
+
+ /*
+ * We can always say "x >= prefix".
+ */
+ if (!op_in_opfamily(geopr, opfamily))
+ return NIL;
+ expr = make_opclause(geopr, BOOLOID, false,
+ (Expr *) leftop, (Expr *) prefix,
InvalidOid, indexcollation);
- result = lappend(result, expr);
+ clauses = list_make1(expr);
+
+ /*-------
+ * If we can create a string larger than the prefix, we can say
+ * "x < greaterstr". NB: we rely on make_greater_string() to generate
+ * a guaranteed-greater string, not just a probably-greater string.
+ * In general this is only guaranteed in C locale, so we'd better be
+ * using a C-locale index collation.
+ *-------
+ */
+ if (op_in_opfamily(ltopr, opfamily))
+ {
+ fmgr_info(get_opcode(ltopr), <proc);
+ greaterstr = make_greater_string(prefix, <proc, indexcollation);
+ if (greaterstr)
+ {
+ expr = make_opclause(ltopr, BOOLOID, false,
+ (Expr *) leftop, (Expr *) greaterstr,
+ InvalidOid, indexcollation);
+ clauses = lappend(clauses, expr);
+ }
+ }
+
+ /*
+ * If case-insensitive pattern matching generated two clauses for
+ * uppder and lower letters, convert them to explicit AND because
+ * they will be under OR later.
+ */
+ if (pstatus == Pattern_Prefix_Partial_IC && list_length(prefixes) > 1)
+ result = lappend(result, make_ands_explicit(clauses));
+ else
+ result = clauses;
}
+ /*
+ * If case-insensitive pattern matching generated two clauses for upper and
+ * lower letters, OR them.
+ */
+ if (pstatus == Pattern_Prefix_Partial_IC && list_length(prefixes) > 1)
+ result = list_make1(make_orclause(result));
+
return result;
}
@@ -997,6 +1079,7 @@ like_fixed_prefix(Const *patt_const, bool case_insensitive, Oid collation,
match_pos;
bool is_multibyte = (pg_database_encoding_max_length() > 1);
pg_locale_t locale = 0;
+ bool has_case_varying = false;
/* the right-hand const is type text or bytea */
Assert(typeid == BYTEAOID || typeid == TEXTOID);
@@ -1058,7 +1141,10 @@ like_fixed_prefix(Const *patt_const, bool case_insensitive, Oid collation,
/* Stop if case-varying character (it's sort of a wildcard) */
if (case_insensitive &&
pattern_char_isalpha(patt[pos], is_multibyte, locale))
+ {
+ has_case_varying = true;
break;
+ }
match[match_pos++] = patt[pos];
}
@@ -1077,6 +1163,9 @@ like_fixed_prefix(Const *patt_const, bool case_insensitive, Oid collation,
pfree(patt);
pfree(match);
+ if (case_insensitive && has_case_varying)
+ return Pattern_Prefix_Partial_IC;
+
/* in LIKE, an empty pattern is an exact match! */
if (pos == pattlen)
return Pattern_Prefix_Exact; /* reached end of pattern, so exact */
diff --git a/src/test/regress/expected/btree_index.out b/src/test/regress/expected/btree_index.out
index 8879554c3f..6ffad39dad 100644
--- a/src/test/regress/expected/btree_index.out
+++ b/src/test/regress/expected/btree_index.out
@@ -459,14 +459,19 @@ select proname from pg_proc where proname ilike '00%foo' order by 1;
explain (costs off)
select proname from pg_proc where proname ilike 'ri%foo' order by 1;
- QUERY PLAN
-----------------------------------------------
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Sort
Sort Key: proname
- -> Seq Scan on pg_proc
- Disabled: true
+ -> Bitmap Heap Scan on pg_proc
+ Recheck Cond: (((proname >= 'R'::text) AND (proname < 'S'::text) AND (proname ~~* 'ri%foo'::text)) OR ((proname >= 'r'::text) AND (proname < 's'::text) AND (proname ~~* 'ri%foo'::text)))
Filter: (proname ~~* 'ri%foo'::text)
-(5 rows)
+ -> BitmapOr
+ -> Bitmap Index Scan on pg_proc_proname_args_nsp_index
+ Index Cond: ((proname >= 'R'::text) AND (proname < 'S'::text))
+ -> Bitmap Index Scan on pg_proc_proname_args_nsp_index
+ Index Cond: ((proname >= 'r'::text) AND (proname < 's'::text))
+(10 rows)
reset enable_seqscan;
reset enable_indexscan;
diff --git a/src/test/regress/expected/collate.icu.utf8.out b/src/test/regress/expected/collate.icu.utf8.out
index d4f327636f..f13f9e1245 100644
--- a/src/test/regress/expected/collate.icu.utf8.out
+++ b/src/test/regress/expected/collate.icu.utf8.out
@@ -988,14 +988,13 @@ SELECT relname, pg_get_indexdef(oid) FROM pg_class WHERE relname LIKE 'collate_t
set enable_seqscan = off;
explain (costs off)
select * from collate_test1 where b ilike 'abc';
- QUERY PLAN
--------------------------------
- Seq Scan on collate_test1
- Disabled: true
+ QUERY PLAN
+------------------------------------------------------
+ Index Scan using collate_test1_idx3 on collate_test1
Filter: (b ~~* 'abc'::text)
-(3 rows)
+(2 rows)
-select * from collate_test1 where b ilike 'abc';
+select * from collate_test1 where b ilike 'abc' order by 1;
a | b
---+-----
1 | abc
@@ -1004,14 +1003,13 @@ select * from collate_test1 where b ilike 'abc';
explain (costs off)
select * from collate_test1 where b ilike 'ABC';
- QUERY PLAN
--------------------------------
- Seq Scan on collate_test1
- Disabled: true
+ QUERY PLAN
+------------------------------------------------------
+ Index Scan using collate_test1_idx3 on collate_test1
Filter: (b ~~* 'ABC'::text)
-(3 rows)
+(2 rows)
-select * from collate_test1 where b ilike 'ABC';
+select * from collate_test1 where b ilike 'ABC' order by 1;
a | b
---+-----
1 | abc
diff --git a/src/test/regress/sql/collate.icu.utf8.sql b/src/test/regress/sql/collate.icu.utf8.sql
index 5ee2da4e0e..948201c3e1 100644
--- a/src/test/regress/sql/collate.icu.utf8.sql
+++ b/src/test/regress/sql/collate.icu.utf8.sql
@@ -344,10 +344,10 @@ SELECT relname, pg_get_indexdef(oid) FROM pg_class WHERE relname LIKE 'collate_t
set enable_seqscan = off;
explain (costs off)
select * from collate_test1 where b ilike 'abc';
-select * from collate_test1 where b ilike 'abc';
+select * from collate_test1 where b ilike 'abc' order by 1;
explain (costs off)
select * from collate_test1 where b ilike 'ABC';
-select * from collate_test1 where b ilike 'ABC';
+select * from collate_test1 where b ilike 'ABC' order by 1;
reset enable_seqscan;
--
2.34.1
--Multipart=_Wed__15_Jan_2025_01_40_46_+0900_vNCdK/fJlevI6qki
Content-Type: text/x-diff;
name="v2-0001-Allow-planner-support-function-to-return-index-co.patch"
Content-Disposition: attachment;
filename="v2-0001-Allow-planner-support-function-to-return-index-co.patch"
Content-Transfer-Encoding: 7bit
^ permalink raw reply [nested|flat] 11+ messages in thread
* Allow ILIKE forward matching to use btree index
@ 2024-12-19 18:22 Yugo Nagata <[email protected]>
0 siblings, 1 reply; 11+ messages in thread
From: Yugo Nagata @ 2024-12-19 18:22 UTC (permalink / raw)
To: pgsql-hackers
Hi,
Currently, btree indexes cannot used for ILIKE (~~*) operator if the pattern
has case-varying characters although LIKE (~~) expression can be converted
to indexable clauses by the planner support function (if the collation
is "C" or operator class 'text_pattern_ops' is used).
For example, "t ~~ '123foo%'" is converted to "(t >= '123foo' AND t < '123fop')"
and index scan can be used for this condition. On the other hand, "t ~~* '123foo'"
cannot be converted and sequential scan is used.
Even in this case, we can use a bitmap index scan for the condition
"(t >= '123f' AND t < '123g') OR "(t >= '123F' AND t < '123G')" followed by
recheck by the original condition "t ~~* '123foo'", and this could be faster
than seqscan.
However, even if the support function would return OR clauses, the current
planner implementation cannot not build bitmap scan paths using them.
The attached patches allow to ILIKE (~~*) forward matching to use btree index.
The patch 0001 enables get_index_clause_from_support to receive OR clauses
from support functions and use them to build bitmap index scan later. OR clauses
returned by support functions are collected in the new argument 'orclauses" of
match_restriction_clauses_to_index(), and they are passed to
generate_bitmap_or_paths() later to build bitmap scan paths.
The patch 0002 modifies the support function to return OR clauses as an example
above when ILIKE's pattern has case-varying characters in forward matching. The
OR clauses contains two index conditions for the upper and the lower letter of
the first case-varying character in the pattern respectively. Although the
subsequent characters are not considered in the index scans, it could enough be
faster then sequent scan.
Here is an example.
1. Create a table with random text records
=# CREATE TABLE tbl (t text);
=# INSERT INTO tbl SELECT CASE WHEN i%2=1 THEN upper(x) ELSE x END
FROM (SELECT i, md5(i::text) x FROM generate_series(1,5000000) i);
2. Create an index
=# CREATE INDEX ON tbl (t text_pattern_ops);
3. Before applying patch: Seq Scan was selected. It takes about 4 sec.
=# EXPLIN ANALYZE SELECT * FROM tbl WHERE t ILIKE '12ab%';
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------
Gather (cost=1000.00..58712.97 rows=500 width=33) (actual time=101.096..4110.979 rows=64 loops=1)
Workers Planned: 4
Workers Launched: 4
Buffers: shared hit=10778 read=31260
-> Parallel Seq Scan on tbl (cost=0.00..57662.97 rows=125 width=33) (actual time=440.232..4101.023 rows=13 loops=5)
Filter: (t ~~* '12ab%'::text)
Rows Removed by Filter: 999987
Buffers: shared hit=10778 read=31260
Planning Time: 0.415 ms
Execution Time: 4111.051 ms
(10 rows)
4. After applying patch: Bitmap Index Scan was selected. It takes only 10 ms.
=# EXPLIN ANALYZE SELECT * FROM tbl WHERE t ILIKE '12ab%';
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
--
Bitmap Heap Scan on tbl (cost=9.38..13.40 rows=500 width=33) (actual time=3.720..9.660 rows=64 loops=1)
Recheck Cond: (((t ~>=~ '12A'::text) AND (t ~<~ '12B'::text) AND (t ~~* '12ab%'::text)) OR ((t ~>=~ '12a'::text) AND (t ~<~ '12b'::text) AND (t ~~* '12ab%'::text))
)
Filter: (t ~~* '12ab%'::text)
Rows Removed by Filter: 1205
Heap Blocks: exact=1254
Buffers: shared hit=1271
-> BitmapOr (cost=9.38..9.38 rows=1 width=0) (actual time=2.370..2.372 rows=0 loops=1)
Buffers: shared hit=17
-> Bitmap Index Scan on tbl_t_idx (cost=0.00..4.57 rows=1 width=0) (actual time=1.192..1.193 rows=604 loops=1)
Index Cond: ((t ~>=~ '12A'::text) AND (t ~<~ '12B'::text))
Buffers: shared hit=8
-> Bitmap Index Scan on tbl_t_idx (cost=0.00..4.57 rows=1 width=0) (actual time=1.174..1.174 rows=675 loops=1)
Index Cond: ((t ~>=~ '12a'::text) AND (t ~<~ '12b'::text))
Buffers: shared hit=9
Planning Time: 1.144 ms
Execution Time: 9.785 ms
(16 rows)
What do you think about it?
I think another application of OR-clause returning support function might be
allowing to use an index for NOT LIKE (!~~) expression because, for example,
"t !~~ '123foo%'" could be converted to "(t < '123foo' OR t >= '123fooz')".
(The second condition is a bit loose but this would be safe and not problem
since tuples are filtered by the original condition after the index scan.)
However, it would not very useful unless the distribution is much skew so that
NOT LIKE expression's selectivity is enough small.
Regards,
Yugo Nagata
--
Yugo Nagata <[email protected]>
^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Allow ILIKE forward matching to use btree index
@ 2024-12-24 07:04 Yugo Nagata <[email protected]>
parent: Yugo Nagata <[email protected]>
0 siblings, 1 reply; 11+ messages in thread
From: Yugo Nagata @ 2024-12-24 07:04 UTC (permalink / raw)
To: Yugo Nagata <[email protected]>; +Cc: pgsql-hackers
On Fri, 20 Dec 2024 03:22:26 +0900
Yugo Nagata <[email protected]> wrote:
> Hi,
>
> Currently, btree indexes cannot used for ILIKE (~~*) operator if the pattern
> has case-varying characters although LIKE (~~) expression can be converted
> to indexable clauses by the planner support function (if the collation
> is "C" or operator class 'text_pattern_ops' is used).
>
> For example, "t ~~ '123foo%'" is converted to "(t >= '123foo' AND t < '123fop')"
> and index scan can be used for this condition. On the other hand, "t ~~* '123foo'"
> cannot be converted and sequential scan is used.
>
> Even in this case, we can use a bitmap index scan for the condition
> "(t >= '123f' AND t < '123g') OR "(t >= '123F' AND t < '123G')" followed by
> recheck by the original condition "t ~~* '123foo'", and this could be faster
> than seqscan.
>
> However, even if the support function would return OR clauses, the current
> planner implementation cannot not build bitmap scan paths using them.
>
>
> The attached patches allow to ILIKE (~~*) forward matching to use btree index.
>
> The patch 0001 enables get_index_clause_from_support to receive OR clauses
> from support functions and use them to build bitmap index scan later. OR clauses
> returned by support functions are collected in the new argument 'orclauses" of
> match_restriction_clauses_to_index(), and they are passed to
> generate_bitmap_or_paths() later to build bitmap scan paths.
>
> The patch 0002 modifies the support function to return OR clauses as an example
> above when ILIKE's pattern has case-varying characters in forward matching. The
> OR clauses contains two index conditions for the upper and the lower letter of
> the first case-varying character in the pattern respectively. Although the
> subsequent characters are not considered in the index scans, it could enough be
> faster then sequent scan.
>
> Here is an example.
>
> 1. Create a table with random text records
>
> =# CREATE TABLE tbl (t text);
> =# INSERT INTO tbl SELECT CASE WHEN i%2=1 THEN upper(x) ELSE x END
> FROM (SELECT i, md5(i::text) x FROM generate_series(1,5000000) i);
>
> 2. Create an index
> =# CREATE INDEX ON tbl (t text_pattern_ops);
>
> 3. Before applying patch: Seq Scan was selected. It takes about 4 sec.
>
> =# EXPLIN ANALYZE SELECT * FROM tbl WHERE t ILIKE '12ab%';
I am sorry, the example in my previous main was wrong. I showed the plan
with enable_index_scan = off. Indead, if the pattern starts with
case-insensitive characters like '12', an index scan can be used even with
ILIKE.
postgres=# EXPLAIN ANALYZE SELECT * FROM tbl WHERE t ILIKE 'abc%';
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------
Gather (cost=1000.00..69129.61 rows=500 width=33) (actual time=36.317..4034.770 rows=1188 loops=1)
Workers Planned: 2
Workers Launched: 2
Buffers: shared hit=99 read=41939
-> Parallel Seq Scan on tbl (cost=0.00..68079.61 rows=208 width=33) (actual time=19.908..4023.668 rows=396 loops=3)
Filter: (t ~~* 'abc%'::text)
Rows Removed by Filter: 1666271
Buffers: shared hit=99 read=41939
Planning Time: 0.726 ms
Execution Time: 4035.101 ms
(10 rows)
4. After applying patch: Bitmap Index Scan was selected.
postgres=# EXPLAIN ANALYZE SELECT * FROM tbl WHERE t ILIKE 'abc%';
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tbl (cost=12563.66..58314.53 rows=500 width=33) (actual time=156.485..1266.789 rows=1188 loops=1)
Recheck Cond: (((t ~>=~ 'A'::text) AND (t ~<~ 'B'::text) AND (t ~~* 'abc%'::text)) OR ((t ~>=~ 'a'::text) AND (t ~<~ 'b'::text) AND (t ~~* 'abc%'::text)))
Filter: (t ~~* 'abc%'::text)
Rows Removed by Filter: 311473
Heap Blocks: exact=42010
Buffers: shared hit=1 read=44600
-> BitmapOr (cost=12563.66..12563.66 rows=297029 width=0) (actual time=136.979..136.980 rows=0 loops=1)
Buffers: shared hit=1 read=2590
-> Bitmap Index Scan on tbl_t_idx (cost=0.00..6281.71 rows=148515 width=0) (actual time=80.548..80.549 rows=158375 loops=1)
Index Cond: ((t ~>=~ 'A'::text) AND (t ~<~ 'B'::text))
Buffers: shared read=1272
-> Bitmap Index Scan on tbl_t_idx (cost=0.00..6281.71 rows=148515 width=0) (actual time=56.427..56.427 rows=157042 loops=1)
Index Cond: ((t ~>=~ 'a'::text) AND (t ~<~ 'b'::text))
Buffers: shared hit=1 read=1318
Planning Time: 0.592 ms
Execution Time: 1267.162 ms
(16 rows)
> What do you think about it?
>
> I think another application of OR-clause returning support function might be
> allowing to use an index for NOT LIKE (!~~) expression because, for example,
> "t !~~ '123foo%'" could be converted to "(t < '123foo' OR t >= '123fooz')".
> (The second condition is a bit loose but this would be safe and not problem
> since tuples are filtered by the original condition after the index scan.)
> However, it would not very useful unless the distribution is much skew so that
> NOT LIKE expression's selectivity is enough small.
Regards,
Yugo Nagata
--
Yugo Nagata <[email protected]>
^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Allow ILIKE forward matching to use btree index
@ 2025-01-14 16:40 Yugo NAGATA <[email protected]>
parent: Yugo Nagata <[email protected]>
0 siblings, 1 reply; 11+ messages in thread
From: Yugo NAGATA @ 2025-01-14 16:40 UTC (permalink / raw)
To: Yugo Nagata <[email protected]>; +Cc: pgsql-hackers
On Tue, 24 Dec 2024 16:04:42 +0900
Yugo Nagata <[email protected]> wrote:
> On Fri, 20 Dec 2024 03:22:26 +0900
> Yugo Nagata <[email protected]> wrote:
>
> > Hi,
> >
> > Currently, btree indexes cannot used for ILIKE (~~*) operator if the pattern
> > has case-varying characters although LIKE (~~) expression can be converted
> > to indexable clauses by the planner support function (if the collation
> > is "C" or operator class 'text_pattern_ops' is used).
> >
> > For example, "t ~~ '123foo%'" is converted to "(t >= '123foo' AND t < '123fop')"
> > and index scan can be used for this condition. On the other hand, "t ~~* '123foo'"
> > cannot be converted and sequential scan is used.
> >
> > Even in this case, we can use a bitmap index scan for the condition
> > "(t >= '123f' AND t < '123g') OR "(t >= '123F' AND t < '123G')" followed by
> > recheck by the original condition "t ~~* '123foo'", and this could be faster
> > than seqscan.
> >
> > However, even if the support function would return OR clauses, the current
> > planner implementation cannot not build bitmap scan paths using them.
> >
> >
> > The attached patches allow to ILIKE (~~*) forward matching to use btree index.
> >
> > The patch 0001 enables get_index_clause_from_support to receive OR clauses
> > from support functions and use them to build bitmap index scan later. OR clauses
> > returned by support functions are collected in the new argument 'orclauses" of
> > match_restriction_clauses_to_index(), and they are passed to
> > generate_bitmap_or_paths() later to build bitmap scan paths.
> >
> > The patch 0002 modifies the support function to return OR clauses as an example
> > above when ILIKE's pattern has case-varying characters in forward matching. The
> > OR clauses contains two index conditions for the upper and the lower letter of
> > the first case-varying character in the pattern respectively. Although the
> > subsequent characters are not considered in the index scans, it could enough be
> > faster then sequent scan.
> >
> > Here is an example.
> >
> > 1. Create a table with random text records
> >
> > =# CREATE TABLE tbl (t text);
> > =# INSERT INTO tbl SELECT CASE WHEN i%2=1 THEN upper(x) ELSE x END
> > FROM (SELECT i, md5(i::text) x FROM generate_series(1,5000000) i);
> >
> > 2. Create an index
> > =# CREATE INDEX ON tbl (t text_pattern_ops);
> >
> > 3. Before applying patch: Seq Scan was selected. It takes about 4 sec.
> >
> > =# EXPLIN ANALYZE SELECT * FROM tbl WHERE t ILIKE '12ab%';
>
> I am sorry, the example in my previous main was wrong. I showed the plan
> with enable_index_scan = off. Indead, if the pattern starts with
> case-insensitive characters like '12', an index scan can be used even with
> ILIKE.
>
> postgres=# EXPLAIN ANALYZE SELECT * FROM tbl WHERE t ILIKE 'abc%';
> QUERY PLAN
> -------------------------------------------------------------------------------------------------------------------------
> Gather (cost=1000.00..69129.61 rows=500 width=33) (actual time=36.317..4034.770 rows=1188 loops=1)
> Workers Planned: 2
> Workers Launched: 2
> Buffers: shared hit=99 read=41939
> -> Parallel Seq Scan on tbl (cost=0.00..68079.61 rows=208 width=33) (actual time=19.908..4023.668 rows=396 loops=3)
> Filter: (t ~~* 'abc%'::text)
> Rows Removed by Filter: 1666271
> Buffers: shared hit=99 read=41939
> Planning Time: 0.726 ms
> Execution Time: 4035.101 ms
> (10 rows)
>
> 4. After applying patch: Bitmap Index Scan was selected.
>
> postgres=# EXPLAIN ANALYZE SELECT * FROM tbl WHERE t ILIKE 'abc%';
> QUERY PLAN
> --------------------------------------------------------------------------------------------------------------------------------------------------------------
> Bitmap Heap Scan on tbl (cost=12563.66..58314.53 rows=500 width=33) (actual time=156.485..1266.789 rows=1188 loops=1)
> Recheck Cond: (((t ~>=~ 'A'::text) AND (t ~<~ 'B'::text) AND (t ~~* 'abc%'::text)) OR ((t ~>=~ 'a'::text) AND (t ~<~ 'b'::text) AND (t ~~* 'abc%'::text)))
> Filter: (t ~~* 'abc%'::text)
> Rows Removed by Filter: 311473
> Heap Blocks: exact=42010
> Buffers: shared hit=1 read=44600
> -> BitmapOr (cost=12563.66..12563.66 rows=297029 width=0) (actual time=136.979..136.980 rows=0 loops=1)
> Buffers: shared hit=1 read=2590
> -> Bitmap Index Scan on tbl_t_idx (cost=0.00..6281.71 rows=148515 width=0) (actual time=80.548..80.549 rows=158375 loops=1)
> Index Cond: ((t ~>=~ 'A'::text) AND (t ~<~ 'B'::text))
> Buffers: shared read=1272
> -> Bitmap Index Scan on tbl_t_idx (cost=0.00..6281.71 rows=148515 width=0) (actual time=56.427..56.427 rows=157042 loops=1)
> Index Cond: ((t ~>=~ 'a'::text) AND (t ~<~ 'b'::text))
> Buffers: shared hit=1 read=1318
> Planning Time: 0.592 ms
> Execution Time: 1267.162 ms
> (16 rows)
>
>
> > What do you think about it?
> >
> > I think another application of OR-clause returning support function might be
> > allowing to use an index for NOT LIKE (!~~) expression because, for example,
> > "t !~~ '123foo%'" could be converted to "(t < '123foo' OR t >= '123fooz')".
> > (The second condition is a bit loose but this would be safe and not problem
> > since tuples are filtered by the original condition after the index scan.)
> > However, it would not very useful unless the distribution is much skew so that
> > NOT LIKE expression's selectivity is enough small.
I added a new patch 0003 that enables ILIKE forward matching to use a SP-Gist index.
Similar to 0002, this generates BitmapOr Index Scan for two index clauses that use
"^@" operator for upper letter and lower letter pattern respectively.
* Before applying the patch:
postgres=# explain analyze select* from tbl where t ilike 'abc%';
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Gather (cost=1000.00..18899.52 rows=101 width=33) (actual time=41.799..930.382 rows=253 loops=1)
Workers Planned: 2
Workers Launched: 2
Buffers: shared hit=96 read=12533
-> Parallel Seq Scan on tbl (cost=0.00..17889.42 rows=42 width=33) (actual time=26.041..917.570 rows=84 loops=3)
Filter: (t ~~* 'abc%'::text)
Rows Removed by Filter: 336582
Buffers: shared hit=96 read=12533
Planning Time: 0.690 ms
Execution Time: 930.545 ms
(10 rows)
* After applying the patch:
postgres=# explain analyze select* from tbl where t ilike 'abc%';
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tbl (cost=3307.96..16702.11 rows=101 width=33) (actual time=69.449..215.636 rows=253 loops=1)
Recheck Cond: (((t ^@ 'A'::text) AND (t ~~* 'abc%'::text)) OR ((t ^@ 'a'::text) AND (t ~~* 'abc%'::text)))
Filter: (t ~~* 'abc%'::text)
Rows Removed by Filter: 62992
Heap Blocks: exact=12437
Buffers: shared hit=18529
-> BitmapOr (cost=3307.96..3307.96 rows=61212 width=0) (actual time=62.567..62.568 rows=0 loops=1)
Buffers: shared hit=6092
-> Bitmap Index Scan on tbl_t_idx (cost=0.00..1653.96 rows=30606 width=0) (actual time=41.893..41.893 rows=31536 loops=1)
Index Cond: (t ^@ 'A'::text)
Buffers: shared hit=2461
-> Bitmap Index Scan on tbl_t_idx (cost=0.00..1653.96 rows=30606 width=0) (actual time=20.671..20.671 rows=31709 loops=1)
Index Cond: (t ^@ 'a'::text)
Buffers: shared hit=3631
Planning Time: 1.414 ms
Execution Time: 215.903 ms
(16 rows)
--
Yugo NAGATA <[email protected]>
^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Allow ILIKE forward matching to use btree index
@ 2025-01-15 22:34 Jeff Davis <[email protected]>
parent: Yugo NAGATA <[email protected]>
0 siblings, 1 reply; 11+ messages in thread
From: Jeff Davis @ 2025-01-15 22:34 UTC (permalink / raw)
To: Yugo NAGATA <[email protected]>; +Cc: pgsql-hackers
On Wed, 2025-01-15 at 01:40 +0900, Yugo NAGATA wrote:
> > > For example, "t ~~ '123foo%'" is converted to "(t >= '123foo' AND
> > > t < '123fop')"
> > > and index scan can be used for this condition. On the other hand,
> > > "t ~~* '123foo'"
> > > cannot be converted and sequential scan is used.
> > >
> > > Even in this case, we can use a bitmap index scan for the
> > > condition
> > > "(t >= '123f' AND t < '123g') OR "(t >= '123F' AND t < '123G')"
> > > followed by
> > > recheck by the original condition "t ~~* '123foo'", and this
> > > could be faster
> > > than seqscan.
In theory, there could be many OR clauses:
(t >= '123foo' AND t < '123fop') OR
(t >= '123foo' AND t < '123fop') OR
(t >= '123foo' AND t < '123fop') OR
(t >= '123foo' AND t < '123fop') OR
(t >= '123foo' AND t < '123fop') OR
(t >= '123foo' AND t < '123fop') OR
> > > The patch 0001 enables get_index_clause_from_support to receive
> > > OR clauses
> > > from support functions and use them to build bitmap index scan
> > > later. OR clauses
> > > returned by support functions are collected in the new argument
> > > 'orclauses" of
> > > match_restriction_clauses_to_index(), and they are passed to
> > > generate_bitmap_or_paths() later to build bitmap scan paths.
If I understand correctly, this
> > > The patch 0002 modifies the support function to return OR clauses
> > > as an example
> > > above when ILIKE's pattern has case-varying characters in forward
> > > matching. The
> > > OR clauses contains two index conditions for the upper and the
> > > lower letter of
> > > the first case-varying character in the pattern respectively.
> > > Although the
> > > subsequent characters are not considered in the index scans, it
> > > could enough be
> > > faster then sequent scan.
> > >
> > > Here is an example.
> > >
> > > 1. Create a table with random text records
> > >
> > > =# CREATE TABLE tbl (t text);
> > > =# INSERT INTO tbl SELECT CASE WHEN i%2=1 THEN upper(x) ELSE x
> > > END
> > > FROM (SELECT i, md5(i::text) x FROM
> > > generate_series(1,5000000) i);
> > >
> > > 2. Create an index
> > > =# CREATE INDEX ON tbl (t text_pattern_ops);
> > >
> > > 3. Before applying patch: Seq Scan was selected. It takes about 4
> > > sec.
> > >
> > > =# EXPLIN ANALYZE SELECT * FROM tbl WHERE t ILIKE '12ab%';
> >
> > I am sorry, the example in my previous main was wrong. I showed the
> > plan
> > with enable_index_scan = off. Indead, if the pattern starts with
> > case-insensitive characters like '12', an index scan can be used
> > even with
> > ILIKE.
> >
> > postgres=# EXPLAIN ANALYZE SELECT * FROM tbl WHERE t ILIKE 'abc%';
> > QUERY
> > PLAN
> > -------------------------------------------------------------------
> > ------------------------------------------------------
> > Gather (cost=1000.00..69129.61 rows=500 width=33) (actual
> > time=36.317..4034.770 rows=1188 loops=1)
> > Workers Planned: 2
> > Workers Launched: 2
> > Buffers: shared hit=99 read=41939
> > -> Parallel Seq Scan on tbl (cost=0.00..68079.61 rows=208
> > width=33) (actual time=19.908..4023.668 rows=396 loops=3)
> > Filter: (t ~~* 'abc%'::text)
> > Rows Removed by Filter: 1666271
> > Buffers: shared hit=99 read=41939
> > Planning Time: 0.726 ms
> > Execution Time: 4035.101 ms
> > (10 rows)
> >
> > 4. After applying patch: Bitmap Index Scan was selected.
> >
> > postgres=# EXPLAIN ANALYZE SELECT * FROM tbl WHERE t ILIKE 'abc%';
> >
> > QUERY
> > PLAN
> >
> > -------------------------------------------------------------------
> > -------------------------------------------------------------------
> > ------------------------
> > Bitmap Heap Scan on tbl (cost=12563.66..58314.53 rows=500
> > width=33) (actual time=156.485..1266.789 rows=1188 loops=1)
> > Recheck Cond: (((t ~>=~ 'A'::text) AND (t ~<~ 'B'::text) AND (t
> > ~~* 'abc%'::text)) OR ((t ~>=~ 'a'::text) AND (t ~<~ 'b'::text) AND
> > (t ~~* 'abc%'::text)))
> > Filter: (t ~~* 'abc%'::text)
> > Rows Removed by Filter: 311473
> > Heap Blocks: exact=42010
> > Buffers: shared hit=1 read=44600
> > -> BitmapOr (cost=12563.66..12563.66 rows=297029 width=0)
> > (actual time=136.979..136.980 rows=0 loops=1)
> > Buffers: shared hit=1 read=2590
> > -> Bitmap Index Scan on tbl_t_idx (cost=0.00..6281.71
> > rows=148515 width=0) (actual time=80.548..80.549 rows=158375
> > loops=1)
> > Index Cond: ((t ~>=~ 'A'::text) AND (t ~<~
> > 'B'::text))
> > Buffers: shared read=1272
> > -> Bitmap Index Scan on tbl_t_idx (cost=0.00..6281.71
> > rows=148515 width=0) (actual time=56.427..56.427 rows=157042
> > loops=1)
> > Index Cond: ((t ~>=~ 'a'::text) AND (t ~<~
> > 'b'::text))
> > Buffers: shared hit=1 read=1318
> > Planning Time: 0.592 ms
> > Execution Time: 1267.162 ms
> > (16 rows)
> >
> >
> > > What do you think about it?
> > >
> > > I think another application of OR-clause returning support
> > > function might be
> > > allowing to use an index for NOT LIKE (!~~) expression because,
> > > for example,
> > > "t !~~ '123foo%'" could be converted to "(t < '123foo' OR t >=
> > > '123fooz')".
> > > (The second condition is a bit loose but this would be safe and
> > > not problem
> > > since tuples are filtered by the original condition after the
> > > index scan.)
> > > However, it would not very useful unless the distribution is much
> > > skew so that
> > > NOT LIKE expression's selectivity is enough small.
>
> I added a new patch 0003 that enables ILIKE forward matching to use a
> SP-Gist index.
> Similar to 0002, this generates BitmapOr Index Scan for two index
> clauses that use
> "^@" operator for upper letter and lower letter pattern respectively.
>
> * Before applying the patch:
>
> postgres=# explain analyze select* from tbl where t ilike 'abc%';
> QUERY
> PLAN
> ---------------------------------------------------------------------
> -------------------------------------------------
> Gather (cost=1000.00..18899.52 rows=101 width=33) (actual
> time=41.799..930.382 rows=253 loops=1)
> Workers Planned: 2
> Workers Launched: 2
> Buffers: shared hit=96 read=12533
> -> Parallel Seq Scan on tbl (cost=0.00..17889.42 rows=42
> width=33) (actual time=26.041..917.570 rows=84 loops=3)
> Filter: (t ~~* 'abc%'::text)
> Rows Removed by Filter: 336582
> Buffers: shared hit=96 read=12533
> Planning Time: 0.690 ms
> Execution Time: 930.545 ms
> (10 rows)
>
>
> * After applying the patch:
>
> postgres=# explain analyze select* from tbl where t ilike 'abc%';
> QUERY
> PLAN
> ---------------------------------------------------------------------
> ----------------------------------------------------------------
> Bitmap Heap Scan on tbl (cost=3307.96..16702.11 rows=101 width=33)
> (actual time=69.449..215.636 rows=253 loops=1)
> Recheck Cond: (((t ^@ 'A'::text) AND (t ~~* 'abc%'::text)) OR ((t
> ^@ 'a'::text) AND (t ~~* 'abc%'::text)))
> Filter: (t ~~* 'abc%'::text)
> Rows Removed by Filter: 62992
> Heap Blocks: exact=12437
> Buffers: shared hit=18529
> -> BitmapOr (cost=3307.96..3307.96 rows=61212 width=0) (actual
> time=62.567..62.568 rows=0 loops=1)
> Buffers: shared hit=6092
> -> Bitmap Index Scan on tbl_t_idx (cost=0.00..1653.96
> rows=30606 width=0) (actual time=41.893..41.893 rows=31536 loops=1)
> Index Cond: (t ^@ 'A'::text)
> Buffers: shared hit=2461
> -> Bitmap Index Scan on tbl_t_idx (cost=0.00..1653.96
> rows=30606 width=0) (actual time=20.671..20.671 rows=31709 loops=1)
> Index Cond: (t ^@ 'a'::text)
> Buffers: shared hit=3631
> Planning Time: 1.414 ms
> Execution Time: 215.903 ms
> (16 rows)
>
>
^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Allow ILIKE forward matching to use btree index
@ 2025-01-15 22:40 Jeff Davis <[email protected]>
parent: Jeff Davis <[email protected]>
0 siblings, 1 reply; 11+ messages in thread
From: Jeff Davis @ 2025-01-15 22:40 UTC (permalink / raw)
To: Yugo NAGATA <[email protected]>; +Cc: pgsql-hackers
My apologies, I sent the previous email prematurely. Let me try again:
On Wed, 2025-01-15 at 14:34 -0800, Jeff Davis wrote:
> On Wed, 2025-01-15 at 01:40 +0900, Yugo NAGATA wrote:
> > > > For example, "t ~~ '123foo%'" is converted to "(t >= '123foo'
> > > > AND
> > > > t < '123fop')"
> > > > and index scan can be used for this condition. On the other
> > > > hand,
> > > > "t ~~* '123foo'"
> > > > cannot be converted and sequential scan is used.
> > > >
> > > > Even in this case, we can use a bitmap index scan for the
> > > > condition
> > > > "(t >= '123f' AND t < '123g') OR "(t >= '123F' AND t < '123G')"
> > > > followed by
> > > > recheck by the original condition "t ~~* '123foo'", and this
> > > > could be faster
> > > > than seqscan.
In theory, there could be many OR clauses:
(t >= '123foo' AND t < '123fop') OR
(t >= '123Foo' AND t < '123Fop') OR
(t >= '123fOo' AND t < '123fOp') OR
(t >= '123FOo' AND t < '123FOp') OR
...
How should that be limited?
> > >
Regards,
Jeff Davis
^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Allow ILIKE forward matching to use btree index
@ 2025-01-16 05:53 Yugo NAGATA <[email protected]>
parent: Jeff Davis <[email protected]>
0 siblings, 1 reply; 11+ messages in thread
From: Yugo NAGATA @ 2025-01-16 05:53 UTC (permalink / raw)
To: Jeff Davis <[email protected]>; +Cc: pgsql-hackers
On Wed, 15 Jan 2025 14:40:19 -0800
Jeff Davis <[email protected]> wrote:
> My apologies, I sent the previous email prematurely. Let me try again:
>
> On Wed, 2025-01-15 at 14:34 -0800, Jeff Davis wrote:
> > On Wed, 2025-01-15 at 01:40 +0900, Yugo NAGATA wrote:
> > > > > For example, "t ~~ '123foo%'" is converted to "(t >= '123foo'
> > > > > AND
> > > > > t < '123fop')"
> > > > > and index scan can be used for this condition. On the other
> > > > > hand,
> > > > > "t ~~* '123foo'"
> > > > > cannot be converted and sequential scan is used.
> > > > >
> > > > > Even in this case, we can use a bitmap index scan for the
> > > > > condition
> > > > > "(t >= '123f' AND t < '123g') OR "(t >= '123F' AND t < '123G')"
> > > > > followed by
> > > > > recheck by the original condition "t ~~* '123foo'", and this
> > > > > could be faster
> > > > > than seqscan.
>
> In theory, there could be many OR clauses:
>
> (t >= '123foo' AND t < '123fop') OR
> (t >= '123Foo' AND t < '123Fop') OR
> (t >= '123fOo' AND t < '123fOp') OR
> (t >= '123FOo' AND t < '123FOp') OR
> ...
>
> How should that be limited?
Instead of generating complete patterns considering every case-varying characters,
two clauses considering only the first case-varying character are generated.
For example, for the condition "t ILIKE '123foo%'", the generated condition is
"(t >= '123f' AND t < '123g') OR "(t >= '123F' AND t < '123G')".
Rows meeting "(t >= '123f' AND t < '123g')" includes those whose "t" start with
'123f', that is meeting the following;
> (t >= '123foo' AND t < '123fop') OR
> (t >= '123fOo' AND t < '123fOp') OR
> ...
, and rows meeting "(t >= '123F' AND t < '123G')" includes those whose "t" start
with '123F', that is meeting the following;
> (t >= '123Foo' AND t < '123Fop') OR
> (t >= '123FOo' AND t < '123FOp') OR
> ...
It is required that the second case-varying character and later are checked after
the index scan, and some rows are filtered, but it will be still faster than full
sequential scan.
Regards,
Yugo Nagata
--
Yugo NAGATA <[email protected]>
^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Allow ILIKE forward matching to use btree index
@ 2025-01-16 17:41 Jeff Davis <[email protected]>
parent: Yugo NAGATA <[email protected]>
0 siblings, 1 reply; 11+ messages in thread
From: Jeff Davis @ 2025-01-16 17:41 UTC (permalink / raw)
To: Yugo NAGATA <[email protected]>; +Cc: pgsql-hackers
On Thu, 2025-01-16 at 14:53 +0900, Yugo NAGATA wrote:
> Instead of generating complete patterns considering every case-
> varying characters,
> two clauses considering only the first case-varying character are
> generated.
Did you consider other approaches that integrate more deeply into the
indexing infrastructure? This feels almost like a skip scan, which
Petter Geoghegan is working on. If you model the disjunctions as skips,
and provide the right API that the index AM can use, then there would
be no limit.
For example:
start scanning at '123FOO'
when you encounter '123FOP' skip to '123FOo'
continue scanning
when you encounter '123FOp' skip to '123FoO'
...
Also, I'm working on better Unicode support to handle multiple case
variants in patterns. For instance, the Greek letter Sigma has three
case variants (one upper and two lower). What's the right API so that
the index AM knows which case variants will sort first, so that the
skips don't go backward?
Regards,
Jeff Davis
^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Allow ILIKE forward matching to use btree index
@ 2025-03-31 14:09 Yugo NAGATA <[email protected]>
parent: Jeff Davis <[email protected]>
0 siblings, 0 replies; 11+ messages in thread
From: Yugo NAGATA @ 2025-03-31 14:09 UTC (permalink / raw)
To: Jeff Davis <[email protected]>; +Cc: pgsql-hackers
On Thu, 16 Jan 2025 09:41:35 -0800
Jeff Davis <[email protected]> wrote:
> On Thu, 2025-01-16 at 14:53 +0900, Yugo NAGATA wrote:
> > Instead of generating complete patterns considering every case-
> > varying characters,
> > two clauses considering only the first case-varying character are
> > generated.
>
> Did you consider other approaches that integrate more deeply into the
> indexing infrastructure? This feels almost like a skip scan, which
> Petter Geoghegan is working on. If you model the disjunctions as skips,
> and provide the right API that the index AM can use, then there would
> be no limit.
>
> For example:
>
> start scanning at '123FOO'
> when you encounter '123FOP' skip to '123FOo'
> continue scanning
> when you encounter '123FOp' skip to '123FoO'
> ...
That seems true there is similarity between ILIKE search and skip scan,
although, on my understand, skip scan is for multi-column indexes
rather than text. I have no concrete idea how the infrastructure for skip
scan to improve ILIKE, anyway.
> Also, I'm working on better Unicode support to handle multiple case
> variants in patterns. For instance, the Greek letter Sigma has three
> case variants (one upper and two lower). What's the right API so that
> the index AM knows which case variants will sort first, so that the
> skips don't go backward?
That seems true there is similarity between ILIKE search and skip scan,
although, on my understand, skip scan is for multi-column indexes
rather than text. I have no concrete idea how the infrastructure for skip
scan to improve ILIKE, anyway.
> Also, I'm working on better Unicode support to handle multiple case
> variants in patterns. For instance, the Greek letter Sigma has three
> case variants (one upper and two lower). What's the right API so that
> the index AM knows which case variants will sort first, so that the
> skips don't go backward?
I don't have idea for handling letters with multiple case variants in my patch,
either. I overlooked such pattern at all. So, I'll withdraw the proposal, for now.
Regards,
Yugo Nagata
--
Yugo NAGATA <[email protected]>
^ permalink raw reply [nested|flat] 11+ messages in thread
end of thread, other threads:[~2025-03-31 14:09 UTC | newest]
Thread overview: 11+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2020-05-03 14:37 [PATCH v36 1/6] Introduce RelOptInfo->notnullattrs attribute 一挃 <[email protected]>
2024-12-19 14:41 [PATCH 2/2] Allow ILIKE forward matching to use btree index Yugo Nagata <[email protected]>
2024-12-19 14:41 [PATCH v2 2/3] Allow ILIKE forward matching to use btree index Yugo Nagata <[email protected]>
2024-12-19 18:22 Allow ILIKE forward matching to use btree index Yugo Nagata <[email protected]>
2024-12-24 07:04 ` Re: Allow ILIKE forward matching to use btree index Yugo Nagata <[email protected]>
2025-01-14 16:40 ` Re: Allow ILIKE forward matching to use btree index Yugo NAGATA <[email protected]>
2025-01-15 22:34 ` Re: Allow ILIKE forward matching to use btree index Jeff Davis <[email protected]>
2025-01-15 22:40 ` Re: Allow ILIKE forward matching to use btree index Jeff Davis <[email protected]>
2025-01-16 05:53 ` Re: Allow ILIKE forward matching to use btree index Yugo NAGATA <[email protected]>
2025-01-16 17:41 ` Re: Allow ILIKE forward matching to use btree index Jeff Davis <[email protected]>
2025-03-31 14:09 ` Re: Allow ILIKE forward matching to use btree index Yugo NAGATA <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox