Line data Source code
1 : /*
2 : * SPDX-License-Identifier: MPL-2.0
3 : *
4 : * This Source Code Form is subject to the terms of the Mozilla Public
5 : * License, v. 2.0. If a copy of the MPL was not distributed with this
6 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7 : *
8 : * Copyright 2024 MonetDB Foundation;
9 : * Copyright August 2008 - 2023 MonetDB B.V.;
10 : * Copyright 1997 - July 2008 CWI.
11 : */
12 :
13 : #include "monetdb_config.h"
14 : #include "gdk.h"
15 : #include "gdk_private.h"
16 :
17 : /* Calculate a cross product between bats l and r with optional
18 : * candidate lists sl for l and sr for r.
19 : * The result is two bats r1 and r2 which contain the OID (head
20 : * values) of the input bats l and r.
21 : * If max_one is set, r can have at most one row. */
22 : static gdk_return
23 45913 : BATcrossci(BAT **r1p, BAT **r2p, struct canditer *ci1, struct canditer *ci2)
24 : {
25 45913 : BAT *bn1, *bn2 = NULL;
26 45913 : oid *restrict p;
27 45913 : BUN i, j;
28 :
29 45913 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
30 :
31 : /* first some special cases */
32 45930 : if (ci1->ncand == 0 || ci2->ncand == 0) {
33 24226 : if ((bn1 = BATdense(0, 0, 0)) == NULL)
34 : return GDK_FAIL;
35 24009 : if (r2p) {
36 23421 : if ((bn2 = BATdense(0, 0, 0)) == NULL) {
37 0 : BBPreclaim(bn1);
38 0 : return GDK_FAIL;
39 : }
40 23466 : *r2p = bn2;
41 : }
42 24054 : *r1p = bn1;
43 24054 : return GDK_SUCCEED;
44 : }
45 21704 : if (ci2->ncand == 1) {
46 14742 : if ((bn1 = canditer_slice(ci1, 0, ci1->ncand)) == NULL)
47 : return GDK_FAIL;
48 14407 : if (r2p) {
49 13878 : if (ci1->ncand == 1) {
50 4494 : bn2 = canditer_slice(ci2, 0, ci2->ncand);
51 : } else {
52 9384 : bn2 = BATconstant(0, TYPE_oid, &ci2->seq, ci1->ncand, TRANSIENT);
53 : }
54 13876 : if (bn2 == NULL) {
55 0 : BBPreclaim(bn1);
56 0 : return GDK_FAIL;
57 : }
58 13876 : *r2p = bn2;
59 : }
60 14405 : *r1p = bn1;
61 14405 : return GDK_SUCCEED;
62 : }
63 6962 : if (ci1->ncand == 1) {
64 2108 : bn1 = BATconstant(0, TYPE_oid, &ci1->seq, ci2->ncand, TRANSIENT);
65 2086 : if (bn1 == NULL)
66 : return GDK_FAIL;
67 2086 : if (r2p) {
68 1892 : bn2 = canditer_slice(ci2, 0, ci2->ncand);
69 1893 : if (bn2 == NULL) {
70 0 : BBPreclaim(bn1);
71 0 : return GDK_FAIL;
72 : }
73 1893 : *r2p = bn2;
74 : }
75 2087 : *r1p = bn1;
76 2087 : return GDK_SUCCEED;
77 : }
78 :
79 4854 : bn1 = COLnew(0, TYPE_oid, ci1->ncand * ci2->ncand, TRANSIENT);
80 4849 : if (r2p)
81 4593 : bn2 = COLnew(0, TYPE_oid, ci1->ncand * ci2->ncand, TRANSIENT);
82 4840 : if (bn1 == NULL || (r2p && bn2 == NULL)) {
83 0 : BBPreclaim(bn1);
84 0 : BBPreclaim(bn2);
85 0 : return GDK_FAIL;
86 : }
87 4840 : if (ci1->ncand > 0 && ci2->ncand > 0) {
88 4840 : BATsetcount(bn1, ci1->ncand * ci2->ncand);
89 4853 : bn1->tsorted = true;
90 4853 : bn1->trevsorted = ci1->ncand <= 1;
91 4853 : bn1->tkey = ci2->ncand <= 1;
92 4853 : bn1->tnil = false;
93 4853 : bn1->tnonil = true;
94 4853 : p = (oid *) Tloc(bn1, 0);
95 276822 : for (i = 0; i < ci1->ncand; i++) {
96 271979 : GDK_CHECK_TIMEOUT_BODY(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
97 272106 : oid x = canditer_next(ci1);
98 8121791 : for (j = 0; j < ci2->ncand; j++) {
99 7577716 : *p++ = x;
100 : }
101 : }
102 4843 : BATtseqbase(bn1, ci2->ncand == 1 ? *(oid *) Tloc(bn1, 0) : oid_nil);
103 :
104 4827 : if (bn2) {
105 4574 : BATsetcount(bn2, ci1->ncand * ci2->ncand);
106 4581 : bn2->tsorted = ci1->ncand <= 1 || ci2->ncand <= 1;
107 4581 : bn2->trevsorted = ci2->ncand <= 1;
108 4581 : bn2->tkey = ci1->ncand <= 1;
109 4581 : bn2->tnil = false;
110 4581 : bn2->tnonil = true;
111 4581 : p = (oid *) Tloc(bn2, 0);
112 225108 : for (i = 0; i < ci1->ncand; i++) {
113 220526 : GDK_CHECK_TIMEOUT_BODY(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
114 2195491 : for (j = 0; j < ci2->ncand; j++) {
115 1974728 : *p++ = canditer_next(ci2);
116 : }
117 220763 : canditer_reset(ci2);
118 : }
119 4582 : BATtseqbase(bn2, ci1->ncand == 1 ? *(oid *) Tloc(bn2, 0) : oid_nil);
120 : }
121 : }
122 4832 : *r1p = bn1;
123 4832 : if (r2p)
124 4579 : *r2p = bn2;
125 4832 : if (r2p)
126 4579 : TRC_DEBUG(ALGO, "BATsubcross()=(" ALGOBATFMT "," ALGOBATFMT ")\n", ALGOBATPAR(bn1), ALGOBATPAR(bn2));
127 : else
128 253 : TRC_DEBUG(ALGO, "BATsubcross()=(" ALGOBATFMT ")\n", ALGOBATPAR(bn1));
129 : return GDK_SUCCEED;
130 :
131 8 : bailout:
132 8 : BBPreclaim(bn1);
133 8 : BBPreclaim(bn2);
134 : return GDK_FAIL;
135 : }
136 :
137 : gdk_return
138 45654 : BATsubcross(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool max_one)
139 : {
140 45654 : struct canditer ci1, ci2;
141 :
142 45654 : canditer_init(&ci1, l, sl);
143 45666 : canditer_init(&ci2, r, sr);
144 45680 : if (max_one && ci1.ncand > 0 && ci2.ncand > 1) {
145 71 : GDKerror("more than one match");
146 71 : return GDK_FAIL;
147 : }
148 45609 : return BATcrossci(r1p, r2p, &ci1, &ci2);
149 : }
150 :
151 : /* [left] outer cross */
152 : gdk_return
153 409 : BAToutercross(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool max_one)
154 : {
155 409 : struct canditer ci1, ci2;
156 :
157 409 : canditer_init(&ci1, l, sl);
158 409 : canditer_init(&ci2, r, sr);
159 409 : if (max_one && ci1.ncand > 0 && ci2.ncand > 1) {
160 0 : GDKerror("more than one match");
161 0 : return GDK_FAIL;
162 : }
163 :
164 409 : if (ci1.ncand == 0) {
165 30 : BAT *bn = COLnew(0, TYPE_void, 0, TRANSIENT);
166 30 : if (bn == NULL)
167 : return GDK_FAIL;
168 30 : BATtseqbase(bn, oid_nil);
169 30 : *r1p = bn;
170 30 : if (r2p) {
171 30 : bn = COLnew(0, TYPE_void, 0, TRANSIENT);
172 30 : if (bn == NULL) {
173 0 : BBPreclaim(*r1p);
174 0 : return GDK_FAIL;
175 : }
176 30 : BATtseqbase(bn, oid_nil);
177 30 : *r2p = bn;
178 : }
179 30 : return GDK_SUCCEED;
180 : }
181 379 : if (ci2.ncand == 0) {
182 29 : BAT *bn = canditer_slice(&ci1, 0, ci1.ncand);
183 29 : if (bn == NULL)
184 : return GDK_FAIL;
185 29 : *r1p = bn;
186 29 : if (r2p) {
187 29 : BAT *bn = COLnew(0, TYPE_void, ci1.ncand, TRANSIENT);
188 29 : if (bn == NULL)
189 : return GDK_FAIL;
190 29 : BATtseqbase(bn, oid_nil);
191 29 : BATsetcount(bn, ci1.ncand);
192 29 : *r2p = bn;
193 : }
194 29 : return GDK_SUCCEED;
195 : }
196 350 : return BATcrossci(r1p, r2p, &ci1, &ci2);
197 : }
|
