UnQL

Check-in [8c09ee47d8]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add support for GROUP BY and HAVING.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 8c09ee47d8872b97ae19368ca6279531f9abc4bd
User & Date: dan 2011-07-21 17:08:52
Context
2011-07-21
17:36
Candidate updates to the language syntax. Also add GIFs and postscript for all bubble diagrams to the check-in. check-in: f23e2c01b8 user: drh tags: trunk
17:08
Add support for GROUP BY and HAVING. check-in: 8c09ee47d8 user: dan tags: trunk
2011-07-20
19:50
Add support for simple aggregates. Fix a problem with joins. check-in: 514e16d7cb user: dan tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/func.c.

22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
..
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
...
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
...
184
185
186
187
188
189
190









191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
  const char *zName;

  JsonNode *(*xFunc)(int nArg, JsonNode **apArg);
  int (*xStep)(int nArg, JsonNode **apArg, void **);
  JsonNode *(*xFinal)(void *);
};

#define ArraySize(X)    ((int)(sizeof(X)/sizeof(X[0])))

/*
** Implementation of scalar function "length(x)".
*/
static JsonNode *xLength(int nArg, JsonNode **apArg){
  JsonNode *pRet;
  JsonNode *pStr;
  int nRet;
................................................................................
}


int xjd1AggregateInit(xjd1_stmt *pStmt, Query *pQuery, Expr *p){
  Aggregate *pAgg = pQuery->pAgg;

  if( pAgg==0 ){
    int nDatasrc;

    pAgg = (Aggregate *)xjd1PoolMallocZero(&pStmt->sPool, sizeof(Aggregate));
    if( pAgg==0 ) return XJD1_NOMEM;
    pQuery->pAgg = pAgg;

    pAgg->nNode = xjd1DataSrcCount(pQuery->u.simple.pFrom);
    nDatasrc = pAgg->nNode * sizeof(JsonNode *);
    pAgg->apNode = (JsonNode **)xjd1PoolMallocZero(&pStmt->sPool, nDatasrc);
    if( pAgg->apNode==0 ) return XJD1_NOMEM;
  }

  if( p ){
    static const int ARRAY_ALLOC_INCR = 8;

    if( (pAgg->nExpr % ARRAY_ALLOC_INCR)==0 ){
      int nByte;                    /* Size of new allocation in bytes */
................................................................................
  if( !p->u.func.apArg ){
    return XJD1_NOMEM;
  }

  return XJD1_OK;
}

int xjd1AggregateStep(Expr *p){
  Function *pFunc = p->u.func.pFunction;
  int i;
  int nItem = p->u.func.args->nEItem;

  assert( p->eType==TK_FUNCTION && p->eClass==XJD1_EXPR_FUNC );
  assert( pFunc->xStep && pFunc->xFinal && pFunc->xFunc==0 );

................................................................................
  pFunc->xStep(nItem, p->u.func.apArg, &p->u.func.pAggCtx);
  for(i=0; i<nItem; i++){
    xjd1JsonFree(p->u.func.apArg[i]);
  }

  return XJD1_OK;
}










/*
** Call any outstanding xFinal() functions for aggregate functions in the
** query. This is required to reset the aggregate contexts when a query is 
** rewound following an error.
*/
void xjd1AggregateClear(Query *pQuery){
  Aggregate *pAgg = pQuery->pAgg;

  if( pAgg ){
    int i;
    for(i=0; i<pAgg->nNode; i++){
      xjd1JsonFree(pAgg->apNode[i]);
      pAgg->apNode[i] = 0;
    }
    for(i=0; i<pAgg->nExpr; i++){
      Expr *p = pAgg->apExpr[i];  /* Aggregate expression to finalize */
      xjd1JsonFree( p->u.func.pFunction->xFinal(p->u.func.pAggCtx) );
      p->u.func.pAggCtx = 0;
    }
  }
}







<
<







 







<
<



<
<
<
<
<







 







|







 







>
>
>
>
>
>
>
>
>











<
<
<
<







22
23
24
25
26
27
28


29
30
31
32
33
34
35
..
70
71
72
73
74
75
76


77
78
79





80
81
82
83
84
85
86
...
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
...
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201




202
203
204
205
206
207
208
  const char *zName;

  JsonNode *(*xFunc)(int nArg, JsonNode **apArg);
  int (*xStep)(int nArg, JsonNode **apArg, void **);
  JsonNode *(*xFinal)(void *);
};



/*
** Implementation of scalar function "length(x)".
*/
static JsonNode *xLength(int nArg, JsonNode **apArg){
  JsonNode *pRet;
  JsonNode *pStr;
  int nRet;
................................................................................
}


int xjd1AggregateInit(xjd1_stmt *pStmt, Query *pQuery, Expr *p){
  Aggregate *pAgg = pQuery->pAgg;

  if( pAgg==0 ){


    pAgg = (Aggregate *)xjd1PoolMallocZero(&pStmt->sPool, sizeof(Aggregate));
    if( pAgg==0 ) return XJD1_NOMEM;
    pQuery->pAgg = pAgg;





  }

  if( p ){
    static const int ARRAY_ALLOC_INCR = 8;

    if( (pAgg->nExpr % ARRAY_ALLOC_INCR)==0 ){
      int nByte;                    /* Size of new allocation in bytes */
................................................................................
  if( !p->u.func.apArg ){
    return XJD1_NOMEM;
  }

  return XJD1_OK;
}

static int aggExprStep(Expr *p){
  Function *pFunc = p->u.func.pFunction;
  int i;
  int nItem = p->u.func.args->nEItem;

  assert( p->eType==TK_FUNCTION && p->eClass==XJD1_EXPR_FUNC );
  assert( pFunc->xStep && pFunc->xFinal && pFunc->xFunc==0 );

................................................................................
  pFunc->xStep(nItem, p->u.func.apArg, &p->u.func.pAggCtx);
  for(i=0; i<nItem; i++){
    xjd1JsonFree(p->u.func.apArg[i]);
  }

  return XJD1_OK;
}

int xjd1AggregateStep(Aggregate *pAgg){
  int i;                /* Used to iterate through aggregate functions */
  for(i=0; i<pAgg->nExpr; i++){
    int rc = aggExprStep(pAgg->apExpr[i]);
    if( rc!=XJD1_OK ) return rc;
  }
  return XJD1_OK;;
}

/*
** Call any outstanding xFinal() functions for aggregate functions in the
** query. This is required to reset the aggregate contexts when a query is 
** rewound following an error.
*/
void xjd1AggregateClear(Query *pQuery){
  Aggregate *pAgg = pQuery->pAgg;

  if( pAgg ){
    int i;




    for(i=0; i<pAgg->nExpr; i++){
      Expr *p = pAgg->apExpr[i];  /* Aggregate expression to finalize */
      xjd1JsonFree( p->u.func.pFunction->xFinal(p->u.func.pAggCtx) );
      p->u.func.pAggCtx = 0;
    }
  }
}

Changes to src/query.c.

16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
..
44
45
46
47
48
49
50















51
52
53
54
55
56
57
..
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
..
89
90
91
92
93
94
95
96
97
98

99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
...
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
...
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
...
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225


226
227
228
229
230
231
232





















233









































234
235
236
237
238

239
240


241
242
243
244



















245
246






247
248


249














250

251
252

253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278

279
280
281
282
283

284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
...
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341

342
343
344
345
346
347
348
...
357
358
359
360
361
362
363
364

365
366




367
368
369





370






371
372


373
374
375
376
377
378
379
...
388
389
390
391
392
393
394
395

396
397
398
399
400
401
402
*************************************************************************
** This file contains code used to implement query processing.
*/
#include "xjd1Int.h"


struct ResultItem {
  JsonNode **apKey;               /* List of JSON objects - the sort key */
  ResultItem *pNext;           /* Next element in list */
};

static int addToResultList(
  ResultList *pList,              /* List to append to */
  JsonNode **apKey                /* Array of values to add to list */
){
  ResultItem *pNew;               /* Newly allocated ResultItem */
................................................................................
  pNew->apKey = (JsonNode **)&pNew[1];
  memcpy(pNew->apKey, apKey, pList->nKey * sizeof(JsonNode *));
  pNew->pNext = pList->pItem;
  pList->pItem = pNew;

  return XJD1_OK;
}
















static ResultItem *mergeResultItems(
  ExprList *pEList,              /* Used for ASC/DESC of each key */
  ResultItem *p1,                /* First list to merge */
  ResultItem *p2                 /* Second list to merge */
){
  ResultItem *pRet = 0;
................................................................................
    if( !p1 ){
      *ppNext = p2;
      p2 = 0;
    }else if( !p2 ){
      *ppNext = p1;
      p1 = 0;
    }else{
      char const *zDir;
      int c;
      int i;

      for(i=0; i<pEList->nEItem; i++){
        if( 0!=(c=xjd1JsonCompare(p1->apKey[i], p2->apKey[i])) ) break;
      }
      zDir = pEList->apEItem[i].zAs;
      if( zDir && zDir[0]=='D' ){
        c = c*-1;
      }

      if( c<=0 ){
        *ppNext = p1;
        ppNext = &p1->pNext;
        p1 = p1->pNext;
      }else{
        *ppNext = p2;
        ppNext = &p2->pNext;
................................................................................
      }
    }
  }

  return pRet;
}

#define N_BUCKET 40
static void sortResultList(ResultList *pList, ExprList *pEList){
  int i;

  ResultItem *aList[40];

  ResultItem *pNext;
  ResultItem *pHead;

  memset(aList, 0, sizeof(aList));
  pHead = pList->pItem;

  while( pHead ){
    pNext = pHead->pNext;
    pHead->pNext = 0;
    for(i=0; aList[i]; i++){
      assert( i<N_BUCKET );
      pHead = mergeResultItems(pEList, pHead, aList[i]);
      aList[i] = 0;
    }
    aList[i] = pHead;
    pHead = pNext;
  }

  pHead = aList[0];
  for(i=1; i<N_BUCKET; i++){
    pHead = mergeResultItems(pEList, pHead, aList[i]);
  }

  pList->pItem = pHead;
}

static void popResultList(ResultList *pList){
................................................................................
    xjd1JsonFree(pItem->apKey[i]);
  }
}

static void clearResultList(ResultList *pList){
  while( pList->pItem ) popResultList(pList);
  xjd1PoolDelete(pList->pPool);
  pList->pPool = 0;
}

/*
** Called after statement parsing to initalize every Query object
** within the statement.
*/
int xjd1QueryInit(Query *pQuery, xjd1_stmt *pStmt, Query *pOuter){
................................................................................
/*
** Rewind a query so that it is pointing at the first row.
*/
int xjd1QueryRewind(Query *p){
  if( p==0 ) return XJD1_OK;
  if( p->eQType==TK_SELECT ){
    xjd1DataSrcRewind(p->u.simple.pFrom);
    p->bUseResultList = 0;
    p->bStarted = 0;
    p->bDone = 0;
    clearResultList(&p->result);
    xjd1AggregateClear(p);
  }else{
    xjd1QueryRewind(p->u.compound.pLeft);
    p->u.compound.doneLeft = 0;
    xjd1QueryRewind(p->u.compound.pRight);
  }
  return XJD1_OK;
................................................................................
/*
** Advance to the next row of the TK_SELECT query passed as the first 
** argument, disregarding any ORDER BY, OFFSET or LIMIT clause.
**
** Return XJD1_ROW if there is such a row, or XJD1_DONE at EOF. Or return 
** an error code if an error occurs.
*/
static int selectStepUnordered(Query *p){
  int rc;                         /* Return code */
  assert( p->eQType==TK_SELECT );
  do{
    rc = xjd1DataSrcStep(p->u.simple.pFrom);
  }while(
    rc==XJD1_ROW
    && (p->u.simple.pWhere!=0 && !xjd1ExprTrue(p->u.simple.pWhere))
  );
  return rc;
}

/*
** Advance to the next row of the TK_SELECT query passed as the first 
** argument, disregarding any OFFSET or LIMIT clause.
**
** Return XJD1_ROW if there is such a row, or XJD1_EOF if there is not. Or 
** return an error code if an error occurs.
*/
static int selectStepOrdered(Query *p){
  int rc;

  if( p->pAgg ){
    Aggregate *pAgg = p->pAgg;

    if( p->u.simple.pGroupBy==0 ){



      /* An aggregate query with no GROUP BY clause. If there is no GROUP BY,
      ** then exactly one row is returned, which makes ORDER BY and DISTINCT 
      ** no-ops. And it is not possible to have a HAVING clause without a
      ** GROUP BY, so no need to worry about that either. 
      */
      assert( p->u.simple.pHaving==0 );
      





















      pAgg->eAction = XJD1_AGG_STEP;









































      while( XJD1_ROW==(rc = selectStepUnordered(p) ) ){
        int i;
        for(i=0; i<pAgg->nExpr; i++){
          rc = xjd1AggregateStep(pAgg->apExpr[i]);
          if( rc!=XJD1_OK ) return rc;

        }
        xjd1DataSrcCacheSave(p->u.simple.pFrom, pAgg->apNode);


      }
      if( rc!=XJD1_DONE ) return rc;
      pAgg->eAction = XJD1_AGG_FINAL;
      p->bDone = 1;



















      rc = XJD1_ROW;







    }else{
      assert(0);


    }














  }else if( p->u.simple.pOrderBy ){

    /* There is an ORDER BY clause. */
    if( p->bUseResultList==0 ){

      int nKey = p->u.simple.pOrderBy->nEItem + 1;
      ExprList *pOrderBy = p->u.simple.pOrderBy;
      Pool *pPool;
      JsonNode **apKey;

      p->result.nKey = nKey;
      pPool = p->result.pPool = xjd1PoolNew();
      if( !pPool ) return XJD1_NOMEM;
      apKey = xjd1PoolMallocZero(pPool, nKey * sizeof(JsonNode *));
      if( !apKey ) return XJD1_NOMEM;

      while( XJD1_ROW==(rc = selectStepUnordered(p) ) ){
        int i;
        for(i=0; i<pOrderBy->nEItem; i++){
          apKey[i] = xjd1ExprEval(pOrderBy->apEItem[i].pExpr);
        }
        apKey[i] = xjd1QueryDoc(p, 0);

        rc = addToResultList(&p->result, apKey);
        if( rc!=XJD1_OK ) break;
      }
      if( rc!=XJD1_DONE ) return rc;

      sortResultList(&p->result, p->u.simple.pOrderBy);
      p->bUseResultList = 1;
    }else{

      popResultList(&p->result);
    }

    rc = p->result.pItem ? XJD1_ROW : XJD1_DONE;
  }else{

    rc = selectStepUnordered(p);
  }

  return rc;
}

/*
** Advance a query to the next row.  Return XDJ1_DONE if there is no
** next row, or XJD1_ROW if the step was successful.
*/
int xjd1QueryStep(Query *p){
  int rc = XJD1_ROW;
  if( p==0 || p->bDone ) return XJD1_DONE;
  if( p->eQType==TK_SELECT ){

    /* Calculate the values, if any, of the LIMIT and OFFSET clauses.
    **
    ** TBD: Should this throw an exception if the result of evaluating
    ** either of these clauses cannot be converted to a number?
    */
................................................................................

        pLimit = xjd1ExprEval(p->u.simple.pLimit);
        if( 0==xjd1JsonToReal(pLimit, &rLimit) ){
          p->nLimit = (int)rLimit;
        }
        xjd1JsonFree(pLimit);
      }
      p->bStarted = 1;
    }

    if( rc==XJD1_ROW ){
      if( p->nLimit==0 ){
        rc = XJD1_DONE;
      }else{
        rc = selectStepOrdered(p);
        if( p->nLimit>0 ) p->nLimit--;
      }
    }

  }else{
    if( !p->u.compound.doneLeft ){
      rc = xjd1QueryStep(p->u.compound.pLeft);
      if( rc==XJD1_DONE ) p->u.compound.doneLeft = 1;
    }
    if( p->u.compound.doneLeft ){
      rc = xjd1QueryStep(p->u.compound.pRight);
................................................................................
**
** The caller must invoke JsonFree() when it is done with this value.
*/
JsonNode *xjd1QueryDoc(Query *p, const char *zDocName){
  JsonNode *pOut = 0;
  if( p ){
    if( p->eQType==TK_SELECT ){
      if( p->bUseResultList ){

        assert( zDocName==0 && p->result.pItem );
        pOut = xjd1JsonRef(p->result.pItem->apKey[p->result.nKey-1]);




      }else if( zDocName==0 && p->u.simple.pRes ){
        pOut = xjd1ExprEval(p->u.simple.pRes);
      }else if( p->pAgg && p->pAgg->eAction==XJD1_AGG_FINAL ){





        pOut = xjd1DataSrcCacheRead(p->u.simple.pFrom,p->pAgg->apNode,zDocName);






      }else{
        pOut = xjd1DataSrcDoc(p->u.simple.pFrom, zDocName);


      }

    }else if( !p->u.compound.doneLeft ){
      pOut = xjd1QueryDoc(p->u.compound.pLeft, zDocName);
    }else{
      pOut = xjd1QueryDoc(p->u.compound.pRight, zDocName);
    }
................................................................................
/*
** The destructor for a Query object.
*/
int xjd1QueryClose(Query *pQuery){
  int rc = XJD1_OK;
  if( pQuery==0 ) return rc;
  if( pQuery->eQType==TK_SELECT ){
    clearResultList(&pQuery->result);

    xjd1ExprClose(pQuery->u.simple.pRes);
    xjd1DataSrcClose(pQuery->u.simple.pFrom);
    xjd1ExprClose(pQuery->u.simple.pWhere);
    xjd1ExprListClose(pQuery->u.simple.pGroupBy);
    xjd1ExprClose(pQuery->u.simple.pHaving);
    xjd1ExprListClose(pQuery->u.simple.pOrderBy);
    xjd1ExprClose(pQuery->u.simple.pLimit);







|
|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|
<
<
<
<
<
<
<
<
<
<
<







 







<

<
>
|
<
<






|


|








|







 







|







 







|

|
|







 







|











<
<
<
<
<
<
<
|




<
|

>
>






|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
|
|
<
<
>
|
|
>
>
|
|
<
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
|
>
>
>
>
>
>
|
<
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
|
<
>





|
|




|






|




|
|

>
|


|

>
|











|







 







<










>







 







|
>
|
<
>
>
>
>
|
|
<
>
>
>
>
>
|
>
>
>
>
>
>
|
|
>
>







 







|
>







16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
..
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
..
77
78
79
80
81
82
83
84











85
86
87
88
89
90
91
..
93
94
95
96
97
98
99

100

101
102


103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
...
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
...
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
...
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211







212
213
214
215
216

217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293


294
295
296
297
298
299
300


301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328

329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348

349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
...
423
424
425
426
427
428
429

430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
...
456
457
458
459
460
461
462
463
464
465

466
467
468
469
470
471

472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
...
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
*************************************************************************
** This file contains code used to implement query processing.
*/
#include "xjd1Int.h"


struct ResultItem {
  JsonNode **apKey;               /* Array of JSON objects */
  ResultItem *pNext;              /* Next element in list */
};

static int addToResultList(
  ResultList *pList,              /* List to append to */
  JsonNode **apKey                /* Array of values to add to list */
){
  ResultItem *pNew;               /* Newly allocated ResultItem */
................................................................................
  pNew->apKey = (JsonNode **)&pNew[1];
  memcpy(pNew->apKey, apKey, pList->nKey * sizeof(JsonNode *));
  pNew->pNext = pList->pItem;
  pList->pItem = pNew;

  return XJD1_OK;
}

static int cmpResultItem(ResultItem *p1, ResultItem *p2, ExprList *pEList){
  int i;
  int c = 0;
  for(i=0; i<pEList->nEItem; i++){
    if( 0!=(c=xjd1JsonCompare(p1->apKey[i], p2->apKey[i])) ) break;
  }
  if( c ){
    char const *zDir = pEList->apEItem[i].zAs;
    if( zDir && zDir[0]=='D' ){
      c = c*-1;
    }
  }
  return c;
}

static ResultItem *mergeResultItems(
  ExprList *pEList,              /* Used for ASC/DESC of each key */
  ResultItem *p1,                /* First list to merge */
  ResultItem *p2                 /* Second list to merge */
){
  ResultItem *pRet = 0;
................................................................................
    if( !p1 ){
      *ppNext = p2;
      p2 = 0;
    }else if( !p2 ){
      *ppNext = p1;
      p1 = 0;
    }else{
      int c = cmpResultItem(p1, p2, pEList);











      if( c<=0 ){
        *ppNext = p1;
        ppNext = &p1->pNext;
        p1 = p1->pNext;
      }else{
        *ppNext = p2;
        ppNext = &p2->pNext;
................................................................................
      }
    }
  }

  return pRet;
}


static void sortResultList(ResultList *pList, ExprList *pEList){

  int i;                          /* Used to iterate through aList[] */
  ResultItem *aList[40];          /* Array of slots for merge sort */


  ResultItem *pHead;

  memset(aList, 0, sizeof(aList));
  pHead = pList->pItem;

  while( pHead ){
    ResultItem *pNext = pHead->pNext;
    pHead->pNext = 0;
    for(i=0; aList[i]; i++){
      assert( i<ArraySize(aList) );
      pHead = mergeResultItems(pEList, pHead, aList[i]);
      aList[i] = 0;
    }
    aList[i] = pHead;
    pHead = pNext;
  }

  pHead = aList[0];
  for(i=1; i<ArraySize(aList); i++){
    pHead = mergeResultItems(pEList, pHead, aList[i]);
  }

  pList->pItem = pHead;
}

static void popResultList(ResultList *pList){
................................................................................
    xjd1JsonFree(pItem->apKey[i]);
  }
}

static void clearResultList(ResultList *pList){
  while( pList->pItem ) popResultList(pList);
  xjd1PoolDelete(pList->pPool);
  memset(pList, 0, sizeof(ResultList));
}

/*
** Called after statement parsing to initalize every Query object
** within the statement.
*/
int xjd1QueryInit(Query *pQuery, xjd1_stmt *pStmt, Query *pOuter){
................................................................................
/*
** Rewind a query so that it is pointing at the first row.
*/
int xjd1QueryRewind(Query *p){
  if( p==0 ) return XJD1_OK;
  if( p->eQType==TK_SELECT ){
    xjd1DataSrcRewind(p->u.simple.pFrom);
    p->eDocFrom = XJD1_FROM_DATASRC;
    p->bStarted = 0;
    clearResultList(&p->ordered);
    clearResultList(&p->grouped);
    xjd1AggregateClear(p);
  }else{
    xjd1QueryRewind(p->u.compound.pLeft);
    p->u.compound.doneLeft = 0;
    xjd1QueryRewind(p->u.compound.pRight);
  }
  return XJD1_OK;
................................................................................
/*
** Advance to the next row of the TK_SELECT query passed as the first 
** argument, disregarding any ORDER BY, OFFSET or LIMIT clause.
**
** Return XJD1_ROW if there is such a row, or XJD1_DONE at EOF. Or return 
** an error code if an error occurs.
*/
static int selectStepWhered(Query *p){
  int rc;                         /* Return code */
  assert( p->eQType==TK_SELECT );
  do{
    rc = xjd1DataSrcStep(p->u.simple.pFrom);
  }while(
    rc==XJD1_ROW
    && (p->u.simple.pWhere!=0 && !xjd1ExprTrue(p->u.simple.pWhere))
  );
  return rc;
}








static int selectStepGrouped(Query *p){
  int rc;

  if( p->pAgg ){
    Aggregate *pAgg = p->pAgg;

    ExprList *pGroupBy = p->u.simple.pGroupBy;

    rc = XJD1_OK;
    if( pGroupBy==0 ){
      /* An aggregate query with no GROUP BY clause. If there is no GROUP BY,
      ** then exactly one row is returned, which makes ORDER BY and DISTINCT 
      ** no-ops. And it is not possible to have a HAVING clause without a
      ** GROUP BY, so no need to worry about that either. 
      */
      assert( p->u.simple.pHaving==0 );

      if( p->grouped.pPool==0 ){
        JsonNode **apSrc;
        int nSrc;
        Pool *pPool;

        pPool = p->grouped.pPool = xjd1PoolNew();
        if( !pPool ) return XJD1_NOMEM;

        p->grouped.nKey = nSrc = xjd1DataSrcCount(p->u.simple.pFrom);
        apSrc = (JsonNode **)xjd1PoolMallocZero(pPool, nSrc*sizeof(JsonNode *));
        if( !apSrc ) return XJD1_NOMEM;

        /* Call the xStep() of each aggregate in the query for each row 
        ** matched by the query WHERE clause. */
        while( rc==XJD1_OK && XJD1_ROW==(rc = selectStepWhered(p) ) ){
          rc = xjd1AggregateStep(pAgg);
          xjd1DataSrcCacheSave(p->u.simple.pFrom, apSrc);
        }
        if( rc==XJD1_DONE ){
          rc = addToResultList(&p->grouped, apSrc);
          if( rc==XJD1_OK ){
            rc = XJD1_ROW;
            p->eDocFrom = XJD1_FROM_GROUPED;
          }
        }
      }else{
        rc = XJD1_DONE;
      }
      
      /* TODO: If this is a top-level query, then xQueryDoc(p, 0) will be
      ** called exactly once to retrieve the query result. When any 
      ** aggregate expressions within the query result are evaluated, the 
      ** xFinal function is evaluated. But this will only work once - if
      ** xQueryDoc(p, 0) is called more than once it will break. Find out if
      ** this is a problem!
      */

    }else{

      /* An aggregate with a GROUP BY clause. There may also be a DISTINCT
      ** qualifier.
      **
      ** Use a ResultList to sort all the rows matched by the WHERE
      ** clause. The apKey[] array consists of each of the expressions
      ** in the GROUP BY clause, followed by each document in the FROM
      ** clause. */
      do {
        ResultItem *pItem;
  
        if( p->grouped.pPool==0 ){
          DataSrc *pFrom = p->u.simple.pFrom;
          JsonNode **apKey;
          int nByte;
          Pool *pPool;
  
          /* Allocate the memory pool for this ResultList. And apKey. */
          pPool = p->grouped.pPool = xjd1PoolNew();
          p->grouped.nKey = pGroupBy->nEItem + xjd1DataSrcCount(pFrom);
          if( !pPool ) return XJD1_NOMEM;
          nByte = p->grouped.nKey * sizeof(JsonNode *);
          apKey = (JsonNode **)xjd1PoolMallocZero(pPool, nByte);
          if( !apKey ) return XJD1_NOMEM;
  
          while( rc==XJD1_OK && XJD1_ROW==(rc = selectStepWhered(p) ) ){
            int i;
            for(i=0; i<pGroupBy->nEItem; i++){


              apKey[i] = xjd1ExprEval(pGroupBy->apEItem[i].pExpr);
            }
            xjd1DataSrcCacheSave(pFrom, &apKey[i]);
            rc = addToResultList(&p->grouped, apKey);
            memset(apKey, 0, nByte);
          }
          if( rc!=XJD1_DONE ) return rc;


          sortResultList(&p->grouped, pGroupBy);
        }else{
          popResultList(&p->grouped);
        }
  
        p->eDocFrom = XJD1_FROM_GROUPED;
        pItem = p->grouped.pItem;
        if( pItem==0 ){
          rc = XJD1_DONE;
        }else{
          while( 1 ){
            ResultItem *pNext = pItem->pNext;
            rc = xjd1AggregateStep(pAgg);
            if( !pNext || cmpResultItem(pItem, pNext, pGroupBy) ){
              break;
            }
            popResultList(&p->grouped);
            pItem = p->grouped.pItem;
          }
          rc = XJD1_ROW;
        }

      }while( rc==XJD1_ROW 
           && p->u.simple.pHaving && !xjd1ExprTrue(p->u.simple.pHaving)
      );
    }

  }else{

    /* Non-aggregate query */
    rc = selectStepWhered(p);
  }

  return rc;
}

/*
** Advance to the next row of the TK_SELECT query passed as the first 
** argument, disregarding any OFFSET or LIMIT clause.
**
** Return XJD1_ROW if there is such a row, or XJD1_EOF if there is not. Or 
** return an error code if an error occurs.
*/
static int selectStepOrdered(Query *p){
  int rc = XJD1_OK;               /* Return Code */

  if( p->u.simple.pOrderBy ){

    /* A non-aggregate with an ORDER BY clause. */

    if( p->ordered.pPool==0 ){
      int nKey = p->u.simple.pOrderBy->nEItem + 1;
      ExprList *pOrderBy = p->u.simple.pOrderBy;
      Pool *pPool;
      JsonNode **apKey;

      p->ordered.nKey = nKey;
      pPool = p->ordered.pPool = xjd1PoolNew();
      if( !pPool ) return XJD1_NOMEM;
      apKey = xjd1PoolMallocZero(pPool, nKey * sizeof(JsonNode *));
      if( !apKey ) return XJD1_NOMEM;

      while( XJD1_ROW==(rc = selectStepGrouped(p) ) ){
        int i;
        for(i=0; i<pOrderBy->nEItem; i++){
          apKey[i] = xjd1ExprEval(pOrderBy->apEItem[i].pExpr);
        }
        apKey[i] = xjd1QueryDoc(p, 0);

        rc = addToResultList(&p->ordered, apKey);
        if( rc!=XJD1_OK ) break;
      }
      if( rc!=XJD1_DONE ) return rc;

      sortResultList(&p->ordered, p->u.simple.pOrderBy);
      p->eDocFrom = XJD1_FROM_ORDERED;
    }else{
      assert( p->eDocFrom==XJD1_FROM_ORDERED );
      popResultList(&p->ordered);
    }

    rc = p->ordered.pItem ? XJD1_ROW : XJD1_DONE;
  }else{
    /* No ORDER BY clause. */
    rc = selectStepGrouped(p);
  }

  return rc;
}

/*
** Advance a query to the next row.  Return XDJ1_DONE if there is no
** next row, or XJD1_ROW if the step was successful.
*/
int xjd1QueryStep(Query *p){
  int rc = XJD1_ROW;
  if( p==0 ) return XJD1_DONE;
  if( p->eQType==TK_SELECT ){

    /* Calculate the values, if any, of the LIMIT and OFFSET clauses.
    **
    ** TBD: Should this throw an exception if the result of evaluating
    ** either of these clauses cannot be converted to a number?
    */
................................................................................

        pLimit = xjd1ExprEval(p->u.simple.pLimit);
        if( 0==xjd1JsonToReal(pLimit, &rLimit) ){
          p->nLimit = (int)rLimit;
        }
        xjd1JsonFree(pLimit);
      }

    }

    if( rc==XJD1_ROW ){
      if( p->nLimit==0 ){
        rc = XJD1_DONE;
      }else{
        rc = selectStepOrdered(p);
        if( p->nLimit>0 ) p->nLimit--;
      }
    }
    p->bStarted = 1;
  }else{
    if( !p->u.compound.doneLeft ){
      rc = xjd1QueryStep(p->u.compound.pLeft);
      if( rc==XJD1_DONE ) p->u.compound.doneLeft = 1;
    }
    if( p->u.compound.doneLeft ){
      rc = xjd1QueryStep(p->u.compound.pRight);
................................................................................
**
** The caller must invoke JsonFree() when it is done with this value.
*/
JsonNode *xjd1QueryDoc(Query *p, const char *zDocName){
  JsonNode *pOut = 0;
  if( p ){
    if( p->eQType==TK_SELECT ){
      switch( p->eDocFrom ){
        case XJD1_FROM_ORDERED:
          assert( zDocName==0 && p->ordered.pItem );

          pOut = xjd1JsonRef(p->ordered.pItem->apKey[p->ordered.nKey-1]);
          break;

        case XJD1_FROM_GROUPED:
          if( zDocName==0 && p->u.simple.pRes ){
            pOut = xjd1ExprEval(p->u.simple.pRes);

          }else{
            JsonNode **apSrc = p->grouped.pItem->apKey;
            if( p->u.simple.pGroupBy ){
              apSrc = &apSrc[p->u.simple.pGroupBy->nEItem];
            }
            pOut = xjd1DataSrcCacheRead(p->u.simple.pFrom, apSrc, zDocName);
          }
          break;

        case XJD1_FROM_DATASRC:
          if( zDocName==0 && p->u.simple.pRes ){
            pOut = xjd1ExprEval(p->u.simple.pRes);
          }else{
            pOut = xjd1DataSrcDoc(p->u.simple.pFrom, zDocName);
          }
          break;
      }

    }else if( !p->u.compound.doneLeft ){
      pOut = xjd1QueryDoc(p->u.compound.pLeft, zDocName);
    }else{
      pOut = xjd1QueryDoc(p->u.compound.pRight, zDocName);
    }
................................................................................
/*
** The destructor for a Query object.
*/
int xjd1QueryClose(Query *pQuery){
  int rc = XJD1_OK;
  if( pQuery==0 ) return rc;
  if( pQuery->eQType==TK_SELECT ){
    clearResultList(&pQuery->ordered);
    clearResultList(&pQuery->grouped);
    xjd1ExprClose(pQuery->u.simple.pRes);
    xjd1DataSrcClose(pQuery->u.simple.pFrom);
    xjd1ExprClose(pQuery->u.simple.pWhere);
    xjd1ExprListClose(pQuery->u.simple.pGroupBy);
    xjd1ExprClose(pQuery->u.simple.pHaving);
    xjd1ExprListClose(pQuery->u.simple.pOrderBy);
    xjd1ExprClose(pQuery->u.simple.pLimit);

Changes to src/xjd1Int.h.

39
40
41
42
43
44
45









46
47
48
49
50
51
52
...
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
...
271
272
273
274
275
276
277
278



279
280
281
282
283
284
285





286
287
288
289
290
291
292
...
456
457
458
459
460
461
462
463
464
465
466
#define TK_ILLEGAL           102
#define TK_CREATECOLLECTION  103
#define TK_DROPCOLLECTION    104
#define TK_ARRAY             105
#define TK_STRUCT            106
#define TK_JVALUE            107










typedef unsigned char u8;
typedef unsigned short int u16;
typedef struct Aggregate Aggregate;
typedef struct Command Command;
typedef struct DataSrc DataSrc;
typedef struct Expr Expr;
typedef struct ExprItem ExprItem;
................................................................................
struct ResultList {
  Pool *pPool;
  int nKey;
  ResultItem *pItem;
};

struct Aggregate {
  int eAction;                    /* One of XJD1_AGG_STEP or XJD1_AGG_FINAL */
  int nNode;                      /* Size of apNode array */
  JsonNode **apNode;              /* Cache of datasource values */
  int nExpr;                      /* Number of aggregate functions */
  Expr **apExpr;                  /* Array of aggregate functions */
};
#define XJD1_AGG_STEP  0
#define XJD1_AGG_FINAL 1

/* A query statement */
struct Query {
  int eQType;                   /* Query type */
  xjd1_stmt *pStmt;             /* Statement this query is part of */
  Query *pOuter;                /* Next outer query for a subquery */
  union {
................................................................................
      Expr *pHaving;              /* The HAVING clause */
      ExprList *pOrderBy;         /* The ORDER BY clause */
      Expr *pLimit;               /* The LIMIT clause */
      Expr *pOffset;              /* The OFFSET clause */
    } simple;
  } u;

  Aggregate *pAgg;              /* Aggregation info. NULL for non-aggregates */




  int bDone;                      /* Set to true after query is finished */
  int bStarted;                   /* Set to true after first Step() */
  int nLimit;                     /* Stop after returning this many more rows */
  int bUseResultList;             /* True to read results from Query.result */
  ResultList result;              /* List of query results in sorted order */
};






/* A Data Source is a representation of a term out of the FROM clause. */
struct DataSrc {
  int eDSType;              /* Source type */
  char *zAs;                /* The identifier after the AS keyword */
  Query *pQuery;            /* Query this data source services */
  JsonNode *pValue;         /* Current value for this data source */
................................................................................

/******************************** func.c *************************************/
int xjd1FunctionInit(Expr *p, xjd1_stmt *pStmt, Query *pQuery, int bAggOk);
JsonNode *xjd1FunctionEval(Expr *p);
void xjd1FunctionClose(Expr *p);

int xjd1AggregateInit(xjd1_stmt *, Query *, Expr *);
int xjd1AggregateStep(Expr *p);
void xjd1AggregateClear(Query *);

#endif /* _XJD1INT_H */







>
>
>
>
>
>
>
>
>







 







<
<
<



<
<







 







|
>
>
>

<


<
<

>
>
>
>
>







 







|



39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
...
248
249
250
251
252
253
254



255
256
257


258
259
260
261
262
263
264
...
275
276
277
278
279
280
281
282
283
284
285
286

287
288


289
290
291
292
293
294
295
296
297
298
299
300
301
...
465
466
467
468
469
470
471
472
473
474
475
#define TK_ILLEGAL           102
#define TK_CREATECOLLECTION  103
#define TK_DROPCOLLECTION    104
#define TK_ARRAY             105
#define TK_STRUCT            106
#define TK_JVALUE            107

/*
** A convenience macro for returning the size of an fixed-size array. 
** For example:
**
**     DataType var[N];
**     assert( ArraySize(var)==N );
*/
#define ArraySize(X)    ((int)(sizeof(X)/sizeof(X[0])))

typedef unsigned char u8;
typedef unsigned short int u16;
typedef struct Aggregate Aggregate;
typedef struct Command Command;
typedef struct DataSrc DataSrc;
typedef struct Expr Expr;
typedef struct ExprItem ExprItem;
................................................................................
struct ResultList {
  Pool *pPool;
  int nKey;
  ResultItem *pItem;
};

struct Aggregate {



  int nExpr;                      /* Number of aggregate functions */
  Expr **apExpr;                  /* Array of aggregate functions */
};



/* A query statement */
struct Query {
  int eQType;                   /* Query type */
  xjd1_stmt *pStmt;             /* Statement this query is part of */
  Query *pOuter;                /* Next outer query for a subquery */
  union {
................................................................................
      Expr *pHaving;              /* The HAVING clause */
      ExprList *pOrderBy;         /* The ORDER BY clause */
      Expr *pLimit;               /* The LIMIT clause */
      Expr *pOffset;              /* The OFFSET clause */
    } simple;
  } u;

  Aggregate *pAgg;                /* Aggregation info. 0 for non-aggregates */
  ResultList grouped;             /* Grouped results, for GROUP BY queries */
  ResultList ordered;             /* Query results in sorted order */
  int eDocFrom;                   /* XJD1_FROM_* - configures xjd1QueryDoc() */


  int bStarted;                   /* Set to true after first Step() */
  int nLimit;                     /* Stop after returning this many more rows */


};

/* Candidate values for Query.eDocFrom */
#define XJD1_FROM_DATASRC 0
#define XJD1_FROM_GROUPED 1
#define XJD1_FROM_ORDERED 2

/* A Data Source is a representation of a term out of the FROM clause. */
struct DataSrc {
  int eDSType;              /* Source type */
  char *zAs;                /* The identifier after the AS keyword */
  Query *pQuery;            /* Query this data source services */
  JsonNode *pValue;         /* Current value for this data source */
................................................................................

/******************************** func.c *************************************/
int xjd1FunctionInit(Expr *p, xjd1_stmt *pStmt, Query *pQuery, int bAggOk);
JsonNode *xjd1FunctionEval(Expr *p);
void xjd1FunctionClose(Expr *p);

int xjd1AggregateInit(xjd1_stmt *, Query *, Expr *);
int xjd1AggregateStep(Aggregate *);
void xjd1AggregateClear(Query *);

#endif /* _XJD1INT_H */

Changes to test/base05.test.

1
2
3
4

5
6
7
8
9
10
11
..
80
81
82
83
84
85
86










87



88



89




-- Further warm body tests. The tests in this file focus on ORDER BY, GROUP BY
-- and DISTINCT.

.new t1.db

CREATE COLLECTION c1;
INSERT INTO c1 VALUE {i:13, z:"Grape"};
INSERT INTO c1 VALUE {i:4, z:"Cherry"};
INSERT INTO c1 VALUE {i:12, z:"Gooseberry"};
INSERT INTO c1 VALUE {i:15, z:"Guava"};
INSERT INTO c1 VALUE {i:17, z:"Huckleberry"};
INSERT INTO c1 VALUE {i:3, z:"Cantaloupe"};
................................................................................

.testcase 14
SELECT count(x) FROM c1, c1 AS b;
SELECT count(x) FROM c1, c1 AS b WHERE c1.i<3 && b.i<3;
SELECT count(x) FROM c1, c1 AS b WHERE c1.i==1;
.result 289 4 17




























>







 







>
>
>
>
>
>
>
>
>
>

>
>
>

>
>
>

>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
..
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
-- Further warm body tests. The tests in this file focus on ORDER BY, GROUP BY
-- and DISTINCT.

.new t1.db

CREATE COLLECTION c1;
INSERT INTO c1 VALUE {i:13, z:"Grape"};
INSERT INTO c1 VALUE {i:4, z:"Cherry"};
INSERT INTO c1 VALUE {i:12, z:"Gooseberry"};
INSERT INTO c1 VALUE {i:15, z:"Guava"};
INSERT INTO c1 VALUE {i:17, z:"Huckleberry"};
INSERT INTO c1 VALUE {i:3, z:"Cantaloupe"};
................................................................................

.testcase 14
SELECT count(x) FROM c1, c1 AS b;
SELECT count(x) FROM c1, c1 AS b WHERE c1.i<3 && b.i<3;
SELECT count(x) FROM c1, c1 AS b WHERE c1.i==1;
.result 289 4 17

.testcase 15
CREATE COLLECTION c2;
INSERT INTO c2 VALUE { a:"a", b:1 };
INSERT INTO c2 VALUE { a:"b", b:2 };
INSERT INTO c2 VALUE { a:"c", b:1 };
INSERT INTO c2 VALUE { a:"a", b:3 };
INSERT INTO c2 VALUE { a:"b", b:1 };
INSERT INTO c2 VALUE { a:"a", b:2 };
SELECT {x:count(c2.b),y:c2.a} FROM c2 GROUP BY c2.a;
.result {"x":3,"y":"a"} {"x":2,"y":"b"} {"x":1,"y":"c"}

.testcase 16
SELECT {x:count(c2.b),y:c2.a} FROM c2 GROUP BY c2.a ORDER BY count(c2.b) DESC;
.result {"x":3,"y":"a"} {"x":2,"y":"b"} {"x":1,"y":"c"}

.testcase 17
SELECT {x:count(c2.b),y:c2.a} FROM c2 GROUP BY c2.a ORDER BY count(c2.b) ASC;
.result {"x":1,"y":"c"} {"x":2,"y":"b"} {"x":3,"y":"a"} 

.testcase 18
SELECT {x:count(c2.b),y:c2.a} FROM c2 GROUP BY c2.a HAVING count(c2.b)>1;
.result {"x":3,"y":"a"} {"x":2,"y":"b"}