query_gist.c 7.85 KB
Newer Older
Teodor Sigaev's avatar
Teodor Sigaev committed
1 2 3
#include "postgres.h"

#include "access/skey.h"
4
#include "storage/bufpage.h"
Teodor Sigaev's avatar
Teodor Sigaev committed
5 6 7 8 9
#include "access/gist.h"

#include "query.h"

typedef uint64 TPQTGist;
10 11

#define SIGLEN	(sizeof(TPQTGist)*BITS_PER_BYTE)
12

Teodor Sigaev's avatar
Teodor Sigaev committed
13 14 15 16

#define GETENTRY(vec,pos) ((TPQTGist *) DatumGetPointer((vec)->vector[(pos)].key))

PG_FUNCTION_INFO_V1(tsq_mcontains);
17
Datum		tsq_mcontains(PG_FUNCTION_ARGS);
Teodor Sigaev's avatar
Teodor Sigaev committed
18 19

PG_FUNCTION_INFO_V1(tsq_mcontained);
20
Datum		tsq_mcontained(PG_FUNCTION_ARGS);
Teodor Sigaev's avatar
Teodor Sigaev committed
21 22

static TPQTGist
23 24 25 26
makesign(QUERYTYPE * a)
{
	int			i;
	ITEM	   *ptr = GETQUERY(a);
Teodor Sigaev's avatar
Teodor Sigaev committed
27 28
	TPQTGist	sign = 0;

29 30 31
	for (i = 0; i < a->size; i++)
	{
		if (ptr->type == VAL)
Bruce Momjian's avatar
Bruce Momjian committed
32
			sign |= ((TPQTGist) 1) << (ptr->val % SIGLEN);
Teodor Sigaev's avatar
Teodor Sigaev committed
33 34
		ptr++;
	}
35

Teodor Sigaev's avatar
Teodor Sigaev committed
36 37 38 39
	return sign;
}

Datum
40 41
tsq_mcontains(PG_FUNCTION_ARGS)
{
Teodor Sigaev's avatar
Teodor Sigaev committed
42 43
	QUERYTYPE  *query = (QUERYTYPE *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(0)));
	QUERYTYPE  *ex = (QUERYTYPE *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(1)));
44 45 46 47 48 49 50 51 52
	TPQTGist	sq,
				se;
	int			i,
				j;
	ITEM	   *iq,
			   *ie;

	if (query->size < ex->size)
	{
Teodor Sigaev's avatar
Teodor Sigaev committed
53 54 55
		PG_FREE_IF_COPY(query, 0);
		PG_FREE_IF_COPY(ex, 1);

56
		PG_RETURN_BOOL(false);
Teodor Sigaev's avatar
Teodor Sigaev committed
57 58 59 60 61
	}

	sq = makesign(query);
	se = makesign(ex);

62 63
	if ((sq & se) != se)
	{
Teodor Sigaev's avatar
Teodor Sigaev committed
64 65 66
		PG_FREE_IF_COPY(query, 0);
		PG_FREE_IF_COPY(ex, 1);

67 68
		PG_RETURN_BOOL(false);
	}
Teodor Sigaev's avatar
Teodor Sigaev committed
69 70 71

	ie = GETQUERY(ex);

72 73
	for (i = 0; i < ex->size; i++)
	{
Teodor Sigaev's avatar
Teodor Sigaev committed
74
		iq = GETQUERY(query);
75
		if (ie[i].type != VAL)
Teodor Sigaev's avatar
Teodor Sigaev committed
76
			continue;
77 78 79 80
		for (j = 0; j < query->size; j++)
			if (iq[j].type == VAL && ie[i].val == iq[j].val)
			{
				j = query->size + 1;
Teodor Sigaev's avatar
Teodor Sigaev committed
81 82
				break;
			}
83 84
		if (j == query->size)
		{
Teodor Sigaev's avatar
Teodor Sigaev committed
85 86 87
			PG_FREE_IF_COPY(query, 0);
			PG_FREE_IF_COPY(ex, 1);

88
			PG_RETURN_BOOL(false);
Teodor Sigaev's avatar
Teodor Sigaev committed
89
		}
90
	}
Teodor Sigaev's avatar
Teodor Sigaev committed
91 92 93 94

	PG_FREE_IF_COPY(query, 0);
	PG_FREE_IF_COPY(ex, 1);

95
	PG_RETURN_BOOL(true);
