You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pinot.apache.org by "chenboat (via GitHub)" <gi...@apache.org> on 2025/07/16 22:33:22 UTC
[PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
chenboat opened a new pull request, #16364:
URL: https://github.com/apache/pinot/pull/16364
Instructions:
1. The PR has to be tagged with at least one of the following labels (*):
1. `feature`
2. `bugfix`
3. `performance`
4. `ui`
5. `backward-incompat`
6. `release-notes` (**)
2. Remove these instructions before publishing the PR.
(*) Other labels to consider:
- `testing`
- `dependencies`
- `docker`
- `kubernetes`
- `observability`
- `security`
- `code-style`
- `extension-point`
- `refactor`
- `cleanup`
(**) Use `release-notes` label for scenarios like:
- New configuration options
- Deprecation of configurations
- Signature changes to public methods/interfaces
- New plugins added or old plugins removed
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "kishoreg (via GitHub)" <gi...@apache.org>.
kishoreg commented on PR #16364:
URL: https://github.com/apache/pinot/pull/16364#issuecomment-3109675037
Do you have a sample query? I had the same concern as @ankitsultana - this can explode the index. I thought its better to have FST on the tokens/dictionary and use that to find matching dictionary ids
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "deemoliu (via GitHub)" <gi...@apache.org>.
deemoliu commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2345327764
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/realtime/impl/invertedindex/RealtimeNgramFilteringIndex.java:
##########
@@ -0,0 +1,191 @@
+/**
+ * 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.pinot.segment.local.realtime.impl.invertedindex;
+
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import org.apache.lucene.analysis.ngram.NGramTokenizer;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.pinot.segment.spi.index.mutable.MutableTextIndex;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * RealtimeNgramFilteringIndex is a mutable inverted index that supports adding document IDs for n-grams. An n-gram
+ * is a contiguous sequence of n characters from input text. The length of the n-gram is variable between
+ * [minNgramLength, maxNgramLength] as specified in the index config. Internally, it uses a realtime inverted index
+ * which maps n-grams to their posting lists (document IDs). The index is thread-safe for single writer and multiple
+ * readers.
+ */
+public class RealtimeNgramFilteringIndex implements MutableTextIndex {
+ private final String _column;
+ // Under the hood, ngram index is implemented as an inverted index from n-grams to their posting lists.
+ private final RealtimeInvertedIndex _invertedIndex;
+ // A mapping from n-grams to their dictionary IDs.
+ private final Object2IntOpenHashMap<String> _ngramToDictIdMapping;
+ // Read and write locks for thread safety.
+ private final ReentrantReadWriteLock.ReadLock _readLock;
+ private final ReentrantReadWriteLock.WriteLock _writeLock;
+
+ // Next document ID to be assigned.
+ private int _nextDocId = 0;
+ private int _nextDictId = 0;
+
+ private final int _minNgramLength;
+ private final int _maxNgramLength;
+
+ public RealtimeNgramFilteringIndex(String column, int minNgramLength, int maxNgramLength) {
+ _column = column;
+ _invertedIndex = new RealtimeInvertedIndex();
+ _ngramToDictIdMapping = new Object2IntOpenHashMap<>();
+ _minNgramLength = minNgramLength;
+ _maxNgramLength = maxNgramLength;
+
+ ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
+ _readLock = readWriteLock.readLock();
+ _writeLock = readWriteLock.writeLock();
+ }
+
+ /**
+ * Index the string value
+ *
+ * @param value the input value as a string
+ */
+ @Override
+ public void add(String value) {
+ if (value == null) {
+ return;
+ }
+ addHelper(value);
+ _nextDocId++;
+ }
+
+ /**
+ * Index an array of string values. Each string in the array is treated as a separate document.
+ *
+ * @param values the documents as an array of strings
+ */
+ @Override
+ public void add(String[] values) {
+ if (values == null || values.length == 0) {
+ return;
+ }
+ for (String value : values) {
+ if (value != null) {
+ addHelper(value);
+ }
+ }
+ _nextDocId++;
+ }
+
+ /**
+ * Returns the matching dictionary ids for the given search query (optional).
+ *
+ * @param searchQuery as a literal string
+ */
+ @Override
+ public ImmutableRoaringBitmap getDictIds(String searchQuery) {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * Returns the matching document ids for the given search query.
+ * Returns null if no n-grams are generated from the search query -- either because the search query is null or empty
+ * or shorter than the minimum n-gram length.
+ * @param searchQuery as a literal string
+ */
+ @Override
+ public MutableRoaringBitmap getDocIds(String searchQuery) {
+ _readLock.lock();
+ Iterable<String> ngrams = generateNgrams(searchQuery);
+ if (!ngrams.iterator().hasNext()) {
+ return null; // No n-grams generated, return null.
+ }
+ ArrayList<MutableRoaringBitmap> bitmapLst = new ArrayList<>();
+ try {
+ for (String ngram : ngrams) {
+ int dictId = _ngramToDictIdMapping.getInt(ngram);
+ bitmapLst.add(_invertedIndex.getDocIds(dictId));
+ }
+ if (bitmapLst.isEmpty()) {
+ return null; // No n-grams found in the index.
+ }
+ MutableRoaringBitmap resultBitmap = bitmapLst.get(0);
+ for (int i = 1; i < bitmapLst.size(); i++) {
+ resultBitmap.and(bitmapLst.get(i));
+ }
+ return resultBitmap;
+ } finally {
+ _readLock.unlock();
+ }
+ }
+
+ /**
+ * Closes this stream and releases any system resources associated with it. If the stream is already closed then
+ * invoking this method has no effect.
+ *
+ * <p> As noted in {@link AutoCloseable#close()}, cases where the
+ * close may fail require careful attention. It is strongly advised to relinquish the underlying resources and to
+ * internally
+ * <em>mark</em> the {@code Closeable} as closed, prior to throwing
+ * the {@code IOException}.
+ *
+ * @throws IOException if an I/O error occurs
+ */
+ @Override
+ public void close()
+ throws IOException {
Review Comment:
should we add
_ngramToDictIdMapping.clear();
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "ankitsultana (via GitHub)" <gi...@apache.org>.
ankitsultana commented on PR #16364:
URL: https://github.com/apache/pinot/pull/16364#issuecomment-3146627518
@chenboat Let's do a design doc as is our standard practice for any reasonably big proposal. Mark from CH recently did a [video on SparseGrams](https://x.com/clickhousedb/status/1951266686201475137?s=46) too, and they took inspiration from GH's Code Search too.
Hooking n-grams into `LIKE` or even Regex is also not straight-forward and may not always be optimal. I'd recommend starting with a UDF first.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2226282109
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/realtime/impl/invertedindex/RealtimeNgramFilteringIndex.java:
##########
@@ -0,0 +1,188 @@
+/**
+ * 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.pinot.segment.local.realtime.impl.invertedindex;
+
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import org.apache.lucene.analysis.ngram.NGramTokenizer;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.pinot.segment.spi.index.mutable.MutableTextIndex;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * RealtimeNgramFilteringIndex is a mutable inverted index that supports adding document IDs for n-grams. An n-gram
+ * is a contiguous sequence of n characters from input text. The length of the n-gram is variable between
+ * [minNgramLength, maxNgramLength] as specified in the index config. Internally, it uses a realtime inverted index
+ * which maps n-grams to their posting lists (document IDs). The index is thread-safe for single writer and multiple
+ * readers.
+ */
+public class RealtimeNgramFilteringIndex implements MutableTextIndex {
Review Comment:
Ngram index applies to string/text data. So it is also one kind of text index. We use inverted index to implement the index. Compared with MutableInvertedIndex, MutableTextIndex interface is more generic. For example, its main API is
`void add(String document);
`
which is much more generic and flexible than MutableInvertedIndex's API
`void add(int dictId, int docId);
`
which expects both dictionary and docId as inputs.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on PR #16364:
URL: https://github.com/apache/pinot/pull/16364#issuecomment-3114365597
> @chenboat @deemoliu : is there a design doc for this? There's quite a lot that can be done with n-grams so it might be best to dive deeper here. (e.g. we can use n-grams to optimize regex queries based on Russ Cox's approach).
I put the first version of mini-design doc and background study in the github issue https://github.com/apache/pinot/issues/16294. I think we can have further discussion over there because that is the umbrella issue. Regarding Russ Cox's approach, are your referring to [Regular Expression Matching with a Trigram Index](Regular Expression Matching with a Trigram Index). I think his approach is the same as ours and even the parameter for ngram length of 3 (they call it trigram) is the same we tested in production and recommend the comments above. As the author summarize:
`Regular expression matching over large numbers of small documents can be made fast by using an index of the trigrams present in each document. ... We can run this query against the trigram index to identify a set of candidate documents and then run the full regular expression search against only those documents.`
>
> Also regarding index size explosion, we can also discuss how we will prevent this in production and what kind of knobs/configs we will support. e.g.
Our primary recommendation is use short ngram length (maxLength 3 recommended) to control the ngram index size. In addition, we might add string column maxlength control to make sure we do not index long strings. With this, the n-gram index size is really reasonable when we test in production. This is also consistent with Russ Cox's report as he reported
`The index file contains a list of paths (for reindexing, as described above), a list of indexed files, and then the same posting lists we saw at the beginning of this article, one for each trigram. In practice, this index tends to be around 20% of the size of the files being indexed.`
>
> * Would we add limits on max number of unique grams that we will track? Would we allow users to configure in the table-config specific gram combinations that they want to force to be tracked, etc.?
> * Should we consider adopting a sparse gram approach like the one used by GitHub in their code-search implementation?
Given the ngram length limit, Ngram filtering index needs to index all ngrams of that length to achieve filtering. So we can not put a limit. But again, with reasonable limit of ngram maxlength (3 recommended or 4 in rare case), we will not get into the scenario with too many unique gram in practice.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on PR #16364:
URL: https://github.com/apache/pinot/pull/16364#issuecomment-3202705045
@ankitsultana The ngram index design doc can be found here: https://docs.google.com/document/d/1FG1adOh9YGuePnX43maR2m3I5TpnEmQ6sU4fGtuCnh0/edit?tab=t.0#heading=h.h51hlujdi0t Please take a look and welcome any comments. We will also discuss how to integrate with Pinot query functions there.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "deemoliu (via GitHub)" <gi...@apache.org>.
deemoliu commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2345207058
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/realtime/impl/invertedindex/RealtimeNgramFilteringIndex.java:
##########
@@ -0,0 +1,191 @@
+/**
+ * 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.pinot.segment.local.realtime.impl.invertedindex;
+
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import org.apache.lucene.analysis.ngram.NGramTokenizer;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.pinot.segment.spi.index.mutable.MutableTextIndex;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * RealtimeNgramFilteringIndex is a mutable inverted index that supports adding document IDs for n-grams. An n-gram
+ * is a contiguous sequence of n characters from input text. The length of the n-gram is variable between
+ * [minNgramLength, maxNgramLength] as specified in the index config. Internally, it uses a realtime inverted index
+ * which maps n-grams to their posting lists (document IDs). The index is thread-safe for single writer and multiple
+ * readers.
+ */
+public class RealtimeNgramFilteringIndex implements MutableTextIndex {
+ private final String _column;
+ // Under the hood, ngram index is implemented as an inverted index from n-grams to their posting lists.
+ private final RealtimeInvertedIndex _invertedIndex;
+ // A mapping from n-grams to their dictionary IDs.
+ private final Object2IntOpenHashMap<String> _ngramToDictIdMapping;
+ // Read and write locks for thread safety.
+ private final ReentrantReadWriteLock.ReadLock _readLock;
+ private final ReentrantReadWriteLock.WriteLock _writeLock;
+
+ // Next document ID to be assigned.
+ private int _nextDocId = 0;
+ private int _nextDictId = 0;
+
+ private final int _minNgramLength;
+ private final int _maxNgramLength;
+
+ public RealtimeNgramFilteringIndex(String column, int minNgramLength, int maxNgramLength) {
+ _column = column;
Review Comment:
is _column being used?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2389573738
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/realtime/impl/invertedindex/RealtimeNgramFilteringIndex.java:
##########
@@ -0,0 +1,191 @@
+/**
+ * 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.pinot.segment.local.realtime.impl.invertedindex;
+
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import org.apache.lucene.analysis.ngram.NGramTokenizer;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.pinot.segment.spi.index.mutable.MutableTextIndex;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * RealtimeNgramFilteringIndex is a mutable inverted index that supports adding document IDs for n-grams. An n-gram
+ * is a contiguous sequence of n characters from input text. The length of the n-gram is variable between
+ * [minNgramLength, maxNgramLength] as specified in the index config. Internally, it uses a realtime inverted index
+ * which maps n-grams to their posting lists (document IDs). The index is thread-safe for single writer and multiple
+ * readers.
+ */
+public class RealtimeNgramFilteringIndex implements MutableTextIndex {
+ private final String _column;
+ // Under the hood, ngram index is implemented as an inverted index from n-grams to their posting lists.
+ private final RealtimeInvertedIndex _invertedIndex;
+ // A mapping from n-grams to their dictionary IDs.
+ private final Object2IntOpenHashMap<String> _ngramToDictIdMapping;
+ // Read and write locks for thread safety.
+ private final ReentrantReadWriteLock.ReadLock _readLock;
+ private final ReentrantReadWriteLock.WriteLock _writeLock;
+
+ // Next document ID to be assigned.
+ private int _nextDocId = 0;
+ private int _nextDictId = 0;
+
+ private final int _minNgramLength;
+ private final int _maxNgramLength;
+
+ public RealtimeNgramFilteringIndex(String column, int minNgramLength, int maxNgramLength) {
+ _column = column;
+ _invertedIndex = new RealtimeInvertedIndex();
+ _ngramToDictIdMapping = new Object2IntOpenHashMap<>();
+ _minNgramLength = minNgramLength;
+ _maxNgramLength = maxNgramLength;
Review Comment:
Good point.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on PR #16364:
URL: https://github.com/apache/pinot/pull/16364#issuecomment-3085066282
Thanks. We have internal tests with Uber to test the PoC for ngram filtering index for metric tag data -- the result looks really good. The tradeoff between space and time is good for use case where string length is relative short (think of less than a few hundred bytes) and we control ngram parameters. Just like other index for Pinot, the use of this index is subject to application need and we will make sure we document this tradeoff.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "ankitsultana (via GitHub)" <gi...@apache.org>.
ankitsultana commented on PR #16364:
URL: https://github.com/apache/pinot/pull/16364#issuecomment-3120169420
> We aim for strict literal string match so it is case sensitive.
> We will support SQL's LIKE() function as mentioned in the issue. So there is no need to introduce a new UDF. It can be extended to support regex_like() in Pinot today too -- it just involves more regex parsing.
Pinot's LIKE is case insensitive so this is not possible. You can refer to #10609.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2389532185
##########
pinot-perf/src/main/java/org/apache/pinot/perf/BenchmarkNgramFilteringIndex.java:
##########
@@ -0,0 +1,100 @@
+/**
+ * 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.pinot.perf;
+
+import java.util.concurrent.TimeUnit;
+import org.apache.pinot.segment.local.realtime.impl.invertedindex.RealtimeNgramFilteringIndex;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+import org.openjdk.jmh.runner.Runner;
+import org.openjdk.jmh.runner.options.ChainedOptionsBuilder;
+import org.openjdk.jmh.runner.options.OptionsBuilder;
+import org.roaringbitmap.IntIterator;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * This benchmark is a benchmark for testing the performance of N-gram filtering index vs a pure regex matcher
+ */
+@OutputTimeUnit(TimeUnit.MILLISECONDS)
+@Fork(1)
+@Warmup(iterations = 1)
+@Measurement(iterations = 2)
+@State(Scope.Benchmark)
+public class BenchmarkNgramFilteringIndex {
+ public static final String PREFIX = "somelonglongveryverylongword";
+ RealtimeNgramFilteringIndex _realtimeNgramFilteringIndex;
+
+ public static void main(String[] args)
+ throws Exception {
+ ChainedOptionsBuilder opt = new OptionsBuilder().include(BenchmarkNgramFilteringIndex.class.getSimpleName());
+ new Runner(opt.build()).run();
+ }
+
+ @Setup(Level.Trial)
+ public void setUp()
+ throws Exception {
+ _realtimeNgramFilteringIndex = new RealtimeNgramFilteringIndex("col", 2, 3);
+ // Load the index with 10000 words
+ for (int i = 0; i < 10000; i++) {
+ _realtimeNgramFilteringIndex.add(PREFIX + i);
+ }
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.All)
+ @OutputTimeUnit(TimeUnit.MILLISECONDS)
+ public int benchmarkTextMatchingUsingNgram() {
+ // First retrieve the docIds using the N-gram index
+ MutableRoaringBitmap map = _realtimeNgramFilteringIndex.getDocIds("ord78");
+ IntIterator intIterator = map.getIntIterator();
+ // Next doing regex matching on the docIds to validate the results
+ while (intIterator.hasNext()) {
+ int docId = intIterator.next();
+ // Simulate regex validate on th
Review Comment:
completed the comments.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "deemoliu (via GitHub)" <gi...@apache.org>.
deemoliu commented on PR #16364:
URL: https://github.com/apache/pinot/pull/16364#issuecomment-3110193826
> Do you have a sample query? I had the same concern as @ankitsultana - this can explode the index. I thought its better to have FST on the tokens/dictionary and use that to find matching dictionary ids
I think it depends on which N we planned to use and what's the size of the column. Based on use cases, usually we used 2grams, 3grams.
Last year we did a benchmark on Tag matching using a derived column of 3-grams with inverted index to simulate this behavior.
For example. a tag value "dca1001" can generate 3-grams values like `dca`, `ca1`, `a10`, `100`, `001` which stored in a multi-value inverted index column called my_column_ngram.
For Query, if we match `REGEXP_LIKE(my_column, '.*dca.*')`
the regex query can be to `SELECT * FROM my_table WHERE my_column_ngram = 'dca'. The inverted indexes on my_column_ngram multi-value field is sufficient to return the query result.
if we match REGEXP_LIKE(my_column, '.*dca1.*'), we can do
`SELECT * FROM my_table WHERE my_column_ngram = 'dca' and my_column_ngram = 'ca1' and REGEXP_LIKE(my_column, '.*dca1.*'). The ngrams match using inverted index executed first, pre-filtered rows to accelerate the query performance for regex matching.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2389572722
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/realtime/impl/invertedindex/RealtimeNgramFilteringIndex.java:
##########
@@ -0,0 +1,191 @@
+/**
+ * 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.pinot.segment.local.realtime.impl.invertedindex;
+
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import org.apache.lucene.analysis.ngram.NGramTokenizer;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.pinot.segment.spi.index.mutable.MutableTextIndex;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * RealtimeNgramFilteringIndex is a mutable inverted index that supports adding document IDs for n-grams. An n-gram
+ * is a contiguous sequence of n characters from input text. The length of the n-gram is variable between
+ * [minNgramLength, maxNgramLength] as specified in the index config. Internally, it uses a realtime inverted index
+ * which maps n-grams to their posting lists (document IDs). The index is thread-safe for single writer and multiple
+ * readers.
+ */
+public class RealtimeNgramFilteringIndex implements MutableTextIndex {
+ private final String _column;
+ // Under the hood, ngram index is implemented as an inverted index from n-grams to their posting lists.
+ private final RealtimeInvertedIndex _invertedIndex;
+ // A mapping from n-grams to their dictionary IDs.
+ private final Object2IntOpenHashMap<String> _ngramToDictIdMapping;
+ // Read and write locks for thread safety.
+ private final ReentrantReadWriteLock.ReadLock _readLock;
+ private final ReentrantReadWriteLock.WriteLock _writeLock;
+
+ // Next document ID to be assigned.
+ private int _nextDocId = 0;
+ private int _nextDictId = 0;
+
+ private final int _minNgramLength;
+ private final int _maxNgramLength;
+
+ public RealtimeNgramFilteringIndex(String column, int minNgramLength, int maxNgramLength) {
+ _column = column;
+ _invertedIndex = new RealtimeInvertedIndex();
+ _ngramToDictIdMapping = new Object2IntOpenHashMap<>();
Review Comment:
Good point. It is undefined now. It is better to be explicit. Added.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2389574776
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/realtime/impl/invertedindex/RealtimeNgramFilteringIndex.java:
##########
@@ -0,0 +1,191 @@
+/**
+ * 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.pinot.segment.local.realtime.impl.invertedindex;
+
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import org.apache.lucene.analysis.ngram.NGramTokenizer;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.pinot.segment.spi.index.mutable.MutableTextIndex;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * RealtimeNgramFilteringIndex is a mutable inverted index that supports adding document IDs for n-grams. An n-gram
+ * is a contiguous sequence of n characters from input text. The length of the n-gram is variable between
+ * [minNgramLength, maxNgramLength] as specified in the index config. Internally, it uses a realtime inverted index
+ * which maps n-grams to their posting lists (document IDs). The index is thread-safe for single writer and multiple
+ * readers.
+ */
+public class RealtimeNgramFilteringIndex implements MutableTextIndex {
+ private final String _column;
+ // Under the hood, ngram index is implemented as an inverted index from n-grams to their posting lists.
+ private final RealtimeInvertedIndex _invertedIndex;
+ // A mapping from n-grams to their dictionary IDs.
+ private final Object2IntOpenHashMap<String> _ngramToDictIdMapping;
+ // Read and write locks for thread safety.
+ private final ReentrantReadWriteLock.ReadLock _readLock;
+ private final ReentrantReadWriteLock.WriteLock _writeLock;
+
+ // Next document ID to be assigned.
+ private int _nextDocId = 0;
+ private int _nextDictId = 0;
+
+ private final int _minNgramLength;
+ private final int _maxNgramLength;
+
+ public RealtimeNgramFilteringIndex(String column, int minNgramLength, int maxNgramLength) {
+ _column = column;
+ _invertedIndex = new RealtimeInvertedIndex();
+ _ngramToDictIdMapping = new Object2IntOpenHashMap<>();
+ _minNgramLength = minNgramLength;
+ _maxNgramLength = maxNgramLength;
+
+ ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
+ _readLock = readWriteLock.readLock();
+ _writeLock = readWriteLock.writeLock();
+ }
+
+ /**
+ * Index the string value
+ *
+ * @param value the input value as a string
+ */
+ @Override
+ public void add(String value) {
+ if (value == null) {
+ return;
+ }
+ addHelper(value);
+ _nextDocId++;
+ }
+
+ /**
+ * Index an array of string values. Each string in the array is treated as a separate document.
+ *
+ * @param values the documents as an array of strings
+ */
+ @Override
+ public void add(String[] values) {
+ if (values == null || values.length == 0) {
+ return;
+ }
+ for (String value : values) {
+ if (value != null) {
+ addHelper(value);
+ }
+ }
+ _nextDocId++;
+ }
+
+ /**
+ * Returns the matching dictionary ids for the given search query (optional).
+ *
+ * @param searchQuery as a literal string
+ */
+ @Override
+ public ImmutableRoaringBitmap getDictIds(String searchQuery) {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * Returns the matching document ids for the given search query.
+ * Returns null if no n-grams are generated from the search query -- either because the search query is null or empty
+ * or shorter than the minimum n-gram length.
+ * @param searchQuery as a literal string
+ */
+ @Override
+ public MutableRoaringBitmap getDocIds(String searchQuery) {
+ _readLock.lock();
+ Iterable<String> ngrams = generateNgrams(searchQuery);
+ if (!ngrams.iterator().hasNext()) {
+ return null; // No n-grams generated, return null.
+ }
+ ArrayList<MutableRoaringBitmap> bitmapLst = new ArrayList<>();
+ try {
+ for (String ngram : ngrams) {
+ int dictId = _ngramToDictIdMapping.getInt(ngram);
+ bitmapLst.add(_invertedIndex.getDocIds(dictId));
+ }
+ if (bitmapLst.isEmpty()) {
+ return null; // No n-grams found in the index.
+ }
+ MutableRoaringBitmap resultBitmap = bitmapLst.get(0);
+ for (int i = 1; i < bitmapLst.size(); i++) {
+ resultBitmap.and(bitmapLst.get(i));
+ }
+ return resultBitmap;
+ } finally {
+ _readLock.unlock();
+ }
+ }
+
+ /**
+ * Closes this stream and releases any system resources associated with it. If the stream is already closed then
+ * invoking this method has no effect.
+ *
+ * <p> As noted in {@link AutoCloseable#close()}, cases where the
+ * close may fail require careful attention. It is strongly advised to relinquish the underlying resources and to
+ * internally
+ * <em>mark</em> the {@code Closeable} as closed, prior to throwing
+ * the {@code IOException}.
+ *
+ * @throws IOException if an I/O error occurs
+ */
+ @Override
+ public void close()
+ throws IOException {
Review Comment:
done.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #16364:
URL: https://github.com/apache/pinot/pull/16364#issuecomment-3085570473
## [Codecov](https://app.codecov.io/gh/apache/pinot/pull/16364?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
Attention: Patch coverage is `0%` with `59 lines` in your changes missing coverage. Please review.
> Project coverage is 56.37%. Comparing base [(`1a476de`)](https://app.codecov.io/gh/apache/pinot/commit/1a476dea72ebf1c15e14ded28ae60c385f71b2c3?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) to head [(`04bb638`)](https://app.codecov.io/gh/apache/pinot/commit/04bb638c6b028da21cd8328cd572232aa85ff372?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
> Report is 464 commits behind head on master.
| [Files with missing lines](https://app.codecov.io/gh/apache/pinot/pull/16364?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [...mpl/invertedindex/RealtimeNgramFilteringIndex.java](https://app.codecov.io/gh/apache/pinot/pull/16364?src=pr&el=tree&filepath=pinot-segment-local%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fpinot%2Fsegment%2Flocal%2Frealtime%2Fimpl%2Finvertedindex%2FRealtimeNgramFilteringIndex.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cGlub3Qtc2VnbWVudC1sb2NhbC9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3Qvc2VnbWVudC9sb2NhbC9yZWFsdGltZS9pbXBsL2ludmVydGVkaW5kZXgvUmVhbHRpbWVOZ3JhbUZpbHRlcmluZ0luZGV4LmphdmE=) | 0.00% | [59 Missing :warning: ](https://app.codecov.io/gh/apache/pinot/pull/16364?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
> :exclamation: There is a different number of reports uploaded between BASE (1a476de) and HEAD (04bb638). Click for more details.
>
> <details><summary>HEAD has 68 uploads less than BASE</summary>
>
>| Flag | BASE (1a476de) | HEAD (04bb638) |
>|------|------|------|
>|java-21|10|1|
>|unittests|6|1|
>|unittests1|3|1|
>|skip-bytebuffers-true|4|0|
>|temurin|15|1|
>|unittests2|3|0|
>|skip-bytebuffers-false|8|0|
>|java-11|5|0|
>|integration|9|0|
>|integration2|3|0|
>|integration1|3|0|
>|custom-integration1|3|0|
></details>
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## master #16364 +/- ##
============================================
- Coverage 62.90% 56.37% -6.54%
+ Complexity 1386 699 -687
============================================
Files 2867 2322 -545
Lines 163354 128396 -34958
Branches 24952 20445 -4507
============================================
- Hits 102755 72378 -30377
+ Misses 52847 50043 -2804
+ Partials 7752 5975 -1777
```
| [Flag](https://app.codecov.io/gh/apache/pinot/pull/16364/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Coverage Δ | |
|---|---|---|
| [custom-integration1](https://app.codecov.io/gh/apache/pinot/pull/16364/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [integration](https://app.codecov.io/gh/apache/pinot/pull/16364/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [integration1](https://app.codecov.io/gh/apache/pinot/pull/16364/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [integration2](https://app.codecov.io/gh/apache/pinot/pull/16364/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [java-11](https://app.codecov.io/gh/apache/pinot/pull/16364/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [java-21](https://app.codecov.io/gh/apache/pinot/pull/16364/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `56.37% <0.00%> (-6.46%)` | :arrow_down: |
| [skip-bytebuffers-false](https://app.codecov.io/gh/apache/pinot/pull/16364/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [skip-bytebuffers-true](https://app.codecov.io/gh/apache/pinot/pull/16364/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [temurin](https://app.codecov.io/gh/apache/pinot/pull/16364/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `56.37% <0.00%> (-6.54%)` | :arrow_down: |
| [unittests](https://app.codecov.io/gh/apache/pinot/pull/16364/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `56.37% <0.00%> (-6.53%)` | :arrow_down: |
| [unittests1](https://app.codecov.io/gh/apache/pinot/pull/16364/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `56.37% <0.00%> (+0.55%)` | :arrow_up: |
| [unittests2](https://app.codecov.io/gh/apache/pinot/pull/16364/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#carryforward-flags-in-the-pull-request-comment) to find out more.
</details>
[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/apache/pinot/pull/16364?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2289441991
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/realtime/impl/invertedindex/RealtimeNgramFilteringIndex.java:
##########
@@ -0,0 +1,188 @@
+/**
+ * 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.pinot.segment.local.realtime.impl.invertedindex;
+
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import org.apache.lucene.analysis.ngram.NGramTokenizer;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.pinot.segment.spi.index.mutable.MutableTextIndex;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * RealtimeNgramFilteringIndex is a mutable inverted index that supports adding document IDs for n-grams. An n-gram
+ * is a contiguous sequence of n characters from input text. The length of the n-gram is variable between
+ * [minNgramLength, maxNgramLength] as specified in the index config. Internally, it uses a realtime inverted index
+ * which maps n-grams to their posting lists (document IDs). The index is thread-safe for single writer and multiple
+ * readers.
+ */
+public class RealtimeNgramFilteringIndex implements MutableTextIndex {
Review Comment:
ngram index is primarily designed for index text data -- so as a sub-class of textindex interface is fine. The interface on add(String doc) is also appropriate for ngram index.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "deemoliu (via GitHub)" <gi...@apache.org>.
deemoliu commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2345321254
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/realtime/impl/invertedindex/RealtimeNgramFilteringIndex.java:
##########
@@ -0,0 +1,191 @@
+/**
+ * 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.pinot.segment.local.realtime.impl.invertedindex;
+
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import org.apache.lucene.analysis.ngram.NGramTokenizer;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.pinot.segment.spi.index.mutable.MutableTextIndex;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * RealtimeNgramFilteringIndex is a mutable inverted index that supports adding document IDs for n-grams. An n-gram
+ * is a contiguous sequence of n characters from input text. The length of the n-gram is variable between
+ * [minNgramLength, maxNgramLength] as specified in the index config. Internally, it uses a realtime inverted index
+ * which maps n-grams to their posting lists (document IDs). The index is thread-safe for single writer and multiple
+ * readers.
+ */
+public class RealtimeNgramFilteringIndex implements MutableTextIndex {
+ private final String _column;
+ // Under the hood, ngram index is implemented as an inverted index from n-grams to their posting lists.
+ private final RealtimeInvertedIndex _invertedIndex;
+ // A mapping from n-grams to their dictionary IDs.
+ private final Object2IntOpenHashMap<String> _ngramToDictIdMapping;
+ // Read and write locks for thread safety.
+ private final ReentrantReadWriteLock.ReadLock _readLock;
+ private final ReentrantReadWriteLock.WriteLock _writeLock;
+
+ // Next document ID to be assigned.
+ private int _nextDocId = 0;
+ private int _nextDictId = 0;
+
+ private final int _minNgramLength;
+ private final int _maxNgramLength;
+
+ public RealtimeNgramFilteringIndex(String column, int minNgramLength, int maxNgramLength) {
+ _column = column;
+ _invertedIndex = new RealtimeInvertedIndex();
+ _ngramToDictIdMapping = new Object2IntOpenHashMap<>();
Review Comment:
shall we handle not existing keys with default value?
_ngramToDictIdMapping.defaultReturnValue(-1);
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2389535429
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/realtime/impl/invertedindex/RealtimeNgramFilteringIndex.java:
##########
@@ -0,0 +1,191 @@
+/**
+ * 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.pinot.segment.local.realtime.impl.invertedindex;
+
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import org.apache.lucene.analysis.ngram.NGramTokenizer;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.pinot.segment.spi.index.mutable.MutableTextIndex;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * RealtimeNgramFilteringIndex is a mutable inverted index that supports adding document IDs for n-grams. An n-gram
+ * is a contiguous sequence of n characters from input text. The length of the n-gram is variable between
+ * [minNgramLength, maxNgramLength] as specified in the index config. Internally, it uses a realtime inverted index
+ * which maps n-grams to their posting lists (document IDs). The index is thread-safe for single writer and multiple
+ * readers.
+ */
+public class RealtimeNgramFilteringIndex implements MutableTextIndex {
+ private final String _column;
+ // Under the hood, ngram index is implemented as an inverted index from n-grams to their posting lists.
+ private final RealtimeInvertedIndex _invertedIndex;
+ // A mapping from n-grams to their dictionary IDs.
+ private final Object2IntOpenHashMap<String> _ngramToDictIdMapping;
+ // Read and write locks for thread safety.
+ private final ReentrantReadWriteLock.ReadLock _readLock;
+ private final ReentrantReadWriteLock.WriteLock _writeLock;
+
+ // Next document ID to be assigned.
+ private int _nextDocId = 0;
+ private int _nextDictId = 0;
+
+ private final int _minNgramLength;
+ private final int _maxNgramLength;
+
+ public RealtimeNgramFilteringIndex(String column, int minNgramLength, int maxNgramLength) {
+ _column = column;
Review Comment:
For now it is not used, but the following PR we can use this column name field. Put it for future proof.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "ankitsultana (via GitHub)" <gi...@apache.org>.
ankitsultana commented on PR #16364:
URL: https://github.com/apache/pinot/pull/16364#issuecomment-3084910778
@chenboat : great to see we are looking to add better support for n-gram indexes in Pinot. I had run an internal PoC on this a couple of years back with a similar approach and one of the main learnings was that the n-gram index size with an approach like this can get very high.
The issue is that this approach stores a bitmap for each unique n-gram. Even for a moderately high number of unique n-grams, since the corresponding bitmaps can be quite dense and are random, the cumulative size of all bitmaps can exceed 100s of MB per-segment very quickly (i.e. almost equal or much higher than rest of the segment size).
I left the PoC at the time because I thought we'll need to add several knobs to the index to support keeping only top n-grams when the size exceeds a certain threshold.
I wonder if you have run some experiments around this already?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2389533984
##########
pinot-perf/src/main/java/org/apache/pinot/perf/BenchmarkNgramFilteringIndex.java:
##########
@@ -0,0 +1,100 @@
+/**
+ * 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.pinot.perf;
+
+import java.util.concurrent.TimeUnit;
+import org.apache.pinot.segment.local.realtime.impl.invertedindex.RealtimeNgramFilteringIndex;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+import org.openjdk.jmh.runner.Runner;
+import org.openjdk.jmh.runner.options.ChainedOptionsBuilder;
+import org.openjdk.jmh.runner.options.OptionsBuilder;
+import org.roaringbitmap.IntIterator;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * This benchmark is a benchmark for testing the performance of N-gram filtering index vs a pure regex matcher
+ */
+@OutputTimeUnit(TimeUnit.MILLISECONDS)
+@Fork(1)
+@Warmup(iterations = 1)
+@Measurement(iterations = 2)
+@State(Scope.Benchmark)
+public class BenchmarkNgramFilteringIndex {
+ public static final String PREFIX = "somelonglongveryverylongword";
+ RealtimeNgramFilteringIndex _realtimeNgramFilteringIndex;
+
+ public static void main(String[] args)
+ throws Exception {
+ ChainedOptionsBuilder opt = new OptionsBuilder().include(BenchmarkNgramFilteringIndex.class.getSimpleName());
+ new Runner(opt.build()).run();
+ }
+
+ @Setup(Level.Trial)
+ public void setUp()
+ throws Exception {
+ _realtimeNgramFilteringIndex = new RealtimeNgramFilteringIndex("col", 2, 3);
+ // Load the index with 10000 words
+ for (int i = 0; i < 10000; i++) {
+ _realtimeNgramFilteringIndex.add(PREFIX + i);
+ }
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.All)
+ @OutputTimeUnit(TimeUnit.MILLISECONDS)
+ public int benchmarkTextMatchingUsingNgram() {
+ // First retrieve the docIds using the N-gram index
+ MutableRoaringBitmap map = _realtimeNgramFilteringIndex.getDocIds("ord78");
+ IntIterator intIterator = map.getIntIterator();
+ // Next doing regex matching on the docIds to validate the results
+ while (intIterator.hasNext()) {
+ int docId = intIterator.next();
+ // Simulate regex validate on th
+ (PREFIX + docId).matches(".*ord78.*");
+ }
+ return 0;
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.All)
+ @OutputTimeUnit(TimeUnit.MILLISECONDS)
+ public int benchmarkMatchingViaRegexScan() {
+ // Matching the documents using regex scan
+ for (int i = 0; i < 10000; i++) {
+ (PREFIX + i).matches(".*ord78.*");
+ }
+ return 0;
+ }
+
+ public void tearDown()
Review Comment:
Added.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "kishoreg (via GitHub)" <gi...@apache.org>.
kishoreg commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2226346834
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/realtime/impl/invertedindex/RealtimeNgramFilteringIndex.java:
##########
@@ -0,0 +1,188 @@
+/**
+ * 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.pinot.segment.local.realtime.impl.invertedindex;
+
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import org.apache.lucene.analysis.ngram.NGramTokenizer;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.pinot.segment.spi.index.mutable.MutableTextIndex;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * RealtimeNgramFilteringIndex is a mutable inverted index that supports adding document IDs for n-grams. An n-gram
+ * is a contiguous sequence of n characters from input text. The length of the n-gram is variable between
+ * [minNgramLength, maxNgramLength] as specified in the index config. Internally, it uses a realtime inverted index
+ * which maps n-grams to their posting lists (document IDs). The index is thread-safe for single writer and multiple
+ * readers.
+ */
+public class RealtimeNgramFilteringIndex implements MutableTextIndex {
+ private final String _column;
+ // Under the hood, ngram index is implemented as an inverted index from n-grams to their posting lists.
+ private final RealtimeInvertedIndex _invertedIndex;
+ // A mapping from n-grams to their dictionary IDs.
+ private final Object2IntOpenHashMap<String> _ngramToDictIdMapping;
+ // Read and write locks for thread safety.
+ private final ReentrantReadWriteLock.ReadLock _readLock;
+ private final ReentrantReadWriteLock.WriteLock _writeLock;
+
+ // Next document ID to be assigned.
+ private int _nextDocId = 0;
+ private int _nextDictId = 0;
+
+ private final int _minNgramLength;
+ private final int _maxNgramLength;
+
+ public RealtimeNgramFilteringIndex(String column, int minNgramLength, int maxNgramLength) {
+ _column = column;
+ _invertedIndex = new RealtimeInvertedIndex();
+ _ngramToDictIdMapping = new Object2IntOpenHashMap<>();
+ _minNgramLength = minNgramLength;
+ _maxNgramLength = maxNgramLength;
+
+ ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
+ _readLock = readWriteLock.readLock();
+ _writeLock = readWriteLock.writeLock();
+ }
+
+ /**
+ * Index the string value
+ *
+ * @param value the input value as a string
+ */
+ @Override
+ public void add(String value) {
+ if (value == null) {
+ return;
+ }
+ addHelper(value);
+ _nextDocId++;
+ }
+
+ /**
+ * Index an array of string values. Each string in the array is treated as a separate document.
+ *
+ * @param values the documents as an array of strings
+ */
+ @Override
+ public void add(String[] values) {
+ if (values == null || values.length == 0) {
+ return;
+ }
+ for (String value : values) {
+ if (value != null) {
+ addHelper(value);
+ }
+ }
+ _nextDocId++;
+ }
+
+ /**
+ * Returns the matching dictionary ids for the given search query (optional).
+ *
+ * @param searchQuery as a literal string
+ */
+ @Override
+ public ImmutableRoaringBitmap getDictIds(String searchQuery) {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * Returns the matching document ids for the given search query.
+ * Returns null if no n-grams are generated from the search query -- either because the search query is null or empty
+ * or shorter than the minimum n-gram length.
+ * @param searchQuery as a literal string
+ */
+ @Override
+ public MutableRoaringBitmap getDocIds(String searchQuery) {
+ _readLock.lock();
+ Iterable<String> ngrams = generateNgrams(searchQuery);
+ if (!ngrams.iterator().hasNext()) {
+ return null; // No n-grams generated, return null.
+ }
+ MutableRoaringBitmap resultBitmap = null;
+ try {
+ for (String ngram : ngrams) {
Review Comment:
better to collect all bitmaps and do AND at the end..
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "deemoliu (via GitHub)" <gi...@apache.org>.
deemoliu commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2345317039
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/realtime/impl/invertedindex/RealtimeNgramFilteringIndex.java:
##########
@@ -0,0 +1,191 @@
+/**
+ * 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.pinot.segment.local.realtime.impl.invertedindex;
+
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import org.apache.lucene.analysis.ngram.NGramTokenizer;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.pinot.segment.spi.index.mutable.MutableTextIndex;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * RealtimeNgramFilteringIndex is a mutable inverted index that supports adding document IDs for n-grams. An n-gram
+ * is a contiguous sequence of n characters from input text. The length of the n-gram is variable between
+ * [minNgramLength, maxNgramLength] as specified in the index config. Internally, it uses a realtime inverted index
+ * which maps n-grams to their posting lists (document IDs). The index is thread-safe for single writer and multiple
+ * readers.
+ */
+public class RealtimeNgramFilteringIndex implements MutableTextIndex {
+ private final String _column;
+ // Under the hood, ngram index is implemented as an inverted index from n-grams to their posting lists.
+ private final RealtimeInvertedIndex _invertedIndex;
+ // A mapping from n-grams to their dictionary IDs.
+ private final Object2IntOpenHashMap<String> _ngramToDictIdMapping;
+ // Read and write locks for thread safety.
+ private final ReentrantReadWriteLock.ReadLock _readLock;
+ private final ReentrantReadWriteLock.WriteLock _writeLock;
+
+ // Next document ID to be assigned.
+ private int _nextDocId = 0;
+ private int _nextDictId = 0;
+
+ private final int _minNgramLength;
+ private final int _maxNgramLength;
+
+ public RealtimeNgramFilteringIndex(String column, int minNgramLength, int maxNgramLength) {
+ _column = column;
+ _invertedIndex = new RealtimeInvertedIndex();
+ _ngramToDictIdMapping = new Object2IntOpenHashMap<>();
+ _minNgramLength = minNgramLength;
+ _maxNgramLength = maxNgramLength;
Review Comment:
shall we add something like
```
if (minNgramLength <= 0 || maxNgramLength <= 0 || minNgramLength > maxNgramLength) {
throw new IllegalArgumentException("Invalid n-gram settings: " + minNgramLength + "..." + maxNgramLength);
}
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "deemoliu (via GitHub)" <gi...@apache.org>.
deemoliu commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2345194231
##########
pinot-perf/src/main/java/org/apache/pinot/perf/BenchmarkNgramFilteringIndex.java:
##########
@@ -0,0 +1,100 @@
+/**
+ * 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.pinot.perf;
+
+import java.util.concurrent.TimeUnit;
+import org.apache.pinot.segment.local.realtime.impl.invertedindex.RealtimeNgramFilteringIndex;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+import org.openjdk.jmh.runner.Runner;
+import org.openjdk.jmh.runner.options.ChainedOptionsBuilder;
+import org.openjdk.jmh.runner.options.OptionsBuilder;
+import org.roaringbitmap.IntIterator;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * This benchmark is a benchmark for testing the performance of N-gram filtering index vs a pure regex matcher
+ */
+@OutputTimeUnit(TimeUnit.MILLISECONDS)
+@Fork(1)
+@Warmup(iterations = 1)
+@Measurement(iterations = 2)
+@State(Scope.Benchmark)
+public class BenchmarkNgramFilteringIndex {
+ public static final String PREFIX = "somelonglongveryverylongword";
+ RealtimeNgramFilteringIndex _realtimeNgramFilteringIndex;
+
+ public static void main(String[] args)
+ throws Exception {
+ ChainedOptionsBuilder opt = new OptionsBuilder().include(BenchmarkNgramFilteringIndex.class.getSimpleName());
+ new Runner(opt.build()).run();
+ }
+
+ @Setup(Level.Trial)
+ public void setUp()
+ throws Exception {
+ _realtimeNgramFilteringIndex = new RealtimeNgramFilteringIndex("col", 2, 3);
+ // Load the index with 10000 words
+ for (int i = 0; i < 10000; i++) {
+ _realtimeNgramFilteringIndex.add(PREFIX + i);
+ }
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.All)
+ @OutputTimeUnit(TimeUnit.MILLISECONDS)
+ public int benchmarkTextMatchingUsingNgram() {
+ // First retrieve the docIds using the N-gram index
+ MutableRoaringBitmap map = _realtimeNgramFilteringIndex.getDocIds("ord78");
+ IntIterator intIterator = map.getIntIterator();
+ // Next doing regex matching on the docIds to validate the results
+ while (intIterator.hasNext()) {
+ int docId = intIterator.next();
+ // Simulate regex validate on th
+ (PREFIX + docId).matches(".*ord78.*");
+ }
+ return 0;
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.All)
+ @OutputTimeUnit(TimeUnit.MILLISECONDS)
+ public int benchmarkMatchingViaRegexScan() {
+ // Matching the documents using regex scan
+ for (int i = 0; i < 10000; i++) {
+ (PREFIX + i).matches(".*ord78.*");
+ }
+ return 0;
+ }
+
+ public void tearDown()
Review Comment:
should this function be annotated?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "deemoliu (via GitHub)" <gi...@apache.org>.
deemoliu commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2345192301
##########
pinot-perf/src/main/java/org/apache/pinot/perf/BenchmarkNgramFilteringIndex.java:
##########
@@ -0,0 +1,100 @@
+/**
+ * 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.pinot.perf;
+
+import java.util.concurrent.TimeUnit;
+import org.apache.pinot.segment.local.realtime.impl.invertedindex.RealtimeNgramFilteringIndex;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+import org.openjdk.jmh.runner.Runner;
+import org.openjdk.jmh.runner.options.ChainedOptionsBuilder;
+import org.openjdk.jmh.runner.options.OptionsBuilder;
+import org.roaringbitmap.IntIterator;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * This benchmark is a benchmark for testing the performance of N-gram filtering index vs a pure regex matcher
+ */
+@OutputTimeUnit(TimeUnit.MILLISECONDS)
+@Fork(1)
+@Warmup(iterations = 1)
+@Measurement(iterations = 2)
+@State(Scope.Benchmark)
+public class BenchmarkNgramFilteringIndex {
+ public static final String PREFIX = "somelonglongveryverylongword";
+ RealtimeNgramFilteringIndex _realtimeNgramFilteringIndex;
+
+ public static void main(String[] args)
+ throws Exception {
+ ChainedOptionsBuilder opt = new OptionsBuilder().include(BenchmarkNgramFilteringIndex.class.getSimpleName());
+ new Runner(opt.build()).run();
+ }
+
+ @Setup(Level.Trial)
+ public void setUp()
+ throws Exception {
+ _realtimeNgramFilteringIndex = new RealtimeNgramFilteringIndex("col", 2, 3);
+ // Load the index with 10000 words
+ for (int i = 0; i < 10000; i++) {
+ _realtimeNgramFilteringIndex.add(PREFIX + i);
+ }
+ }
+
+ @Benchmark
+ @BenchmarkMode(Mode.All)
+ @OutputTimeUnit(TimeUnit.MILLISECONDS)
+ public int benchmarkTextMatchingUsingNgram() {
+ // First retrieve the docIds using the N-gram index
+ MutableRoaringBitmap map = _realtimeNgramFilteringIndex.getDocIds("ord78");
+ IntIterator intIterator = map.getIntIterator();
+ // Next doing regex matching on the docIds to validate the results
+ while (intIterator.hasNext()) {
+ int docId = intIterator.next();
+ // Simulate regex validate on th
Review Comment:
nit: what does th means.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on PR #16364:
URL: https://github.com/apache/pinot/pull/16364#issuecomment-3119985002
> In #16294, ES and StarRocks are mentioned but they use n-gram in a very different way. ES/Lucene use n-grams for tokenization and they still rely on a FST (afaik). StarRocks stores the n-grams into a bloom filter and doesn't explicitly track each of them separately based on their documentation: https://docs.starrocks.io/docs/table_design/indexes/Ngram_Bloom_Filter_Index/
The issue cited two peer libs uses of n-gram index and advocate Pinot to adopt ngram index too. The goal is not to follow their implementations.
>
> I don't see much details in #16294. Just some example questions that need more color:
>
> * Will this work for both raw encoded columns and dict-encoded columns?
Ngram filtering in our proposed work on string column. Since the implementation uses Pinot's inverted index internally, there is dictionary for ngrams. The raw string will be retained for final validation. It can be raw encoded or dict-encoded.
> * How are we going to handle case sensitivity? Are we going to allow case insensitive matching too?
We aim for strict literal string match so it is case sensitive.
> * What's the UDF for queries going to look like. I suppose something like `ngram_substring_search(colName, 'xyzabc')`?
We will support SQL's LIKE() function as mentioned in the issue first. So there is no need to introduce a new UDF. It can be extended to support regex_like() in Pinot later.
> * What are some concrete numbers around n-gram size and nature of data. e.g. would this scale for brand names from say a Grocery catalog? Outside of metric tag values, what are some other use-cases where we can use this index?
Our internal test can work on multiple terabytes of data with recommended ngram length of 3 to 4 support 4-5k qps. Another example is that google [code search use trigram](https://swtch.com/~rsc/regexp/regexp4.html) to code search which reported similar founding to ours -- their report is about 20% of index vs raw data ratio. The above paper also gives a good summary of applicability: i.e., _ngram filtering is good for indexing large number of short documents_. Short can be interpreted in the range of ~100bytes in our test case.
> * If a user has a Regex based use-case, will we need to ask them to add n_gram predicates in their query? Russ Cox's approach is to automatically generate n-grams from a user specified Regex pattern.
Our approach is the same as Cox's approach. Given a LIKE('%pinot%') function, we can parse it can generate the ngrams to perform the filtering.
> * Should we consider taking inspiration from StarRocks and combine n-grams with bloom filters? e.g. one idea could be that within a segment we could store a configurable number of bloom-filters built on n-grams, and during search we can try to match all n-grams of the input string against each of the bloom filters. This could allow us to prune parts of a segment and can also ensure that the size of the index remains manageable.
That can be a further improvement and test needs to be done -- ngram filtering in segment level may or may not be effective due to distribution of ngram in large number of strings in aggregate. Our version of n-gram filtering work more like a Pinot inverted index -- so we take Russ Cox route you can say (thanks @ankitsultana for the reference :)).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat merged PR #16364:
URL: https://github.com/apache/pinot/pull/16364
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "deemoliu (via GitHub)" <gi...@apache.org>.
deemoliu commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2224006824
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/realtime/impl/invertedindex/RealtimeNgramFilteringIndex.java:
##########
@@ -0,0 +1,188 @@
+/**
+ * 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.pinot.segment.local.realtime.impl.invertedindex;
+
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import org.apache.lucene.analysis.ngram.NGramTokenizer;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.pinot.segment.spi.index.mutable.MutableTextIndex;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * RealtimeNgramFilteringIndex is a mutable inverted index that supports adding document IDs for n-grams. An n-gram
+ * is a contiguous sequence of n characters from input text. The length of the n-gram is variable between
+ * [minNgramLength, maxNgramLength] as specified in the index config. Internally, it uses a realtime inverted index
+ * which maps n-grams to their posting lists (document IDs). The index is thread-safe for single writer and multiple
+ * readers.
+ */
+public class RealtimeNgramFilteringIndex implements MutableTextIndex {
Review Comment:
should we implements MutableInvertedIndex instead of MutableTextIndex?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on PR #16364:
URL: https://github.com/apache/pinot/pull/16364#issuecomment-3111519330
In the test @deemoliu mentioned above, we try to do regex (mostly wildcard) over a corpus of metric tags for time series data. Each time-series point usually has about around 7 tag/value pairs. We model them as multiple value columns. We find ngram length of 3 is really good tradeoff between space and search speed-up. As mentioned above, most of the user queries are relatively short wildcard search like (*dca*, *dca11*). Ngram index with our inverted index implementation did not result in storage space explosion (because the number of unique 3-grams are actually fairly limited) and search performance is 10x better than Lucene based FST term text index.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "ankitsultana (via GitHub)" <gi...@apache.org>.
ankitsultana commented on PR #16364:
URL: https://github.com/apache/pinot/pull/16364#issuecomment-3114110642
@chenboat @deemoliu : is there a design doc for this? There's quite a lot that can be done with n-grams so it might be best to dive deeper here. (e.g. we can use n-grams to optimize regex queries based on Russ Cox's approach).
Also regarding index size explosion, we can also discuss how we will prevent this in production and what kind of knobs/configs we will support. e.g.
* Would we add limits on max number of unique grams that we will track? Would we allow users to configure in the table-config specific gram combinations that they want to force to be tracked, etc.?
* Should we consider adopting a sparse gram approach like the one used by GitHub in their code-search implementation?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "ankitsultana (via GitHub)" <gi...@apache.org>.
ankitsultana commented on PR #16364:
URL: https://github.com/apache/pinot/pull/16364#issuecomment-3114553908
In #16294, ES and StarRocks are mentioned but they use n-gram in a very different way. ES/Lucene use n-grams for tokenization and they still rely on a FST (afaik). StarRocks stores the n-grams into a bloom filter and doesn't explicitly track each of them separately based on their documentation: https://docs.starrocks.io/docs/table_design/indexes/Ngram_Bloom_Filter_Index/
I don't see much details in #16294. Just some example questions that need more color:
* Will this work for both raw encoded columns and dict-encoded columns?
* How are we going to handle case sensitivity? Are we going to allow case insensitive matching too?
* What's the UDF for queries going to look like. I suppose something like `ngram_substring_search(colName, 'xyzabc')`?
* What are some concrete numbers around n-gram size and nature of data. e.g. would this scale for brand names from say a Grocery catalog? Outside of metric tag values, what are some other use-cases where we can use this index?
* If a user has a Regex based use-case, will we need to ask them to add n_gram predicates in their query? Russ Cox's approach is to automatically generate n-grams from a user specified Regex pattern.
* Should we consider taking inspiration from StarRocks and combine n-grams with bloom filters? e.g. one idea could be that within a segment we could store a configurable number of bloom-filters built on n-grams, and during search we can try to match all n-grams of the input string against each of the bloom filters. This could allow us to prune parts of a segment and can also ensure that the size of the index remains manageable.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on PR #16364:
URL: https://github.com/apache/pinot/pull/16364#issuecomment-3120494731
> > We will support SQL's LIKE() function as mentioned in the issue. So there is no need to introduce a new UDF. It can be extended to support regex_like() in Pinot today too -- it just involves more regex parsing.
>
> Pinot's LIKE is case insensitive so this is not possible. You can refer to #10609.
Thanks for the link to this discussion. To support case insensitive matching, we can during index time lower case all the ngrams (it may save a bit of ngrams here) and then during query time lower case all query strings too. Then we can support the current Pinot LIKE() case insensitive behavior. This is the preferred solution. There is also a query time expansion approach (i.e, *ab* becomes *(AB|ab|Ab|aB)* but it is too many combinations for long strings. Also
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "deemoliu (via GitHub)" <gi...@apache.org>.
deemoliu commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2226705870
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/realtime/impl/invertedindex/RealtimeNgramFilteringIndex.java:
##########
@@ -0,0 +1,188 @@
+/**
+ * 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.pinot.segment.local.realtime.impl.invertedindex;
+
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import org.apache.lucene.analysis.ngram.NGramTokenizer;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.pinot.segment.spi.index.mutable.MutableTextIndex;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * RealtimeNgramFilteringIndex is a mutable inverted index that supports adding document IDs for n-grams. An n-gram
+ * is a contiguous sequence of n characters from input text. The length of the n-gram is variable between
+ * [minNgramLength, maxNgramLength] as specified in the index config. Internally, it uses a realtime inverted index
+ * which maps n-grams to their posting lists (document IDs). The index is thread-safe for single writer and multiple
+ * readers.
+ */
+public class RealtimeNgramFilteringIndex implements MutableTextIndex {
Review Comment:
shall we add another interface if needed? i feel it's inferring ngram index is one subcategory of text index.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "deemoliu (via GitHub)" <gi...@apache.org>.
deemoliu commented on code in PR #16364:
URL: https://github.com/apache/pinot/pull/16364#discussion_r2392946417
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/realtime/impl/invertedindex/RealtimeNgramFilteringIndex.java:
##########
@@ -0,0 +1,191 @@
+/**
+ * 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.pinot.segment.local.realtime.impl.invertedindex;
+
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import org.apache.lucene.analysis.ngram.NGramTokenizer;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.pinot.segment.spi.index.mutable.MutableTextIndex;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+
+
+/**
+ * RealtimeNgramFilteringIndex is a mutable inverted index that supports adding document IDs for n-grams. An n-gram
+ * is a contiguous sequence of n characters from input text. The length of the n-gram is variable between
+ * [minNgramLength, maxNgramLength] as specified in the index config. Internally, it uses a realtime inverted index
+ * which maps n-grams to their posting lists (document IDs). The index is thread-safe for single writer and multiple
+ * readers.
+ */
+public class RealtimeNgramFilteringIndex implements MutableTextIndex {
+ private final String _column;
+ // Under the hood, ngram index is implemented as an inverted index from n-grams to their posting lists.
+ private final RealtimeInvertedIndex _invertedIndex;
+ // A mapping from n-grams to their dictionary IDs.
+ private final Object2IntOpenHashMap<String> _ngramToDictIdMapping;
+ // Read and write locks for thread safety.
+ private final ReentrantReadWriteLock.ReadLock _readLock;
+ private final ReentrantReadWriteLock.WriteLock _writeLock;
+
+ // Next document ID to be assigned.
+ private int _nextDocId = 0;
+ private int _nextDictId = 0;
+
+ private final int _minNgramLength;
+ private final int _maxNgramLength;
+
+ public RealtimeNgramFilteringIndex(String column, int minNgramLength, int maxNgramLength) {
+ _column = column;
Review Comment:
gotcha, thanks!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] [ngram index part 1]Add realtime ngram filtering index and benchmark results. [pinot]
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on PR #16364:
URL: https://github.com/apache/pinot/pull/16364#issuecomment-3238553118
@ankitsultana @kishoreg any comment on this PR or the design doc?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org