You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@carbondata.apache.org by qi...@apache.org on 2020/06/30 02:22:38 UTC
[carbondata] branch master updated: [CARBONDATA-3871] Optimize
performance when getting row from heap
This is an automated email from the ASF dual-hosted git repository.
qiangcai pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/carbondata.git
The following commit(s) were added to refs/heads/master by this push:
new 9da42c4 [CARBONDATA-3871] Optimize performance when getting row from heap
9da42c4 is described below
commit 9da42c495e84deb74c277e182e2e4b93bca8c129
Author: Manhua <ke...@qq.com>
AuthorDate: Wed Jun 24 16:53:28 2020 +0800
[CARBONDATA-3871] Optimize performance when getting row from heap
Why is this PR needed?
Currently carbon uses priority queue to sort holders of sorted rows.
It first polls a holder from the heap, and adds it back if holder is not empty.
This will cause two times heap maintainance. We can reduce half of that operation,
and test shows it can save one third of time to get rows .
What changes were proposed in this PR?
What will be done when poll item from priority queue currently is:
1. remove first item.
2. move the last item to the position of first item, siftDown the new first item.
In this patch, we will peek(without removing from heap) the first item and get a row,
and siftDown the holder to a proper position if the holder is not empty.
Since this will affect order of non-sorted columns, it depends on #3813
Does this PR introduce any user interface change?
No
Is any new testcase added?
No
This closes #3804
---
.../loading/sort/CarbonPriorityQueue.java | 66 ++++++++++++++++++++++
.../UnsafeInMemoryIntermediateDataMerger.java | 17 +++---
.../merger/UnsafeIntermediateFileMerger.java | 16 +++---
.../UnsafeSingleThreadFinalSortFilesMerger.java | 16 +++---
.../merger/RowResultMergerProcessor.java | 15 ++---
.../sort/sortdata/IntermediateFileMerger.java | 15 +++--
.../sortdata/SingleThreadFinalSortFilesMerger.java | 16 +++---
7 files changed, 114 insertions(+), 47 deletions(-)
diff --git a/processing/src/main/java/org/apache/carbondata/processing/loading/sort/CarbonPriorityQueue.java b/processing/src/main/java/org/apache/carbondata/processing/loading/sort/CarbonPriorityQueue.java
new file mode 100644
index 0000000..aa3f19a
--- /dev/null
+++ b/processing/src/main/java/org/apache/carbondata/processing/loading/sort/CarbonPriorityQueue.java
@@ -0,0 +1,66 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.carbondata.processing.loading.sort;
+
+import java.lang.reflect.Field;
+import java.lang.reflect.Method;
+import java.util.Comparator;
+import java.util.PriorityQueue;
+
+import org.apache.carbondata.processing.loading.exception.CarbonDataLoadingException;
+
+/**
+ * This class is used to optimize sort step performance while getting row from heap,
+ * including intermediate merge and final sort merge in loading process,
+ * by accessing member/method in PriorityQueue
+ */
+public class CarbonPriorityQueue<E> extends PriorityQueue<E> {
+ private transient Field queueField;
+ private transient Method siftDownMethod;
+ private static final long serialVersionUID = 1L;
+
+ public CarbonPriorityQueue(int initialCapacity) {
+ super(initialCapacity);
+ init();
+ }
+
+ public CarbonPriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
+ super(initialCapacity, comparator);
+ init();
+ }
+
+ private void init() {
+ try {
+ queueField = PriorityQueue.class.getDeclaredField("queue");
+ queueField.setAccessible(true);
+ siftDownMethod = PriorityQueue.class.getDeclaredMethod("siftDown", int.class, Object.class);
+ siftDownMethod.setAccessible(true);
+ } catch (ReflectiveOperationException e) {
+ throw new CarbonDataLoadingException("Reflective operation failed", e);
+ }
+ }
+
+ public void siftTopDown() {
+ try {
+ Object topNode = ((Object[]) queueField.get(this))[0];
+ siftDownMethod.invoke(this, 0, topNode);
+ } catch (ReflectiveOperationException e) {
+ throw new CarbonDataLoadingException("Reflective operation failed", e);
+ }
+ }
+}
diff --git a/processing/src/main/java/org/apache/carbondata/processing/loading/sort/unsafe/merger/UnsafeInMemoryIntermediateDataMerger.java b/processing/src/main/java/org/apache/carbondata/processing/loading/sort/unsafe/merger/UnsafeInMemoryIntermediateDataMerger.java
index 34f3585..558a40a 100644
--- a/processing/src/main/java/org/apache/carbondata/processing/loading/sort/unsafe/merger/UnsafeInMemoryIntermediateDataMerger.java
+++ b/processing/src/main/java/org/apache/carbondata/processing/loading/sort/unsafe/merger/UnsafeInMemoryIntermediateDataMerger.java
@@ -20,9 +20,7 @@ package org.apache.carbondata.processing.loading.sort.unsafe.merger;
import java.io.DataOutputStream;
import java.io.File;
import java.io.IOException;
-import java.util.AbstractQueue;
import java.util.NoSuchElementException;
-import java.util.PriorityQueue;
import java.util.Random;
import java.util.concurrent.Callable;
@@ -31,6 +29,7 @@ import org.apache.carbondata.core.constants.CarbonCommonConstants;
import org.apache.carbondata.core.datastore.impl.FileFactory;
import org.apache.carbondata.core.util.CarbonUtil;
import org.apache.carbondata.processing.loading.row.IntermediateSortTempRow;
+import org.apache.carbondata.processing.loading.sort.CarbonPriorityQueue;
import org.apache.carbondata.processing.loading.sort.SortStepRowHandler;
import org.apache.carbondata.processing.loading.sort.unsafe.UnsafeCarbonRowPage;
import org.apache.carbondata.processing.loading.sort.unsafe.holder.UnsafeCarbonRowForMerge;
@@ -49,7 +48,7 @@ public class UnsafeInMemoryIntermediateDataMerger implements Callable<Void> {
/**
* recordHolderHeap
*/
- private AbstractQueue<UnsafeInmemoryMergeHolder> recordHolderHeap;
+ private CarbonPriorityQueue<UnsafeInmemoryMergeHolder> recordHolderHeap;
/**
* fileCounter
@@ -141,25 +140,27 @@ public class UnsafeInMemoryIntermediateDataMerger implements Callable<Void> {
// be based on comparator we are passing the heap
// when will call poll it will always delete root of the tree and then
// it does trickel down operation complexity is log(n)
- UnsafeInmemoryMergeHolder poll = this.recordHolderHeap.poll();
+ UnsafeInmemoryMergeHolder poll = this.recordHolderHeap.peek();
// get the row from chunk
row = poll.getRow();
// check if there no entry present
if (!poll.hasNext()) {
+ poll.close();
+ this.recordHolderHeap.poll();
// change the file counter
--this.holderCounter;
- // reaturn row
+ // return row
return row;
}
// read new row
poll.readRow();
- // add to heap
- this.recordHolderHeap.add(poll);
+ // maintain heap
+ this.recordHolderHeap.siftTopDown();
// return row
return row;
@@ -203,7 +204,7 @@ public class UnsafeInMemoryIntermediateDataMerger implements Callable<Void> {
*/
private void createRecordHolderQueue(UnsafeCarbonRowPage[] pages) {
// creating record holder heap
- this.recordHolderHeap = new PriorityQueue<UnsafeInmemoryMergeHolder>(pages.length);
+ this.recordHolderHeap = new CarbonPriorityQueue<>(pages.length);
}
/**
diff --git a/processing/src/main/java/org/apache/carbondata/processing/loading/sort/unsafe/merger/UnsafeIntermediateFileMerger.java b/processing/src/main/java/org/apache/carbondata/processing/loading/sort/unsafe/merger/UnsafeIntermediateFileMerger.java
index 2764acc..b7c3627 100644
--- a/processing/src/main/java/org/apache/carbondata/processing/loading/sort/unsafe/merger/UnsafeIntermediateFileMerger.java
+++ b/processing/src/main/java/org/apache/carbondata/processing/loading/sort/unsafe/merger/UnsafeIntermediateFileMerger.java
@@ -21,15 +21,14 @@ import java.io.DataOutputStream;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
-import java.util.AbstractQueue;
import java.util.NoSuchElementException;
-import java.util.PriorityQueue;
import java.util.concurrent.Callable;
import org.apache.carbondata.common.logging.LogServiceFactory;
import org.apache.carbondata.core.datastore.impl.FileFactory;
import org.apache.carbondata.core.util.CarbonUtil;
import org.apache.carbondata.processing.loading.row.IntermediateSortTempRow;
+import org.apache.carbondata.processing.loading.sort.CarbonPriorityQueue;
import org.apache.carbondata.processing.loading.sort.SortStepRowHandler;
import org.apache.carbondata.processing.loading.sort.unsafe.holder.SortTempChunkHolder;
import org.apache.carbondata.processing.loading.sort.unsafe.holder.UnsafeSortTempFileChunkHolder;
@@ -49,7 +48,7 @@ public class UnsafeIntermediateFileMerger implements Callable<Void> {
/**
* recordHolderHeap
*/
- private AbstractQueue<SortTempChunkHolder> recordHolderHeap;
+ private CarbonPriorityQueue<SortTempChunkHolder> recordHolderHeap;
/**
* fileCounter
@@ -163,7 +162,7 @@ public class UnsafeIntermediateFileMerger implements Callable<Void> {
// be based on comparator we are passing the heap
// when will call poll it will always delete root of the tree and then
// it does trickel down operation complexity is log(n)
- SortTempChunkHolder poll = this.recordHolderHeap.poll();
+ SortTempChunkHolder poll = this.recordHolderHeap.peek();
// get the row from chunk
row = poll.getRow();
@@ -172,19 +171,20 @@ public class UnsafeIntermediateFileMerger implements Callable<Void> {
if (!poll.hasNext()) {
// if chunk is empty then close the stream
poll.close();
+ this.recordHolderHeap.poll();
// change the file counter
--this.fileCounter;
- // reaturn row
+ // return row
return row;
}
// read new row
poll.readRow();
- // add to heap
- this.recordHolderHeap.add(poll);
+ // maintain heap
+ this.recordHolderHeap.siftTopDown();
// return row
return row;
@@ -232,7 +232,7 @@ public class UnsafeIntermediateFileMerger implements Callable<Void> {
*/
private void createRecordHolderQueue(File[] listFiles) {
// creating record holder heap
- this.recordHolderHeap = new PriorityQueue<SortTempChunkHolder>(listFiles.length);
+ this.recordHolderHeap = new CarbonPriorityQueue<>(listFiles.length);
}
/**
diff --git a/processing/src/main/java/org/apache/carbondata/processing/loading/sort/unsafe/merger/UnsafeSingleThreadFinalSortFilesMerger.java b/processing/src/main/java/org/apache/carbondata/processing/loading/sort/unsafe/merger/UnsafeSingleThreadFinalSortFilesMerger.java
index 2d0fbd3..6d8df39 100644
--- a/processing/src/main/java/org/apache/carbondata/processing/loading/sort/unsafe/merger/UnsafeSingleThreadFinalSortFilesMerger.java
+++ b/processing/src/main/java/org/apache/carbondata/processing/loading/sort/unsafe/merger/UnsafeSingleThreadFinalSortFilesMerger.java
@@ -19,18 +19,17 @@ package org.apache.carbondata.processing.loading.sort.unsafe.merger;
import java.io.File;
import java.io.FileFilter;
-import java.util.AbstractQueue;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
-import java.util.PriorityQueue;
import org.apache.carbondata.common.CarbonIterator;
import org.apache.carbondata.common.logging.LogServiceFactory;
import org.apache.carbondata.core.datastore.exception.CarbonDataWriterException;
import org.apache.carbondata.processing.loading.row.IntermediateSortTempRow;
+import org.apache.carbondata.processing.loading.sort.CarbonPriorityQueue;
import org.apache.carbondata.processing.loading.sort.SortStepRowHandler;
import org.apache.carbondata.processing.loading.sort.unsafe.UnsafeCarbonRowPage;
import org.apache.carbondata.processing.loading.sort.unsafe.holder.SortTempChunkHolder;
@@ -57,7 +56,7 @@ public class UnsafeSingleThreadFinalSortFilesMerger extends CarbonIterator<Objec
/**
* recordHolderHeap
*/
- private AbstractQueue<SortTempChunkHolder> recordHolderHeapLocal;
+ private CarbonPriorityQueue<SortTempChunkHolder> recordHolderHeapLocal;
private SortParameters parameters;
private SortStepRowHandler sortStepRowHandler;
@@ -188,7 +187,7 @@ public class UnsafeSingleThreadFinalSortFilesMerger extends CarbonIterator<Objec
*/
private void createRecordHolderQueue() {
// creating record holder heap
- this.recordHolderHeapLocal = new PriorityQueue<SortTempChunkHolder>(fileCounter);
+ this.recordHolderHeapLocal = new CarbonPriorityQueue<>(fileCounter);
}
/**
@@ -218,7 +217,7 @@ public class UnsafeSingleThreadFinalSortFilesMerger extends CarbonIterator<Objec
// be based on comparator we are passing the heap
// when will call poll it will always delete root of the tree and then
// it does trickel down operation complexity is log(n)
- SortTempChunkHolder poll = this.recordHolderHeapLocal.poll();
+ SortTempChunkHolder poll = this.recordHolderHeapLocal.peek();
// get the row from chunk
row = poll.getRow();
@@ -227,11 +226,12 @@ public class UnsafeSingleThreadFinalSortFilesMerger extends CarbonIterator<Objec
if (!poll.hasNext()) {
// if chunk is empty then close the stream
poll.close();
+ recordHolderHeapLocal.poll();
// change the file counter
--this.fileCounter;
- // reaturn row
+ // return row
return row;
}
@@ -242,8 +242,8 @@ public class UnsafeSingleThreadFinalSortFilesMerger extends CarbonIterator<Objec
throw new CarbonDataWriterException(e);
}
- // add to heap
- this.recordHolderHeapLocal.add(poll);
+ // maintain heap
+ this.recordHolderHeapLocal.siftTopDown();
// return row
return row;
diff --git a/processing/src/main/java/org/apache/carbondata/processing/merger/RowResultMergerProcessor.java b/processing/src/main/java/org/apache/carbondata/processing/merger/RowResultMergerProcessor.java
index 121b798..c044257 100644
--- a/processing/src/main/java/org/apache/carbondata/processing/merger/RowResultMergerProcessor.java
+++ b/processing/src/main/java/org/apache/carbondata/processing/merger/RowResultMergerProcessor.java
@@ -18,11 +18,9 @@
package org.apache.carbondata.processing.merger;
import java.io.IOException;
-import java.util.AbstractQueue;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
-import java.util.PriorityQueue;
import org.apache.carbondata.common.logging.LogServiceFactory;
import org.apache.carbondata.core.constants.CarbonCommonConstants;
@@ -38,6 +36,7 @@ import org.apache.carbondata.core.scan.wrappers.ByteArrayWrapper;
import org.apache.carbondata.core.util.ByteUtil;
import org.apache.carbondata.processing.exception.SliceMergerException;
import org.apache.carbondata.processing.loading.model.CarbonLoadModel;
+import org.apache.carbondata.processing.loading.sort.CarbonPriorityQueue;
import org.apache.carbondata.processing.store.CarbonFactDataHandlerColumnar;
import org.apache.carbondata.processing.store.CarbonFactDataHandlerModel;
import org.apache.carbondata.processing.store.CarbonFactHandler;
@@ -59,7 +58,7 @@ public class RowResultMergerProcessor extends AbstractResultProcessor {
/**
* record holder heap
*/
- private AbstractQueue<RawResultIterator> recordHolderHeap;
+ private CarbonPriorityQueue<RawResultIterator> recordHolderHeap;
private static final Logger LOGGER =
LogServiceFactory.getLogService(RowResultMergerProcessor.class.getName());
@@ -97,7 +96,7 @@ public class RowResultMergerProcessor extends AbstractResultProcessor {
private void initRecordHolderHeap(List<RawResultIterator> rawResultIteratorList) {
// create the List of RawResultIterator.
- recordHolderHeap = new PriorityQueue<RawResultIterator>(rawResultIteratorList.size(),
+ recordHolderHeap = new CarbonPriorityQueue<>(rawResultIteratorList.size(),
new RowResultMergerProcessor.CarbonMdkeyComparator());
}
@@ -126,11 +125,12 @@ public class RowResultMergerProcessor extends AbstractResultProcessor {
RawResultIterator iterator = null;
while (index > 1) {
// iterator the top record
- iterator = this.recordHolderHeap.poll();
+ iterator = this.recordHolderHeap.peek();
Object[] convertedRow = iterator.next();
if (null == convertedRow) {
index--;
iterator.close();
+ this.recordHolderHeap.poll();
continue;
}
if (!isDataPresent) {
@@ -144,10 +144,11 @@ public class RowResultMergerProcessor extends AbstractResultProcessor {
if (!iterator.hasNext()) {
index--;
iterator.close();
+ this.recordHolderHeap.poll();
continue;
}
- // add record to heap
- this.recordHolderHeap.add(iterator);
+ // maintain heap
+ this.recordHolderHeap.siftTopDown();
}
// if record holder is not empty then iterator the slice holder from
// heap
diff --git a/processing/src/main/java/org/apache/carbondata/processing/sort/sortdata/IntermediateFileMerger.java b/processing/src/main/java/org/apache/carbondata/processing/sort/sortdata/IntermediateFileMerger.java
index d601fe5..bdf76f6 100644
--- a/processing/src/main/java/org/apache/carbondata/processing/sort/sortdata/IntermediateFileMerger.java
+++ b/processing/src/main/java/org/apache/carbondata/processing/sort/sortdata/IntermediateFileMerger.java
@@ -21,15 +21,14 @@ import java.io.DataOutputStream;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
-import java.util.AbstractQueue;
import java.util.NoSuchElementException;
-import java.util.PriorityQueue;
import java.util.concurrent.Callable;
import org.apache.carbondata.common.logging.LogServiceFactory;
import org.apache.carbondata.core.datastore.impl.FileFactory;
import org.apache.carbondata.core.util.CarbonUtil;
import org.apache.carbondata.processing.loading.row.IntermediateSortTempRow;
+import org.apache.carbondata.processing.loading.sort.CarbonPriorityQueue;
import org.apache.carbondata.processing.loading.sort.SortStepRowHandler;
import org.apache.carbondata.processing.sort.exception.CarbonSortKeyAndGroupByException;
@@ -45,7 +44,7 @@ public class IntermediateFileMerger implements Callable<Void> {
/**
* recordHolderHeap
*/
- private AbstractQueue<SortTempFileChunkHolder> recordHolderHeap;
+ private CarbonPriorityQueue<SortTempFileChunkHolder> recordHolderHeap;
/**
* fileCounter
@@ -159,7 +158,7 @@ public class IntermediateFileMerger implements Callable<Void> {
// be based on comparator we are passing the heap
// when will call poll it will always delete root of the tree and then
// it does trickel down operation complexity is log(n)
- SortTempFileChunkHolder poll = this.recordHolderHeap.poll();
+ SortTempFileChunkHolder poll = this.recordHolderHeap.peek();
// get the row from chunk
row = poll.getRow();
@@ -168,7 +167,7 @@ public class IntermediateFileMerger implements Callable<Void> {
if (!poll.hasNext()) {
// if chunk is empty then close the stream
poll.closeStream();
-
+ this.recordHolderHeap.poll();
// change the file counter
--this.fileCounter;
@@ -179,8 +178,8 @@ public class IntermediateFileMerger implements Callable<Void> {
// read new row
poll.readRow();
- // add to heap
- this.recordHolderHeap.add(poll);
+ // maintain heap
+ this.recordHolderHeap.siftTopDown();
// return row
return row;
@@ -231,7 +230,7 @@ public class IntermediateFileMerger implements Callable<Void> {
*/
private void createRecordHolderQueue(File[] listFiles) {
// creating record holder heap
- this.recordHolderHeap = new PriorityQueue<>(listFiles.length);
+ this.recordHolderHeap = new CarbonPriorityQueue<>(listFiles.length);
}
/**
diff --git a/processing/src/main/java/org/apache/carbondata/processing/sort/sortdata/SingleThreadFinalSortFilesMerger.java b/processing/src/main/java/org/apache/carbondata/processing/sort/sortdata/SingleThreadFinalSortFilesMerger.java
index 3a21039..c3f45b1 100644
--- a/processing/src/main/java/org/apache/carbondata/processing/sort/sortdata/SingleThreadFinalSortFilesMerger.java
+++ b/processing/src/main/java/org/apache/carbondata/processing/sort/sortdata/SingleThreadFinalSortFilesMerger.java
@@ -19,12 +19,10 @@ package org.apache.carbondata.processing.sort.sortdata;
import java.io.File;
import java.io.FileFilter;
-import java.util.AbstractQueue;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;
-import java.util.PriorityQueue;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
@@ -42,6 +40,7 @@ import org.apache.carbondata.core.metadata.schema.table.column.CarbonColumn;
import org.apache.carbondata.core.scan.result.iterator.RawResultIterator;
import org.apache.carbondata.core.util.CarbonProperties;
import org.apache.carbondata.processing.loading.row.IntermediateSortTempRow;
+import org.apache.carbondata.processing.loading.sort.CarbonPriorityQueue;
import org.apache.carbondata.processing.loading.sort.SortStepRowHandler;
import org.apache.carbondata.processing.sort.exception.CarbonSortKeyAndGroupByException;
@@ -62,7 +61,7 @@ public class SingleThreadFinalSortFilesMerger extends CarbonIterator<Object[]> {
/**
* recordHolderHeap
*/
- private AbstractQueue<SortTempFileChunkHolder> recordHolderHeapLocal;
+ private CarbonPriorityQueue<SortTempFileChunkHolder> recordHolderHeapLocal;
/**
* tableName
@@ -233,7 +232,7 @@ public class SingleThreadFinalSortFilesMerger extends CarbonIterator<Object[]> {
*/
private void createRecordHolderQueue(int size) {
// creating record holder heap
- this.recordHolderHeapLocal = new PriorityQueue<SortTempFileChunkHolder>(size);
+ this.recordHolderHeapLocal = new CarbonPriorityQueue<>(size);
}
private synchronized void notifyFailure(Throwable throwable) {
@@ -270,7 +269,7 @@ public class SingleThreadFinalSortFilesMerger extends CarbonIterator<Object[]> {
// be based on comparator we are passing the heap
// when will call poll it will always delete root of the tree and then
// it does trickel down operation complexity is log(n)
- SortTempFileChunkHolder poll = this.recordHolderHeapLocal.poll();
+ SortTempFileChunkHolder poll = this.recordHolderHeapLocal.peek();
// get the row from chunk
row = poll.getRow();
@@ -279,8 +278,9 @@ public class SingleThreadFinalSortFilesMerger extends CarbonIterator<Object[]> {
if (!poll.hasNext()) {
// if chunk is empty then close the stream
poll.closeStream();
+ this.recordHolderHeapLocal.poll();
- // reaturn row
+ // return row
return row;
}
@@ -292,8 +292,8 @@ public class SingleThreadFinalSortFilesMerger extends CarbonIterator<Object[]> {
throw new CarbonDataWriterException(e);
}
- // add to heap
- this.recordHolderHeapLocal.add(poll);
+ // maintain heap
+ this.recordHolderHeapLocal.siftTopDown();
// return row
return row;