Teodor Sigaev's avatar
Teodor Sigaev committed
96 97 98
}

Datum
99 100
tsq_mcontained(PG_FUNCTION_ARGS)
{
Teodor Sigaev's avatar
Teodor Sigaev committed
101
	PG_RETURN_DATUM(
102 103 104 105 106
					DirectFunctionCall2(
										tsq_mcontains,
										PG_GETARG_DATUM(1),
										PG_GETARG_DATUM(0)
										)
Bruce Momjian's avatar
Bruce Momjian committed
107
		);
Teodor Sigaev's avatar
Teodor Sigaev committed
108 109 110
}

PG_FUNCTION_INFO_V1(gtsq_in);
111
Datum		gtsq_in(PG_FUNCTION_ARGS);
Teodor Sigaev's avatar
Teodor Sigaev committed
112 113

PG_FUNCTION_INFO_V1(gtsq_out);
114
Datum		gtsq_out(PG_FUNCTION_ARGS);
Teodor Sigaev's avatar
Teodor Sigaev committed
115 116

PG_FUNCTION_INFO_V1(gtsq_compress);
117
Datum		gtsq_compress(PG_FUNCTION_ARGS);
Teodor Sigaev's avatar
Teodor Sigaev committed
118 119

PG_FUNCTION_INFO_V1(gtsq_decompress);
120
Datum		gtsq_decompress(PG_FUNCTION_ARGS);
Teodor Sigaev's avatar
Teodor Sigaev committed
121 122

PG_FUNCTION_INFO_V1(gtsq_consistent);
123
Datum		gtsq_consistent(PG_FUNCTION_ARGS);
Teodor Sigaev's avatar
Teodor Sigaev committed
124 125

PG_FUNCTION_INFO_V1(gtsq_union);
126
Datum		gtsq_union(PG_FUNCTION_ARGS);
Teodor Sigaev's avatar
Teodor Sigaev committed
127 128

PG_FUNCTION_INFO_V1(gtsq_same);
129
Datum		gtsq_same(PG_FUNCTION_ARGS);
Teodor Sigaev's avatar
Teodor Sigaev committed
130 131

PG_FUNCTION_INFO_V1(gtsq_penalty);
132
Datum		gtsq_penalty(PG_FUNCTION_ARGS);
Teodor Sigaev's avatar
Teodor Sigaev committed
133 134

PG_FUNCTION_INFO_V1(gtsq_picksplit);
135
Datum		gtsq_picksplit(PG_FUNCTION_ARGS);
Teodor Sigaev's avatar
Teodor Sigaev committed
136 137 138


Datum
139 140
gtsq_in(PG_FUNCTION_ARGS)
{
141
	elog(ERROR, "not implemented");
142
	PG_RETURN_DATUM(0);
Teodor Sigaev's avatar
Teodor Sigaev committed
143 144 145
}

Datum
146 147
gtsq_out(PG_FUNCTION_ARGS)
{
148
	elog(ERROR, "not implemented");
149
	PG_RETURN_DATUM(0);
Teodor Sigaev's avatar
Teodor Sigaev committed
150 151 152
}

Datum
153 154
gtsq_compress(PG_FUNCTION_ARGS)
{
Teodor Sigaev's avatar
Teodor Sigaev committed
155 156 157
	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	GISTENTRY  *retval = entry;

158 159 160 161
	if (entry->leafkey)
	{
		TPQTGist   *sign = (TPQTGist *) palloc(sizeof(TPQTGist));

Teodor Sigaev's avatar
Teodor Sigaev committed
162
		retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
163
		*sign = makesign((QUERYTYPE *) DatumGetPointer(PG_DETOAST_DATUM(entry->key)));
Teodor Sigaev's avatar
Teodor Sigaev committed
164 165

		gistentryinit(*retval, PointerGetDatum(sign),
166
					  entry->rel, entry->page,
Teodor Sigaev's avatar
Teodor Sigaev committed
167
					  entry->offset, FALSE);
Teodor Sigaev's avatar
Teodor Sigaev committed
168 169 170 171 172 173
	}

	PG_RETURN_POINTER(retval);
}

Datum
174 175
gtsq_decompress(PG_FUNCTION_ARGS)
{
Teodor Sigaev's avatar
Teodor Sigaev committed
176 177 178 179
	PG_RETURN_DATUM(PG_GETARG_DATUM(0));
}

