← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/postgresql-9.1/oneiric-security

« back to all changes in this revision

Viewing changes to src/backend/access/gin/ginbulk.c

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2011-05-11 10:41:53 UTC
  • Revision ID: james.westby@ubuntu.com-20110511104153-psbh2o58553fv1m0
Tags: upstream-9.1~beta1
Import upstream version 9.1~beta1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/access/gin/ginbulk.c
 
1
/*-------------------------------------------------------------------------
 
2
 *
 
3
 * ginbulk.c
 
4
 *        routines for fast build of inverted index
 
5
 *
 
6
 *
 
7
 * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
 
8
 * Portions Copyright (c) 1994, Regents of the University of California
 
9
 *
 
10
 * IDENTIFICATION
 
11
 *                      src/backend/access/gin/ginbulk.c
 
12
 *-------------------------------------------------------------------------
 
13
 */
 
14
 
 
15
#include "postgres.h"
 
16
 
 
17
#include "access/gin_private.h"
 
18
#include "utils/datum.h"
 
19
#include "utils/memutils.h"
 
20
 
 
21
 
 
22
#define DEF_NENTRY      2048            /* GinEntryAccumulator allocation quantum */
 
23
#define DEF_NPTR        5                       /* ItemPointer initial allocation quantum */
 
24
 
 
25
 
 
26
/* Combiner function for rbtree.c */
 
27
static void
 
28
ginCombineData(RBNode *existing, const RBNode *newdata, void *arg)
 
29
{
 
30
        GinEntryAccumulator *eo = (GinEntryAccumulator *) existing;
 
31
        const GinEntryAccumulator *en = (const GinEntryAccumulator *) newdata;
 
32
        BuildAccumulator *accum = (BuildAccumulator *) arg;
 
33
 
 
34
        /*
 
35
         * Note this code assumes that newdata contains only one itempointer.
 
36
         */
 
37
        if (eo->count >= eo->maxcount)
 
38
        {
 
39
                accum->allocatedMemory -= GetMemoryChunkSpace(eo->list);
 
40
                eo->maxcount *= 2;
 
41
                eo->list = (ItemPointerData *)
 
42
                        repalloc(eo->list, sizeof(ItemPointerData) * eo->maxcount);
 
43
                accum->allocatedMemory += GetMemoryChunkSpace(eo->list);
 
44
        }
 
45
 
 
46
        /* If item pointers are not ordered, they will need to be sorted later */
 
47
        if (eo->shouldSort == FALSE)
 
48
        {
 
49
                int                     res;
 
50
 
 
51
                res = ginCompareItemPointers(eo->list + eo->count - 1, en->list);
 
52
                Assert(res != 0);
 
53
 
 
54
                if (res > 0)
 
55
                        eo->shouldSort = TRUE;
 
56
        }
 
57
 
 
58
        eo->list[eo->count] = en->list[0];
 
59
        eo->count++;
 
60
}
 
61
 
 
62
/* Comparator function for rbtree.c */
 
63
static int
 
64
cmpEntryAccumulator(const RBNode *a, const RBNode *b, void *arg)
 
65
{
 
66
        const GinEntryAccumulator *ea = (const GinEntryAccumulator *) a;
 
67
        const GinEntryAccumulator *eb = (const GinEntryAccumulator *) b;
 
68
        BuildAccumulator *accum = (BuildAccumulator *) arg;
 
69
 
 
70
        return ginCompareAttEntries(accum->ginstate,
 
71
                                                                ea->attnum, ea->key, ea->category,
 
72
                                                                eb->attnum, eb->key, eb->category);
 
73
}
 
74
 
 
75
/* Allocator function for rbtree.c */
 
76
static RBNode *
 
77
ginAllocEntryAccumulator(void *arg)
 
