granicus.if.org Git - postgresql/blob - 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 }