Datum
180 181
gtsq_consistent(PG_FUNCTION_ARGS)
{
Teodor Sigaev's avatar
Teodor Sigaev committed
182
	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
183
	TPQTGist   *key = (TPQTGist *) DatumGetPointer(entry->key);
Teodor Sigaev's avatar
Teodor Sigaev committed
184
	QUERYTYPE  *query = (QUERYTYPE *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(1)));
185
	StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
Teodor Sigaev's avatar
Teodor Sigaev committed
186
	TPQTGist	sq = makesign(query);
187
	bool		retval;
Teodor Sigaev's avatar
Teodor Sigaev committed
188

189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208
	switch (strategy)
	{
		case RTContainsStrategyNumber:
		case RTOldContainsStrategyNumber:
			if (GIST_LEAF(entry))
				retval = (*key & sq) == sq;
			else
				retval = (*key & sq) != 0;
			break;
		case RTContainedByStrategyNumber:
		case RTOldContainedByStrategyNumber:
			if (GIST_LEAF(entry))
				retval = (*key & sq) == *key;
			else
				retval = (*key & sq) != 0;
			break;
		default:
			retval = FALSE;
	}
	PG_RETURN_BOOL(retval);
Teodor Sigaev's avatar
Teodor Sigaev committed
209 210 211
}

Datum
212 213
gtsq_union(PG_FUNCTION_ARGS)
{
Teodor Sigaev's avatar
Teodor Sigaev committed
214
	GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
215 216 217
	TPQTGist   *sign = (TPQTGist *) palloc(sizeof(TPQTGist));
	int			i;
	int		   *size = (int *) PG_GETARG_POINTER(1);
Teodor Sigaev's avatar
Teodor Sigaev committed
218

219
	memset(sign, 0, sizeof(TPQTGist));
Teodor Sigaev's avatar
Teodor Sigaev committed
220

221
	for (i = 0; i < entryvec->n; i++)
Teodor Sigaev's avatar
Teodor Sigaev committed
222 223 224 225 226 227 228 229
		*sign |= *GETENTRY(entryvec, i);

	*size = sizeof(TPQTGist);

	PG_RETURN_POINTER(sign);
}

Datum
230 231 232 233
gtsq_same(PG_FUNCTION_ARGS)
{
	TPQTGist   *a = (TPQTGist *) PG_GETARG_POINTER(0);
	TPQTGist   *b = (TPQTGist *) PG_GETARG_POINTER(1);
Teodor Sigaev's avatar
Teodor Sigaev committed
234

235
	PG_RETURN_POINTER(*a == *b);
Teodor Sigaev's avatar
Teodor Sigaev committed
236 237 238
}

static int
239 240 241 242
sizebitvec(TPQTGist sign)
{
	int			size = 0,
				i;
Teodor Sigaev's avatar
Teodor Sigaev committed
243

244 245
	for (i = 0; i < SIGLEN; i++)
		size += 0x01 & (sign >> i);
Teodor Sigaev's avatar
Teodor Sigaev committed
246 247

	return size;
Teodor Sigaev's avatar
Teodor Sigaev committed
248 249 250
}

static int
251 252 253
hemdist(TPQTGist a, TPQTGist b)
{
	TPQTGist	res = a ^ b;
Teodor Sigaev's avatar
Teodor Sigaev committed
254 255 256 257 258

	return sizebitvec(res);
}

Datum
259 260 261 262 263
gtsq_penalty(PG_FUNCTION_ARGS)
{
	TPQTGist   *origval = (TPQTGist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(0))->key);
	TPQTGist   *newval = (TPQTGist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(1))->key);
	float	   *penalty = (float *) PG_GETARG_POINTER(2);
Teodor Sigaev's avatar
Teodor Sigaev committed
264 265 266 267 268 269 270

	*penalty = hemdist(*origval, *newval);

	PG_RETURN_POINTER(penalty);
}


271 272 273 274
typedef struct
{
	OffsetNumber pos;
	int4		cost;
Bruce Momjian's avatar
Bruce Momjian committed
275
}	SPLITCOST;
Teodor Sigaev's avatar
Teodor Sigaev committed
276 277

static int
278 279 280 281 282 283
comparecost(const void *a, const void *b)
{
	if (((SPLITCOST *) a)->cost == ((SPLITCOST *) b)->cost)
		return 0;
	else
		return (((SPLITCOST *) a)->cost > ((SPLITCOST *) b)->cost) ? 1 : -1;
Teodor Sigaev's avatar
Teodor Sigaev committed
284 285 286 287 288
}