78
{
 
79
        BuildAccumulator *accum = (BuildAccumulator *) arg;
 
80
        GinEntryAccumulator *ea;
 
81
 
 
82
        /*
 
83
         * Allocate memory by rather big chunks to decrease overhead.  We have no
 
84
         * need to reclaim RBNodes individually, so this costs nothing.
 
85
         */
 
86
        if (accum->entryallocator == NULL || accum->eas_used >= DEF_NENTRY)
 
87
        {
 
88
                accum->entryallocator = palloc(sizeof(GinEntryAccumulator) * DEF_NENTRY);
 
89
                accum->allocatedMemory += GetMemoryChunkSpace(accum->entryallocator);
 
90
                accum->eas_used = 0;
 
91
        }
 
92
 
 
93
        /* Allocate new RBNode from current chunk */
 
94
        ea = accum->entryallocator + accum->eas_used;
 
95
        accum->eas_used++;
 
96
 
 
97
        return (RBNode *) ea;
 
98
}
 
99
 
 
100
void
 
101
ginInitBA(BuildAccumulator *accum)
 
102
{
 
103
        /* accum->ginstate is intentionally not set here */
 
104
        accum->allocatedMemory = 0;
 
105
        accum->entryallocator = NULL;
 
106
        accum->eas_used = 0;
 
107
        accum->tree = rb_create(sizeof(GinEntryAccumulator),
 
108
                                                        cmpEntryAccumulator,
 
109
                                                        ginCombineData,
 
110
                                                        ginAllocEntryAccumulator,
 
111
                                                        NULL,           /* no freefunc needed */
 
112
                                                        (void *) accum);
 
113
}
 
114
 
 
115
/*
 
116
 * This is basically the same as datumCopy(), but extended to count
 
117
 * palloc'd space in accum->allocatedMemory.
 
118
 */
 
119
static Datum
 
120
getDatumCopy(BuildAccumulator *accum, OffsetNumber attnum, Datum value)
 
121
{
 
122
        Form_pg_attribute att = accum->ginstate->origTupdesc->attrs[attnum - 1];
 
123
        Datum           res;
 
124
 
 
125
        if (att->attbyval)
 
126
                res = value;
 
127
        else
 
128
        {
 
129
                res = datumCopy(value, false, att->attlen);
 
130
                accum->allocatedMemory += GetMemoryChunkSpace(DatumGetPointer(res));
 
131
        }
 
132
        return res;
 
133
}
 
134
 
 
135
/*
 
136
 * Find/store one entry from indexed value.
 
137
 */
 
138
static void
 
139
ginInsertBAEntry(BuildAccumulator *accum,
 
140
                                 ItemPointer heapptr, OffsetNumber attnum,
 
141
                                 Datum key, GinNullCategory category)
 
142
{
 
143
        GinEntryAccumulator eatmp;
 
144
        GinEntryAccumulator *ea;
 
145
        bool            isNew;
 
146
 
 
147
        /*
 
148
         * For the moment, fill only the fields of eatmp that will be looked at by
 
149
         * cmpEntryAccumulator or ginCombineData.
 
150
         */
 
151
        eatmp.attnum = attnum;
 
152
        eatmp.key = key;
 
153
        eatmp.category = category;
 
154
        /* temporarily set up single-entry itempointer list */
 
155
        eatmp.list = heapptr;
 
156
 
 
157
        ea = (GinEntryAccumulator *) rb_insert(accum->tree, (RBNode *) &eatmp,
 
158
                                                                                   &isNew);
 
159
 
 
160
        if (isNew)
 
161
        {
 
162
                /*
 
163
                 * Finish initializing new tree entry, including making permanent
 
164
                 * copies of the datum (if it's not null) and itempointer.
 
165
                 */
 
166
                if (category == GIN_CAT_NORM_KEY)
 
167
                        ea->key = getDatumCopy(accum, attnum, key);
 
168
                ea->maxcount = DEF_NPTR;
 
169
                ea->count = 1;
 
170
                ea->shouldSort = FALSE;
 
171
                ea->list =
 
172
                        (ItemPointerData *) palloc(sizeof(ItemPointerData) * DEF_NPTR);
 
173
                ea->list[0] = *heapptr;
 
174
                accum->allocatedMemory += GetMemoryChunkSpace(ea->list);
 
175
        }
 
176
        else
 
177
        {
 
178
                /*
 
179
                 * ginCombineData did everything needed.
 
180
                 */
 
181
        }
 
182
}
 
