MonetDB: default - Use hash for long grouping expressions too

[Pedro Ferreira]

Changeset: 72cfd4cf9bb8 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/72cfd4cf9bb8
Modified Files:
        sql/server/rel_select.c
Branch: default
Log Message:

Use hash for long grouping expressions too


diffs (56 lines):

diff --git a/sql/server/rel_select.c b/sql/server/rel_select.c
--- a/sql/server/rel_select.c
+++ b/sql/server/rel_select.c
@@ -5318,6 +5318,43 @@ check_distinct_exp_names(mvc *sql, list 
 }
 
 static list *
+group_merge_exps(mvc *sql, list *gexps, list *exps)
+{
+       int nexps = list_length(gexps) + list_length(exps);
+
+       if (nexps < 5) {
+               return list_distinct(list_merge(gexps, exps, (fdup) NULL), 
(fcmp) exp_equal, (fdup) NULL);
+       } else { /* for longer lists, use hashing */
+               sql_hash *ht = hash_new(sql->ta, nexps, (fkeyvalue)&exp_key);
+
+               for (node *n = gexps->h; n ; n = n->next) { /* first add 
grouping expressions */
+                       sql_exp *e = n->data;
+                       int key = ht->key(e);
+
+                       hash_add(ht, key, e);
+               }
+
+               for (node *n = exps->h; n ; n = n->next) { /* then test if the 
new grouping expressions are already there */
+                       sql_exp *e = n->data;
+                       int key = ht->key(e);
+                       sql_hash_e *he = ht->buckets[key&(ht->size-1)];
+                       bool duplicates = false;
+
+                       for (; he && !duplicates; he = he->chain) {
+                               sql_exp *f = he->value;
+
+                               if (!exp_equal(e, f))
+                                       duplicates = true;
+                       }
+                       hash_add(ht, key, e);
+                       if (!duplicates)
+                               list_append(gexps, e);
+               }
+               return gexps;
+       }
+}
+
+static list *
 rel_table_exp(sql_query *query, sql_rel **rel, symbol *column_e, bool 
single_exp )
 {
        mvc *sql = query->sql;
@@ -5359,7 +5396,7 @@ rel_table_exp(sql_query *query, sql_rel 
                        if (!(exps = check_distinct_exp_names(sql, exps)))
                                return sql_error(sql, 02, SQLSTATE(42000) 
"Duplicate column names in table%s%s%s projection list", tname ? " '" : "", 
tname ? tname : "", tname ? "'" : "");
                        if (groupby) {
-                               groupby->exps = 
list_distinct(list_merge(groupby->exps, exps, (fdup) NULL), (fcmp) exp_equal, 
(fdup) NULL);
+                               groupby->exps = group_merge_exps(sql, 
groupby->exps, exps);
                                for (node *n = groupby->exps->h ; n ; n = 
n->next) {
                                        sql_exp *e = n->data;
 
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
https://www.monetdb.org/mailman/listinfo/checkin-list