[CalendarServer-changes] [10746] CalendarServer/trunk/twext/who
source_changes at macosforge.org
source_changes at macosforge.org
Fri Feb 15 14:49:55 PST 2013
Revision: 10746
http://trac.calendarserver.org//changeset/10746
Author: wsanchez at apple.com
Date: 2013-02-15 14:49:55 -0800 (Fri, 15 Feb 2013)
Log Message:
-----------
Implement unindexed search.
Optimize search where multiple expressions are composed with AND by
passing the result from the prior expression into the next one,
thereby reducing the number of records being searched through.
Modified Paths:
--------------
CalendarServer/trunk/twext/who/directory.py
CalendarServer/trunk/twext/who/test/test_xml.py
CalendarServer/trunk/twext/who/xml.py
Modified: CalendarServer/trunk/twext/who/directory.py
===================================================================
--- CalendarServer/trunk/twext/who/directory.py 2013-02-15 22:45:11 UTC (rev 10745)
+++ CalendarServer/trunk/twext/who/directory.py 2013-02-15 22:49:55 UTC (rev 10746)
@@ -79,11 +79,14 @@
return succeed(self.recordType.iterconstants())
- def recordsFromExpression(self, expression):
+ def recordsFromExpression(self, expression, records=None):
"""
Finds records matching a single expression.
@param expression: an expression
@type expression: L{object}
+ @param records: a set of records to search within. C{None} if
+ the whole directory should be searched.
+ @type records: L{set} or L{frozenset}
"""
return fail(QueryNotSupportedError("Unknown expression: %s" % (expression,)))
@@ -100,12 +103,19 @@
results = set((yield self.recordsFromExpression(expression)))
for expression in expressions:
- if (operand == Operand.AND and not results):
- # No need to bother continuing here
- returnValue(())
+ if operand == Operand.AND:
+ if not results:
+ # No need to bother continuing here
+ returnValue(())
- recordsMatchingExpression = frozenset((yield self.recordsFromExpression(expression)))
+ records = results
+ else:
+ records = None
+ recordsMatchingExpression = frozenset((
+ yield self.recordsFromExpression(expression, records=records)
+ ))
+
if operand == Operand.AND:
results &= recordsMatchingExpression
elif operand == Operand.OR:
Modified: CalendarServer/trunk/twext/who/test/test_xml.py
===================================================================
--- CalendarServer/trunk/twext/who/test/test_xml.py 2013-02-15 22:45:11 UTC (rev 10745)
+++ CalendarServer/trunk/twext/who/test/test_xml.py 2013-02-15 22:49:55 UTC (rev 10746)
@@ -392,9 +392,7 @@
)
self.assertRecords(records, ("__sagen__",))
- test_queryNotNoIndex.todo = "Not implemented."
-
@inlineCallbacks
def test_queryCaseInsensitive(self):
service = self._testService()
@@ -408,13 +406,11 @@
def test_queryCaseInsensitiveNoIndex(self):
service = self._testService()
records = yield service.recordsFromQuery((
- service.query("fullNames", "moRG", flags=QueryFlags.caseInsensitive),
+ service.query("fullNames", "moRGen SAGen", flags=QueryFlags.caseInsensitive),
))
self.assertRecords(records, ("__sagen__",))
- test_queryCaseInsensitiveNoIndex.todo = "Not implemented."
-
@inlineCallbacks
def test_queryStartsWith(self):
service = self._testService()
@@ -432,9 +428,7 @@
))
self.assertRecords(records, ("__wsanchez__",))
- test_queryStartsWithNoIndex.todo = "Not implemented."
-
@inlineCallbacks
def test_queryStartsWithNot(self):
service = self._testService()
@@ -508,11 +502,24 @@
flags = QueryFlags.NOT,
),
))
- self.assertRecords(records, ("__wsanchez__",))
+ self.assertRecords(
+ records,
+ (
+ '__alyssa__',
+ '__calendar-dev__',
+ '__cdaboo__',
+ '__developers__',
+ '__dre__',
+ '__dreid__',
+ '__exarkun__',
+ '__glyph__',
+ '__joe__',
+ '__sagen__',
+ '__twisted__',
+ ),
+ )
- test_queryStartsWithNotNoIndex.todo = "Not implemented."
-
@inlineCallbacks
def test_queryStartsWithCaseInsensitive(self):
service = self._testService()
@@ -538,9 +545,7 @@
))
self.assertRecords(records, ("__wsanchez__",))
- test_queryStartsWithCaseInsensitiveNoIndex.todo = "Not implemented."
-
@inlineCallbacks
def test_queryContains(self):
service = self._testService()
@@ -558,9 +563,7 @@
))
self.assertRecords(records, ("__wsanchez__",))
- test_queryContainsNoIndex.todo = "Not implemented."
-
@inlineCallbacks
def test_queryContainsNot(self):
service = self._testService()
@@ -616,9 +619,7 @@
),
)
- test_queryContainsNotNoIndex.todo = "Not implemented."
-
@inlineCallbacks
def test_queryContainsCaseInsensitive(self):
service = self._testService()
@@ -644,9 +645,7 @@
))
self.assertRecords(records, ("__wsanchez__",))
- test_queryContainsCaseInsensitiveNoIndex.todo = "Not implemented."
-
def test_unknownRecordTypesClean(self):
service = self._testService()
self.assertEquals(set(service.unknownRecordTypes), set())
Modified: CalendarServer/trunk/twext/who/xml.py
===================================================================
--- CalendarServer/trunk/twext/who/xml.py 2013-02-15 22:45:11 UTC (rev 10745)
+++ CalendarServer/trunk/twext/who/xml.py 2013-02-15 22:49:55 UTC (rev 10746)
@@ -43,7 +43,7 @@
from twext.who.idirectory import DirectoryQueryMatchExpression
from twext.who.directory import DirectoryService as BaseDirectoryService
from twext.who.directory import DirectoryRecord as BaseDirectoryRecord
-from twext.who.util import MergedConstants, describe, iterFlags
+from twext.who.util import MergedConstants, describe, uniqueResult, iterFlags
@@ -351,21 +351,13 @@
self._lastRefresh = 0
- def indexedRecordsFromMatchExpression(self, expression):
- """
- Finds records in the internal indexes matching a single
- expression.
- @param expression: an expression
- @type expression: L{object}
- """
- #
- # Flags
- #
+ @staticmethod
+ def _queryFlags(flags):
predicate = lambda x: x
normalize = lambda x: x
- if expression.flags is not None:
- for flag in iterFlags(expression.flags):
+ if flags is not None:
+ for flag in iterFlags(flags):
if flag == QueryFlags.NOT:
predicate = lambda x: not x
elif flag == QueryFlags.caseInsensitive:
@@ -373,56 +365,93 @@
else:
raise NotImplementedError("Unknown query flag: %s" % (describe(flag),))
- #
- # Find matching index keys
- #
+ return predicate, normalize
+
+
+ def indexedRecordsFromMatchExpression(self, expression, records=None):
+ """
+ Finds records in the internal indexes matching a single
+ expression.
+ @param expression: an expression
+ @type expression: L{object}
+ """
+ predicate, normalize = self._queryFlags(expression.flags)
+
fieldIndex = self.index[expression.fieldName]
matchValue = normalize(expression.fieldValue)
+ matchType = expression.matchType
- if expression.matchType == MatchType.startsWith:
+ if matchType == MatchType.startsWith:
indexKeys = (key for key in fieldIndex if predicate(normalize(key).startswith(matchValue)))
- elif expression.matchType == MatchType.contains:
+ elif matchType == MatchType.contains:
indexKeys = (key for key in fieldIndex if predicate(matchValue in normalize(key)))
- elif expression.matchType == MatchType.equals:
+ elif matchType == MatchType.equals:
if predicate(True):
indexKeys = (matchValue,)
else:
indexKeys = (key for key in fieldIndex if normalize(key) != matchValue)
else:
- raise NotImplementedError("Unknown match type: %s" % (describe(expression.matchType),))
+ raise NotImplementedError("Unknown match type: %s" % (describe(matchType),))
- #
- # Lookup and return the results
- #
matchingRecords = set()
for key in indexKeys:
matchingRecords |= fieldIndex.get(key, frozenset())
+ if records is not None:
+ matchingRecords &= records
+
return succeed(matchingRecords)
- def unIndexedRecordsFromMatchExpression(self, expression):
+ def unIndexedRecordsFromMatchExpression(self, expression, records=None):
"""
Finds records not in the internal indexes matching a single
expression.
@param expression: an expression
@type expression: L{object}
"""
- raise NotImplementedError("Handle unindexed fields")
+ predicate, normalize = self._queryFlags(expression.flags)
+ matchValue = normalize(expression.fieldValue)
+ matchType = expression.matchType
- def recordsFromExpression(self, expression):
+ if matchType == MatchType.startsWith:
+ match = lambda fieldValue: predicate(fieldValue.startswith(matchValue))
+ elif matchType == MatchType.contains:
+ match = lambda fieldValue: predicate(matchValue in fieldValue)
+ elif matchType == MatchType.equals:
+ match = lambda fieldValue: predicate(fieldValue == matchValue)
+ else:
+ raise NotImplementedError("Unknown match type: %s" % (describe(matchType),))
+
+ result = set()
+
+ if records is None:
+ records = (uniqueResult(values) for values in self.index[self.fieldName.uid].itervalues())
+
+ for record in records:
+ fieldValues = record.fields.get(expression.fieldName, None)
+
+ if fieldValues is None:
+ continue
+
+ for fieldValue in fieldValues:
+ if match(normalize(fieldValue)):
+ result.add(record)
+
+ return result
+
+
+ def recordsFromExpression(self, expression, records=None):
if isinstance(expression, DirectoryQueryMatchExpression):
if expression.fieldName in self.indexedFields:
- records = self.indexedRecordsFromMatchExpression(expression)
+ return self.indexedRecordsFromMatchExpression(expression, records=records)
else:
- records = self.unIndexedRecordsFromMatchExpression(expression)
+ return self.unIndexedRecordsFromMatchExpression(expression, records=records)
else:
- records = BaseDirectoryService.recordsFromExpression(self, expression)
+ return BaseDirectoryService.recordsFromExpression(self, expression, records=records)
- return records
-
def updateRecords(self, records, create=False):
# Index the records to update by UID
recordsByUID = dict(((record.uid, record) for record in records))
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.macosforge.org/pipermail/calendarserver-changes/attachments/20130215/66b53e9b/attachment-0001.html>
More information about the calendarserver-changes
mailing list