#define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )

Datum
289 290
gtsq_picksplit(PG_FUNCTION_ARGS)
{
Teodor Sigaev's avatar
Teodor Sigaev committed
291 292 293
	GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
	OffsetNumber maxoff = entryvec->n - 2;
294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309
	OffsetNumber k,
				j;

	TPQTGist   *datum_l,
			   *datum_r;
	int4		size_alpha,
				size_beta;
	int4		size_waste,
				waste = -1;
	int4		nbytes;
	OffsetNumber seed_1 = 0,
				seed_2 = 0;
	OffsetNumber *left,
			   *right;

	SPLITCOST  *costvector;
Teodor Sigaev's avatar
Teodor Sigaev committed
310 311 312 313 314 315 316

	nbytes = (maxoff + 2) * sizeof(OffsetNumber);
	left = v->spl_left = (OffsetNumber *) palloc(nbytes);
	right = v->spl_right = (OffsetNumber *) palloc(nbytes);
	v->spl_nleft = v->spl_nright = 0;

	for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
317 318 319 320 321
		for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
		{
			size_waste = hemdist(*GETENTRY(entryvec, j), *GETENTRY(entryvec, k));
			if (size_waste > waste)
			{
Teodor Sigaev's avatar
Teodor Sigaev committed
322 323 324 325 326 327 328
				waste = size_waste;
				seed_1 = k;
				seed_2 = j;
			}
		}


329 330
	if (seed_1 == 0 || seed_2 == 0)
	{
Teodor Sigaev's avatar
Teodor Sigaev committed
331 332 333 334
		seed_1 = 1;
		seed_2 = 2;
	}

335 336 337 338 339 340
	datum_l = (TPQTGist *) palloc(sizeof(TPQTGist));
	*datum_l = *GETENTRY(entryvec, seed_1);
	datum_r = (TPQTGist *) palloc(sizeof(TPQTGist));
	*datum_r = *GETENTRY(entryvec, seed_2);


Teodor Sigaev's avatar
Teodor Sigaev committed
341 342
	maxoff = OffsetNumberNext(maxoff);
	costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
343 344
	for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
	{
Teodor Sigaev's avatar
Teodor Sigaev committed
345
		costvector[j - 1].pos = j;
346 347
		size_alpha = hemdist(*GETENTRY(entryvec, seed_1), *GETENTRY(entryvec, j));
		size_beta = hemdist(*GETENTRY(entryvec, seed_2), *GETENTRY(entryvec, j));
Teodor Sigaev's avatar
Teodor Sigaev committed
348 349 350 351
		costvector[j - 1].cost = abs(size_alpha - size_beta);
	}
	qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);

352 353
	for (k = 0; k < maxoff; k++)
	{
Teodor Sigaev's avatar
Teodor Sigaev committed
354
		j = costvector[k].pos;
355 356
		if (j == seed_1)
		{
Teodor Sigaev's avatar
Teodor Sigaev committed
357 358 359
			*left++ = j;
			v->spl_nleft++;
			continue;
360 361 362
		}
		else if (j == seed_2)
		{
Teodor Sigaev's avatar
Teodor Sigaev committed
363 364 365 366
			*right++ = j;
			v->spl_nright++;
			continue;
		}
367 368
		size_alpha = hemdist(*datum_l, *GETENTRY(entryvec, j));
		size_beta = hemdist(*datum_r, *GETENTRY(entryvec, j));
Teodor Sigaev's avatar
Teodor Sigaev committed
369

370 371 372
		if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.05))
		{
			*datum_l |= *GETENTRY(entryvec, j);
Teodor Sigaev's avatar
Teodor Sigaev committed
373 374
			*left++ = j;
			v->spl_nleft++;
375 376 377 378
		}
		else
		{
			*datum_r |= *GETENTRY(entryvec, j);
Teodor Sigaev's avatar
Teodor Sigaev committed
379 380 381 382 383 384 385 386 387 388 389
			*right++ = j;
			v->spl_nright++;
		}
	}

	*right = *left = FirstOffsetNumber;
	v->spl_ldatum = PointerGetDatum(datum_l);
	v->spl_rdatum = PointerGetDatum(datum_r);

	PG_RETURN_POINTER(v);
}