183
 
 
184
/*
 
185
 * Insert the entries for one heap pointer.
 
186
 *
 
187
 * Since the entries are being inserted into a balanced binary tree, you
 
188
 * might think that the order of insertion wouldn't be critical, but it turns
 
189
 * out that inserting the entries in sorted order results in a lot of
 
190
 * rebalancing operations and is slow.  To prevent this, we attempt to insert
 
191
 * the nodes in an order that will produce a nearly-balanced tree if the input
 
192
 * is in fact sorted.
 
193
 *
 
194
 * We do this as follows.  First, we imagine that we have an array whose size
 
195
 * is the smallest power of two greater than or equal to the actual array
 
196
 * size.  Second, we insert the middle entry of our virtual array into the
 
197
 * tree; then, we insert the middles of each half of our virtual array, then
 
198
 * middles of quarters, etc.
 
199
 */
 
200
void
 
201
ginInsertBAEntries(BuildAccumulator *accum,
 
202
                                   ItemPointer heapptr, OffsetNumber attnum,
 
203
                                   Datum *entries, GinNullCategory *categories,
 
204
                                   int32 nentries)
 
205
{
 
206
        uint32          step = nentries;
 
207
 
 
208
        if (nentries <= 0)
 
209
                return;
 
210
 
 
211
        Assert(ItemPointerIsValid(heapptr) && attnum >= FirstOffsetNumber);
 
212
 
 
213
        /*
 
214
         * step will contain largest power of 2 and <= nentries
 
215
         */
 
216
        step |= (step >> 1);
 
217
        step |= (step >> 2);
 
218
        step |= (step >> 4);
 
219
        step |= (step >> 8);
 
220
        step |= (step >> 16);
 
221
        step >>= 1;
 
222
        step++;
 
223
 
 
224
        while (step > 0)
 
225
        {
 
226
                int                     i;
 
227
 
 
228
                for (i = step - 1; i < nentries && i >= 0; i += step << 1 /* *2 */ )
 
229
                        ginInsertBAEntry(accum, heapptr, attnum,
 
230
                                                         entries[i], categories[i]);
 
231
 
 
232
                step >>= 1;                             /* /2 */
 
233
        }
 
234
}
 
235
 
 
236
static int
 
237
qsortCompareItemPointers(const void *a, const void *b)
 
238
{
 
239
        int                     res = ginCompareItemPointers((ItemPointer) a, (ItemPointer) b);
 
240
 
 
241
        /* Assert that there are no equal item pointers being sorted */
 
242
        Assert(res != 0);
 
243
        return res;
 
244
}
 
245
 
 
246
/* Prepare to read out the rbtree contents using ginGetBAEntry */
 
247
void
 
248
ginBeginBAScan(BuildAccumulator *accum)
 
249
{
 
250
        rb_begin_iterate(accum->tree, LeftRightWalk);
 
251
}
 
252
 
 
253
/*
 
254
 * Get the next entry in sequence from the BuildAccumulator's rbtree.
 
255
 * This consists of a single key datum and a list (array) of one or more
 
256
 * heap TIDs in which that key is found.  The list is guaranteed sorted.
 
257
 */
 
258
ItemPointerData *
 
259
ginGetBAEntry(BuildAccumulator *accum,
 
260
                          OffsetNumber *attnum, Datum *key, GinNullCategory *category,
 
261
                          uint32 *n)
 
262
{
 
263
        GinEntryAccumulator *entry;
 
264
        ItemPointerData *list;
 
265
 
 
266
        entry = (GinEntryAccumulator *) rb_iterate(accum->tree);
 
267
 
 
268
        if (entry == NULL)
 
269
                return NULL;                    /* no more entries */
 
270
 
 
271
        *attnum = entry->attnum;
 
272
        *key = entry->key;
 
273
        *category = entry->category;
 
274
        list = entry->list;
 
275
        *n = entry->count;
 
276
 
 
277
        Assert(list != NULL && entry->count > 0);
 
278
 
 
279
        if (entry->shouldSort && entry->count > 1)
 
280
                qsort(list, entry->count, sizeof(ItemPointerData),
 
281
                          qsortCompareItemPointers);
 
282
 
 
283
        return list;
 
284
}